startsWith()와 같은 빠른 문자열 검색 equals()

Question

나는이 목록에서 자주 검색 할 수있는 정렬 된 목록 (사전 - 100,000 단어)과 많은 단어가 있습니다. 따라서 성능이 문제입니다. HashSet.contains (theWord) 또는 Collections.binarySearch (sortedList, theWord)는 매우 빠르다는 것을 알고 있습니다. 그러나 나는 실제로 전체 단어를 찾고 있지 않습니다.

내가 원하는 것은 "se"를 검색하고 모든 단어를 "se"로 시작한다고 가정 해 보겠습니다. Java 나 라이브러리에서 사용할 수있는 솔루션이 있습니까?

더 나은 예 : 정렬 된 목록에서

myWordList.subList ("AB"의 간격을 반환 // 다음 조작

List.subList (문자열 beginIndex의, 문자열에서 endIndex)에 대한 빠른 솔루션, "기원전");

참고 : 여기는 매우 비슷한 질문이지만 허용 된 대답은 만족스럽지 않습니다. Overriding HashSet's Contains Method

Answer 1

당신이 여기에서 찾고있는 것은 데이터 구조가 commanly에 '트라이을'이라는 것입니다 문자열의 첫 번째 문자, 두 번째 문자, 두 번째 문자 등입니다. 결과는 매우 큰 문자열 집합의 하위 집합을 매우 빠르게 접두어로 추출 할 수있게합니다.

Answer 2

Trie 구조는 사전과 공통 접두어가있는 단어를 찾기에 매우 적합합니다. Google Collections/Guava에는 의 기고 물이 있습니다.

http://en.wikipedia.org/wiki/Trie

그것은 나무의 첫 번째 레벨이 포함되어 접두사에 의해 색인 나무에 문자열을 저장합니다

Answer 3

새로운 구조는별로 필요하지 않습니다. 문제는 목록에서 이진 검색으로 해결할 수 있습니다. 특히 이진 검색을 수정하여 첫 번째 요소 (지정된 접두어가있는 첫 번째 요소)를 반환 할 수 있습니다.

List.subList (문자열 beginIndex의, 문자열에서 endIndex는) // 내가 바보가 될 수있다
간격을 반환하지만 인덱스 어떤 종류의 문자열 유형이? 이 부분을 명확히 할 수 있습니까?

Answer 4

검색 결과는 주문한 단어 목록의 범위가됩니다. 이를 얻으려면 범위의 첫 번째 요소와 마지막 요소의 색인이 필요합니다.

첫 번째 검색을 수행하려면 원래 검색 문자열 ("se")을 사용하여 이진 검색을 실행하고 각 반복의 현재 위치와 비교하십시오. 현재 위치의 단어가 검색 문자열보다 크지 만 현재 단어가 더 낮 으면 중지하십시오.

마지막 색인을 얻으려면 검색어 "+"z "("sez ")에서 다른 이진 검색을 실행하십시오. 그러나 현재 색인의 단어가"sez "보다 작지만 현재 +1이 더 큰 경우에만 중지하십시오 .

마지막으로 프로그래밍 언어에서 사용할 수있는 모든 방법으로 첫 번째 및 마지막 색인으로 표시된 범위를 반환하십시오.

이 방법은 두 가지 가정에 구축된다

• 문자열 비교는 "B"를보고 'AZ'보다
• "Z"는 단어의 목록 중 가장 숯 값

이 알고리즘은 JavaScript 데이터 조작 라이브러리 (jOrder.net)에 구현되어 있습니다.