상당히 작은 데이터 세트로 Java로 입력 할 때 find를 구현하는 더 좋은 방법이 있습니까?

Question

파일에 약 2500 개의 짧은 문구가 있습니다. 내가 가능한 부분 문자열을 입력 할 때 구문을 찾을 수 있기를 원합니다. 내 응용 프로그램에는 텍스트 상자와 구문 목록이 있습니다. 텍스트 상자는 처음에는 비어 있으며 빈 문자열은 모든 문자열의 하위 문자열이므로 목록에 2500 개의 모든 구가 포함됩니다. 텍스트 상자에 입력 할 때 텍스트 상자의 값을 부분 문자열로 포함하는 구만 항상 포함되도록 목록이 업데이트됩니다. 순간

내가 특별히 구글의 multimap의 중 하나가 :의 가능한 일치에 매핑 된 모든 단일 가능한 문자열로

LinkedHashMultimap<String, String> 

. 이것은 (약 1 초)로드하는 데 시간이 걸리고 앞으로는 상당한 공간을 차지해야한다고 생각합니다. (이것은 앞으로 걱정이 될 수도 있습니다.) 조회가 매우 빠릅니다.

다른 데이터 구조 나 전략을 사용하여로드를 줄이고 공간을 적게 차지할 수있는 방법이 있습니까 (조회 속도가 저하 될 수 있음)?

Answer 1

목록에 2500 개의 요소 만있는 경우 간단한 루프와 contains contains()를 모두 사용하면 충분히 빠릅니다.

• 은 사용자 유형으로 즉시 각 문자를 검색하지 말고 약간의 지연을 소개 : 그것은 더 큰 성장 및/또는 너무 느린 경우

  , 당신은 몇 가지 쉬운 최적화를 적용 할 수 있습니다. 그래서 그가 "foobar"를 정말로 빨리 입력하면, "foo"가 아닌 "foobar"만 검색하고, "fo", "foo"는 검색하지 않습니다.

• 사용자가 이전에 사용한 결과를 다시 사용합니다 : 사용자가 "foo "그 다음 그것을"foobar "로 확장하고 원래의 전체 목록을 다시 검색하지 않고"foobar "를 포함하는 모든 것이"foo "를 포함해야하므로"foo "에 대한 결과를 검색하십시오.

이러한 기본적인 최적화 덕분에 이미 상당히 멀리 떨어져 있습니다.

목록이 커지면 속도가 너무 느려지므로 여기서 다른 답변 (시도, 접미어 트리 등)에서 제안 된 "더 똑똑한"최적화가 필요할 수 있습니다.

Answer 2

Trie data structure을 사용하는 것이 좋습니다.

Answer 3

당신은 definetely 접미사 트리을 .. 필요 (wiki)

은 (내가이 구현은 확인 될 수 있다고 생각 : link)

편집 :

나는 당신의 코멘트를 읽은

, 당신 문자열이 어구의 어딘가에있는 부분인지 맹목적으로 검사해서는 안되며, 보통 공백이 아닌 단어로 시작합니다. 어쩌면 문구 안에 단어를 토큰 화하는 것이 더 낫겠습니까?

허용 하시겠습니까? 그렇지 않으면 가장 좋은 방법은 모든 문구에 대해 또는 비슷한 알고리즘 (예 : Karp-Rabin string search 알고리즘)을 사용하여 오토 마톤을 작성하는 것입니다.

Answer 4

단순히 전체 목록을 반복하고 을 호출 해보십시오.이 작업을 2500 번 수행하면 아마 눈치 채지 못할 것입니다.

Answer 5

Wouter Coekaerts는 좋은 접근 방식을 가지고 있지만, 조금 더 나아갈 것입니다.

1. 텍스트 상자에 단일 문자가 포함되어 있으면 아무 것도 표시하지 마십시오. 결과는 유용하지 않습니다. 이것은 두 문자에 대해서도 마찬가지라는 것을 알 수 있습니다.
2. 두 문자의 결과를 미리 계산하십시오. 두 문자가있을 때 미리 계산 된 목록을 가져옵니다.
3. 세 번째 문자가 추가되면 현재 표시된 목록에서 '포함'검색을 수행합니다 (c1c2를 포함하지 않는 것은 c1c2c3을 포함 할 수 없음). 지금까지리스트는 충분히 작아야 'contains'가 완벽하게 적절한 성능을가집니다.
4. 마찬가지로 4 자 등
5. 위와 같이 검색을 시작하기 전에 약간의 시간 지연을 넣으십시오. 아니면 다른 문자가 입력되기 전에 검색이 종료되도록 배열하는 것이 좋습니다.