레벤슈타인 자동 기계

컴퓨터 과학에서, 문자열 w와 숫자 n에 대한 레벤슈타인 자동 기계()는 w로부터의 레벤슈타인 거리가 최대 n인 모든 문자열의 집합을 인식할 수 있는 유한 상태 기계이다. 즉, 문자열 x가 레벤슈타인 자동 기계에 의해 인식되는 형식 언어에 포함될 조건은 x가 최대 n번의 단일 문자 삽입, 삭제, 치환을 통해 w로 변환될 수 있는 경우와 필요충분조건을 이룬다.

 응용 
레벤슈타인 자동 기계는 철자가 틀린 단어와 가까운 단어를 주어진 사전에서 찾아내는 철자 교정에 사용될 수 있다. 이 응용 분야에서 특정 단어의 철자가 틀린 것으로 식별되면, 해당 단어에 대한 레벤슈타인 자동 기계를 구축한 다음 이를 사전의 모든 단어에 적용하여 어떤 단어가 오타와 가까운지 결정한다. 만약 사전이 트라이 형태로 압축되어 저장되어 있다면, 이 알고리즘의 실행 시간(자동 기계가 구축된 후)은 트라이의 노드 수에 비례하며, 이는 각 사전 단어에 대해 개별적으로 레벤슈타인 거리를 계산하는 동적 계획법을 사용하는 것보다 상당히 빠르다.

또한, 단어에 대한 레벤슈타인 자동 기계를 계산한 후 곱집합 구성을 사용하여 이를 정규 언어용 자동 기계와 결합함으로써, 유한한 사전이 아닌 정규 언어에 속하면서 주어진 대상 단어와 가까운 단어를 찾는 것도 가능하다. 대안적으로, 곱집합 구성을 사용하는 대신 레벤슈타인 자동 기계와 주어진 정규 언어용 자동 기계를 퇴각검색 알고리즘을 사용하여 동시에 탐색할 수도 있다.

레벤슈타인 자동 기계는 루씬에서 검색어가 틀리더라도 관련 문서를 반환할 수 있는 전문 검색에 사용된다.

 구축 
임의의 고정된 상수 n에 대해, w와 n에 대한 레벤슈타인 자동 기계는 O(|w|) 시간 내에 구축될 수 있다.

페타르 N. 미탄킨(Petar N. Mitankin)은 범용 레벤슈타인 자동 기계(universal Levenshtein automaton)라 불리는 이 구성의 변형을 연구했다. 이는 수치 매개변수 n에 의해서만 결정되며, 서로 레벤슈타인 거리 n 이내에 있는 단어 쌍(비트 벡터로 특정 방식으로 인코딩됨)을 인식할 수 있다. 엘렌 투제(Hélène Touzet)는 이 자동 기계를 구축하기 위한 효과적인 알고리즘을 제안했다. 

레벤슈타인(또는 다메라우-레벤슈타인 거리) 거리의 또 다른 유한 자동 기계 구성으로는 아메드 하산(Ahmed Hassan) 등이 제안한 레벤슈타인 변환기가 있다. 이들은 편집 거리 1을 구현하는 유한 상태 변환기를 보여준 뒤, 이를 합성하여 일정 상수까지의 편집 거리를 구현한다.

 같이 보기 
 Agrep: 근사 정규 표현식 매칭을 위한 도구
 TRE: 레벤슈타인 스타일의 편집에 관대한 정규 표현식 매칭 라이브러리

 각주 

분류:문자열 검색 알고리즘
분류:유한 상태 기계