プレフィックスツリーとプレフィックストライの解説 - tanakakenji/Rinko GitHub Wiki

プレフィックスツリーとプレフィックストライの解説

1. 基本的な理解

プレフィックスツリーとプレフィックストライは、実際には同じデータ構造を指す異なる名称です。これらは以下のように呼ばれることがあります：

  • プレフィックスツリー (Prefix Tree)
  • プレフィックストライ (Prefix Trie)
  • トライ (Trie)
  • デジタルツリー (Digital Tree)
  • 基数木 (Radix Tree)

2. 構造の特徴

この構造の主な特徴は以下の通りです：

  • 文字列や配列などの順序付けられたデータを格納するための木構造
  • 各ノードは文字（または数字などの要素）を表す
  • 共通の接頭辞（プレフィックス）を持つ文字列は同じパスを共有する
  • ルートから特定のパスをたどることで、完全な文字列を表現する

3. 「ツリー」と「トライ」の語源

  • 「ツリー（Tree）」：一般的な木構造を指す用語
  • 「トライ（Trie）」：検索（retrieve）の中間部分「trie」から派生した造語

4. 名称の使い分け

  • 「プレフィックスツリー」：構造の視覚的な特徴（木のように分岐する）を強調
  • 「プレフィックストライ」：データ検索の効率性を強調

5. 主な用途

  • 文字列の効率的な格納と検索
  • 接頭辞マッチング
  • 自動補完機能の実装
  • 辞書やスペルチェッカーの実装
  • IPルーティングテーブルの管理

6. 利点

  • 文字列の長さ（m）に比例するO(m)の検索時間複雑度
  • 共通接頭辞の共有によるメモリ効率
  • 接頭辞検索の高速性

7. 欠点

  • 大きな文字セットを扱う場合のメモリ消費
  • 単一の文字列を格納する場合の非効率性

8. 実装例（疑似コード）

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

クラス定義

TrieNodeクラス

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

このクラスはTrie内の単一のノードを表します。

  • self.children: 子ノードを格納する辞書です。キーは文字、値はTrieNodeオブジェクトです。
  • is_end_of_word: このノードが単語の終端を表すかどうかを示すブール値のフラグです。

Trieクラス

class Trie:
    def __init__(self):
        self.root = TrieNode()

このクラスはTrie構造全体を表します。

  • self.root: Trieのルートノードです。これは空のTrieNodeで、全ての挿入と検索の開始点となります。

メソッド

insertメソッド

def insert(self, word):
    node = self.root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.is_end_of_word = True

このメソッドは新しい単語をTrieに挿入します。

  1. ルートノードから開始します。
  2. 単語の各文字について：
    • その文字が現在のノードの子として存在しない場合、新しいTrieNodeを作成します。
    • その文字に対応する子ノードに移動します。
  3. 全ての文字を処理した後、最後のノードを単語の終端としてマークします。

例：「cat」を挿入する場合

  • ルートの下に「cat」のノードが存在しなければ作成
  • 「cat」ノードをis_end_of_word=Trueとしてマーク

searchメソッド

def search(self, word):
    node = self.root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end_of_word

このメソッドはTrieから単語を検索します。

  1. ルートノードから開始します。
  2. 単語の各文字について：
    • その文字が現在のノードの子として存在しない場合、その単語はTrie内に存在しません。Falseを返します。
    • 存在する場合、その文字に対応する子ノードに移動します。
  3. 全ての文字を処理した後、最後のノードが単語の終端としてマークされているかチェックします。
    • マークされている場合、その単語はTrie内に存在します。Trueを返します。
    • マークされていない場合、この文字列はより長い単語の接頭辞であり、完全な単語ではありません。Falseを返します。

例：「cat」を検索する場合

  • ルートの下に「cat」を探す
  • 「cat」ノードがis_end_of_word=Trueかチェック

時間複雑度と空間複雑度

  • 挿入：O(m)の時間複雑度。mは単語の長さ。
  • 検索：O(m)の時間複雑度。mは単語の長さ。
  • 空間：最悪の場合O(n*m)。nは単語数、mは平均単語長。

このTrie実装は接頭辞ベースの操作に効率的で、接頭辞検索や自動補完機能などの追加メソッドで拡張できます。

まとめ

プレフィックスツリーとプレフィックストライは同じデータ構造を指す異なる名称です。この構造は文字列の効率的な格納と検索に特化しており、特に接頭辞を共有する多数の文字列を扱う場合に強力です。用語の選択は文脈や強調したい特性によって異なる場合がありますが、基本的な概念と実装は同じです。