fuzzily 사전 단어를 검색하는 방법?

가정한다 제가 fuzzily 사전 단어를 검색하는 방법?

f(x, y) = 1, if x and y are similar 
     = 0, otherwise

이 "유사성"

의해 지정 될 수있는 단어 사전, { "고양이 ','요람 ','촉매 '} 및 문자 유사성 관계 f (x, y)를 가지고 프로그래머. 말하자면, 그러한

f('t', 'l') = 1 
f('a', 'o') = 1 
f('f', 't') = 1

하지만 지금

f('a', 'z') = 0 
etc.

우리가 쿼리 'cofatyst', 알고리즘은 다음과 일치보고해야합니다 경우 :

('cot', 0) 
('cat', 0) 
('catalyst', 0)

어디 수 발견 된 일치의 0부터 시작하는 인덱스입니다. 나는 Aho-Corasick algorithm을 시도해 봤는데 정확한 일치를 위해 훌륭하게 작동하고 문자가 "비슷한"문자의 수가 상대적으로 적 으면 캐릭터의 비슷한 문자 수를 늘리면 성능이 기하 급수적으로 떨어집니다. 누구든지이 일을하는 더 좋은 방법을 가르쳐 줄 수 있습니까? 퍼지는 절대적 필요성이며 캐릭터 유사점을 고려해야합니다 (즉, 편집 거리에 따라 맹목적으로 의존하지 않아야 함).

출처

2013-05-02 yati sagade

그래서 기본적으로, 당신은 (키보드에 가깝게 문자 등) 계정으로 그 특정 문자를 필요 최소 편집 거리의 어떤 종류가 교체 될 가능성이 더 높습니다 싶어? 제 직감은 StackOverflow에 대한보다 나은 응답을 얻으려고한다는 것을 말하고 있습니다. – acattle

맞음! 그리고 유사한 문자의 개념은 다를 수 있습니다 (예를 들어, 어떤 물건을 OCR 할 때, 나는 'a'로 오인되기보다는 't'또는 'i'로 오독 될 가능성이 큽니다). 잘 –

가능한 중복 [사전 단어를 모호하게 검색하는 방법?] (http://stackoverflow.com/questions/16333766/how-to-fuzzily-search-for-a-dictionary-word) SO와 언어학. 스택 교환. 후자에 대한 질문은 여기에서 이전되었습니다. – jogojapan

levenshtein 거리는 미세한 입자는 아니지만 찾고있는 것과 비슷합니다. 그 알고리즘의 제어 된 버전을 다시 구현할 수는 있지만 확신합니다.

http://en.wikipedia.org/wiki/Levenshtein_distance

출처

2013-05-02 13:19:58 beiller

이것은 시작이지만 문제는 거대한 사전과 함께 쿼리 내에서 사전 * 부분 문자열 *을 어떻게 검색합니까? Levenshtein 거리 계산 알고리즘은이를 수용하도록 수정 될 수 있습니다 : http://ginstrom.com/scribbles/2007/12/01/fuzzy-substring-matching-with-levenshtein-distance-in-python/하지만, 일치하는 하위 문자열의 Levenshtein 거리가 가장 적음 - 일치 항목을 상자 밖으로 가져 오지 않습니다. 나는 내가 가까이에 있다고 생각한다. 그리고 여기에 충분한 브레인 스토밍이 있다면, 우리는 깔끔한 것을 생각해 낼 수있다. –

fuzzily 사전 단어를 검색하는 방법?

답변

관련 문제