トライデータ構造は、情報検索の際に非常に効率的です。
主に辞書や電話帳の実装に利用されている。
また、キーボードで入力中に表示される自動テキストサジェストを実装するのにも便利です。
この記事では、Pythonで独自のTrieデータ構造を実装する方法を理解します。
この記事では、以下のことを学びます。
- トライデータ構造を実装する方法。
- トライデータ構造への挿入の仕方。
- Trieデータ構造内の単語を検索する方法。
この記事もチェック：PythonでMax Heapデータ構造を実装する方法
TrieNode クラスの実装
まず、TrieNode クラスのコードを書きましょう。
各トライ・ノードは以下のフィールドを持つ必要があります。
- 文字
- 子ノードのリスト
- 単語がそのノードで終わっているかどうかを示すブール値。
では、TrieNodeクラスのコードを書いてみましょう。
class TrieNode:
def __init__(self, char):
self.char = char
self.is_end = False
self.children = {}
|
TrieNodeを初期化するときに、文字を提供する必要がある。
.is_end は、単語が現在のノードで終わるかどうかを示す。
デフォルトではfalseに設定されている。
Trieデータ構造クラスの作成
Trie クラスのコードを書くことに移りましょう。
トライを初期化するためには、トライノードを初期化し、トライの挿入と検索のためのメソッドを提供する必要があります。
class Trie(object):
def __init__(self):
self.root = TrieNode("")
|
このパートでは、空の TrieNode を初期化することを担当します。
TrieにInsertionを行うには？
Trieデータ構造で挿入がどのように行われるかを見てみましょう。
挿入を行うには、挿入する単語を一文字ずつたどる必要があります。
同時に、ルートからトライを下降させ、子リストにその文字があるかどうかを確認する必要があります。
その文字がない場合は、その文字を含む新しいTrieNodeを作成し、childrenのリストに追加する必要があります。
単語の最後に到達したら、単語の最後の文字に対応するノードのis_endをtrueに設定する必要があります。
以下は、上記のアプローチの実装です。
def insert(self, word):
node = self.root
#traverse the word character by character for char in word:
#check if the character is there in the list of children if char in node.children:
node = node.children[char]
else:
# else make a new TrieNode corresponding to that character new_node = TrieNode(char)
# add the new node to the list of children node.children[char] = new_node
node = new_node
#after traversig the word set .is_end to true for the last #char node.is_end = True
|
これで、すべての挿入を行うことができる。
以下の単語を持つトライを考えてみましょう。
- Here
- Hear
- 彼女
- He
- こんにちは
- どのように
これらの単語に対応するトライは、次のようになります。
def dfs(self, node, pre):
if node.is_end:
self.output.append((pre + node.char))
for child in node.children.values():
self.dfs(child, pre + node.char)
|
ここで、緑色のノードは、そのノードに対して is_end が真であることに対応します。
トリーの検索方法は？
それでは、Trieでどのように単語を検索するか見てみましょう。
検索する際に完全一致を求めるわけではありません。
むしろ、検索する文字列で始まる単語のリストを取得することが目的です。
検索時には接頭辞のみを指定し、検索機能はその接頭辞で始まるすべての単語を返せるようにしなければなりません。
たとえば、”He “を検索すると、次のような単語が得られるはずです。
- He
- Here
- Hear
- 彼女
- こんにちは
これらは、”He “から始まる単語です。
このようにトライはキーボードのオートコンプリートを実現するのに有効です。
単語を検索する際には、DFS方式で検索を行う。
そこで、トライの中でDFS検索を行うための関数を記述する必要がある。
def search(self, x):
node = self.root
# traverse the search query and move down the trie for char in x:
if char in node.children:
node = node.children[char]
else:
#if query doesn't match the nodes in trie
return []
self.output = []
#call DFS self.dfs(node, x[:-1])
return self.output
|
この関数を呼び出す際には、ノードとこれまでに検索された接頭辞を渡す必要がある。
検索結果で isanium_end が真であるノードに到達すると、その単語を出力リストに追加します。
そうでなければ、DFS方式で子ノードを検索し続ける。
検索関数は以下の通りです。
class TrieNode:
def __init__(self, char):
self.char = char
self.is_end = False
self.children = {}
class Trie(object):
def __init__(self):
self.root = TrieNode("")
def insert(self, word):
node = self.root
for char in word:
if char in node.children:
node = node.children[char]
else:
new_node = TrieNode(char)
node.children[char] = new_node
node = new_node
node.is_end = True
def dfs(self, node, pre):
if node.is_end:
self.output.append((pre + node.char))
for child in node.children.values():
self.dfs(child, pre + node.char)
def search(self, x):
node = self.root
for char in x:
if char in node.children:
node = node.children[char]
else:
return []
self.output = []
self.dfs(node, x[:-1])
return self.output
|
検索中は、検索クエリを走査し、同時にトライを下降させる。
そして、クエリの最後の文字に対応するノードでDFSを呼び出す。
DFS関数はこの最後の文字から下へ移動し、すべての完全な単語を出力リストに追加します。
コンプリートコード
このチュートリアルの完全なコードは、以下のとおりです。
tr = Trie()
tr.insert("here")
tr.insert("hear")
tr.insert("he")
tr.insert("hello")
tr.insert("how ")
tr.insert("her")
|
Trie in Action
トライにいくつかの単語を追加して、検索クエリを作ってみましょう。
tr.search("he")
|
これはトライを作り、そこにこれら5つの単語を追加します。
次に、次の行を使って検索クエリを作成します。
['he', 'her', 'here', 'hear', 'hello'] |
結果は以下の通りです。
tr.search("her")
|
別のクエリを作ってみましょう。
['her', 'here'] |
結果は以下の通りです。
まとめ
この記事では、Python による Trie データ構造の実装を学びました。
Trie クラスの作成方法、挿入の実行方法、Trie 内の単語の問い合わせ方法について学びました。