Java에서 문자열 검색 알고리즘

Question

많은 양의 데이터와 문자열 일치를 수행하고 있습니다.

편집 : 큰 목록에 포함 된 단어를 일부 온톨로지 텍스트 파일과 일치시킵니다. 온톨로지에서 각 파일을 가져 와서 각 파일 행의 세 번째 String과 목록의 단어를 검색합니다.

필자가해야 할 일은 순수한 일치 (결과가 좋지 않음)가 아니라, 문자열이 다른 문자열 안에 포함될 때 결과를 반환하는 좀 더 느슨한 일치 함수가 필요하다는 사실을 과오 감독 한 것입니다.

나는 이것을 Radix Trie; 그것은 매우 빠르며 훌륭하게 작동하지만, 이제는 trie가 정확한 일치만을 반환하기 때문에 내 작업이 쓸모 없다고 생각합니다. :/

• 이 작업을 수행하는 알고리즘 유형은 문자열 검색 알고리즘입니까?
• 누군가가 경험이있는 Java 구현을 제안 할 수 있습니까?

알고리즘은 빠르지 만 최우선 순위가 아니기 때문에 속도는 & 복잡합니다.

모든 조언/예/설명/링크에 대해 매우 감사드립니다.

감사합니다.

Answer 1

Suffix Trees이 유용 할 수 있습니다 (개념은 Tries와 유사 함).

각 문자열 앞에 ^가 붙고 $로 끝나고 추가 된 모든 문자열의 접미어 트리를 만듭니다. 공간 사용량은 O (n)이고 아마도 trie에 대한 것보다 더 나쁠 것입니다.

문자열 s를 검색해야하는 경우 trie처럼 쉽게 O (| s |) 시간을 할 수 있으며 일치하는 문자열은 부분 문자열 일치입니다 (기본적으로 일부는 일부 문자열의 접미사).

죄송합니다. 유용한 Java 구현에 대한 참조가 없습니다.

발견 유용한 유래 답변 : Generalized Suffix Tree Java Implementation

있습니다 http://illya-keeplearning.blogspot.com/2009/04/suffix-trees-java-ukkonens-algorithm.html

차례가 어떤 : 소스 코드 : http://illya.yolasite.com/resources/suffix-tree.zip

Answer 2

는 내가 제대로 질문을 이해하면 완전히 모르겠지만, 정규 표현식

http://java.sun.com/developer/technicalArticles/releases/1.4regex/

Answer 3

정규 표현식은 확실히 당신의 최선의 방법입니다 작업을 할 것 같은데. 쓸데없는 것일 수도 있지만 이해하기 어려운 일련의 if/else 또는 switch 문을 사용하지 않고 느슨한 일치를 얻을 수있는 유일한 방법입니다.

더하기, 대안보다 훨씬 빠릅니다.

Answer 4

당신이 하나의 패턴 텍스트 파일에서 검색 BM algorithm을 사용할 수 있습니다 , 그리고 귀하의 목록에있는 모든 패턴에 대해이 알고리즘을 반복하십시오. 당신이 자바에서 같이 IndexOf 메서드를 사용하지 않는 이유는 Aho–Corasick string matching algorithm

Answer 5

:

다른 가장 좋은 방법은 같은 멀티 패턴 검색 알고리즘을 사용하는 것입니다. 메모리 가용성에 따라 콘텐츠를 읽으십시오. indexOf를 수행하고 필요한 모든 행을 가져옵니다. 다음 내용 세트를로드하십시오.

파일에서 읽는다면 스트림을 사용하십시오.

아이디어가 좋지 않을 수도 있지만, 나는 자바에서 믿습니다. 그것은 최고의 알고리즘을 사용합니다.

정규 표현식을 사용하면 더 좋습니다.