구현 방법 "X보다 적은 Levenshtein 거리로 모든 문자열 가져 오기"

Question

효율적인 데이터 구조가 "levenshtein distance가 X 미만인 모든 문자열 검색"을 수행 할 수 있는지 궁금합니다. 알고리즘의

• 설명 :

  몇 가지 내가 관심.

• 기존 데이터베이스/프로그래밍 언어에 기존 구현이 있습니까?
• 내가 참조 할 수있는 종이/기사?

Answer 1

이 levenshtein의 측정 항목 등의 거리 (또는 간격) 함수와 거리 공간의 가까운 neighborer 됨이다

VP-tree가

이 Python VP-tree implementation은 그 문제를 해결하는 방법 중 하나이다 VP-tree 작동 방식을 보여주는 작업 데모로 단어 목록을 말합니다. 단어를 입력하면 대화 형 쉘을 제공하고 입력 한 단어에서 X 거리 이상 떨어진 단어를 반환합니다

Answer 2

단순한 breadth-first search처럼 들리지만, 각 세대는 이전의 것과는 '편집'되어 있습니다. 단 하나의 레벨에 문자열이 나타나는지 확인하기위한 검사가 필요합니다.

이것은 한 쌍의 루프에서 두 개의 해시/해시 테이블을 사용하여 쉽게 구현할 수 있습니다.