주소록 및 트리 구조

Question

질문이 있습니다. 30000 개의 이름이 포함 된 비즈니스 주소록을 구현해야합니다. 모든 이름에는 성과 이름이 있습니다. 성을 입력 할뿐만 아니라 성을 검색하는 자동 완성 텍스트 상자를 구현해야합니다. Google에서 검색 patricia trie를 사용하여이 문제를 해결했음을 알았지 만 접두사 검색 만하므로 firstname + 성으로 trie를 만들면 firstname과 lastname을 어떻게 검색 할 수 있습니까?

이렇게 두 문자열을 삽입하여 항목을 복제해야합니까? 성 및 이름 및 성 + 이름

도와주세요!

매우 효율적이어야합니다.

감사합니다.

Answer 1

예, 가장 간단한 해결책은 두 변종을 모두 삽입하는 것입니다. 그러나이 항목은 항목이 아닌 검색 문자열 만 복제해야합니다. 어쩌면 이름과 성의 구분을 정규화하고 싶을 것입니다 (= 주소록과 사용자 입력에 대한 구두점 문자 제거). 따라서 모든 경우에 "John Doe", "Doe , John ","Doe John "등.

부분 트라이가 아니라 균형 잡힌 트리를 사용합니다. 많은 언어에서, 균형 잡힌 트리가 라이브러리의 정렬 된 맵 구현 (Java 및 C++ 이상)으로 사용됩니다.

Answer 2

또 다른 가능성은 두 번의 시도를 만드는 것입니다.

첫 번째 이름은 T1이되고, 마지막 이름은 두 번째 이름입니다 (T2).

당신이 (보통 $ 기호로 표시) T1 각 단어 터미네이터에서의 트라이를 구성

는 T2의 관련 항목에 대한 포인터의 목록을 추가하고, 그 반대.

I.E.

T1: 
    J 
    | 
    O 
    | 
    H 
    | 
    N 
    | 
    $1 
T2: 
    D 
    | 
    O 
    | 
    E 
    | 
    $2 

$ 1 $ 1 포함, 목록을 개최한다 $ 2 $ 2로 포인터를 포함하는 목록을 개최한다 : 존 도우는 입장 인 경우.

각 접두사 검색은 자동 완성을 얻은 다음 포인터를 사용하여 전체 이름을 가져옵니다 (부분 검색은 성/이름 만 입력하면 포인터를 사용하여 두 번째 정보를 얻음). 이름을 검색

이 모두 시도에서 검색하면됩니다, 당신은 포인터의 일치 여부를 확인해야합니다 (T1과 T2의 마지막 이름의 이름을 찾아, 각각 관련 $1 및 $2를 얻을 수) (목록 l1 in $1은 $2이고 목록 l2은 $2에 $1을 포함합니다. 그들이하는 경우 - 이름은 사전에 있습니다.

$ 노드에 대한 포인터가 있으면 루트가되어 $ 기호가 나타내는 단어를 얻을 때까지 간단히 트라이로 돌아갈 수 있습니다.(각 노드의 상위 노드에 대한 포인터가 필요함)

참고 : 간단한 시도에 대해 설명했지만, patricia를 사용하지 않는 이유는 없습니다. 동일한 접근 방식을 사용합니다.