Pythonコードを使った辞書ツリーTrieの実装構造テクニックを詳しく解説

辞書ツリー (Trie) は、文字列と値の対応関係を保存できます。基本的には、Java の HashMap と同じ機能 (キーと値のマッピング) を持ちますが、Trie のキーは文字列のみである点が異なります。

Trie の力はその時間の複雑さにあります。 Trie に保存される要素の数に関係なく、挿入時間とクエリ時間の複雑さは両方とも O(k) です。ここで、k はキーの長さです。ハッシュ テーブルは O(1) であると主張されていますが、ハッシュを計算すると間違いなく O(k) になり、衝突などの問題もあります。Trie の欠点は非常に多くのスペースを消費することです。
トライツリーの実装に関しては、配列を使用することも、ポインタを動的に割り当てることもできます。私が質問したときは、便宜上、静的に領域を割り当てるために配列を使用しました。
単語検索ツリーまたはキー ツリーとも呼ばれるトライ ツリーは、ツリー構造であり、ハッシュ ツリーの変形です。一般的なアプリケーションは、多数の文字列 (文字列に限定されません) を数えたり並べ替えたりするためのもので、テキスト ワードの頻度統計のために検索エンジン システムでよく使用されます。その利点は、不必要な文字列比較を最小限に抑え、ハッシュ テーブルよりもクエリ効率が高いことです。
Trie の核となるアイデアは、空間を時間と交換することです。文字列の共通プレフィックスを使用してクエリ時間のオーバーヘッドを削減し、効率を向上させます。
Trie ツリー内の各単語は文字ごとの方法で保存され、同じ接頭辞を持つ単語は接頭辞ノードを共有します。
上記のツリーは、/tea/ted/ten/ に保存されていることがわかります。

トライ木の基本的な性質は次のように要約できます:
(1) ルートノードには文字が含まれません。ルートノードを除き、各ノードには 1 つの文字しか含まれません。
(2) ルートノードからあるノードまで、パスを通る文字を繋いでノードに対応する文字列を形成します。
(3) 各ノードのすべての子ノードには異なる文字列が含まれます。

プロパティ
(1) ルートノードには文字が含まれず、ルートノードを除く各ノードには文字が 1 つだけ含まれます。
(2) ルートノードからあるノードまで、パスを通る文字を繋いでノードに対応する文字列を形成します。
(3) 各ノードのすべての子ノードには異なる文字列が含まれます。

基本的な考え方 (文字ツリーを例にします):
1. 挿入プロセス
単語の場合、ルートから開始して、単語の各文字に対応するツリーのノードの枝に沿って単語が現れるまで下に進みます。を通過した場合、最後のノードを赤でマークします。これは、単語がトライ ツリーに挿入されたことを示します。
2. クエリ処理
同様に、ノードマークが存在しない、またはワードトラバースが完了して最後のノードがマークされていないことが判明したら、トライ木をルートから単語のアルファベット順に下方向にトラバースします。赤は単語が存在しないことを意味します。最後のノードが赤でマークされている場合は、単語が存在することを意味します。

アプリケーション
(1) 単語頻度統計
ハッシュを直接使用するよりもスペースを節約
(2) 検索プロンプト
プレフィックスを入力すると、形成可能な単語をプロンプト表示
(3) 補助構造として接尾辞ツリーなどの
、AC オートマトンなどの補助構造

実装
Python にはポインターがありませんが、入れ子になった辞書を使用してツリー構造を実装できます。非 ASCII 単語については、挿入と挿入に Unicode エンコーディングが使用されます。 search.

#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

More Pythonコードを使った辞書ツリートライの実装構造手法の詳しい解説は、PHP中国語サイトの関連記事に注目してください！