1. はじめに
この記事では、文字列検索に使われるデータ構造の一つである トライ木について説明する。
トライ木は、共通する接頭辞（prefix）を持つ文字列を効率的に検索するデータ構造であり、次のような特徴を持つ。
- 一つのノードが一つの文字を表す
- 共通する文字列（接頭辞）はできる限りノードを共有する
この仕組みにより、単語の検索・追加・部分一致検索を文字数に比例する時間 $O(L)$ の時間計算量で行うことができる。
2. トライ木とは
2.1. トライ木の構築
トライ木は、複数の文字列が共通して持つ部分をまとめて管理する木構造である。
例として、次の3つの単語を考える。
cat
car
dog
この3つの単語について、トライ木を構築すると次のような図になる。単語の終端には is_end フラッグを設定する。これは、そのノードが単語の終わりを示すかどうかを判定するためのフラッグである。
cat, car の2つの単語は、ca という単語を共有しているため、トライ木では c → a までのノードを一度だけ作り、そこから t と r に枝分かれして管理している。
このように、共通接頭辞を1度だけ保存することで、文字列検索を効率的に行えるというのが、トライ木の基本的な考え方である。
2.2. トライ木を使った探索
前節では、トライ木の構築について説明をした。
ここでは、トライ木を使って「特定の文字列が登録済みかどうか」を調べる方法を説明する。
探索の対象は次の3つの文字列とする。
car
ca
doggy
2.2.1. 単語 car の探索
はじめに、car について考える。
まず root から c という枝が存在するかを確認する。c は存在するため、root から c へと進む。
次に c から a という枝が存在するかを確認する。これも存在するため、c から a へと進む。
同様に、a の下に r が存在するかを確認する。r は存在するため、a から r の枝へと進む。
さいごに、r ノードは単語の終端（is_end）として登録されているため、car はトライ木に登録されている単語であるということがわかる。
2.2.2. 単語 ca の探索
つぎに、ca について考える。
探索の手順は car の場合と同じく、root から順番に枝をたどる。car と ca を共有しているので、a まで進む。
ここで、探索は終わるが、a のノードには単語の終端を示すフラッグである is_end が設定されていない。
したがって、ca は途中まで一致しているものの、単語としては登録されていないことがわかる。
2.2.3. 単語 doggy の探索
doggy も同様の手順で探索を行う。
dog まで探索を終えた時点で、トライ木は終端を示すフラッグが存在するが、単語の探索は終えていない。
したがって、doggy も途中まで一致しているものの、単語としては登録されていないことがわかる。
3. トライ木の実装
ここでは、トライ木の実装をPythonを用いて行う。
トライ木は次の2つのクラスによって構成される。
-
Nodeクラス：各ノード（1文字）を示す -
Trieクラス：木全体を表し、単語の登録（insert）や探索（search）を行う
3.1. Node クラスの実装
Node クラスは次の2つのプロパティを持つ
-
children：ノードの配下に続く文字を連想配列で保存する -
is_end：単語の終端を示す
children は連想配列で作成することで、文字の探索を時間計算量$O(1)$で行うことができる。
実装は次の通り。
class Node:
def __init__(self):
self.children = {}
self.is_end = False
3.2. Trie クラスの実装
Trie クラスは次の1つのプロパティと、2つのメソッドを持つ。
プロパティ
-
root：トライ木のスタート地点を示す
メソッド
-
insert(word)：トライ木に文字を登録する -
search(word)：トライ木に単語が含まれているかどうかを調べる
以下に実装を示す。
class Trie:
def __init__(self):
self.root = Node() # トライ木のスタート地点
def insert(self, word: str) -> None:
node = self.root
for ch in word:
# ノードが存在しなければ新しく作成
if ch not in node.children:
node.children[ch] = Node()
node = node.children[ch]
# 単語の終端をマーク
node.is_end = True
def search(self, word: str) -> bool:
node = self.root
for ch in word:
# 枝が存在しない場合は未登録
if ch not in node.children:
return False
node = node.children[ch]
# 経路が存在し、かつ終端マークがある場合のみ True
return node.is_end
3.3. 動作確認（テストケース）
トライ木の動作確認に次のテストケースを使用した。
def test_trie_basic():
trie = Trie()
words = ["cat", "car", "dog", "door", "doll"]
# 単語を登録
for w in words:
trie.insert(w)
# 存在する単語の検索
assert trie.search("cat") == True
assert trie.search("dog") == True
assert trie.search("door") == True
# 未登録の単語
assert trie.search("cow") == False
assert trie.search("do") == False # prefixのみ
# 共通接頭辞を持つ単語の確認
assert trie.search("doll") == True
assert trie.search("dollar") == False # 末端ノードの延長
print("All basic Trie tests passed!")
コードの全体は次のようになる。
class Node:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = Node() # トライ木のスタート地点
def insert(self, word: str) -> None:
node = self.root
for ch in word:
# ノードが存在しなければ新しく作成
if ch not in node.children:
node.children[ch] = Node()
node = node.children[ch]
# 単語の終端をマーク
node.is_end = True
def search(self, word: str) -> bool:
node = self.root
for ch in word:
# 枝が存在しない場合は未登録
if ch not in node.children:
return False
node = node.children[ch]
# 経路が存在し、かつ終端マークがある場合のみ True
return node.is_end
def test_trie_basic():
trie = Trie()
words = ["cat", "car", "dog", "door", "doll"]
# 単語を登録
for w in words:
trie.insert(w)
# 存在する単語の検索
assert trie.search("cat") == True
assert trie.search("dog") == True
assert trie.search("door") == True
# 未登録の単語
assert trie.search("cow") == False
assert trie.search("do") == False # prefixのみ
# 共通接頭辞を持つ単語の確認
assert trie.search("doll") == True
assert trie.search("dollar") == False # 末端ノードの延長
print("All basic Trie tests passed!")
test_trie_basic()
実行した結果は次の通り。
All basic Trie tests passed!
トライ木は正しく実装されたことが示された。
4. まとめ
トライ木は、文字列を共通部分でまとめることで、高速に検索できるデータ構造である。今回は最小限の insert と search の実装を通して、その仕組みを説明した。