メディアチームトライ木で高速な辞書を作ってみた！
メディアチームIT技術
トライ木で高速な辞書を作りたい！
トライ木（英: trie）というデータ構造を知ってますか？
トライ木はテキストを扱う際に良く用いられているデータ構造で、文字列を非常に高速に検索することができるため、辞書の実装などに利用されています。
本記事では、トライ木の特徴の紹介と構築方法の解説・実装を行っていきます。
最終的に単語とその読み方を入力としたトライ木を構築し、単語を入力することでその読み方を出力する辞書システムを作成します。
トライ木とは
トライ木とは、上の図のようなデータ構造で、順序付き木の一つです。
この図は、例として「a」「ab」「abc」「ac」「bc」という5単語が入ったトライ木です。
ノードの左上の数字は、ノードidを表します。
id0のノードの <s> というのは先頭文字を表していて、検索の際はここからスタートします。
丸が二重になっているノードは、そのノードが単語の終端文字を表していることを示します。
検索の際は、先頭ノードから入力文字に対応するエッジをたどります。
手順
例えば、「ab」という単語を検索する際には、以下のような手順をたどります。
| 1 | 先頭ノードからでているエッジに「ab」の1文字めである「a」があるかを探す |
| 2 | ノード1に伸びるエッジが「a」なので、ノード1に遷移 |
| 3 | ノード1のエッジに「ab」の2文字目である「b」があるかを探す |
| 4 | ノード3に伸びるエッジが「b」なので、ノード2に遷移 |
| 5 | 入力文字が最後まで行ったので現在のノードが終端文字を表すノードか確認 |
| 6 | ノード3は終端文字を表すノードなので辞書に「ab」が存在することがわかる |
トライ木の特徴
トライ木には、以下のような特徴があります。
検索が高速[計算量O(M)]で、構築が高速[単語1つにつきO(L)]
検索が高速という点は、トライ木を用いる際の最も大きな利点といえるでしょう。
検索単語の長さがMのとき、計算量はO(M)となります。
これは辞書に格納されている単語数によらず、検索単語の長さにのみ比例した時間で検索できることを表しています。
つまり、数百万単語(あるいは数億、数兆)の中から「トライ木」という単語を抜き出してくる処理を、2単語の中から「トライ木」という単語を抜き出す処理と同じくらい高速にできるということです。
同様に、構築の際も長さLの1単語を挿入するのにかかる計算量はO(L)となり、辞書の大きさによらず、挿入単語の長さに比例した時間で挿入できます。
一度の探索でキーのprefixの検索もできる
一度の探索でキーのprefixの検索もできるというのもトライ木特有の優れた点です。
例えば、「情報処理技術者」という単語を検索することを考えます。
このとき、辞書には「情報」「情報処理」「情報処理技術」という3つの単語も登録されていたとします。
この辞書がトライ木で実装されていたとしたら、「情報処理技術者」という単語を検索する1回の処理で、他の3単語の情報も得ることができます。
この特徴は、日本語の形態素解析をする際に非常によく利用されています。
また、オートコンプリートシステムの構築にも用いることができます。
サイズが大きくなることがある
次は、欠点です。
トライ木においては、登録されている単語によっては、サイズが大きくなることがあります。
そのため、なるべくサイズが小さくなるような実装方法や工夫が研究されています。
トライ木の実装方法
トライ木には、LOUDSやダブルアレイなどの様々な実装方法があります。
しかし、今回は(おそらく)最も素直で単純な実装である配列を用いた実装を行います。
この実装では、1つのノードを1つの配列として表現します。
図で表すと
次の図は、先ほど例として示した図を配列表現したものです。
| 各行 | 各ノードを表す |
| WORDの列 | 格納される単語を表す |
| abc...zの列 | どの文字でどのノードに遷移するか、つまり木の表現におけるエッジを表す |
| ENDの列 | そのノードが単語の終端文字であるかどうか、木の表現における二重丸かどうかを表す |
検索を行う際のノードの巡り方
実際に検索を行う際のノードの巡り方の例は以下の図のようになります。
図の、木の表現と列の表現の赤い矢印は、同じ「ab」という単語を検索した際のノードの巡り方を示しています。
トライ木の実装(準備)
それでは、いよいよ実際にトライ木を実装し、辞書システムを作っていきましょう！
今回の言語は、Python（パイソン）を用いたいと思います。
要件
要件は以下のようなものです。
- 単語とその読み方のペアを登録する
- 単語を入力することで読み方を出力する
- 単語に使える文字はasciiのみ
単語とその読み方のペアとして、今回は以下のデータを用います。
| 単語 | 読み方 |
| a | エー |
| ab | エービー |
| ac | エーシー |
| abc | エービーシー |
| bc | ビーシー |
さて、まずは準備段階として、トライ木実装の際に用いる構造体(クラス)を作っていきます。
今回は、TrieNodeクラスとTrieクラスという2種類のクラスを用います。
TrieNodeクラス
TrieNodeクラスは、トライ木の1つのノードを表すクラスで、itemとchildrenという2つの変数を持ちます。
itemは、辞書引きを行った際に取得したい情報です。
今回は単語を入力し、その読み方を得るシステムなので、itemには単語の読み方が入ります。
単語の終端ノードでない場合には、Noneが入ります。
今回は、このitemを単語の終端ノードかどうかの判定にも利用します。
childrenは、どの文字でどのノードに遷移するかのリストです。
先のトライ木の配列の例の図におけるabc...zの列を表します。
Trieクラス
Trieクラスは、トライ木の実態を表すクラスで、nodesという変数を持ちます。
nodesは、TrieNodeのリストになります。
コード
1VOCAB_SIZE = 128 # 語彙数(今回はasciiのみの対応なので128)
2
3class TrieNode:
4 """
5 Trie木の1ノードを表すクラス
6
7 Attributes
8 ----------
9 item : str
10 登録された単語の読み方
11 単語終端ノード以外の場合はNone
12
13 children : list
14 遷移先のリスト
15 """
16
17
18 def __init__(self, item = None):
19 self.item = item
20 self.children = [-1 for i in range(VOCAB_SIZE)]
21
22 def __str__(self):
23 ret = ""
24 ret = ret + "item = {}\n".format(self.item)
25 ret = ret + "children = \n{}".format(self.children)
26 return ret
27
28class Trie:
29 """
30 Trie木を表すクラス
31
32 Attributes
33 ----------
34 nodes : TrieNode
35 ノードのリスト
36 """
37
38 def __init__(self):
39 root = TrieNode()
40 self.nodes = [root]トライ木の実装(構築部分)
前章で作ったTrieクラスに単語を登録し、トライ木を構築するためのinsertメソッドを実装します。
1class Trie:
2 """
3 Trie木を表すクラス
4
5 Attributes
6 ----------
7 nodes : TrieNode
8 ノードのリスト
9 """
10
11 def __init__(self):
12 root = TrieNode()
13 self.nodes = [root]
14
15
16 def __add_node(self, node):
17 """
18 nodesにノードを追加する
19 追加したノードのインデックスを返す
20
21 Parameters
22 ----------
23 node : TrieNode
24 追加するノード
25
26 Returns
27 -------
28 index : int
29 追加したノードのインデックス
30 """
31 self.nodes.append(node)
32 return len(self.nodes) - 1
33
34 def __get_char_num(self, c):
35 """
36 文字のidを返す
37 aが1, bが2, ..., zが26となる
38
39 Parameters
40 ----------
41 c : char
42 idを取得したいしたい文字
43
44 Returns
45 -------
46 id : int
47 文字のid
48 """
49
50 return ord(c) - ord('a')
51
52 def insert(self ,word, item, char_index=0, node_index=0):
53 """
54 Trieに新しい単語を登録する
55
56 Parameters
57 ----------
58 word : str
59 登録する単語
60
61 item : str
62 wordに対応する読み方
63
64 char_index : int
65 現在着目している文字の位置
66
67 node_index : int
68 現在着目しているノードの位置
69 """
70
71 char_num = self.__get_char_num(word[char_index])
72 next_node_index = self.nodes[node_index].children[char_num]
73 if next_node_index == -1:
74 # 現在のノードにword[char_index]での遷移がなかった場合
75 new_node = TrieNode()
76 next_node_index = self.__add_node(new_node)
77 self.nodes[node_index].children[char_num] = next_node_index
78
79 if char_index == len(word) - 1:
80 # 最後の文字だった場合
81 self.nodes[next_node_index].item = item
82 else:
83 self.insert(word, item, char_index+1, next_node_index)insertを実装するために__add_node() と__get_char_num() というメソッドを作りました。
それぞれ、nodesにnodeを追加し、追加したノードのインデックスを返すメソッドと、文字のidを返すメソッドになります。
詳しくは実装とコメントを参考にしてください。
insertメソッド
insertメソッドを見ていきます。
insertメソッドは、再帰的に呼び出され、すでにあるトライ木を辿っていき、その過程で対応するノードがなかった場合に追加していくことで、トライ木を構築するメソッドです。
一度、insertメソッドが呼び出されるたびに登録単語の1文字分のノードをたどります。
例えば、「ab」という単語を登録する際には、「a」の分と「b」の分の2回のinsertメソッドが呼び出されます。
まず、1,2行目で、現在の文字で遷移すべきノード(next_node_index)を取得します。
このときに遷移すべきノードがまだなかった場合、3行目からの分岐で新たなノードを作成します。
9行目のif char_index == len(word) - 1: の分岐は、現在見ている文字が単語の最後の文字かどうかを判定する分岐です。
最後の文字だった場合、対応するノードに item (今回は読み方)を保存します。
そうでなかった場合は、文字を1つ進めて、もう一度 insert を呼び出します。
トライ木の実装(検索部分)
続いて、検索を行うqueryメソッドを実装します。
1class Trie:
2 """
3 Trie木を表すクラス
4
5 Attributes
6 ----------
7 nodes : TrieNode
8 ノードのリスト
9 """
10
11 def __init__(self):
12 root = TrieNode()
13 self.nodes = [root]
14
15 # -
16 # - 中略
17 # -
18
19 def query(self, word):
20 """
21 作ったTrieを検索する
22
23 Parameters
24 ----------
25 word : str
26 検索したい単語
27
28 Returns
29 -------
30 item : str or None
31 検索結果
32 見つからなかった場合はNone
33 """
34 node_index = 0
35
36 for c in word:
37 char_num = self.__get_char_num(c)
38 tmp_node = self.nodes[node_index]
39
40 node_index = tmp_node.children[char_num]
41 if node_index == -1:
42 return None
43
44 return self.nodes[node_index].itemqueryメソッドは、入力された単語を一文字ずつ見て、トライ木を辿っていきます。
最終的に、単語の終端となるノードのインデックスを取得し、そのノードに保存された item を返します。
コード解説
まず、1行目で現在着目しているノードを表すnode_indexを先頭文字のノードである0に初期化します。
次に、3行目から始まるループで、単語を1文字ずつ見ていきます。
5行目では、現在着目している文字に対応するノードである tmp_node を取得しています。
7行目で、次に遷移するべきノードの index を取得します。
このとき、遷移すべきノードがなかった場合は、その単語が辞書に登録されていないことになるので、Noneを返します。(8行目の分岐)
トライ木の実装(全体)
ここまでで、トライ木を用いた辞書の実装が終わりました。
構築部分と検索部分をまとめたコードは以下のようになります。
1import sys
2
3VOCAB_SIZE = 128 # 語彙数(今回はasciiのみの対応なので128)
4
5class TrieNode:
6 """
7 Trie木の1ノードを表すクラス
8
9 Attributes
10 ----------
11 item : str
12 登録された単語の読み方
13 単語終端ノード以外の場合はNone
14
15 children : list
16 子ノードのリスト
17 """
18
19
20 def __init__(self, item = None):
21 self.item = item
22 self.children = [-1 for i in range(VOCAB_SIZE)]
23
24 def __str__(self):
25 ret = ""
26 ret = ret + "item = {}\n".format(self.item)
27 ret = ret + "children = \n{}".format(self.children)
28 return ret
29
30class Trie:
31 """
32 Trie木を表すクラス
33
34 Attributes
35 ----------
36 nodes : TrieNode
37 ノードのリスト
38 """
39
40 def __init__(self):
41 root = TrieNode()
42 self.nodes = [root]
43
44
45 def __add_node(self, node):
46 """
47 nodesにノードを追加する
48 追加したノードのインデックスを返す
49
50 Parameters
51 ----------
52 node : TrieNode
53 追加するノード
54
55 Returns
56 -------
57 index : int
58 追加したノードのインデックス
59 """
60 self.nodes.append(node)
61 return len(self.nodes) - 1
62
63 def __get_char_num(self, c):
64 """
65 文字のidを返す
66 aが1, bが2, ..., zが26となる
67
68 Parameters
69 ----------
70 c : char
71 idを取得したいしたい文字
72
73 Returns
74 -------
75 id : int
76 文字のid
77 """
78
79 return ord(c) - ord('a')
80
81 def insert(self ,word, item, char_index=0, node_index=0):
82 """
83 Trieに新しい単語を登録する
84
85 Parameters
86 ----------
87 word : str
88 登録する単語
89
90 item : str
91 wordに対応する読み方
92
93 char_index : int
94 現在着目している文字の位置
95
96 node_index : int
97 現在着目しているノードの位置
98 """
99
100 char_num = self.__get_char_num(word[char_index])
101 next_node_index = self.nodes[node_index].children[char_num]
102 if next_node_index == -1:
103 # 現在のノードにword[char_index]での遷移がなかった場合
104 new_node = TrieNode()
105 next_node_index = self.__add_node(new_node)
106 self.nodes[node_index].children[char_num] = next_node_index
107
108 if char_index == len(word) - 1:
109 # 最後の文字だった場合
110 self.nodes[next_node_index].item = item
111 else:
112 self.insert(word, item, char_index+1, next_node_index)
113
114 def query(self, word):
115 """
116 作ったTrieを検索する
117
118 Parameters
119 ----------
120 word : str
121 検索したい単語
122
123 Returns
124 -------
125 item : str or None
126 検索結果
127 見つからなかった場合はNone
128 """
129 node_index = 0
130
131 for c in word:
132 char_num = self.__get_char_num(c)
133 tmp_node = self.nodes[node_index]
134
135 node_index = tmp_node.children[char_num]
136 if node_index == -1:
137 return None
138
139 return self.nodes[node_index].item登録・検索
最後に、Trieクラスを利用して単語の登録、検索を行います。
1trie = Trie()
2
3trie.insert("a", "エー")
4trie.insert("ab", "エービー")
5trie.insert("abc", "エービーシー")
6trie.insert("b", "ビー")
7trie.insert("bc", "ビーシー")
8trie.insert("c", "シー")
9
10
11print(trie.query("a"))
12print(trie.query("abc"))
13print(trie.query("bc"))
14print(trie.query("abcd"))実行
このコードを実行すると、以下のような結果になります。
エー
エービーシー
ビーシー
None
辞書に登録した3単語はきちんと読み方が返ってきて、登録していない「abcd」という単語はNoneが返ることがわかります。
さいごに
トライ木は一見難しそうですが、一度理解してしまえば実装は、さほど難しくなかったと思います。
トライ木を用いると今回のような辞書だけでなく、「形態素解析機」「オートコンプリート」など、様々な分野に応用がきく便利なデータ構造です。
この期にぜひマスターしてみてください。
また、今回の実装では配列を用いた実装ということで、サイズがとても大きくなっています。
実際に使う際には「パトリシア木」「LOUDS」「ダブルアレイ」といった、サイズを小さくする工夫、実装を行います。
これについても、近いうちに記事にできたらと思います！
この記事の続き
2019.08.08トライ木で高速な辞書を作ってみた！トライ木で高速な辞書を作りたい！トライ木（英: trie）というデータ構造を知ってますか？トライ木はテキストを扱う際に...
こちらの記事もオススメ！
関連記事
2019.08.08トライ木で高速な辞書を作ってみた！トライ木で高速な辞書を作りたい！トライ木（英: trie）というデータ構造を知ってますか？トライ木はテキストを扱う際に...
2020.01.15トリプルアレイで軽量で高速な辞書を作ってみた！軽量で高速に検索できる辞書システムをつくるトリプルアレイというデータ構造をご存知でしょうか？「ダブルアレイ」は聞いたこ...
2020.01.28ダブルアレイで高速でコンパクトな辞書を実装してみた！ダブルアレイを使って辞書を実装してみるダブルアレイは、トライ木を表現することができるデータ構造で、コンパクトで高速に辞...
ライトコードでは、エンジニアを積極採用中！
ライトコードでは、エンジニアを積極採用しています！社長と一杯しながらお話しする機会もご用意しております。そのほかカジュアル面談等もございますので、くわしくは採用情報をご確認ください。
採用情報へ
「好きを仕事にするエンジニア集団」の（株）ライトコードです！ ライトコードは、福岡、東京、大阪、名古屋の４拠点で事業展開するIT企業です。 現在は、国内を代表する大手IT企業を取引先にもち、ITシステムの受託事業が中心。 いずれも直取引で、月間PV数1億を超えるWebサービスのシステム開発・運営、インフラの構築・運用に携わっています。 システム開発依頼・お見積もり大歓迎！ また、現在「WEBエンジニア」「モバイルエンジニア」「営業」「WEBデザイナー」を積極採用中です！ インターンや新卒採用も行っております。 以下よりご応募をお待ちしております！ https://rightcode.co.jp/recruit
