BK 트리란 무엇인가?
BK 트리(BK Tree), 또는 버크하트 트리(Burkhard Tree)는 레벤슈타인 거리(Levenshtein Distance)를 기반으로 맞춤법 검사를 수행하는 데 널리 사용되는 데이터 구조입니다. 자동 수정(AutoCorrect) 기능을 구현할 때도 이 자료구조가 활용됩니다.
예를 들어 사전에 여러 단어가 저장되어 있고, 입력된 단어의 철자 오류를 검사해야 한다고 가정해 보겠습니다. 이때 검사 대상 단어와 철자가 유사한 단어들의 집합이 필요합니다. 예컨대 "uck"이라는 단어가 입력되었다면 올바른 후보로는 truck, duck, suck 등이 있을 수 있습니다. 즉, 철자 오류는 글자를 삭제하거나 추가하거나, 적절한 글자로 교체하는 방식으로 수정할 수 있습니다. 이처럼 편집 거리(Edit Distance)를 기준값으로 삼아 사전 속 단어들과 비교함으로써 철자를 검사하게 됩니다.
BK 트리의 기본 구조
다른 트리 자료구조와 마찬가지로 BK 트리도 노드(Node)와 간선(Edge)으로 구성됩니다. 각 노드는 사전에 있는 단어를 나타내며, 간선에는 한 노드에서 다른 노드까지의 편집 거리 정보를 담은 정수 가중치가 저장됩니다.
{book, books, boo, cake, cape}라는 단어로 이루어진 사전을 예로 들어 보겠습니다.
BK 트리의 삽입 원리
BK 트리의 모든 노드는 동일한 편집 거리를 가지는 자식 노드를 최대 하나씩만 가질 수 있습니다. 따라서 노드를 삽입하는 도중 편집 거리가 겹치는 충돌이 발생하면, 적절한 자식 위치를 찾을 때까지 삽입 과정을 하위 노드로 계속 전파합니다. 모든 삽입 연산은 루트 노드에서 시작하며, 루트 노드는 사전 속 어떤 단어든 될 수 있습니다.
가장 가까운 올바른 단어 찾기
이제 BK 트리를 활용해 오타와 가장 가까운 올바른 단어를 찾는 방법을 살펴보겠습니다. 먼저 허용 오차(Tolerance) 값을 설정해야 하는데, 이는 오타 단어와 올바른 단어 사이에 허용되는 최대 편집 거리를 의미합니다.
허용 오차 범위 내에서 적합한 단어를 찾는 가장 단순한 방법은 모든 경우를 반복 탐색하는 것이지만, 이 방식은 복잡도가 매우 높습니다. 바로 이 지점에서 BK 트리가 강력한 성능을 발휘합니다. BK 트리의 각 노드는 부모 노드와의 편집 거리를 기준으로 배치되어 있으므로, 루트 노드에서 허용 오차 범위에 해당하는 특정 노드로 곧장 이동할 수 있습니다.
허용 오차를 TOL, 현재 노드와 오타 단어 사이의 편집 거리를 dist라고 할 때, 편집 거리가 [dist - TOL, dist + TOL] 범위 안에 있는 자식 노드만 탐색하면 됩니다. 이를 통해 탐색 복잡도를 크게 줄일 수 있습니다.
C++ 구현 예제
아래는 BK 트리의 작동 방식을 보여주는 C++ 프로그램입니다.
#include "bits/stdc++.h"
using namespace std;
#define MAXN 100
#define TOL 2
#define LEN 10
struct Node {
string word;
int next[2*LEN];
Node(string x):word(x){
for(int i=0; i<2*LEN; i++)
next[i] = 0;
}
Node() {}
};
Node RT;
Node tree[MAXN];
int ptr;
int min(int a, int b, int c) {
return min(a, min(b, c));
}
int editDistance(string& a,string& b) {
int m = a.length(), n = b.length();
int dp[m+1][n+1];
for (int i=0; i<=m; i++)
dp[i][0] = i;
for (int j=0; j<=n; j++)
dp[0][j] = j;
for (int i=1; i<=m; i++) {
for (int j=1; j<=n; j++) {
if (a[i-1] != b[j-1])
dp[i][j] = min( 1 + dp[i-1][j], 1 + dp[i][j-1], 1 + dp[i-1][j-1] );
else
dp[i][j] = dp[i-1][j-1];
}
}
return dp[m][n];
}
void insertValue(Node& root,Node& curr) {
if (root.word == "" ){
root = curr;
return;
}
int dist = editDistance(curr.word,root.word);
if (tree[root.next[dist]].word == ""){
ptr++;
tree[ptr] = curr;
root.next[dist] = ptr;
}
else{
insertValue(tree[root.next[dist]],curr);
}
}
vector <string> findCorrectSuggestions(Node& root,string& s){
vector <string> corrections;
if (root.word == "")
return corrections;
int dist = editDistance(root.word,s);
if (dist <= TOL) corrections.push_back(root.word);
int start = dist - TOL;
if (start < 0)
start = 1;
while (start < dist + TOL){
vector <string> temp = findCorrectSuggestions(tree[root.next[start]],s);
for (auto i : temp)
corrections.push_back(i);
start++;
}
return corrections;
}
int main(){
string dictionary[] = {"book","cake","cart","books", "boo" };
ptr = 0;
int size = sizeof(dictionary)/sizeof(string);
for(int i=0; i<size; i++){
Node tmp = Node(dictionary[i]);
insertValue(RT,tmp);
}
string word1 = "ok";
string word2 = "ke";
vector <string> match = findCorrectSuggestions(RT,word1);
cout<<"Correct words suggestions from dictionary for : "<<word1<<endl;
for (auto correctWords : match)
cout<<correctWords<<endl;
match = findCorrectSuggestions(RT,word2);
cout<<"Correct words suggestions from dictionary for : "<<word2<<endl;
for (auto correctWords : match)
cout<<correctWords<<endl;
return 0;
}실행 결과
Correct words suggestions from dictionary for : ok book boo Correct words suggestions from dictionary for : ke cake
실행 결과를 보면 오타 "ok"에 대해서는 편집 거리가 허용 오차(TOL=2) 이내인 "book"과 "boo"가 추천되었고, "ke"에 대해서는 "cake"가 추천된 것을 확인할 수 있습니다. 이처럼 BK 트리는 사전 전체를 일일이 비교하지 않고도 유사한 단어를 빠르게 찾아낼 수 있는 효율적인 자료구조입니다.