퍼지 문자열 검색(Fuzzy string search)
차례
- 영문 : Fuzzy string search
- 원문 : Нечёткий поиск в тексте и словаре
- 소스코드 : bitap.py
소개
퍼지 검색 알고리즘(또한, 유사성 검색 알고리즘으로 알려짐)들은 철자 검사기와 구글(Google)과 얀덱스(Yandex) 완성된 검색 엔진의 근본을 이루고 있다. 예를 들어, 이 알고리즘들은 "당신은 ...을 말하려고 하는가요?" 함수를 제공하는데 이용되어져 왔다.
이 글에서는 다음의 개념, 방법, 그리고 알고리즘들을 설명할 것이다.
- 레펜슈타인 거리(Levenshtein distance)
- 다메라우-레펜슈타인 거리(Damerau-Levenshtein)
- 우(Wu)와 만버(Manber)씨에 의한 비탭 알고리즘과 변형
- 철자 검사 기법
- N-그램 기법
- 시그니처 해싱 기법
- BK-트리
또한 알고리즘의 품질과 효율에 대한 비교 검사를 수행할 것이다.
그래서..
퍼지 검색은 모든 검색 엔진에서 매우 중요한 기능이다. 하지만, 그것의 효율적인 구현은 단순히 완전 일치를 위한 검색을 구현하기 보다 훨씬 더 복잡하다.
퍼지 문자열 검색 문제는 다음과 같이 수식화 될 수 있다.
주어진 문자에 일치하는 모든 문자(또는 주어진 문자열의 시작 지점)를 n의 크기를 가진 특정 문자열이나 사전에서 찾고, 이 때, k개의 가능한 차이점(에러)을 가지는 것을 고려한다.
예를 들어, 만약 당신이 "machine"을 2개의 차이점을 가진채로 검색한다고 하면, "marine", "lachine", "martine" 등등을 검색할 것이다.
퍼지 검색 알고리즘은 메트릭(metric)에 의해 설명된다. 메트릭은 두 단어 간의 거리 함수로, 그들 간의 유사성에 대한 척도를 제공한다. 메트릭의 엄격한 수학적 정의는 삼각 부등식을 따르는 것을 요구한다.(X - 단어 집합, p - 메트릭):
한편, 대부분의 경우 메트릭은 위의 조건을 만족하지 않는 일반적인 개념으로 이해된다. 이런 개념은 또한 거리라고 불릴 수 있다.
가장 잘 알려진 메트릭들은 해밍(Hamming), 레펜슈타인(Levenshtein), 그리고 다메라우-레펜슈타인(Dameraue-Levenshtein) 거리들이다. 해밍 거리는 오직 단어들 집합의 길이가 같을 때만 성립하며, 바로 그 점이 해밍 거리의 응용을 심각하게 제한하는 점이다.
해밍 거리가 무용 지물이라지만, 다음에서 우리가 논의할 내용에 대해 실제적으로 인간의 관점에서 좀 더 자연스러운 이해를 도울 것이다.
레펜슈타인 거리
레펜슈타인 거리는 또한 "편집 거리"로 알려져 있고, 가장 일반적으로 사용되는 메트릭이다. 그것을 계산하는 알고리즘은 어디에서나 쉽게 발견된다.
그럼에도 불구하고, 그것의 계산에 대한 가장 잘 알려진 알고리즘인 바그너-피셔 방식에 대해서 약간 언급할 필요가 있다.
원래 이 알고리즘은 O(mn)의 시간 복잡도와 O(mn)의 메모리를 소비한다. 여기에서 각각 m과 n은 비교하려는 문자열의 길이이다. 전체 처리 단계는 다음의 행렬로 표현될 수 있다.
만약 알고리즘의 처리 단계를 살펴보면, 각 단계 별로 행렬에서 최종 두 행들만 사용되어짐을 알 수 있다. 그래서, 메모리의 소비는 O(min(m, n))으로 줄어들 수 있다.
하지만 그것이 전부는 아니다. 알고리즘은 만약 더 이상의 k 차이점이 발견될 필요가 없다면, 더 향상될 수 있다. 이 경우에 행렬에서 2k+1의 넓이의 대각선 영역만이 계산될 필요가 있다(Ukkonen의 잘라내기 방식). 이 방식은 시간 복잡도를 O(k min(m, n))으로 감소시킨다.
접두사 거리
일반적으로 접미사 패턴과 하나의 문자열의 거리를 계산할 필요가 있다. 가령, 주어진 접두사와 가장 근사한 문자열 접두사 사이의 거리를 찾기 위해서, 이 경우에, 우리는 문자열의 모든 접두사 중에 가장 작은 거리를 가진 접두사를 선택해야 한다. 명백하게, 접두사 거리는 엄격한 수학적 관점에서 메트릭으로 여겨질 수 없다. 그리고 이것이 접두사 거리의 응용 영역을 제한한다.
주로, 특정한 거리값 자체 보다는 그 값이 어떤 값보다 크다는 사실이 더 중요하다.
다메라우-레펜슈타인 거리
이 변이된 방식은 레펜슈타인 거리에 한 가지의 규칙을 추가했다. 두 인접한 문자 간의 전치(transposition, 위치 바꾸기) 역시, 삽입, 삭제, 대체와 마찬가지로 하나의 연산으로 계산된다는 점이다.
몇 년 전에 , 프레데릭 다메라우(Frederick Damerau)는 대부분의 타이핑 오류가 전치임을 확신했다. 그런 까닭에, 이 메트릭은 실제에서 최대의 결과를 가져왔다.
이 거리를 계산하기 위해서, 일반적인 레펜슈타인 알고리즘을 다음과 같이 약간 변형했다. 두 개의 행이 아니라 세 개의 행에 대해서 연산을 수행하고, 전치가 일어났음을 고려해야할 경우 그에 대한 절절한 조건을 추가한 것이다.
위의 내용에 덧붙여서, 실제에서 사용되는 많은 다른 거리들이 있다. 가령, 자로-윙클러(Jaro-Winkler) 메트릭 같은 것이다. 대부분의 이러한 알고리즘들은 SimMetrics, SecondString 라이브러리 들에 의해 사용 가능하다.
색인 없이 수행하는 퍼지 검색 알고리즘(온라인 방식)
이들 알고리즘은 검색은 이전에 알려지지 않은 문자에 대해 검색을 수행하기 위해서 설계된 알고리즘들이고 예를 들어, 텍스트 에디터나, 문서 뷰어, 혹은 웹 브라우저에서 페이지 검색 등에 이용될 수 있다. 그들은 문자열에 대해 미리 가공을 수행할 필요가 없으며, 연속적인 데이터 스트림에 대해서 처리를 수행할 수 있다.
선형 검색
이것은 입력 문자열의 단어들에 대해서 단순히 한단계 한단계 메트릭 계산(예를 들어 레펜슈타인 메트릭)을 수행하는 것을 의미한다. 우리가 메트릭 제한을 사용할 때, 이 방식은 최적의 속도를 얻을 수 있다.
하지만, 동시에, k가 증가하면 할수록, 시간이 더욱 걸리게 된다. 근사적인 시간 복잡도는 O(kn)이다.
비탭 알고리즘
(Bitap, 또한 쉬프트-Or 또는 배자-얏츠-고넷(Baeza-Yates-Gonnet), 그리고 우(Wu)와 만버(Manber)씨에 의한 그것의 변형)비탭 알고리즘과 그것의 다양한 변형들은 색인 없이 수행되는 퍼지 검색에서 가장 자주 이용된다. 그것의 변형들은 예를 들어, 표준의 grep과 유사한 동작을 하는 유닉스 유틸리티 agrep에서 사용된다. 하지만, 이 유틸리티는 검색 질의에 에러를 지원하며, 제한적이지만 정규 표현식까지도 지원한다.
처음에 이 알고리즘에 대한 생각은 리카르도 배자-야츠와 개스톤 고넷(Ricardo Baeza-Yates, Gaston Gonnet)에 의해서 제안되었고, 관련 글이 1992년에 발표되었다.
원래 알고리즘은 오직 문자 치환만을 다루었고, 사실 해밍 거리를 계산했다. 하지만, 나중에 썬 우와 우디 만버(Sun Wu, Udi Manber)가 레벤슈타인 거리를 계산하기 위해 이 알고리즘을 수정할 것을 제안했다. 가령 삽입과 삭제에 대한 지원을 가져오게 되었고, agrep 유틸리티의 초기 버전을 개발했다.
비트쉬프트 연산
삽입 연산
삭제 연산
치환 연산
결과 값
여기에서 k는 에러 갯수이고, j는 문자 색인 번호, Sx는 문자 마스크(마스크 값에서 1의 비트값들이 질의 문자열을 비트로 표현했을 때 해당 문자가 있는 위치에 있게 된다).
질의의 일치 혹은 불일치의 결과는 결과 벡터 R의 최종 비트에 의해서 결정되게 된다.
이 알고리즘의 높은 속도는 비트 병렬화 기법에 의해서 보증된다. 계산들은 32 이상의 비트 수에 대해서 단일 연산으로 처리된다.
이 경우에, 간단한 구현이 32개의 기호들보다 적은 단어들을 검색하는 것을 지원한다. 이것은 표준 정수(int, 32비트 아키텍처)의 넓이에 의해서 제한 받는다. 우리는 더 넓은 타입을 사용할 수 있으나, 그것의 사용은 알고리즘의 성능을 하락 시킬 것이다.
이 알고리즘의 근사적인 시간 복잡도가 선형 방식의 시간과 동일한 O(kn)임에도 불구하고, 질의가 길고 에러의 크기인 k 가 2개 이상인 경우 훨씬 빠르게 동작한다.
성능 평가
성능 평가는 3백 2십만 단어들에 대해서 수행되었고, 평균적인 단어 길이는 10이다.
완전 일치 검색
검색 시간: 3562 ms
레펜슈타인 메트릭을 이용한 선형 검색
k=2일 때 검색 시간: 5728 ms
k=5일 때 검색 시간: 8385 ms
비탭과 우-만버 변형 검색
k=2일 때 검색 시간: 5499 ms
k=5일 때 검색 시간: 5928 ms
메트릭을을 이용한 검사에서 비탭 알고리즘과 대조적으로 에러의 갯수인 k에 매우 의존한다는 것이 명백하다.
동시에, 만약 우리가 변하지 않은 거대한 문자열에서 검색을 해야 한다면, 문자열 전처리(색인 작업)를 통해서 검색 시간을 엄청나게 줄일 수 있음을 알 수 있다.
색인 작업을 수행한 퍼지 검색 알고리즘(오프라인 방식)
색인 작업을 수행한 모든 퍼지 검색 알고리즘의 특징은 색인이 원래 문자열에 의해 생성된 사전이나 데이터베이스의 레코드 집합에 기반을 둔다는 점이다.
이 알고리즘들은 문제를 해결하기 위해서 다른 접근법들을 사용한다. 몇몇은 완전 일치 검색으로의 질의의 감소를 이용하고, 다른 알고리즘은 다양한 공간적 구조나 기타 등등을 생성하기 위해서 메트릭들의 특성을 이용한다.
첫째 단계에서, 원래의 문자열을 이용하여 사전을 생성한다. 이것은 단어들을 가지고 있고, 문자열에서의 위치를 가지고 있다. 또한, 검색 결과를 향상시키기 위해서 단어와 구절의 발생횟수를 계산할 수도 있다.
색인과 사전은 완전히 메모리에 올라온 상태라는 것이 가정되어져 있다.
사전의 명세는 다음과 같다.
- 원본 문자열 - 8.2 Gb 모쉬코우(Moshkow)의 사전(lib.ru), 6억 8천만 단어들
- 사전 크기 - 65 Mb
- 단어 갯수 - 3백 2십만개
- 평균 단어 길이 - 9.5 문자들
- 평균 워드 정방 길이 - 10 문자들
- 러시아 알파벳(32 문자), 알파벳 안에 없는 문자들을 포함한 단어들은 사전에 포함되지 않았다.
원본 문자열에 대한 사전 크기의 의존성은 엄격하기 선형적이지 않다. 특정한 크기의 기본 단어 집합이 형성되며, 50만 단어들에 대해서는 15%, 5백만 단어들에 대해서는 5% 사이에 있다가, 선형 의존성에 접근한 후에, 조금씩 감소하다가 결국 6억 8천만 단어들에서 0.5%에 이른다. 차후의 증가는 희귀 단어들에 의해서 확실시된다.
철자 검사 방식
이름이 암시하듯이, 이 알고리즘은 사전의 크기가 작거나 속도가 큰 문제가 아닌 경우에 철자 교정 시스템(예를 들어, 철자 검사 시스템)에서 사용된다.
이 방식은 퍼지 검색을 정확한 검색의 문제로 감소시키는 것에 기반을 두고 있다.
"잘못 철자된" 단어들의 집합이 원래의 질의를 기반으로 생성된다. 다음에 이 집합에 있는 모든 단어들을 사전에서 완전 일치 검색을 수행한다.
이 것의 방식은 에러의 수 k와 알파벳 크기인 |A|에 강하게 의존하며, 사전에 대한 이진 검색은 다음의 시간 복잡도를 가진다.
예를 들어, 에러 갯수 k=1이고, 영어 알파벳 집합의 문자를 가진 단어의 길이가 7일 때, 잘못 철자된 단어들은 대략 370개 정도이고, 우리는 사전에 대해서 370번의 질의를 필요로 하게 된다. 이것은 받아들일만한 수준이다.
하지만, k=2가 될 때, 이 잘못 철자된 단어의 갯수는 75,000 단어들 이상이고, 이것은 작은 사전에 완전한 검색 절차들에 대응되기 때문에 결국 이를 처리하는데 걸리는 시간은 엄청나게 길어지게 된다. 이 경우에, 우리는 또한 잊지 말아야 하는 것이 각각 잘못 철자된 단어들마다 사전에서 그만큼의 완전 일치 검색이 요구되어진다는 점이다.
명세
알고리즘은 임의의 규칙을 사용해서 "잘못 철자된" 단어들을 생성하기 위해서 쉽게 변경될 수 있고, 더구나 사전 전처리라던지 추가적인 메모리를 요구하지 않는다.
가능한 성능 향샹들
우리는 "잘못 철자된" 모든 단어들을 생성할 것이 아니라, 실제 상황에서 좀 더 자주 나타날 것 같은 문자들만 생성하는 것이다. 가령, 주로 사람들이 범하기 쉬운 철자 실수라던지 오타 같은 것을 생성한다.
N-그램 방식
이 방식은 오래전에 개발되었고, 가장 널리 사용된다. 왜냐하면, 그것의 구현이 간단하고, 상대적으로 좋은 성능을 제공하기 때문이다. 이 알고리즘은 다음 원칙에 기반을 두고 있다.
만약 단어 A가 여러개의 에러를 고려한 상태에서 단어 B에 일치한다면, 그들은 최소한 N의 길이를 가진 하나의 공통의 부분 문자열을 가지고 있을 것이다.
이 N의 길이를 가진 부분 문자열을 "N-그램" 이라고 한다.
색인 단계에서 단어는 N-그램들로 쪼개진다. 그리고 단어는 대응하는 이들 N-그램들의 리스트로 추가된다. 검색 단계에서, 질의 역시 N-그램들로 쪼개지고, 리스트들에 대응하는 그들 각각은 메트릭을 이용해서 검색된다.
현실에서 가장 자주 사용되는 것은 트라이-그램이다. 즉 길이 3의 부분 문자열들을 가진다. 커다란 N의 값을 선택하는 것은 에러 검출이 여전히 가능한 단어의 최소 길이의 제한을 야기한다.
명세
N-그램 알고리즘은 모든 가능한 철자 에러를 찾지 않는다. 예를 들어, 단어 VOTKA를 선택하고(물론 이 단어는 VODKA로 교정되어져야 한다), 트라이-그램으로 쪼개보자. VOTKA > VOT,OTK, TKA. 우리는 모든 이 트라이-그램이 에러 T를 가지고 있는 것을 알 수 있다. 그런 까닭에, 단어 " VODKA"는 발견되지 않을 것이다. 왜냐하면, 그것은 어떠한 트라이-그램도 포함하고 있지 않고, 그들의 리스트에도 역시 추가되지 앉을 것이기 때문이다. 단어를 쪼개면 쪼갤 수록 더 많은 에러가 그 안에 있게 되고, 더 높은 확률로 그것이 질의에 대응하는 N-그램 리스트에 나타나지 않게 될 것이고, 결국 결과 집합에도 나타나지 않을 것이다.
한편, N-그램 방식은 임의의 특성과 복잡도를 가진 사용자 정의의 광대한 가능성을 남겨두었지만, 대략 사전의 15% 정도에 대해 막무가내(brute force)식 검색이 남아 있다.
우리는 N-그램 해시 테이블을 N-그램의 단어에서의 위치에 의해서 쪼갤 수 있다(첫째 수정 M1). 단어와 질의의 길이가 k 이상으로 다를 수 없고, 단어에서 N-그램들의 위치 역시 k 이상으로 다를 수 없다. 그런 까닭에, 우리는 단어에서 N-그램의 위치에 대응하는 테이블, 왼쪽의 k개 테이블, 그리고 오른쪽의 k개 테이블, 총 2k+1 이웃 테이블을 검사해야 한다.
우리는 검사해야하는 집합을 테이블을 단어 길이에 의해 쪼갬으로써 심지어 약간 더 줄일 수 있고, 유사하게, 이웃하는 2k+1개의 테이블만을 검색할 수 있다(둘째 수정 M2).
시그니처 해싱 기법
이 알고리즘은 L. M. 보이츠소브(L. M. Boytsov)의 글 "시그니처 해싱 기법"을 설명한다. 그것은 해시 테이블에서 해시(시그니처)로서되는 비트 워드로 단어의 "구조"를 상대적으로 명백하게 표현한 것에 기반을 둔다.
색인하는 동안, 그러한 해시들은 각 단어에 대해서 계산되고, 이 단어는 대응되는 테이블 행에 추가된다. 다음에, 검색하는 동안, 해시는 질의를 위해서 계산되고, 질의의 해시에 대해서 k 비트 안의 차이를 가진 인접한 해시들의 집합을 계산한다. 이러한 해시들 각각에 대해서 우리는 메트릭을 사용해서 대응되는 단어의 리스트를 순회한다.
해시 계산 단계는 다음과 같다. 각각 해시 비트에 대해서, 알파벳으로 부터 일련의 문자 집합들이 일치된다. 해시 비트열에서 위치 i에서 비트값 1의 의미는 i 번째 알파벳 그룹의 기호가 단어에 있다는 것을 의미한다. 단어에서 문자들의 순서는 궁극적으로 문제가 아니다.
단일 문자의 삭제는 해시 값을 변경시키지 않거나(만약, 여전히 같은 알파벳 그룹의 문자들을 가지고 있다면) 해당 그룹의 비트 값이 0으로 변할 것이다. 삽입도 유사한 방식으로 한 비트가 1의 값을 얻거나 변화가 없을 것이다. 단일 문자 치환은 조금 더 복잡하다. 즉, 해시가 안 변하거나 1 또는 2개의 비트가 변경될 것이다. 전치의 경우에는 해시에서 아무런 변화가 없다. 왜냐하면 이전에 언급했듯이 해시 생성에서 기호의 순서는 문제가 아니기 때문이다. 그런 까닭에, k 개의 에러를 완전히 처리하려면 우리는 해시에서 최소한 2k 비트개의 변경을 해야할 필요가 있다.
k개의 "불완전한"(삽입, 삭제, 전치, 그리고 치환의 일부)에러를 가진채로 평균 복잡도는 다음과 같다.
명세
우리가 다루고 있는 알고리즘에서 한 문자의 치환은 동시에 두 비트를 변경할 수 있다는 사실은, 가령, 해시에서 2 비트를 변경시키는 것은, 현실적으로 두 개의 치환을 가진 현저한(알파벳 크기와 해시 크기의 비율에 의존한다) 양의 단어들의 수의 부족으로 인해 전체 결과 집합을 반환하지 않을 것이다(그리고 해시를 넓히면, 동시에 더 자주 두 비트들이 변경될 것이고 더 불와전한 집합이 반환될 것이다). 덧붙이면 이 알고리즘은 접두사 검색을 허용하지 않는다.
BK-트리
버크하드-켈러(Burkhard-Keller) 트리는 메트릭 트리로, 그런 트리를 생성하는 알고리즘은 삼각 부등식에 부합하는 메트릭들의 능력에 기반을 두고 있다.
이 특성은 메트릭들이 임의의 차원에서 메트릭 공간을 형성하도록 해준다. 이들 메트릭 공간들은 유클리디언 공간일 필요가 없다. 예를 들어, 레펜슈타인과 다메라우-레펜슈타인 메트릭들은 비-유클리디안 공간을 형성한다. 이들 특성에 기반을 두고, 우리는 메트릭 공간에서 검색을 수행할 수 있는 자료 구조를 생성할 수 있다. 이것이 바로 버크하드-켈러 트리이다.
개선
우리는 제한된 거리를 계산하기 위해서 몇몇 메트릭들의 능력을 사용할 수 있다. 하위 노드들에 대해서 최대 거리의 합의 상향 제한선과 결과 거리를 설정하는 것은 이 처리단계의 성능을 약간 향상 시킬 것이다.
성능 평가
성능 평가는 인텔 코어 듀오 T2500 (2GHz/667MHz FSB/2MB), 2Gb RAM, OS — 우분투 10.10 데스크탑 i686, JRE — OpenJDK 6 Update 20)을 이용해서 수행되었다.
성능 평가는 k=2의 에러 갯수를 가진 다메라우-레펜슈타인 거리를 이용하여 수행되었다. 색인 크기는 사전 크기 (65 Mb)를 포함하여 명시되었다.
철자 검사 방식
색인 크기: 65 Mb
검색 시간: 320 ms / 330 ms
결과 호출: 100%
N-그램 (원본)
색인 크기: 170 Mb
색인 생성 시간: 32 초
검색 시간: 71 ms / 110 ms
결과 호출: 65%
N-그램 (첫째 수정 M1)
색인 크기: 170 Mb
색인 생성 시간: 32 초
검색 시간: 39 ms / 46 ms
결과 호출: 63%
N-그램 (둘째 수정 M1)
색인 크기: 170 Mb
색인 생성 시간: 32 초
검색 시간: 37 ms / 45 ms
결과 호출: 62%
시그니처 해싱
색인 크기: 85 Mb
색인 생성 시간: 0.6 초
검색 시간: 55 ms
결과 호출: 56.5 %
BK-트리
색인 크기: 150 Mb
색인 생성 시간: 120 초
검색 시간: 540 ms
결과 호출: 63 %
결론
대부분의 색인 작업을 수행한 검색 알고리즘은 진정한 부선형(sublinear, 예를 들어, 근사 시간 복잡도 O(log n) 또는 그 이하)이 아니고, 그들의 성능은 일반적으로 N에 의존적이다. 그럼에도 불구하고, 다양한 개선과 성능 향상은 심지어 매우 커다란 사전을 가지고도 충분히 적은 연산 시간을 달성할 수 있도록 해준다.
여전히 기술들의 채용에 기반을 두거나 다른 주제 영역에서의 방식에 기반을 둔 다양하고 비효율적인 방식들이 존재한다. 이들 방식들은 퍼지 검색 문제에 대해 접미사 트리(트라이) 채용이며, 나는 그것의 낮은 효율로 인해 여전히 그들을 방치하고 있다. 하지만, 여기에는 또한 기본 접근법에 기반을 둔 알고리즘들이 있다. 예를 들어, 마스-노박(Mass-Novak) 알고리즘 같은 것이 있다. 그것은 부선형 근사 시간 복잡도를 가지고 있지만, 심각하게 비효율적이다. 왜냐하면, 매우큰 상수들이 부선형 시간 측정에 숨어 있기 때문이고, 이것은 커다란 색인을 야기한다.
실제 검색 엔진에서 퍼지 검색 알고리즘의 사용은 음성학 알고리즘, 어휘 스테밍 알고리즘(같은 단어의 다른 형태로부터 기본 부분을 추출하는 알고리즘(예를 들어, Snowball이 제공하는 기능), 통계 기반 랭킹 또는 몇몇 복잡한 메트릭들의 사용과 밀접하게 연관되어 있다.
fuzzy-search-tools 은 당신을 나의 자바 구현물로 데려다 줄 것이다.
- 레펜슈타인 거리 (Ukkonnen의 잘라내기와 접두사 버전)
- 다메라우-레펜슈타인 거리(Ukkonne의 잘라내기와 접두사 버전)
- 비탭(쉬프트-Or과 우-만버 수정)
- 철자 검사 방식
- N-그램 방식
- 시그니처 해싱 방식
- 버크하드-켈러(BK) 트리
나는 코드를 이해하기 쉽고 실제 응용에서도 충분히 효율적으로 만들려고 노력했다. 그러니 즐겁게 사용해 주시길..
이 주제에 대해 연구를 하는 과정 중에 나는 내 자신의 방식을 만들었고, 이것은 적당한 색인 크기의 증가와 사용된 메트릭들의 자유에 제약을 가함으로써 검색 시간을 엄청나게 줄일 수 있게 되었다. 하지만, 그것은 다른 멋진 이야기 이다.
참고자료
이 글의 자바 소스 코드: fuzzy-search-tools
레펜슈타인 거리: Levenshtein distance
다메라우-레펜슈타인 거리: Damerau–Levenshtein distance
우-만버 변경과 함께 쉬프트-Or 설명, 독일어 설명: Baeza-Yates-Gonnet-Algorithmus
N-그램 방식: http://www.cs.helsinki.fi/u/ukkonen/TCS92.pdf
시그니쳐 해싱: Using Signature Hashing for Approximate String Matching
시그니쳐 해싱, 러시아어 설명: http://itman.narod.ru/articles/rtf/confart.zip
정보 검색과 퍼지 문자열 검색: http://itman.narod.ru/english/index.htm
쉬프트-Or과 몇몇 알고리즘의 구현: StringSearch
젠장하게 멋진 알고리즘들 - 레펜슈타인 오토마타, BK-트리, 그리고 몇몇 다른 것들: Damn Cool Algorithms, Part 1: BK-Trees
BK-트리 자바 구현: java-bk-tree
마스-노박 알고리즘: http://yury.name/internet/09ia-seminar.ppt
SecondString 메트릭 라이브러리: SecondString
