automata1 레벤슈타인 오토마타(Levenshtein Automata) 본 문서는 http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata을 번역한 것이다. 소개 레벤슈타인 오토마타의 배경에 있는 통찰은 찾으려고하는 단어의 주어진 레벤슈타인 거리 안에 있는 문자열 집합들을 정확히 인지하는 유한 상태 오토마타를 생성하도록 해준다는 것이다. 그리고 어떠한 단어를 제공하던지 간에 오토마타는 생성할 때 명시한 레벤슈타인 거리에 근거하여 찾으려고 하는 단어가 최대 이 거리 안에 있는지 여부를 판단하여 수용하거나 거부할 것이다. 유한 상태 오토마타의 특성 덕분에, 주어진 문자열의 길이에 대해서 시간 안에 처리될 것이다. 시간이 걸리는 표준적인 동적 프로그래밍 레벤슈타인 알고리즘과 비교하여 보자. 여기에서 m과 n.. 2012. 11. 27. 이전 1 다음
