소개
레벤슈타인 오토마타의 배경에 있는 통찰은 찾으려고하는 단어의 주어진 레벤슈타인 거리 안에 있는 문자열 집합들을 정확히 인지하는 유한 상태 오토마타를 생성하도록 해준다는 것이다. 그리고 어떠한 단어를 제공하던지 간에 오토마타는 생성할 때 명시한 레벤슈타인 거리에 근거하여 찾으려고 하는 단어가 최대 이 거리 안에 있는지 여부를 판단하여 수용하거나 거부할 것이다. 유한 상태 오토마타의 특성 덕분에, 주어진 문자열의 길이에 대해서 
물론, 만약 레벤 슈타인 오토마타의 장점이 그것 뿐이라면, 이것은 짧은 설명이 될 것이다. 거기에는 더 많은 것들이 있지만, 먼저 레벤슈타인 오토마타가 어떻게 보이는지 보고, 어떻게 생성하는 지 알아 보자.
생성과 평가
오른쪽에 보이는 그림은 단어 food를 최대 2의 편집 거리(레벤슈타인 거리)에 대한 레벤슈타인 오토마타에 대한 NFA 표현을 보인다. 그림에서 알 수 있듯이, 그것은 매우 일반적이고, 생성은 상당히 직관적이다. 시작 상태는 왼쪽 아래에 있다. 상태들은 
이제 주어진 단어와 최대 편집 거리를 가지고 어떻게 NFA를 생성하는지 알아보자. NFA 클래스에 대한 구현은 gist(https://gist.github.com/491973)를 참고하길 바란다.
def levenshtein_automata(term, k):
nfa = NFA((0, 0))
for n, c in enumerate(term):
for e in range(k + 1):
# Correct character
nfa.add_transition((n, e), c, (n + 1, e))
if e < k:
# Deletion
nfa.add_transition((n, e), NFA.ANY, (n, e + 1))
# Insertion
nfa.add_transition((n, e), NFA.EPSILON, (n + 1, e + 1))
# Substitution
nfa.add_transition((n, e), NFA.ANY, (n + 1, e + 1))
for e in range(k + 1):
if e < k:
nfa.add_transition((len(term), e), NFA.ANY, (len(term), e + 1))
nfa.add_final_state((len(term), e))
return nfa
위의 코드는 기본적으로 위의 그림에 보이는 전이를 최대한 직관적으로 구현한 것이다. 상태는 문자열로 표기하는 것보다는 위에 설명한 것과 마찬가지로(
이것은 NFA이기 때문에, 여기에는 다양한 활성 상태들이 존재할 수 있다. 활성 상태들 사이에서, 지금까지 처리된 문자열들의 가능한 해석 방법을 나타내게 된다. 예를 들어, 문자 f와 x를 처리한 후에 활성 상태들이 어떻게 되었는지 생각해 보자.
현재의 NFA는 처음 두 문자인 f와 x를 가지는 다양한 변이들이 가능함을 보인다. 예를 들자면, 한 번의 대치가 일어난 상황이라고 생각한다면, fxod라고 해석하는 것이 가능할 것이고, 한 번의 삽입이 일어난 상황이라고 생각한다면, fxood가 될 것이고, 두 번의 삽입이라고 생각한다면, fxfood가 될 것이고, 한 번의 대치와 한 번의 삭제가 각각 일어났다고 본다면, fxd로도 해석될 것이다. 게다가 여러개의 중복되는 문자열도 가능한데, 가령 하나의 삭제와 삽입이 일어났다고 보면, fxod가 또 될 수 있다. 결국, 더 많은 문자들이 처리되면 될 수록, 몇몇 이러한 가능성들은 사라지게 되겠지만, 마찬가지로 다른 새로운 가능성들이 또 나타나게 될 것이다. 만약 주어진 문자의 모든 내용을 다 처리한 후에 하나의 허용 상태(굵은 테두리)가 현재의 상태들 중에 존재한다면, 입력된 문자열을 찾으려고 하는 문자열로 적은 수의 편집을 통해서 변화시킬 수 있을 것이고, 우리는 주어진 문자가 적합하다는 것을 받아들일 수 있게 된다.
사실 NFA를 직접적으로 평가하는것은 다수의 활성 상태와 엡실론 전이(입력 기호가 요구되지 않는 전이들) 꽤나 알고리즘적으로 비싼 연산이다. 그래서 표준적인 실제 방식은 파워젯 생성(http://en.wikipedia.org/wiki/Powerset_construction)을 이용하여 NFA를 DFA로 변환하는 것이다. 이 알고리즘을 이용하여, 원본 NFA에 있던 활성 상태들의 집합에 대응되는 각 상태들을 이용하여 DFA를 생성한다. 다음의 그림은 하나의 에러를 허용하는 입력 문자열 food에 대한 NFA에서 변환된 DFA를 보인다.
위의 DFA는 food에 대해 편집 거리가 1이하인 문자열 들에 대응하는 문자열들을 받아들일 것이다. 아무런 문자열들을 선택해서, DFA를 따라 해당 문자의 경로를 따라가 보자. 만약 두껍게 칠해진 상태에서 끝이 난다면, 해당 문자열은 적합한 것이다.
런타임 효율성에 대해서 간단히 언급하자면, 얼마나 레벤슈타인 DFA 생성이 효율적인지 알고 싶을 것이다. 우리는 NFA를 
색인
이제 우리는 레벤슈타인 오토마타를 생성할 수 있고, 어떻게 그것이 동작하는지를 보았다. 이제 퍼지 검색(부분 일치 검색)을 효율적으로 하기 위한 색인을 검색하기 위해서 어떻게 이 구조를 사용할 수 있을 지 살펴보자. 첫째 통찰은 그리고 많은 논문들(Fast string correction with Levenshtein automata와 Fast approximate search in large dictionaries(http://dl.acm.org/citation.cfm?id=1105590))에서 사용했던 접근법은 사전(우리가 검색하고자 하는 레코드 집합들)을 관찰하는 것이다. 사전은 그 자체로 DFA로 표현되어질 수 있다. 사실, 그들은 주로 트라이 또는 하나의 DAWG로 저장되는데, 이 두 구조 모두 특별한 경우의 DFA로 보아질 수 있다. 주어진 사전과 조건(레벤슈타인 오토마타)들이 DFA로 표현되기 때문에, 두 DFA들의 교집합을 효과적으로 취하는 것을 통해 우리의 조건에 부합하는 단어들을 사전에서 정확히 찾을 수 있게 된다. 그 처리 단계는 매우 간단하며 이렇게 보인다.
def intersect(dfa1, dfa2):
stack = [("", dfa1.start_state, dfa2.start_state)]
while stack:
s, state1, state2 = stack.pop()
for edge in set(dfa1.edges(state1)).intersect(dfa2.edges(state2)):
state1 = dfa1.next(state1, edge)
state2 = dfa2.next(state2, edge)
if state1 and state2:
s = s + edge
stack.append((s, state1, state2))
if dfa1.is_final(state1) and dfa2.is_final(state2):
yield s
우리는 두 DFA들에서 발을 맞춰서 순회를 하고, 오직 두 DFA에서 일치하는 값을 가지는 에지만을 따라가면서, 우리가 이전 예제에서 따라갔던 경로와 같은 방식으로 처리하게 된다. 언제든지 두 DFA들이 최종 상태에 이르게 되면, 찾아진 문자열은 출력 집합에 있게 되고 그것을 출력하게 된다.
이 모든 것은 만약 색인이 DFA(혹은 트라이나 DAWG)로 저장되어 있다면, 잘 동작할 것이다. 그러나 많은 색인들은 그렇지 않다. 만약, 그들이 메모리에 상주하는 형태이면, 아마도 정렬된 리스트일 것이고, 그들이 디스크에 존재하는 타입이면 아마 B-트리나 유사한 형태일 것이다. 그렇다면, 이런 다른 색인 구조들과 동작도 하고 막무가내 방식 알고리즘 보다 더 빠르게 동작하게 할 수 있는 방법은 없을까? 사실 그런 방법이 존재한다.
가장 중요한 통찰은 우리의 조건이 DFA로 표현됬다는 것이고, 우리는 DFA에 매칭이 되지 않은 문자열을 가지고, 사전식 순서에 따라서 DFA 매칭이 되는 다음의 문자열을 찾을 수 있다. 직관적으로, 이것은 꽤나 쉬운 방법이다. 우리는 입력 문자열을 DFA에 대해 평가함에 있어서, 우리가 더 이상 진행할 수 없을 때까지 평가를 수행한다. 가령, 다음 문자에 대해서 적합한 전이가 없는 경우를 생각해볼 수 있다. 다음으로, 우리는 최종 상태에 도달할 때까지 사전식 순서에서 가장 적은 값을 가지는 표기(예를 들면, 312에서 1)를 가지는 에지를 계속 따라간다. 여기에는 두가지 특별한 경우가 적용된다. 첫째, 첫 전이에서, 우리는 사전식 순서가 이전 단계에서 적합한 전이가 없던 문자보다는 큰 가장 작은 표기를 따라가야할 필요가 있다. 둘째로, 만약 바깥으로 나가는 적합한 에지를 가지지 못한 상태에 도달한 경우, 우리는 이전 상태로 백트래킹을 수행해야 하고, 다시 시도를 해야 한다. 이것은 DFA에 적용된 '벽을 따라가는' 방식으로 미로를 헤쳐나가는 알고리즘과 매우 유사하다.
이것의 예를 들어보자면, 위에 있는 food(1)을 위한 DFA를 살펴보자. 그리고 입력 단어가 foogle이라고 하자. 우리는 처음 4 문자들을 적절히 처리할 것이고, 상태는 
다음은 그 동작을 위한 파이썬 코드이다.
def next_valid_string(self, input):
state = self.start_state
stack = []
# Evaluate the DFA as far as possible
for i, x in enumerate(input):
stack.append((input[:i], state, x))
state = self.next_state(state, x)
if not state: break
else:
stack.append((input[:i+1], state, None))
if self.is_final(state):
# Input word is already valid
return input
# Perform a 'wall following' search for the lexicographically smallest
# accepting state.
while stack:
path, state, x = stack.pop()
x = self.find_next_edge(state, x)
if x:
path += x
state = self.next_state(state, x)
if self.is_final(state):
return path
stack.append((path, state, None))
return None
함수의 첫째 부분에서, 우리는 DFA를 일반적인 방법으로 평가하고, 지금까지 방문한 상태들과 지금까지 왔던 경로, 그리고 우리가 따라가려고 시도했던 에지들에 대한 스택을 유지한다. 다음에, 우리는 하나의 정확한 매칭을 찾지 못했다고 가정하고, 우리는 우리가 위에서 설명한 백트래킹을 수행한다. 즉, 허용 상태로 나아가기 위해서 우리가 따라야 하는 최소한의 전이 집합을 찾으려고 시도한다. 이 함수의 일반성에 대한 몇몇 단점들이 있으니 더 살펴 보자.
여기에서 우리는 또한 find_next_edge라는 함수가 필요하다. 이 함수를 통해서 주어진 입력 보다 더 큰 상태로부터 나아가는 방향의 에지 중에 사전식 순서에서 가장 작은 에지를 찾게 된다.
def find_next_edge(self, s, x):
if x is None:
x = u'\0'
else:
x = unichr(ord(x) + 1)
state_transitions = self.transitions.get(s, {})
if x in state_transitions or s in self.defaults:
return x
labels = sorted(state_transitions.keys())
pos = bisect.bisect_left(labels, x)
if pos < len(labels):
return labels[pos]
return None
몇몇 전처리와 함께, 이것은 훨씬 더 효율적으로 수행될 수 있다. 예를 들자면, 많은 상황에 대해서 이진 검색을 사용하여 계속 찾는 것보다는 각 문자로부터 각 문자보다 큰 나아가는 방향의 에지 중 첫 에지로의 매핑을 미리 생성하는 것이다.
이제 우리는 이런 단계를 가진다. 우리는 색인을 통해서 어떻게 검색을 수행하는지 섦ㅇ할 수 있다. 알고리즘은 놀랄 정도로 간단하다.
- 색인으로부터 첫째 요소를 얻는다. 아니면, 대신 색인에서 당신이 아는 어떠한 합당한 문자열보다 작은 문자열을 선택하고, 그것을 현재 문자열이라고 부른다.
- 현재 문자열을 우리가 위에 설명한 DFA 계승 알고리즘에 적용하고, 다음의 문자열을 얻는다.
- 만약, 다음의 문자열이 현재 문자열과 같으면, 일치되는 문자열을 찾은 것이다. 이제 그것을 출력하고, 다음의 요소를 색인으로부터 꺼내와서 현재의 문자열로 만들고 단계 2를 계속 수행한다.
- 만약 다음의 문자열이 현재의 문자열과 같지 않으면, 다음의 문자열과 같거나 큰 첫번째 문자열을 검색한다. 찾으면 새로운 현재 문자열로 만들고 단계 2를 반복한다.
여기에 이 프로시져의 파이썬 구현이 있다.
def find_all_matches(word, k, lookup_func):
"""Uses lookup_func to find all words within levenshtein distance k of word.
Args:
word: The word to look up
k: Maximum edit distance
lookup_func: A single argument function that returns the first word in the database that is greater than or equal to the input argument.
Yields:
Every matching word within levenshtein distance k from the database.
"""
lev = levenshtein_automata(word, k).to_dfa()
match = lev.next_valid_string(u'\0')
while match:
next = lookup_func(match)
if not next:
return
if match == next:
yield match
next = next + u'\0'
match = lev.next_valid_string(next)
이 알고리즘을 살퍄보는 한 가지 방법은 레벤슈타인 DFA와 색인을 정렬된 리스트로 보고, 위의 프로시져를 App Engine의 "지그재그 합병 조인(zigzag merge join)" 전략과 유하게 보는 것이다. 우리는 반복적으로 한 문자열을 한 쪽에서 보고, 그것을 이용하여 다른 쪽의 적절한 곳으로 점프하는데 이용한다. 만약, 거기에 일치하는 노드가 없다면, 우리는 룩업의 결과를 사용하여 이전의 첫째 쪽으로 다시 점프해가고, 다시 프로시져를 진행한다. 그 결과 우리는 일치하지 않는 색인 요소들을 넘어가게 되고 그와 더불어 레벤슈타인 문자열과 일치하지 않는 문자열들도 건너 뛰게 됨으로써, 둘 중 한가지라도 엄청나게 반복해야 하는 일을 줄이게 된다. 그리고 더 좋은 점은 이 프로시져가 모든 색인 요소나 혹은 모든 레벤슈타인 후보 문자열들 어느 것이든지 평가할 필요를 잠재적으로 피하게 해주는 것이 명백하다는 것이다.
부연으로, 모든 DFA가 모든 문자열에 대해서 사전식 순서에서 최소한의 다음 문자열을 찾는 것이 언제나 가능한 것이 아니다. 예를 들면, a+b 패턴을 인식하는 DFA에서 문자열 a의 다음 문자를 고려해보자. 답은 거기에는 그런 것이 없다는 것이다. b 다음에 무한 개의 a 문자들이 있어야 할 것이다. 위의 프로시져를 조금 수정함으로써 우리의 목적에 부합하게 DFA에 의해 인식되는 다음의 문자열의 접두사가 반환되도록 보장할 수도 있을 것이다. 레벤슈타인 DFA는 언제나 유한하기 때문에, 언제나 유한한 길이의 다음 문자열(당연히 마지막 문자열을 제외하고)이 있게 된다. 우리는 그런 확장을 독자의 연습 문제로 남겨둔다. 이 접근법을 적용할 수 있는 잠재적으로 흥미로운 응용들이 있으며, 가령 색인된 정규 표현식 검색 같은 것은 이런 수정이 필요할 것이다.
검사하기
먼저, 어떻게 동작하는 지 보자. 우리는 단순한 Matcher 클래스를 선언했다. 이 클래스는 find_all_matches 함수에서 요구되는 lookup_func를 구현하고 있다.
class Matcher(object):
def __init__(self, l):
self.l = l
self.probes = 0
def __call__(self, w):
self.probes += 1
pos = bisect.bisect_left(self.l, w)
if pos < len(self.l):
return self.l[pos]
else:
return None
여기에서 callable 클래스를 구현한 이유는 우리가 몇몇 속성들을 추출하고 싶기 때문이다. 특히 얼마나 많은 probe를 수행했는지를 알기 위해서 이다. 프로시져로부터, 일반적인 함수나 내재(nested) 함수로 충분할 것이다. 이제 우리는 샘플 데이터 셋이 필요하다. 이제 web2 사전을 불러오자.
>>> words = [x.strip().lower().decode('utf-8') for x in open('/usr/share/dict/web2')]
>>> words.sort()
>>> len(words)
234936
우리는 또한 크기에 따라서 어떻게 알고리즘이 다르게 반응하는지 검사하기 위해서 하위 집합을 선택할 수도 있다.
>>> words10 = [x for x in words if random.random() <= 0.1]
>>> words100 = [x for x in words if random.random() <= 0.01]
그리고 이제 동작시키면 이렇게 된다.
>>> m = Matcher(words)
>>> list(automata.find_all_matches('nice', 1, m))
[u'anice', u'bice', u'dice', u'fice', u'ice', u'mice', u'nace', u'nice', u'niche', u'nick', u'nide', u'niece', u'nife', u'nile', u'nine', u'niue', u'pice', u'rice', u'sice', u'tice', u'unice', u'vice', u'wice']
>>> len(_)
23
>>> m.probes
142
완벽하게 동작한다! 235,00 단어를 포함한 사전에서 nice 문자열에 대해 23개의 근사 일치를 찾는데 142 번의 검사가 요구된다. 만약 우리가 26개의 문자를 가진 알파벳을 고려한다면, 4+26*4+26*5-237 뮨저욜둘아 nice 문자열의 레벤슈타인 거리 1 안에 있다고 할 수 있다. 그러므로 그들 모두를 검색해 나가는 대신 합리적인 호출횟수 감소를 이뤘다고 할 수 있다. 많은 수의 문자와, 긴 문자열들, 혹은 큰 편집 거리에 대해서 이러한 감소는 더욱 큰 효과를 발휘할 것이다. 문자열의 길이와 사전 크기를 바꿔가면서 어떻게 검사 횠수가 변화하는지 보는 것은 더욱 이해하는데 도움이될 것이다.
| 검색 문자열 길이 | 최대 가능 문자열 수 | 작은 사전 | 중간 사전 | 큰 사전 |
|---|---|---|---|---|
| 1 | 79 | 47 (59%) | 54 (68%) | 81 (100%) |
| 2 | 132 | 81 (61%) | 103 (78%) | 129 (97%) |
| 3 | 185 | 94 (50%) | 120 (64%) | 147 (79%) |
| 4 | 238 | 94 (39%) | 123 (51%) | 155 (65%) |
| 5 | 291 | 94 (32%) | 124 (43%) | 161 (55%) |
이 표에서, 최대 가능 문자열은 한 입력 문자열에 대해서 1의 편집 거리를 가지는 총 문자열의 수이고, 작은 사전, 중간 사전, 큰 사전은 각각 세 사전(1%, 10%, 그리고 전체의 web2 사전)에서 수행된 검사 횟수를 나타낸다. 다음의 열들에서, 10의 길이의 검색문자열까지, 5의 길이의 검색 문자열과 유사한 숫자의 검사가 요구되었다. 샘플로 사용된 입력 문자열은 단어 abracadabra의 접두사를 포함한다.
몇몇 관찰은 명백하다.
- 매우 짧은 문자열과 큰 사전에 대해서, 검사의 횟수는 최대 가능 문자열 수보다 훨씬 작지 않기 때문에 약간만 감소하게 된다.
- 검색 문자열이 길어지게 되면서, 검사의 횟수는 잠재적인 결과의 수의 증가보다 훨씬 더 느린 속도로 증가한다. 그래서 10개의 문자열에서, 우리는 오직 821번 중에 161번(대략 20%)의 검사 만 필요하다. 일반적으로 만나게 되는 단어 길이(web2 사전에 있는 97%의 단어 들은 최소 5의 길이이다.) 단순하게 검사한 모든 문자열 변화에 대한 검사 감소는 이미 매우 크다
- 비록 샘플 사전의 크기가 꽤나 큰 차이를 가지고 있지만, 요구되는 검사의 횟수는 각 증가 별로 크게 증가하지 않았다. 이것은 큰 색인에 대해서 잘 적용될 수 있을 것에 대한 고무적인 증거이다.
편집 거리 제약을 증가시킴으로써, 어떻게 검사 횟수가 증가하는지 보는 것도 이해하는데 도움이 될 것이다. 여기에 최대 편집 거리가 2인 동일한 표가 있다.
| 검색 문자열 길이 | 최대 가능 문자열 수 | 작은 사전 | 중간 사전 | 큰 사전 |
|---|---|---|---|---|
| 1 | 2054 | 413 (20%) | 843 (41%) | 1531 (75%) |
| 2 | 10428 | 486 (5%) | 1226 (12%) | 2600 (25%) |
| 3 | 24420 | 644 (3%) | 1643 (7%) | 3229 (13%) |
| 4 | 44030 | 646 (1.5%) | 1676 (4%) | 3366 (8%) |
| 5 | 69258 | 648 (0.9%) | 1676 (2%) | 3377 (5%) |
이것 역시 고무적이다. 편집 거리를 2로 증가시킴으로써, 더 많은 검사를 해야 하지만, 전체 문자열에 비해 훨씬 작은 비율임을 알 수 있다. 문자열 길이 5와 편집 거리 2에서 3377번의 검사는 최대 가능한 문자열 수 69,258 번(모든 일치 문자열)을 검사하는 것보다 낫고, 234,936 번(사전의 모든 단어)을 검사하는 것보다 낫다.
간단히 비교해서, 같은 사전을 이용하여 단순한 BK-트리 구현을 하는 것은 5의 길이를 가지고 1의 편집거리를 가지는 문자열에 대해서(위에 사용한 동일한 샘플 문자열) 5858의 노드를 검사하도록 요구한다. 그리고, 같은 질의와 편집 거리 2는 58,928 노드가 검사되어야 하는 것으로 나타났다! 다만, 많은 이 노드들 대부분은 같은 디스크 페이지 상에 위치할 것이고, 만약 적절히 구조가 만들어진다면, 거기에는 여전히 검사에 대한 놀라운 다른 점이 있을 수 있다.
최종적으로 말하고 싶은 것은, 우리가 여기에서 참고한 논문 2는 매우 솜씨 좋게 공용 레벤슈타인 오토마타 생성에 대해서 설명하고 있다. 이 DFA는 선형 시간에, 만약 주어진 고정된 레벤슈타인 거리에 주어진 문자열 쌍이 존재함을 결정한다. 지금까지 설명한 알고리즘을 여기에 적용하는 것은, 독자의 연습문제로 남겨둔다.
이 기사에 대한 전체 소스 코드는 다음(https://gist.github.com/491973)에서 발견할 수 있다.
Fast string correction with Levenshtein automata(http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.652)
Fast approximate search in large dictionaries(http://dl.acm.org/citation.cfm?id=1105590)
댓글