자바의 퍼지 문자열 검색 라이브러리
퍼지 문자열 검색을위한 고성능 Java 라이브러리를 찾고 있습니다.
유사한 문자열, Levenshtein 거리, Daitch-Mokotoff Soundex, n-gram 등을 찾는 수많은 알고리즘이 있습니다.
어떤 Java 구현이 존재합니까? 그들에 대한 장단점? Lucene을 알고 있습니다. 다른 솔루션이나 Lucene이 가장 좋습니다.
나는 이것들을 찾았습니다. 누구든지 그들에 대한 경험이 있습니까?
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"과 같이 두 글자를 바꾸는 오타는 감지 할 수 없습니다. 이를 해결하는 몇 가지 방법을 생각할 수 있습니다.
- 정확한 검색에서 일치하는 항목이없는 경우에만 퍼지 검색을 수행 (그리고 이에 대한 메시지를 사용자에게 표시)
- 스왑이 2 대신 거리 1을 갖는 Damerau-Levenshtein 거리를 사용하도록 Bitap을 조정하십시오. wikipedia 에 따르면 이것이 가능하지만 Java에서 기존 구현을 찾을 수 없습니다.
- "contains"대신 "startsWith"를 수행하십시오. 퍼지 검색 도구는 Damerau - Levenshtein의 접두사 버전이 포함되어 있지만, 그것은 나했다
ArrayIndexOutOfBoundsException
- 정확한 일치 점수가 더 높은 검색 결과 순위를 도입하도록 알고리즘 조정
2 또는 4를 수행하려는 경우 어쨌든 Lucene과 같은 적절한 전체 텍스트 검색 라이브러리를 사용하는 것이 더 나을 수 있습니다.
- 퍼지 검색에 대한 자세한 내용은 이 블로그 에서 찾을 수 있습니다 . 작성자는 또한 라는 Java 구현을
BitapOnlineSearcher
만들었지 만java.io.Reader
Alphabet 클래스와 함께 사용해야 합니다. 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
'program story' 카테고리의 다른 글
Await 연산자는 Async 메서드 내에서만 사용할 수 있습니다. (0) | 2020.11.12 |
---|---|
JSDoc에서 약속의 해결 및 거부 유형을 지정하는 방법은 무엇입니까? (0) | 2020.11.12 |
RNGCryptoServiceProvider의 장단점 (0) | 2020.11.12 |
C # 템플릿 엔진 (0) | 2020.11.12 |
C # ASP.NET Single Sign-On 구현 (0) | 2020.11.12 |