데이터 구조와 일치

Question

무엇을 다음과 같은 작업을위한 최상의 데이터 구조는

:
는 데이터 구조 단어
입력의 목록 저장 : 문자열 우리가 이름을 말하는 '사전'
출력을 : 저장된 단어 목록에서 접두어로 pre를 갖는 모든 문자열 목록과 목록의 단어는 우선 순위가 내림차순으로 정렬되어야합니다.
특정 문자열의 우선 순위가 출력으로 반환 된 문자열 목록에서 사용되면 증가합니다.
나는 이것을 단어 예측에 사용할 것이므로 사용자가 반환 된 단어 목록에서 특정 단어를 선택할 때마다 우선 순위가 1 씩 증가합니다. 은 이미을 구현했지만 출력 (목록) 사전 순으로 정렬 우선 순위에 따라 정렬하고 싶습니다.

Answer 1

문제의 최상의 데이터 구조는 trie입니다. 공간을 소비하면서 빠른 검색이 가능합니다. link

Answer 2

이 아마 최선의 해결책은 아니지만 어쩌면 그것은 당신에게 몇 가지 아이디어를 줄 것이다 :

자세한 내용은이 링크를 따르십시오.

모든 단어를 저장하고 노드에 우선 순위 필드가 포함되도록하려면 trie를 사용하십시오.

쿼리 함수와 동일한 범위를 갖는 사용자의 트라이가 볼 수있는 일종의 목록 데이터 구조가 있습니다. 목록에는 (단어, 우선 순위) 항목이 포함됩니다.

입력 단어 아래의 트리를 반복 ('pre'아래의 하위 트리)하고 모든 단어를 찾습니다 (아마도 노드에는 부울 '단어'필드 또는 다른 것이 있습니다). 단어가 발견되면 (단어 == 1), (단어, 우선 순위)를 목록의 끝에 추가합니다.

i가 새 항목의 위치라고 가정하고 list (i)와 list (i - 1)를 비교하십시오. 목록 (i - 1)의 우선 순위가 목록 (i)보다 작 으면 자신의 위치를 ​​전환합니다. i-1 번째 항목이 새로 추가 된 항목보다 우선 순위가 같거나 더 높아질 때까지 계속하십시오.

일단 트라이 검색 기능이 완료되면 (단어, 우선 순위) 항목이 감소하는 순서로 목록이 표시됩니다.

나는 이것이 의미가 있기를 바랍니다.

Answer 3

다른 답변이 표시되면 trie를 사용하여 주어진 접두사가있는 모든 단어를 빠르게 가져온 다음 우선 순위에 따라 단어를 정렬 할 수 있습니다. trie에서 일치하는 단어를 얻으려는 액세스 시간을 무시하고 k 개의 단어가 일치하면 우선 순위에 따라 정렬하려면 O(k log k) 시간이 걸립니다. 이것은 이론적으로 최적 인 O(k) 시간에 매우 가깝습니다. 실용적인 응용 분야에서 특히 문자를 인쇄 한 후에 k 단어를 인쇄 한 후 실제로 개선하기 위해 노력하고 싶지 않을 것입니다. O(kl) 은 일치하는 평균 길이가 단어 수와 l의 배율은 대개 대략 log k과 같은 순서입니다.그러나 사용하는 공간의 양을 O(L_avg)으로 늘리려는 경우 모든 단어의 평균 길이가 L_avg 인 경우 정렬 된 순서로 단어에 액세스하고 우선 순위 +1을 O(k + L log n)까지 업데이트하는 시간을 얻을 수 있습니다. 여기서 L 선택한 단어의 길이가 우선 순위 +1이되고, n은 총 단어 수입니다.

아이디어가 약간 미친 듯이 들리지만 내게 참아주십시오. 설명해 드리겠습니다. 메모리에는 실제로 O(L_avg)이 곱해집니다. 아이디어는 트리의 각 노드에서 우선 순위와 함께 해당 접두사가있는 모든 단어를 자체 균형 조정 이진 검색 트리 (우선 순위에 따라 정렬 됨)에 저장한다는 것입니다. 전체 단어 대신 단어를 저장하는 배열에 단어로 색인을 표시 할 수 있으므로 해당 트리의 각 노드에서 저장 요구 사항은 해당 접두어가있는 단어 수에 선형입니다. 단어가 우선 순위 +1이되면 trie를 거쳐 해당 트라이 노드에 대한 균형 이진 검색 트리를 업데이트하고 모든 부모 노드는 O(L log n) 시간이 걸립니다. 그러나 쿼리에 대한 응답으로 정렬 된 순서로 단어의 인덱스를 얻으려면 선주문으로 이진 트리를 탐색해야합니다.이 작업은 O(k) 시간이 걸립니다. 스토리지에 관해서. 길이가 L 인 단어는 L 바이너리 트리에 저장됩니다. 단어의 트라이 노드에있는 트리와 모든 L-1 상위 노드에 대한 트리입니다. 그러므로 트리의 모든 노드에있는 모든 나무의 총 저장 공간을 합산하면 트리에서 각 단어가 몇 번 발생했는지 계산하면 총 트리 저장 용량은 모든 단어의 총 길이에 선형입니다. O(n L_avg). 저장소에서 해당 승수를 처리 할 수 ​​있다면 쿼리 결과를 정렬하여 얻을 수있는 승수를 실제로 제거하려면 이론적으로 쿼리와 우선 순위 변경을 처리하는 가장 빠른 방법이라고 생각합니다.

Answer 4

이것은 메모리 비효율적 인 솔루션입니다.

참조 : 각 노드 저장소로 지금까지 통과 부모 접두사가 가능한 모든 유효한 접미사에서 Trie example

. 또한 빠른 검색을 위해서는 이러한 접미어를 저장하는 우선 순위에 따라 최대 힙을 사용하십시오. 예를 들어

당신의 C++ 트라이 노드 (I 코드를 테스트하지 않았습니다)

typedef pair<int, string> SUFFIX; 
class Compare { 
public: 
    bool operator() (SUFFIX &d1, SUFFIX &d2) { 
     return d1.first < d2.first; 
    } 
}; 
typedef priority_queue<SUFFIX, vector<SUFFIX>, Compare> max_heap; 

struct TrieNode { 
    char data; // char at current node 
    max_heap word_suffixes; 
    bool is_complete; 
}; 

/* Note: max_heap word_suffixes basically hold all strings without prefix so far. 
For example: You have dictionary of egg, eye at the starting node "e" your max 
heap will have two entries "gg" and "ye" (with highest priority say "gg" 
as root of max heap) 
*/ 

지금은 시간 복잡도가

1이됩니다) 접두사 "사전"에 따라, 트라이을 통과 같이 표시됩니다 O (L) (L = pre len)

2) 노드 힙에서 최대 문자열의 각 문자열, 우선 순위에 따라 정렬 된 목록을 제공합니다. O (nlogn) (n = 힙 크기) 3) 사용 된 단어의 우선 순위를 증가시킨 후 힙을 재구성합니다. O (nlogn)

참고 : 우선 순위가 높은 BST를 접미어로 사용해 볼 수도 있습니다. 순차적 순회는 우선 순위 정렬 된 접미사 목록을 제공합니다 (O (n)). 사용 된 단어의 우선 순위는 BST에서 접미사를 제거하고 새 우선 순위로 다시 추가하여 증가시킬 수 있습니다 (삽입/검색/삭제는 균형 BST의 경우 O (높이)가됩니다).