2010-06-07 4 views
3

몇 줄의 문자열이 있고 모든 접두사에 대해 가장 일반적인 접미사 10 개를 찾고 싶습니다. 그것에 대한 효율적인 알고리즘이 있습니까?효율적인 가장 일반적인 접미사 알고리즘입니까?

확실한 해결책은 다음과 같습니다

  • 스토어 <string, count>쌍 목록을 분류.
  • 우리가 검색하는 접두사에 대한 이진 검색 범위로 식별하십시오.
  • 이 범위에서 가장 높은 숫자는 count입니다.
  • 모든 짧은 접두사에 대해 사전 계산이 가능하므로 데이터의 많은 부분을 볼 필요가 없습니다.

실제로 그렇게 효율적인지 확실하지 않습니다. 내가 간과 한 더 나은 방법이 있습니까?

답변은 실시간이어야하지만 필요한만큼 사전 처리가 필요할 수 있습니다.

+0

사용중인 특정 언어는 무엇입니까? C++ 또는 Java로 추측 할 수 있습니다 ... 또한 DB에있는 문자열 또는 파일에있는 문자열입니까? – nico

+0

그것은 모든 파일이고 어떤 언어가 가장 빠르므로 거의 확실합니다. – taw

답변

6

단어를 트리에 배치하십시오. trie 또는 radix으로 각 단어에 대해 "발생 횟수"카운터를 배치하여 어떤 노드가 결말인지 및 얼마나 일반적인 지 알 수 있습니다.

접두사/접미어 콤보를 반복으로 찾습니다.

이러한 연산은 모두 O (n * k)입니다. 여기서 k은 가장 긴 단어의 길이입니다. 이것은 해시 테이블로 same complexity입니다.

HAT-trie는 고성능을 약속하는 캐시를 고려한 버전입니다.

+0

+1하지만 트라이에서 오른쪽에서 왼쪽으로 문자를 추가하는 것이 좋습니다. –

+0

@Lieven : 트 리는 접두어 트리 또는 접미어 트리로 사용될 수 있습니다. –

+0

@Matthieu : 감사합니다. 오해 한 것 같습니다. –

관련 문제