C에서 100k + 문자열 이상의 빠른 동적 퍼지 검색 #

Question

텍스트 상자에 입력 된 주식 기호가 사전로드되어 있다고 가정 해 보겠습니다. 설치할 수있는 코드가 아니라 복사 할 수있는 코드를 찾고 있습니다.

Are there any Fuzzy Search or String Similarity Functions libraries written for C#?

Levenstein 거리 알고리즘이 잘 작동하는 것 같다,하지만 계산 시간이 걸립니다 :

이

는이 질문에 의해 영감을했다. 사용자가 추가 문자를 입력 할 때 쿼리를 다시 실행해야한다는 사실에 대한 최적화가 있습니까? 각 입력에 대해 상위 10 개 일치를 표시하는 데 관심이 있습니다.

Answer 1

문자열 주위의 일치 규칙을 결정해야합니다. 무엇이 '와 유사한 캐릭터'와 일치하는 문자의

• 수를 결정
• 유사한 일치하지 않는 문자 길이
• 오타 또는 음성 오류
• 사업 특정 약어의
• 숫자로 시작해야합니다
• 동일한 하위 문자열
• 은 같은 하위 문자열로 끝나야합니다.

나는 문자열 매칭 알고리즘을 사용하여 많은 작업을 수행했으며 아직 특정 요구 사항을 충족하는 기존 라이브러리 나 코드를 찾지 못했습니다. 그것들을 검토하고 아이디어를 빌리 자. 그러나 당신은 언제나 자신 만의 코드를 커스터마이징하고 작성해야 할 것이다.

Levenstein 알고리즘은 훌륭하지만 조금 느립니다. Smith-Waterman & Jaro-Winkler 알고리즘을 사용하여 성공했지만 가장 좋은 점은 Monge (메모리)였습니다. 그러나 원래 연구를 읽고 왜 알고리즘과 목표 데이터 세트를 작성했는지 판단해야합니다.

정확하게 일치시키고 측정하려는 것을 정의하지 않으면 예기치 않은 일치에서 높은 점수를 얻고 예상되는 일치에서 낮은 점수를 얻습니다. 문자열 일치는 매우 도메인 특정입니다. 도메인을 제대로 정의하지 않으면 어부가되어 단서가 없으며 주변에 갈고리를 던지고 최선을 희망합니다.

Answer 2

This blog post은이 영역의 Lucene에 들어간 작업에 대해 설명합니다. Finnite Transducer (오토 마톤)를 사용하여 2의 편집 거리까지 매우 효율적으로 Levenshtein 거리 퍼지 매칭을 구현할 수있었습니다. 코드는 모두 Java로 작성되었으며 오픈 소스이지만 다소 복잡합니다.

그러나 기본적인 생각은 간단합니다. 사전을 문자 상태의 거대한 나무로 생각하십시오. state0에는 편지가 없습니다. state1에서는 단어의 첫 글자가 될 수있는 글자를 인정합니다. State2는 state1에 의해 조절됩니다. 첫 번째 문자가 'x'이면 다음 상태는 x 다음에 올 수있는 문자 만 허용합니다 (위치 2에서).

Levenshtein 매칭의 경우, 삭제, 삽입 (한 글자 와일드 카드), 그리고 아마도 전송 (Levenshtein의 멋진 확장은 오히려 단 하나의 편집으로 간주됩니다. 2보다). 허용 된 편집 수를 추적하려면 상태를 유지해야합니다. 이는 매우 효율적으로 수행 할 수 있습니다. 대화 형 "입력하는 동안"철자 수첩에 충분히 빠릅니다.