파이썬에서 퍼지 키 조회를 수행하는 가장 좋은 방법은 무엇입니까?

Question

필자는 해시 맵에서 퍼지 조회를 수행해야하는 문제가 있습니다. 즉, 필자의 경우 Levenshtein 거리로 측정 한 쿼리와 가장 유사한 키에 해당하는 값을 반환해야합니다.

현재 나의 접근 방식은 dict을 모든 키에 대한 Levenshtein 거리를 계산하는 특수 검색 방법으로 하위 클래스 화 한 다음 가장 낮은 점수를 갖는 키 값을 반환합니다. 기본적으로 다음과 같습니다.

import Levenshtein 

class FuzzyLookupDict(dict): 

    def fuzzy_lookup(self, query): 
     levs = [(key, Levenshtein.ratio(query, key)) for key in self.keys()] 
     key, score = max(levs, key=lambda lev: lev[1]) 
     return self.get(key) 

이것은 좋은 접근 방법입니까, 아니면 더 좋은 해결책이 있습니까?

Answer 1

이 문제는 일반적으로 Levenshtein automata으로 해결됩니다.w 문자열 및 숫자 N Levenshtein 용 오토 마톤은 Levenshtein 거리 에서w N 이하인 모든 스트링의 세트를 인식 할 수있는 유한 상태 오토 마톤이다.

이 알고리즘은 동적 프로그래밍을 사용하여 사전 단어마다 Levenshtein 거리를 따로 계산하는 것보다 훨씬 빠릅니다.

쥴 제이콥의 블로그 게시물 Levenshtein automata can be simple and fast은 좋은 시작점이며 Nick Johnsonz의 Damn Cool Algorithms: Levenshtein Automata은 깊이있는 소개입니다.

Github에서 일부 Python 구현을 찾을 수 있습니다 (예 : https://github.com/antoinewdg/pyffs).