주어진 집합이 집합 집합에 있는지 여부를 쿼리하기위한 데이터 구조

Question

단어 게임 해결사의 데이터 구조를 작성하려고합니다.

{A, A, D, E, I, L, P, T, V, Y} 형식의 약 150,000 세트를 저장해야합니다. (정규화 된 영어 단어, 즉 정렬 된 문자입니다. 멀티 세트에 동일한 문자를 두 번 포함 할 수 있습니다.)

다음 쿼리 종류에 대한 예/아니오 대답을 효율적으로 가져와야합니다. 주어진 부분 집합으로 설정? 예를 들어, 알려진 단어 중 어느 것도 {D, E, I, L, L, P} 집합을 포함합니까?

요구 사항 :

• 쿼리는
• 이 데이터 구조는 데이터 구조가 가 실시간으로을 구축 할 필요는
• 공간의 합리적인 금액 (예를 들어 < 50메가바이트)에 맞게해야 빨라야 시각; 미리 계산됩니다.

이 필요성에 잘 부합하는 데이터 구조가 있습니까? 이것은 목표 세트가 실제로 멀티 세트라는 점에서 StackOverflow의 otherset matching 질문과 조금 다릅니다.

Answer 1

이것은 내가 한 번 만든 mutation prefix tree/trie를 상기시켜줍니다. 약간 다르지만 작동 할 수 있습니다. 크거나 경계가 없거나 언어로 변환 할 수없는 경우 작동하지 않을 수 있습니다 (C++의 코드).

기본적으로 트라이에서는 보통 다음 편지에 해당하는 어린이를 저장하지만 내가 한 일은 각 문자의 빈도에 따라 어린이를 저장하는 것입니다.

기본적으로 (내 관점에서) 질문은 "하위 집합과 같거나 그 이상의 문자가있는 집합이 있습니까?예를 들어, 하위 집합이 {A, D, E, E}이면 하나 이상의 A, D 및 두 개의 E가있는 집합이 있는지 찾아야합니다.

따라서 trie의 경우 . 기본적으로이

  Root 
     /| \ 
     //|\ \ 
     // | \ \ 
     1 2 ... MAX <-- This represents the frequency of "A" 
     /|\ ..... /|\ 
     1..MAX 1..MAX <-- Frequency of "B" 
     ............... 
     ............... 
     ............... 
    1 ... ... ... MAX <-- Frequency of "Y" 
    /|\ .... ..../| \ 
    1..MAX ...... 1 .. MAX <-- Frequency of "Z" 

의 모든 같은 일이 ... '의는/표시하는 데 시간이 너무 오래 걸릴 것 물건을 많이 표현 | 부모 자식 관계를 나타내고 \ 및 MAX 편지의 최대 주파수를 나타냅니다

:

그래서 당신이 무엇을, 당신은 같은 몇 가지 종류의 구조체 (C에서 내가 코드를 ++)이있다

노드를 만들 때 모든 자식을 NULL로 초기화해야합니다. 당신은 (C++에서) 생성자 또는 시작시

NODE* makeNode() { 
    NODE* n = new NODE;   // Create a NODE 
    for(int i = 0;i <= MAX;i++) // For each child 
     n->child[i] = NULL;  // Initialize to NULL 
}; 

같은 makeNode() 함수를 통해이 작업을 수행 할 수 있습니다는 트라이 그냥 루트

NODE* root = new NODE; 

당신이에 세트를 추가 trie, 당신은 각 편지의 빈도를 얻고 트라이를 통과합니다. 특정 노드에서 다음 문자에 해당하는 자식이 NULL이면 새 NODE를 작성하기 만하면됩니다.

트라이를 검색 할 때 하위 집합의 문자 빈도에 해당하는 모든 노드의 하위를 모두 검색합니다. 예를 들어 하위 집합에 3 개의 A가있는 경우 루트 -> 하위 [3]을 모두 검색 한 다음 루트 -> 하위 [4]를 선택한 다음 루트 -> 하위 [MAX]를 검색합니다. 당신이해야처럼 내가 혼란 무엇인지에 대해 언급하시기 바랍니다 다음 화가 아니에요 생각하고 2)/아마 간단한 방법

Answer 2

트라이를 사용하여 각 세트를 트라이에 삽입하고 대상 서브 세트를 사용하여 반복적으로 트라이를 통과하여 일치하는 서브 세트가 있는지 확인할 수 있습니다. 적어도 내가 그렇게 할 것이라고 생각합니다.

'트라이'

실제로 검색 할 데이터 구조에 대한 생각, 그리고 거의 정상적인 나무와 비슷하지만 예를 들어, 서로 다른 순열과 노드가되었습니다

 A 
    /\ 
    AT AN 
    /| \ 
    | | AND 
    ANN ANY 
    | 
    ANNA 

위의 예에서, 당신은 할 수 ANN과 ANNA를 집합과 같이 검색 할 수 있으므로 이것이 아마도 당신의 경우에 유용하다는 것을 알 수 있습니다. 이 유형의 ADT (Abstract Data Type)와 함께 일부 순열 코드를 사용할 수도 있습니다.

는 KD-Trees 또는 변형을 사용하여 시도 할 수처럼 더 here

Answer 3

이 보이는 찾을 수 있습니다.

탐색 할 관련 주제는 다차원 범위 검색/쿼리입니다.

경고 : 나는이 글을 사용하지 않았지만 위의 주제에 대한 몇 가지 문헌을 읽으면 유용한 것을 발견 할 수 있기를 바랍니다.

희망이 있습니다.