본 분서는 http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees의 내용을 번역한 것이다.
BK-트리, 또는 버크하드-켈러 트리는 트리 기반의 구조로 주어진 문자열에 대한 빠른 근사 매치를 하도록 해준다. 예를 들어, 스펠링 검사기나 '퍼지(유사어)' 검색을 수행하는 등의 작업에 사용된다. 더 자세히 예를 들자면, "aeek"를 검색하는데 이와 유사한 "seek"과 "peek"의 단어들이 반환되는 것이 목적이다. 무엇이 BK-트리를 빛나게 하냐면, 단순 무식한 무작위 검색 방식(brute-force search) 외에는 뾰족한 검색 방법이 없는 문제가 있을 때, 검색 속도를 엄청나게 향상시킬 수 있는 단순하고 우아한 방법을 제공해 주기 때문이다.
BK-트리는 1973년에 버크하드씨와 켈러 씨에 의해서 그들의 논문인 Some approaches to best match file searching(http://dl.acm.org/citation.cfm?id=362003.362025)에 의해 처음 제안되었다. 더 자세한 내용은 Fast Approximate String Matching in a Dictionary(http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.3317)에 소개 되어 있다.
BK-트리를 정의하기 전에, 우리는 몇 가지 내용을 먼저 정의할 필요가 있다. 우리의 사전을 색인하고 검색하기 위해서는 문자열들을 검색할 방법이 필요하다. 전통적인 방법은 레번슈타인 거리이다. 이 거리는 두 문자열 중에 한 문자열에서 다른 문자열로 변환시키기 위해서 요구되는 삽입, 삭제, 대체의 최소 횟수를 나타낸다. 다른문자열 함수들 역시 아래의 조건들을 만족한다면 허용된다.(가령, 전치의 개념을 포함하고 있는 함수가 아토믹 연산으로써 사용될 수 있다.)
이제 우리는 레번슈타인 거리에 대한 특별히 유용환 관찰을 할 수 있다. 그것은 행렬 공간을 생성한다. 간단히 말해서, 행렬 공간은 세 개의 기본 규칙을 따른다.
(x와 y의 거리가 0일 때, x = y이다)
(x에서 y의 거리가 y에서 x로의 거리와 같을 때)
이 조건들은 삼각 부등식이라고 불린다. 삼각 부등식은 x에서 z로의 선분은 다른 중간 지점들을 거쳐 지나가는 어떠한 선분(x에서 y 선분, y에서 z 선분)보다 짧아야 한다는 것이다. 예를 들어 한 삼각형을 보자. 삼각형의 한 점에서 다른 점으로 가는 길 중에 두 개의 선분을 따라 가는 길은 한 개의 선분만 따라가는 길보다 더 짧게 해서 삼각형을 그릴 수는 없다.
이 세 개의 조건은 매우 기초적인 것이지만, 레벤슈타인 거리가 행렬 공간에 있도록 해주는 필수 조건이다. 이것은 예를 들어 유클리디안 공간보다도 더 일반적이다. 유클리디안 공간은 행렬로 표현되지만, 많은 행렬 공간들(레벤슈타인 거리와 같은)은 유클리디안 공간이 아니다. 이제 레벤슈타인 거리(그리고 다른 유사한 문자열 거리 함수)가 행렬 공간을 포함하는 것을 알았으니, 버크하드와 켈러의 주요 발견을 알 수 있다.
지금 현재 우리가 두 개의 매개변수를 가지고 있다고 가정하자. 하나는 질의인데, 이것은 우리의 검색에서 사용하는 문자이다. 다른 하나는 n이고, 주어진 질의로 부터 반환될 수 있는 문자열의 최대 거리이다. 우리가 임의의 문자열인 test를 선택했고, 이것을 질의와 비교한다고 하고 결과 거리를 d라고 하자. 우리는 삼각 부등식을 알고 있기 때문에, 우리의 모든 결과들은 test로부터 최대 d+n의 거리와 최소 d-n의 거리를 가지고 있어야 한다.
여기에서부터, BK 트리의 생성은 간단하다. 각 노드는 임의이 자식 노드를 가지고 있고, 각 에지는 레벤슈타인 거리 값을 가지고 있다. n으로 표기된 모든 하위 노드는 부모 노드로 정확히 n의 레벤슈타인 거리를 가지고 있다. 그래서, 예를 들자면, 만약 부모 노드가 "book"이고 두개의 자식 노드가 "rook"와 "nook"인 자식 노드를 가진 트리를 가지고 있을 때, "book"에서 "rook"으로의 에지는 1로 표시되고, "book"에서 "nooks"로의 에지는 1로 표시된다.
사전으로부터 트리를 생성하기 위해서는 임의의 단어를 선택하고 그것을 트리의 루트 노드로 만든다. 한 단어를 추가할 때마다, 새로 입력되는 새 단어와 트리의 루트 노드 사이의 레벤슈타인 거리를 취하고, d(새 단어,루트노드)의 숫자를 가지는 에지를 검색한다. 재귀적으로 노드가 존재하지 않을 때까지, 계속 에지에 있는 질의와 자식 노드의 값을 비교한다. 그리고 노드가 존재하지 않는 위치에서 새 단어를 저장한다. 예를 들어, "boon"을 예시에서 언급한 트리에 입력하려면, 우리는 루트 노드를 검사하고, d("book", "boon") = 1을 찾고, 1로 표시된 에지에서 "rook"라는 단어를 가진 자식 노드들을 검사하게 된다. 그리고 다음으로는 d("rook", "boon") = 2를 계산하게 되고, 새로운 단어를 "rook" 노드 아래에 입력하고, 에지의 값은 2로 표시한다.
트리를 질의하기 위해서, 이 검색 문자열에서 루트 노드까지의 레벤슈타인거리를 취하고, 재귀적으로 d-n과 d+n(d+n의 값을 가지는 에지도 포함) 사이에 있는 에지에 있는 모든 자식 노드들을 재귀적으로 비교한다. 만약 비교하는 중의 검색 문자열의 d 안에 있다면, 그것을 반환하고 질의는 계속 진행한다.
이 트리는 N-진 트리이고 비정규형이다(하지만 일반적으로는 잘 균형화 되어 있다). 1의 거리를 가지는 질의는 트리의 5~8% 정도만 검색하는 것을 보이고, 두개의 에러를 가지는 질의는 17~25%의 트리를 검색함을 보인다. 이것은 전체 노드를 검색하는 것보다 훨씬 큰 성능 향상이다! 정확한 매칭을 위한 검색 역시 간단히 n을 0으로 설정함으로써 상당히 효율적으로 수행된다.
댓글