Trie 데이터 구조의 간단한 구현.

Trie는 세트 내에서 특정 키를 찾는 데 사용되는 트리 데이터 구조인 k-ary 검색 트리 유형입니다.

Trie는 중첩된 사전으로 구현됩니다. 중첩을 위해 새 임시 사전을 삽입할 때마다 생성되며 Trie는 사전의 사전입니다. Trie는 4개의 빌딩 블록이 있는 데이터 구조로 식별할 수 있습니다.

트라이 빌딩 블록의 구성 요소는 다음과 같습니다.

make_trie.make_trie.

입력: 단어 목록
출력: 트라이
프로세스: 사전의 맨 위를 만들고 각 단어에 대해 사전에 add_word를 호출합니다.

add_word

입력: 시도와 추가할 단어.
출력: 단어가 추가된 중첩 사전.
프로세스: 매개변수에서 사전의 사본을 작성하십시오. 단어의 각 문자에 대해 값 사전을 가져오거나 새 값 사전을 작성하여 추가로 중첩하십시오. 단어 추가의 끝을 나타내는 마커를 추가합니다.

is_word

입력: 시도 및 테스트할 단어
출력: 단어가 사전에 있으면 참입니다.
프로세스: 복사본으로 작업하여 단어가 끝날 때까지 중첩을 유지합니다. 문자를 찾을 수 없으면 False를 반환합니다. 마지막으로 단어의 끝에는 "end_marker"키가 있어야 합니다.

is_prefix

입력: 시도 및 테스트할 단어
출력: 단어가 접두사이면 참
프로세스: is_word와 동일하며 모든 문자가 존재해야 하지만 단어 순회를 완료할 때 end_marker가 존재할 필요가 없습니다.

Python을 사용하여 Trie를 빌드합니다.

import json

_end_marker = "*"

def add_word(trie, word):
    word_trie = trie

    for ch in word:
        if ch in word_trie:
            word_trie = word_trie[ch]
        else:
            word_trie[ch] = {}
            word_trie = word_trie[ch]

    word_trie[_end_marker] = _end_marker

    return word_trie

def make_trie(*words):
    trie = dict()

    for word in words:
        add_word(trie, word)

    return trie

def is_word(trie, word):
    word_trie = trie
    for ch in word:
        if ch in word_trie:
            word_trie = word_trie[ch]
        else:
            return False
    return _end_marker in word_trie

def is_prefix(trie, word):
    word_trie = trie
    for ch in word:
        if ch in word_trie:
            word_trie = word_trie[ch]
        else:
            return False

    return True

def print_trie(trie):
    print(json.dumps(trie, sort_keys=True, indent=2))

trie = make_trie("hi", "hello", "help")

print_trie(trie)

print(is_word(trie, "hello"))
print(is_word(trie, "he"))
print(is_prefix(trie, "he"))

산출



다음은 "hi", "help"및 "hello"가 trie에 삽입될 때 상태를 이해하는 데 도움이 되는 시각화입니다. ""는 종료 단어 마커이므로 hi와 help 다음에 포인터가 ""로 이어지지만 문자 h, e, l은 더 확장되어 "hello"를 만듭니다.