자바의 퍼지 문자열 검색 라이브러리

자바의 퍼지 문자열 검색 라이브러리

---

퍼지 문자열 검색을위한 고성능 Java 라이브러리를 찾고 있습니다.

유사한 문자열, Levenshtein 거리, Daitch-Mokotoff Soundex, n-gram 등을 찾는 수많은 알고리즘이 있습니다.

어떤 Java 구현이 존재합니까? 그들에 대한 장단점? Lucene을 알고 있습니다. 다른 솔루션이나 Lucene이 가장 좋습니다.

나는 이것들을 찾았습니다. 누구든지 그들에 대한 경험이 있습니까?

• SimMetrics
• NGramJ

---

Commons Lang은 Levenshtein distance를 구현했습니다 .

Commons Codec에는 soundex 및 metaphone이 구현되어 있습니다.

---

대부분 짧은 문자열을 비교하고 이식 가능하고 가벼운 것을 원한다면 Java로 포팅 된 잘 알려진 파이썬 알고리즘 fuzzywuzzy를 사용할 수 있습니다 .

여기에서 자세한 내용을 읽을 수 있습니다.

---

Apache Lucene을 사용할 수 있지만 사용 사례에 따라 너무 무거울 수 있습니다. 매우 간단한 퍼지 검색의 경우 사용하기가 약간 복잡 할 수 있으며 (내가 틀렸다면 수정) 인덱스를 작성해야합니다.

간단한 온라인 (= 인덱스를 유지하지 않음) 알고리즘이 필요한 경우 퍼지 Bitap 알고리즘을 사용할 수 있습니다 . 여기 에서 Java 구현을 찾았 습니다 . 이 코드는 거의 자명 한 서명을 가진 비교적 짧은 단일 방법에 적합합니다.

public static List<Integer> find(String doc, String pattern, int k)

Apache Commons StringUtils에는 퍼지 문자열 일치를위한 Levenshtein 알고리즘이 구현되어 있습니다. 의 퍼지 버전으로 볼 수 있으며 String.equals, Bitap은의 퍼지 버전과 같 String.indexOf으며 여전히 Levenshtein 거리 측정을 사용합니다. 일반적으로 Levenshtein을 순진하게 사용하는 것보다 검색 패턴을 일치 할 수있는 각 하위 문자열과 비교하는 것이 더 효율적입니다.

참고 :

• Bitap 알고리즘은 비교적 작은 알파벳 (예 : 일반 ASCII)에 주로 유용합니다. 실제로 내가 링크 한 Simon Watiau 버전 ArrayIndexOutOfBoundsException은 ASCII가 아닌 문자 (> = 128)를 사용하므로이를 필터링해야합니다.

• 응용 프로그램에서 Bimap을 사용하여 메모리 내 사람 목록을 이름으로 검색해 보았습니다. Levenhstein 거리가 2이면 오 탐지가 너무 많이 발생한다는 것을 알았습니다. Levenhstein 거리가 1이면 더 잘 작동하지만 "William"과 "Willaim"과 같이 두 글자를 바꾸는 오타는 감지 할 수 없습니다. 이를 해결하는 몇 가지 방법을 생각할 수 있습니다.

  1. 정확한 검색에서 일치하는 항목이없는 경우에만 퍼지 검색을 수행 (그리고 이에 대한 메시지를 사용자에게 표시)
  2. 스왑이 2 대신 거리 1을 갖는 Damerau-Levenshtein 거리를 사용하도록 Bitap을 조정하십시오. wikipedia 에 따르면 이것이 가능하지만 Java에서 기존 구현을 찾을 수 없습니다.
  3. "contains"대신 "startsWith"를 수행하십시오. 퍼지 검색 도구는 Damerau - Levenshtein의 접두사 버전이 포함되어 있지만, 그것은 나했다ArrayIndexOutOfBoundsException
  4. 정확한 일치 점수가 더 높은 검색 결과 순위를 도입하도록 알고리즘 조정

  2 또는 4를 수행하려는 경우 어쨌든 Lucene과 같은 적절한 전체 텍스트 검색 라이브러리를 사용하는 것이 더 나을 수 있습니다.

• 퍼지 검색에 대한 자세한 내용은 이 블로그 에서 찾을 수 있습니다 . 작성자는 또한 라는 Java 구현을BitapOnlineSearcher 만들었지 만 java.io.ReaderAlphabet 클래스와 함께 사용해야 합니다. Javadoc은 러시아어로 작성되었습니다.

---

SimMetrics는 아마도 당신에게 필요한 것입니다 : http://sourceforge.net/projects/simmetrics/

다양한 편집 거리를 계산하기위한 여러 알고리즘이 있습니다.

Lucene은 매우 강력한 전체 텍스트 검색 엔진이지만 FT 검색은 퍼지 문자열 일치와 정확히 일치하지 않습니다 (예 : 문자열 목록이 주어지면 일부 후보 문자열과 가장 유사한 문자열을 찾습니다).

---

Lucene에 SOLR http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters를 추가합니다 .

---

Completely 라이브러리를 사용해 볼 수 있으며 , 텍스트 전처리에 의존하여 대용량 데이터 세트에서 효율적으로 응답 (퍼지) 검색을 수행하기위한 인 메모리 인덱스를 생성합니다. Lucene 및 기타 모든 기능을 갖춘 텍스트 검색 라이브러리와 달리 API는 작고 시작하기 쉽습니다.

---

비탑을 시도해 볼 수 있습니다. 나는 ANSI C로 작성된 bitap을 가지고 놀고 있었고 http://www.crosswire.org에 자바 구현이 꽤 빠르다 .

---

Apache Lucene 이 유일한 방법이라고 생각합니다. 나는 더 나은 검색 lib를 모른다.

Apache Lucene (TM)은 전적으로 Java로 작성된 고성능의 완전한 기능을 갖춘 텍스트 검색 엔진 라이브러리입니다. 전체 텍스트 검색이 필요한 거의 모든 애플리케이션, 특히 크로스 플랫폼에 적합한 기술입니다.

참고 URL : https://stackoverflow.com/questions/327513/fuzzy-string-search-library-in-java