BK-tree

BK-tree

BK-Tree(Burkhard-Keller Tree)는 메트릭 공간(metric space)에서 효율적인 근사 검색을 위해 설계된 트리 기반 데이터 구조이다.
주로 레벤슈타인 거리(Levenshtein Distance)를 활용한 문자열 유사성 검색, 맞춤법 검사, DNA 시퀀스 분석에 활용된다.

BK-Tree는 유사성 검색이 필요한 분야에서 여전히 유효하나, 최근에는 SymSpell 등 더 빠른 알고리즘도 등장했다.
그러나 이론적 우아함과 구현 용이성으로 교육 및 소규모 시스템에서 널리 사용된다.

BK-트리의 주요 특징

• 메트릭 공간에서의 효율적인 검색: BK-트리는 요소 간의 거리를 기반으로 데이터를 구성하여, 특정 요소와 유사한 요소를 빠르게 찾을 수 있다.
• 이산 메트릭 사용: 주로 레벤슈타인 거리(편집 거리)와 같은 이산 메트릭을 사용하여 문자열 간의 유사성을 측정한다.

BK-트리의 구조 및 동작 원리

1. 노드 구성: 각 노드는 하나의 요소를 저장하며, 자식 노드는 부모 노드와의 거리(d)를 기준으로 분류된다.
2. 삽입: 새로운 요소를 삽입할 때, 루트 노드부터 시작하여 현재 노드와의 거리를 계산한다. 계산된 거리에 해당하는 자식 노드가 없으면 해당 위치에 새로운 노드를 추가하고, 있으면 해당 자식 노드로 이동하여 동일한 과정을 반복한다.
3. 검색: 특정 요소와 유사한 요소를 찾기 위해, 루트 노드부터 시작하여 현재 노드와의 거리를 계산한다. 이 거리가 설정한 임계값 이하인 경우 해당 노드를 결과에 추가하고, 자식 노드들 중 현재 거리와 임계값의 차이 범위 내에 있는 노드들만 재귀적으로 탐색한다.

BK-트리의 예시

단어 집합 {“book”, “books”, “cake”, “boo”, “boon”, “cook”, “cape”, “cart”}가 있을 때, 레벤슈타인 거리를 사용하여 BK-트리를 구성하면 다음과 같은 구조가 될 수 있다:

• 루트 노드: “book”
  • 거리 1: “books”
    • 거리 2: “boo”
      • 거리 1: “boon”
      • 거리 2: “cook”
  • 거리 4: “cake”
    • 거리 1: “cape”
    • 거리 2: “cart”

이러한 구조를 통해 “book"과 유사한 단어를 효율적으로 검색할 수 있다.

장단점

장점:

1. 효율적인 유사성 검색
2. 메트릭 공간에서 잘 작동
3. 구현이 상대적으로 간단
4. 동적 업데이트 가능

단점:

1. 비균형 트리 가능성
2. 거리 계산 비용
3. 최악의 경우 선형 시간 소요

실제 응용 분야

1. 맞춤법 검사기: “exaple” → “example” 추천
2. 생물정보학: 유사 DNA 시퀀스 매칭
3. 데이터 클린징: 중복 레코드 탐지
4. 채팅 봇: 오타 자동 수정

최적화 전략

• 동적 재구성: 주기적 재배치로 트리 균형 유지
• 카운팅 BK-Tree: 삭제 연산 지원 확장
• 병렬 탐색: GPU 가속을 통한 대량 데이터 처리

구현 예시

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

class BKTreeNode:
    def __init__(self, word):
        self.word = word
        self.children = {}  # 거리를 키로 사용하는 자식 노드 딕셔너리

class BKTree:
    def __init__(self):
        self.root = None
    
    def levenshtein_distance(self, str1, str2):
        """편집 거리(Levenshtein distance) 계산"""
        if len(str1) < len(str2):
            return self.levenshtein_distance(str2, str1)
        
        if len(str2) == 0:
            return len(str1)
        
        previous_row = range(len(str2) + 1)
        
        for i, c1 in enumerate(str1):
            current_row = [i + 1]
            for j, c2 in enumerate(str2):
                insertions = previous_row[j + 1] + 1
                deletions = current_row[j] + 1
                substitutions = previous_row[j] + (c1 != c2)
                current_row.append(min(insertions, deletions, substitutions))
            previous_row = current_row
        
        return previous_row[-1]
    
    def add(self, word):
        """트리에 단어 추가"""
        if self.root is None:
            self.root = BKTreeNode(word)
            return
        
        node = self.root
        while True:
            distance = self.levenshtein_distance(word, node.word)
            if distance == 0:
                return  # 중복 단어는 추가하지 않음
            
            if distance not in node.children:
                node.children[distance] = BKTreeNode(word)
                return
            
            node = node.children[distance]
    
    def search(self, word, tolerance):
        """주어진 허용 오차 내의 유사 단어 검색"""
        if self.root is None:
            return []
        
        results = []
        
        def search_recursive(node):
            distance = self.levenshtein_distance(word, node.word)
            if distance <= tolerance:
                results.append((node.word, distance))
            
            # 삼각 부등식을 이용한 가지치기
            min_distance = distance - tolerance
            max_distance = distance + tolerance
            
            for d in node.children:
                if min_distance <= d <= max_distance:
                    search_recursive(node.children[d])
        
        search_recursive(self.root)
        return sorted(results, key=lambda x: x[1])

응용 사례

1. 철자 검사기 구현

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   class SpellChecker: def __init__(self, dictionary_words): self.bk_tree = BKTree() for word in dictionary_words: self.bk_tree.add(word.lower()) def suggest_corrections(self, word, max_distance=2): """철자가 틀린 단어에 대한 수정 제안""" suggestions = self.bk_tree.search(word.lower(), max_distance) return [suggestion for suggestion, distance in suggestions] # 사용 예시 dictionary = ["apple", "banana", "orange", "grape", "pear"] spell_checker = SpellChecker(dictionary) print(spell_checker.suggest_corrections("appel")) # ['apple']

2. 유사 단어 검색기

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   class SimilarWordFinder: def __init__(self): self.bk_tree = BKTree() def add_words(self, words): for word in words: self.bk_tree.add(word) def find_similar(self, query, tolerance=1): """유사한 단어 찾기""" return self.bk_tree.search(query, tolerance) # 사용 예시 finder = SimilarWordFinder() words = ["cat", "dog", "rat", "bat", "hat"] finder.add_words(words) print(finder.find_similar("cat", 1)) # [('cat', 0), ('bat', 1), ('hat', 1), ('rat', 1)]

3. 자동 완성 시스템

   1 2 3 4 5 6 7 8 9 10

   class AutoCompleteSystem: def __init__(self, words): self.bk_tree = BKTree() for word in words: self.bk_tree.add(word) def get_suggestions(self, prefix, max_distance=2): """입력 중인 단어에 대한 자동 완성 제안""" suggestions = self.bk_tree.search(prefix, max_distance) return [word for word, _ in suggestions if word.startswith(prefix)]

4. 중복 문서 감지

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   class DuplicateDocumentDetector: def __init__(self): self.bk_tree = BKTree() def add_document(self, document_id, content): """문서 추가""" self.bk_tree.add((document_id, self._hash_content(content))) def find_similar_documents(self, content, threshold=0.9): """유사한 문서 찾기""" content_hash = self._hash_content(content) similar = self.bk_tree.search(content_hash, tolerance=int((1-threshold) * len(content))) return [doc_id for doc_id, _ in similar]

참고 및 출처