辞書ツリーTrie構造とPythonコードの詳細解

辞書ツリー（Trie）は、いくつかの文字列->値の対応関係を保持してもよい。基本的には、JavaのHashMap機能と同じkey-valueマッピングですが、Trieのkeyは文字列だけです。
Trieの強みは時間の複雑さにある。その挿入および照会時間の複雑さはいずれもO（k）であり、ここではkはkeyの長さであり、Trieに保存されたいくつかの要素とは無関係である。Hash表はO（1）と呼ばれていますが、hashを計算する時は必ずO（k）であり、しかも衝突などの問題があります。Trieの欠点は空間消費が高いことです。
Trieツリーの実現については、配列を使ってもいいし、ポインタを使って動的に分配してもいいです。私は問題をする時、配列を使いやすくするために、静的に空間を割り当てました。
Trieツリーは、単語検索ツリーまたは結合ツリーとも呼ばれ、ツリー構造であり、ハッシュツリーの変種である。典型的なアプリケーションは、大量の文字列を統計して並べ替えるためのものです。ただし、文字列に限らず、検索エンジンシステムはしばしばテキストの語彙統計に用いられます。無意味な文字列比較を最大限に低減し、ハッシュ・テーブルよりもクエリ効率が高いという利点がある。
Trieの核心思想は空間交換時間である。文字列の共通プレフィックスを使用して、クエリ時間のオーバーヘッドを低減し、効率を向上させる目的を達成する。
Trieツリーの各単語は、character by character方法によって記憶され、同じプレフィックス単語はプレフィックスノードを共有する。
上の木にはto/tea/ted/ten/innという言葉があります。
Trieツリーの基本的な性質は、以下に要約することができる。
（1）ルートノードは文字を含まず、ルートノード以外の各ノードは1文字のみを含む。
（2）ルートノードからあるノードに経路上を通る文字が接続され、ノードに対応する文字列である。
（3）各ノードのすべてのサブノードに含まれる文字列は異なる。
性質
（1）ルートノードは文字を含まず、ルートノード以外の各ノードは1文字のみを含む。
（2）ルートノードからあるノードに経路上を通る文字が接続され、ノードに対応する文字列である。
（3）各ノードのすべてのサブノードに含まれる文字列は異なる。
基本的な考え方(アルファベットの木を例に):
1、挿入プロセス
単語については、ルートから単語の各アルファベットに対応するツリー内のノード分岐に沿って下に進み、単語が巡回されるまで最後のノードを赤色としてマークし、その単語がTrieツリーに挿入されたことを示す。
2、照会プロセス
同様に、ルートから単語のアルファベット順に下にtrieツリーを巡回し、あるノードマークが存在しない、または単語が巡回していると発見された後、最後のノードが赤色でマークされていないということは、単語が存在しないということを表し、最後のノードが赤色である場合、単語の存在を表している。
適用
（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