수색…


Trie 소개

혹시 검색 엔진이 어떻게 작동하는지 궁금해 한 적이 있습니까? Google은 몇 밀리 초 만에 수백만 개의 결과를 어떻게 앞에 표시합니까? 수천 킬로미터 떨어져있는 거대한 데이터베이스는 어떻게 검색중인 정보를 찾아내어 다시 보내 줄 수 있습니까? 이것의 뒤에 이유는 더 빠른 인터넷 및 최고 컴퓨터 만 사용해서 가능하지 않다. 일부 매혹적인 검색 알고리즘과 데이터 구조가 뒤에서 작동합니다. 그 중 하나가 트라이 입니다.

Trie프리픽스 로 검색 할 수있는 디지털 트리 및 때로는 기수 트리 또는 접두사 트리 라고도하며, 일종의 검색 트리입니다.이 트리는 동적 집합이나 연관 배열을 저장하는 데 사용되는 정렬 된 트리 데이터 구조입니다. 보통 문자열. 이것은 쉽게 구현 될 수있는 데이터 구조 중 하나입니다. 수백만 단어로 구성된 거대한 데이터베이스가 있다고 가정 해 보겠습니다. trie를 사용하여 이러한 정보를 저장할 수 있으며 이러한 단어 검색의 복잡성은 검색하는 단어의 길이에만 의존합니다. 이는 데이터베이스가 얼마나 큰지에 달려 있지 않다는 것을 의미합니다. 그게 놀랍지 않니?

우리가 다음 단어들을 가지고 사전을 가지고 있다고 가정합시다 :

algo
algea
also
tom
to

우리는 우리가 찾고있는 단어를 쉽게 찾을 수있는 방법으로이 사전을 메모리에 저장하려고합니다. 이 방법 중 하나는 단어 사전 적 분류 - 실제 생활 사전에 단어가 저장되는 방식 -을 포함합니다. 그런 다음 이진 검색 을 수행하여 단어를 찾을 수 있습니다. 또 다른 방법은 Prefix Tree 또는 Trie를 사용하는 것입니다. 'Trie' 라는 단어는 Re trie val이라는 단어에서 유래했습니다. 여기서 접두사는 다음과 같이 정의 할 수 있습니다 문자열의 접두사를 나타냅니다 : 문자열의 처음부터 시작을 만들 수 있습니다 모든 문자열은 접두사라고합니다. 예 : 'c', 'ca', 'cat'은 모두 'cat'문자열의 접두어입니다.

이제 Trie로 돌아 가자. 이름에서 알 수 있듯이 나무를 만듭니다. 처음에는 루트가있는 빈 트리가 있습니다.

뿌리

우리는 'algo' 라는 단어를 삽입 할 것입니다. 우리는 새로운 노드를 만들고이 두 노드 사이의 가장자리를 'a'라고 명명 할 것입니다. 새 노드에서 'l' 이라는 다른 가장자리를 만들고 다른 노드와 연결합니다. 이 방법으로 'g''o'에 대해 두 개의 새 가장자리를 만듭니다. 우리는 노드에 정보를 저장하지 않는다는 것을 주목하십시오. 지금은 이러한 노드에서 새로운 가장자리를 만드는 것을 고려할 것입니다. 이제부터 'x' 라는 가장자리를 호출하자. -edge-x

알 고를 삽입하다.

이제 우리는 'algea' 라는 단어를 추가하려고합니다. 우리는 우리가 이미 갖고있는 뿌리로부터 한 모서리 가 필요합니다. 따라서 우리는 새로운면을 추가 할 필요가 없습니다. 비슷하게, 우리는 'a' 에서 'l''l' 에서 'g' 의 경계를가집니다. 그것은 'alg' 가 이미 trie 에 있음을 의미합니다. edge-eedge-a 만 추가합니다.

algea라는 단어 삽입하기

우리는 '또한' 이라는 단어를 추가 할 것입니다. 우리는 루트에서 접두어 'al' 을 가진다. 우리는 그것과 함께 'so' 만 추가 할 것입니다.

단어 삽입하기

'톰'을 추가합시다. 이번에는 이전에 생성 된 톰의 접두사가 없으므로 루트에서 새로운 가장자리를 만듭니다.

톰이라는 단어 삽입하기

이제 'to'를 어떻게 추가해야합니까? 'to' 는 완전히 'tom' 의 접두사이므로, 가장자리를 추가 할 필요가 없습니다. 우리가 할 수있는 일은, 우리는 어떤 마디에 끝 표시를 할 수 있다는 것입니다. 하나 이상의 단어가 완성 된 노드에 끝 표시를합니다. 녹색 원은 엔드 마크를 나타냅니다. trie는 다음과 같습니다.

에 단어 삽입

왜 우리가 엔드 마크를 추가했는지 쉽게 이해할 수 있습니다. 우리는 트라이에 저장된 단어를 결정할 수 있습니다. 문자는 모서리에 있고 노드에는 끝 기호가 포함됩니다.

이제 이런 단어를 저장하는 목적은 무엇입니까? 예를 들어 사전에 'alice' 라는 단어를 찾으라는 요청을받습니다. 트라이를 지나칠거야. 루트에서 에지 -a가 있는지 확인합니다. 그런 다음 'a' 에서 확인하십시오. 가장자리 가 있다면. 그 후, 당신은 어떤 가장자리도 발견하지 못할 것입니다. 그래서 당신은 alice 라는 단어가 사전에 존재하지 않는다는 결론에 도달 할 수 있습니다.

사전에서 'alg' 라는 단어를 찾으라는 요청을 받으면 루트 -> a , > l , l - > g를 지나 가게 되지만 끝에는 녹색 노드가 없습니다. 그래서 단어는 사전에 존재하지 않습니다. '톰' 을 검색하면 녹색 노드가 표시됩니다. 즉, 단어가 사전에 있음을 의미합니다.

복잡성:

트라이 에서 단어를 검색하는 데 필요한 최대 단계는 우리가 찾고있는 단어의 길이입니다. 복잡성은 O (길이) 입니다. 삽입의 복잡성은 동일합니다. trie 를 구현하는 데 필요한 메모리 양은 구현에 따라 다릅니다. 우리는 10 개의 6 개의 문자 (단어, 문자가 아닌)를 트라이에 저장할 수있는 다른 예제를 구현할 것이다.

Trie의 사용 :

  • 사전에 단어를 삽입, 삭제 및 검색합니다.
  • 문자열이 다른 문자열의 접두사인지 확인하려면 다음을 수행하십시오.
  • 공통 접두어를 가진 문자열의 수를 확인합니다.
  • 우리가 입력하는 접두어에 따라 전화에서 연락처 이름을 제안하십시오.
  • 두 문자열의 'Longest Common Substring'찾기.
  • 'Longest Common Ancestor'를 사용하여 두 단어에 대한 '공통 접두어'길이 찾기

Trie의 구현

이 예를 읽기 전에 먼저 Trie 소개를 읽는 것이 좋습니다.

Trie 를 구현하는 가장 쉬운 방법 중 하나는 연결된 목록을 사용하는 것입니다.

마디:

노드는 다음으로 구성됩니다.

  1. 엔드 마크 용 변수.
  2. 포인터를 다음 노드로 이동합니다.

End-Mark 변수는 단순히 종점인지 아닌지를 나타냅니다. 포인터 배열은 만들 수있는 모든 가능한 모서리를 나타냅니다. 영어 알파벳의 경우 배열의 크기는 26이며 단일 노드에서 최대 26 개의 모서리를 만들 수 있습니다. 맨 처음에 포인터 배열의 각 값은 NULL이되고 끝 변수는 false가됩니다.

Node:
Boolean Endmark
Node *next[26]
Node()
    endmark = false
    for i from 0 to 25
        next[i] := NULL
    endfor
endNode

next [] 배열의 모든 요소는 다른 노드를 가리 킵니다. next [0]edge-a를 공유하는 노드를 가리키고, next [1]edge-b를 공유하는 노드를 가리 킵니다. 우리는 Node의 생성자를 Endmark를 false로 초기화하도록 정의하고 next [] 포인터 배열의 모든 값에 NULL을 넣습니다.

Trie 를 만들려면 먼저 루트 를 인스턴스화해야 합니다 . 그런 다음 루트 에서 정보를 저장할 다른 노드를 만듭니다.

삽입:

Procedure Insert(S, root):    // s is the string that needs to be inserted in our dictionary
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        curr -> next[id] = Node()
    curr := curr -> next[id]
endfor
curr -> endmark = true

여기 우리는 az 와 함께 일하고 있습니다. 따라서 ASCII 값을 0-25 로 변환하려면 ASCII 값인 'a' 를 빼십시오. 현재 노드 (curr)가 현재 캐릭터의 가장자리를 가지고 있는지 확인합니다. 그럴 경우 새 노드를 만들지 않으면 그 가장자리를 사용하여 다음 노드로 이동합니다. 마지막으로 endmark를 true로 변경합니다.

수색:

Procedure Search(S, root)      // S is the string we are searching
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        Return false
    curr := curr -> id
Return curr -> endmark

과정은 삽입과 유사합니다. 결국 엔 드 마크를 반환합니다. 따라서 엔드 마크 가 참이면 사전에 단어가 있음을 의미합니다. 거짓이면 단어가 사전에 없습니다.

이것은 우리의 주요 구현이었다. 이제 trie에 단어를 삽입하고 검색 할 수 있습니다.

삭제:

때로는 더 이상 메모리를 절약하는 데 사용되지 않는 단어를 지워야합니다. 이를 위해 사용하지 않은 단어는 삭제해야합니다.

Procedure Delete(curr):       //curr represents the current node to be deleted
for i from 0 to 25
    if curr -> next[i] is not equal to NULL
        delete(curr -> next[i])
    delete(curr)               //free the memory the pointer is pointing to

이 함수는 curr의 모든 자식 노드로 가서 삭제하고, curr 을 삭제하여 메모리를 비운다 . delete (root)를 호출하면 전체 Trie 가 삭제됩니다.

Trie배열을 사용하여 구현할 수도 있습니다.



Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow