Python 코드를 사용하여 사전 트리 Trie를 구현하는 구조적 기술에 대한 자세한 설명

사전 트리(Trie)는 일부 문자열->값 대응을 저장할 수 있습니다. 기본적으로 Trie의 키는 문자열만 될 수 있다는 점을 제외하면 키-값 매핑인 Java의 HashMap과 동일한 기능을 가지고 있습니다.

Trie의 힘은 시간 복잡도에 있습니다. 삽입 및 쿼리 시간 복잡도는 모두 O(k)입니다. 여기서 k는 Trie에 저장된 요소 수에 관계없이 키의 길이입니다. Hash 테이블은 O(1)이라고 주장하지만, Hash를 계산하면 반드시 O(k)가 되며, 충돌 등의 문제도 있습니다. Trie의 단점은 매우 높은 공간을 소비한다는 것입니다.
Trie 트리 구현에 관해서는 배열을 사용하거나 포인터를 동적으로 할당할 수 있습니다. 제가 질문할 때는 편의상 배열을 사용하고 공간을 정적으로 할당했습니다.
단어 검색 트리 또는 키 트리라고도 알려진 트리 트리는 트리 구조이며 해시 트리의 변형입니다. 일반적인 응용 프로그램은 많은 수의 문자열(문자열에 국한되지 않음)을 계산하고 정렬하는 데 사용되므로 검색 엔진 시스템에서 텍스트 단어 빈도 통계를 위해 자주 사용됩니다. 장점은 불필요한 문자열 비교를 최소화하고 해시 테이블보다 쿼리 효율성이 높다는 것입니다.
Trie의 핵심 아이디어는 공간과 시간을 교환하는 것입니다. 문자열의 공통 접두사를 사용하면 쿼리 시간 오버헤드를 줄여 효율성을 높일 수 있습니다.
Trie 트리의 각 단어는 문자별 방식으로 저장되며, 동일한 접두사를 가진 단어는 접두사 노드를 공유합니다.
위의 트리는 to/tea/ted에 저장되는 것을 볼 수 있습니다. /ten/inn 이 단어는

Trie 트리의 기본 속성은 다음과 같이 요약됩니다.
(1) 루트 노드에는 루트 노드를 제외하고는 문자가 포함되지 않습니다. 각 노드에는 하나의 문자만 포함됩니다.
(2) 루트 노드부터 특정 노드까지 경로를 통과하는 문자들이 연결되어 해당 노드에 해당하는 문자열을 형성합니다.
(3) 각 노드의 모든 하위 노드에는 서로 다른 문자열이 포함됩니다.

속성
(1) 루트 노드에는 문자가 포함되지 않으며, 루트 노드를 제외한 각 노드에는 문자가 하나만 포함됩니다.
(2) 루트 노드부터 특정 노드까지 경로를 통과하는 문자들이 연결되어 해당 노드에 해당하는 문자열을 형성합니다.
(3) 각 노드의 모든 하위 노드에는 서로 다른 문자열이 포함됩니다.

기본 아이디어(문자 트리를 예로 들어):
1. 삽입 과정
단어는 루트에서 시작하여 각 문자에 해당하는 트리를 따릅니다. 단어 분기는 단어가 횡단될 때까지 아래쪽으로 이동하고 마지막 노드는 빨간색으로 표시되어 해당 단어가 Trie 트리에 삽입되었음을 나타냅니다.
2. 쿼리 과정
마찬가지로 루트부터 단어의 알파벳순으로 아래쪽으로 순회합니다. 노드 마크가 존재하지 않거나 단어 순회가 완료됩니다. 하지만 마지막 노드는 그렇지 않습니다. 빨간색으로 표시되면 해당 단어가 존재하지 않는다는 의미입니다. 마지막 노드가 빨간색으로 표시되면 해당 단어가 존재한다는 의미입니다.

응용 프로그램
(1) 단어 빈도 통계
해시를 직접 사용하는 것보다 공간을 절약합니다
(2) 검색 프롬프트
접두사 프롬프트가 표시되면
(3)을 형성할 수 있는 단어가 접미사 트리, AC 오토마타 등과 같은 보조 구조
로 구현됩니다.

>그러나 Python에는 포인터가 없으며 중첩된 사전을 사용하여 ASCII가 아닌 단어의 경우 삽입 및 검색에 유니코드 인코딩이 사용됩니다.

#coding=utf-8 
class Trie: 
  root = {} 
  END = '/' 
  def add(self, word): 
    #从根节点遍历单词,char by char,如果不存在则新增,最后加上一个单词结束标志 
    node = self.root 
    for c in word: 
      node=node.setdefault(c,{}) 
    node[self.END] = None 
 
  def find(self, word): 
    node = self.root 
    for c in word: 
      if c not in node: 
        return False 
      node = node[c] 
    return self.END in node

Python의 자세한 설명은 다음과 같습니다. 사전 트리 Trie 구조 기술의 코드 구현에 관한 관련 기사는 PHP 중국어 웹사이트를 주목하세요!