Reverse Levenshtein distance

Question

levenshtein 거리에서이 두 문자열을 주어진 levenshtein distance에서 질문하십시오. 어떻게 문자열과 levenshtein 거리를 가져 와서 모든 문자열을 그 levenshtein 거리 내에서 생성하려고합니다. (문자 집합도 포함됩니다). 그래서 문자열 x와 거리 d를 전달하면됩니다. 그러면 편집 거리 내에서 d-1과 d-2 ...를 포함한 모든 문자열을 얻을 수 있습니다. d-n; (n < d).

예상 기능 :

>>> getWithinDistance('apple',2,{'a','b',' '}) 
['applea','appleb','appel','app le'...] 

공간이 문자 세트에 포함되어 같은 프로그램이 app le을 생산할 수 있습니다.

Answer 1

이 작업을 수행하는 데이터 구조는 Levenshtein automaton입니다. 문자열 집합 (하나의 멤버 만있을 수 있음)과 고정 거리 k에서 구성한 다음 저장 한 문자열 중 거리가 최대 인 문자열을 모두 k으로 쿼리 할 수 ​​있습니다. 파이썬 구현은 here으로 논의됩니다.

또는 해당 문자열에 대해 역 추적으로 깊이 제한 검색을 수행 할 수 있습니다.