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

Question

나는 Elasticsearch/Lucene와 같은 도구가 기본적으로 제공하는 편집 거리 기반 퍼지 검색에 대해 여기서 많은 스레드를 읽었지만 문제는 약간 다릅니다. I는에 의해 지정 될 수있는 단어들의 사전 { '고양이', '요람', '촉매'} 및 문자 유사성 관계 f (x, y)를

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

(이 "유사성"이 가정 프로그래머)

같은 말, 즉,

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

하지만 지금

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

우리가 'cofatyst'쿼리가있는 경우 algorit HM은 다음과 일치를보고해야합니다 :

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

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

주목할 점은 야생에서 사전은 실제로 커질 것입니다.

Answer 1

저는 광산 프로젝트에 Fuse JavaScript Library을 사용하고 있습니다. JSON 데이터 세트에서 작동하는 자바 스크립트 파일입니다. 꽤 빠릅니다. 그것을보십시오.
Google은 자신의 사이트에서 Diff, Match & 패치 도구의 수정 된 버전을 사용하여 전체 Bitap 알고리즘을 구현했습니다.

코드는 완료된 알고리즘 구현을 이해하기 쉽습니다.

Answer 2

각 문자의 위치를 ​​피쳐로 사용하고 문자 관계를 기반으로하는 일치 함수를 사용하여 피쳐간에 제품을 매핑하려고하면 코사인 유사성을 사용하려고 할 수 있습니다.

아주 구체적인 조언은 아니지만 나는 그것이 당신을 돕기를 바랍니다.

편집 : 확장 답변.

코사인 유사도를 사용하면 비슷한 두 벡터가 얼마나 유사한 지 계산하게됩니다. 귀하의 경우 정규화가 이치에 맞지 않을 수 있습니다. 그래서, 내가하는 일은 매우 간단합니다 (문제를 지나치게 단순화하는 것일 수도 있습니다) : 첫째, CxC의 행렬을 두 문자가 관련이있을 확률을 가진 종속 행렬로 봅니다 (예 : P ('t'| 'l') = 1). 또한 부분 일치를 통해 전체 및 부분 일치를 구별 할 수 있습니다. 이 후, 각 위치에 대해 각 단어의 문자가 같지 않은 확률 (P (t_i, t_j)의 보수를 사용)을 계산 한 다음 합계를 사용하여 결과를 집계 할 수 있습니다.

특정 단어 쌍에 대해 다른 용어의 수를 세며 부분적인 종속성을 정의 할 수 있습니다. 또한, 구현은 매우 간단하며 잘 확장되어야합니다. 그래서 내가 당신의 질문을 오해하는지 확실하지 않습니다.