고정 된 접두사로 시작하는 'k'단어의 빈도가 내림차순으로 나열하십시오.

Question

나는 약 10^5 영어 단어와 그 초기 빈도 목록이 있습니다. 나는 단어의 완성을 제안하는 프로그램을 쓰고 싶다. 최대 숫자는 k이다. 주어진 접두어로 시작하여 빈도의 내림차순으로 정렬된다. 데이터 구조는 단어의 빈도 카운트를 1 씩 업데이트 할 수 있어야합니다 (단어가 사용될 때마다).

접두어로 '지점을 인식'을 감안할 때 예 - 를 들어

및 k = 3, 그것은 같은 목록을 반환해야 this- {{17, "엔진"}, {10, "엔지니어"}, {4, "엔지니어링" }}

k의 값은 [1, 15] 내에 있어야합니다.

Trie 데이터 구조는 주파수 별 정렬이 문제가 아니었지만 충분해야합니다. 아무도이 문제를 해결하기 위해 어떤 데이터 구조 나 접근법에 대해 나에게 암시 할 수 있습니까?

참고 : Trie 데이터 구조가 너무 많은 공간을 사용합니다. 나는이 데이터 구조에 대해 10MB 이상의 여유가 없다. 또한, 트라이 노드 (적어도 3/4 깊이까지)와 연관된 최대 힙을 사용하면 메모리 소비가 엄청나게 커집니다.

지금은 이것을 시도했습니다. 4 개의 정렬 된 세트 (포인터를 가리키고 문자열을 가리킴)를 유지합니다. 설정 i는

문자열의 첫 번째 i 문자 string length >= i sorted-

• 사전 순 문자열 만약 충돌, 주파수의 순으로
• 하면 임의의 순서로 다시 충돌, (에 대한 포인터의 목록입니다

이 고려, 잘 작동) 중요하지, 난 초기화 (4N 은 log2 (N)) 시간 및 O (N은 log2 (N)) 공간 O를 필요로한다. 각 쿼리에 대해 O (log2 (n))의 조회 시간 복잡도와 최악의 경우 최대 약 100 단어 순회가 있습니다. 단어의 빈도를 업데이트하려면 O (8 * log2 (n)) 시간이 필요합니다.

Answer 1

왜 트라이가 아니겠습니까? 카운터에 여분의 데이터 필드를 사용하고 정렬 알고리즘을 검색 알고리즘에 추가 할 수 있습니다. 카운터와 트라이를 업데이트하는 것도 빠릅니다. k 최대/위쪽 가장자리 만 원한다면 모두 정렬 할 필요가 없기 때문에 더 빠릅니다.

Answer 2

이것은 두 개의 데이터 구조 trie와 세그먼트 트리의 조합으로 수행 할 수 있습니다. (사전이 정적이고 k이 그리 크지 않은 경우).

사전에 대한 trie를 구성한 후 각 노드를이 노드에 속한 첫 번째/마지막 단어의 색인으로 늘립니다. 예를 들어 'engin'노드는 'engine'에 대한 인덱스 1001과 'engineering'에 대한 인덱스 1003을 저장할 수 있습니다.

k 개의 단어 목록을 검색 할 때는 trie에서 주어진 prefix를 검색하는 것으로 시작하십시오. 그런 다음 첫 번째/마지막 단어 색인을 사용하여 k 개의 범위 최대 쿼리를 수행합니다. 각 쿼리 후 일시적으로 찾은 단어의 빈도 카운트를 -1으로 설정합니다.

범위 최대 쿼리에 세그먼트 트리 데이터 구조를 사용하십시오. 자세한 내용은 tutorial at TopCoder을 참조하십시오.

이 접근 방식은 시간 O (prefix_size + k * log (dict_size))의 각 쿼리를 처리 할 수있게합니다. 카운터 업데이트에는 O (log (dict_size)) 시간이 필요합니다. 초기 주파수는 O (dict_size) 시간에로드됩니다.

---

다른 대안은 트라이 각 노드 {k_max 카운터 인덱스} 쌍의 정렬 된 배열을 저장한다.

초기 주파수는 O (k_max * dict_size) 시간의 상향 순서 (DFS 포함)의 각 노드에서 병합으로 업데이트해야합니다. 각 카운터 업데이트에는 O (k_max * word_length) 시간이 필요합니다. Top-k 쿼리는 O (prefix_size) 시간에 제공됩니다. 단점은 훨씬 더 높은 메모리 요구 사항입니다.