メディアチームトリプルアレイで軽量で高速な辞書を作ってみた！
メディアチームIT技術
軽量で高速に検索できる辞書システムをつくる
トリプルアレイというデータ構造をご存知でしょうか？
「ダブルアレイ」は聞いたことがあっても、「トリプルアレイ」は知らないという方も多いのではないかと思います。
トリプルアレイは、ダブルアレイの元となったデータ構造で、ダブルアレイ同様トライ木を表現することができます。
基本的なアイデアは、トリプルアレイもダブルアレイも一緒です。
ただ、性能はダブルアレイのほうが良いです。
しかし、実装の簡単さから、トリプルアレイが適当な場合もあるかと思います。
そこで、今回は、トリプルアレイを用いて、軽量で高速に検索できる辞書システムを実装してみたいと思います。
トリプルアレイとダブルアレイ
元々、トリプルアレイは「YACC」や「LEX」といったツールで使われていた技術です。
これを検索に特化し改良したものとして、「ダブルアレイ」が生まれました。
※詳しくは『An Efficient Digital Search Algorithm by Using a Double-Array Structure(JI-Aoe.1989)』という論文に書かれています。
ただ、トリプルアレイも、Trie木を表現できるデータ構造なので、辞書検索に利用することができます。
ダブルアレイ
ダブルアレイの方がメモリ効率が良く、検索速度もトリプルアレイと同等であるため、できればダブルアレイを用いたほうが良いです。
しかし、その分、仕組みがやや複雑になるため、理解、実装するのがやや難しいという面があります。
トリプルアレイ
一方、トリプルアレイは、メモリ効率はダブルアレイに劣りますが、仕組みはダブルアレイほど複雑でないため、理解、実装が比較的簡単にできます。
トリプルアレイでは、その名の通り3本の配列を利用することでトライ木を表現します。
下記図の左側、配列で表現されたトライ木では無駄な要素が多く、メモリ効率が非常に悪いです。
右側のトリプルアレイでは、この隙間を無くし、よりコンパクトにトライ木を格納することができます。
以前の記事はこちら
トライ木の配列表現がよく分からない方は、以前の記事を参照してください。
2019.08.08トライ木で高速な辞書を作ってみた！トライ木で高速な辞書を作りたい！トライ木（英: trie）というデータ構造を知ってますか？トライ木はテキストを扱う際に...
トリプルアレイ構築方法
それでは、トリプルアレイの構築方法について解説していきます。
トリプルアレイは、トライ木の配列表現を利用して構築していきます。
まず、トライ木の配列表現の各行を、要素がぶつからないようにずらし、潰して一本の配列にします。
この配列が、トリプルアレイの一本目の配列、NEXT配列になります。
また、この際に各行のずらし幅を2本目の配列、OFFSET配列として記録しておきます。
ここで、このトライ木において、ノード1 にいる状態で「c」を入力し、ノード3 に遷移する場合を考えます。
配列表現においては、まず ノード1 の行をみます。
この ノード1 の配列を TRIE[1] と表すことにします。
入力される文字「c」の単語idは「2」です。
ここから、遷移先は TRIE[1][2] に格納されていることが分かります。
ここにある数字が3なので、ノード3 の行に遷移する となります。
NEXT配列とOFFSET配列を用いて、同様の遷移をすることを考える
まずは、NEXT配列 のなかで、ノード1 に対応する場所を見つける必要があります。
NEXT配列は、配列表現の各行をずらして潰した配列ですので、ノード1 の行のずらし幅が分かれば、ノード1 が NEXT配列 においてどこから始まるのかが分かります。
ノード1 のずらし幅は、OFFSET配列の1の位置（OFFSET[1]）に入っています。
OFFSET[1] をみると、ずらし幅は「-1」です。
ここから、ノード1 は NEXT[-1] から始まることがわかります。
(ノード1 の配列が-1の位置からはじまるというだけで、実際には NEXT[-1] に要素は保存されていません。)
次に、ノード1 において「c」が入力された場合に対応する位置を探します。
NEXT配列 を作成する際に各行をずらしましたが、各行内での要素の位置関係は変わっていません。
そのため、「c」の単語idである「2」をずらし幅に足した NEXT[-1+2] に遷移先が格納されています。
NEXT[1] の要素は「3」ですので、ノード3 に遷移することがわかります。
このように、「NEXT配列」と「OFFSET配列」があれば、トライ木を遷移していくことが可能です。
問題点
しかし、この2本だけでは1つ問題点があります。
例）
ノード1において、今度はこのトライ木格納されていない「d」が入力された場合を考えます。
先程と同様に、OFFSET配列 からずらし幅が「-1」であることがわかり、これに「d」の単語idである「3」を足した NEXT[2] に遷移先の情報が入っていることがわかります。
NEXT[2] は、「2」となっています。
これはおかしいです。
ノード1 における「d」、は本来格納されていない単語なので、どこにも遷移できないはずですが、ノード2 に遷移することになっています。
この「2」というのは実は、ノード0 において「c」が入力された際に遷移する先です。
このように、NEXT配列 と OFFSET配列 だけで遷移すると、NEXT配列 の要素がどのノードからの遷移情報であるかが分からないため、誤った場所に遷移してしまいます。
この問題を解決するために、CHECK配列を導入します。
CHECK配列
CHECK配列 には、NEXT配列 の同じ位置にある要素が、どのノードからの遷移情報を表しているかを格納しておきます。
CHECK配列 を導入した状態でもう一度、ノード1 で「d」が入力された場合を考えます。
先程同様、OFFSETと「d」のidから、NEXT[2] に遷移先の情報が入っていることが分かります。
ここで、CHECK[2] をみると、「0」となっています。
いまは、ノード1 からの遷移をしようとしており、ノード0ではありません。
ここから、ノード1 から「d」では遷移できない。
つまり、この単語は格納されていないということが分かります。
以上、「NEXT配列」「OFFSET配列」「 CHECK配列」でトリプルアレイの構築は完了です。
トリプルアレイの実装(準備)
いよいよ、実際にトリプルアレイを実装し、辞書システムを作っていきましょう！
言語は、Python を用います。
要件
要件は、トライ木、パトリシア木のときと同様です。
- 単語とその読み方のペアを登録する
- 単語を入力することで読み方を出力する
- 単語に使える文字はasciiのみ
単語とその読み方のペアとして、以下のデータを用います。
| 単語 | 読み方 |
| a | エー |
| ab | エービー |
| ac | エーシー |
| abc | エービーシー |
| bc | ビーシー |
構造体を作る
まずは、準備段階として、構造体から作っていきます。
TripleArrayクラス
今回は、TripleArray というクラスを作成します。
なお、トリプルアレイは、トライ木を元に作成するため、以前の記事で作成したTrieクラスを用いています。
TripleArrayクラスは、「NEXT配列」「CHECK配列」「OFFSETS配列」と「items」「 trie」の5つの変数を持ちます。
NEXT配列とCHECK配列
NEXT配列 と CHECK配列 は、構築するまでどのくらいの長さになるのか分かりません。
そのため、まずは 長さ2 で初期化し、構築中に長さが足りなくなったら伸ばすというようにします。
OFFSETS配列
OFFSETS（ずらし幅）は、負の値になることもあるので、要素が入っているかどうかを判断するために十分小さな値で初期化します。
実装
__init__() 関数の最後の行で、後に説明するmake_triple_array() を呼び出し、trie を元にトリプルアレイを構築します。
1class TripleArray:
2 """
3 トリプルアレイクラス
4
5 Attributes
6 ----------
7 NEXT : list
8 遷移先を格納するNEXT配列
9
10 CHECK : list
11 遷移元を格納するCHECK配列
12
13 OFFSETS : list
14 ずらし幅を格納するOFFSETS配列
15
16 items : list
17 登録された単語の読み方
18 単語終端ノード以外の場合はNone
19
20 trie : Trie
21 トリプルアレイの元となるTrie木
22
23 """
24
25 def __init__(self, trie):
26 self.CHECK = [-1] * 2
27 self.NEXT = [-1] * 2
28 # オフセットは-(VOCAB_SIZE)以下になることはない
29 # 少し余裕をもたせて-(VOCAB_SIZE+10)で初期化する
30 # (VOCAB_SIZEはTRIEクラスの方で定義されています)
31 self.OFFSETS = [-(tr.VOCAB_SIZE+10)] * len(trie.nodes)
32 self.items = [None] * len(trie.nodes)
33
34 self.trie = trie
35 self.make_triple_array()トリプルアレイ実装(構築部分)
Trieクラスからトリプルアレイを構築するmake_triple_array() を実装していきます。
このメソッドは、trieのノードに一つずつ以下の処理を適応することで、3つの配列を構築していきます。
- 要素がぶつからないずらし幅を見つける(find_offset)
- 見つかったずらし幅で、3つの配列に挿入する(update_arraies)
- NEXTの長さが足りない場合は、倍に増やす(resize_arraies)
コード
1class TripleArray:
2
3 .
4 .
5 .
6
7 def make_triple_array(self):
8 """
9 トリプルアレイを構築する
10 """
11 def is_have_child(node):
12 """
13 nodeが子ノードを持っているかを調べる
14 """
15 tmp = [i for i in node.children if i != -1]
16 if len(tmp) > 0:
17 return True
18 else:
19 return False
20
21 node_id = 0
22 for node in self.trie.nodes:
23 self.items[node_id] = node.item # itemの登録
24 if is_have_child(node):
25 # 子ノードを持ってるノードだったら
26 offset = self.find_offset(node)
27 self.update_arraies(offset, node_id, node)
28 node_id = node_id + 1
29
30 def resize_arraies(self, new_size):
31 """
32 CHECKとNEXTのサイズをnew_sizeにする
33 """
34 now_size = len(self.CHECK)
35 add_size = new_size - now_size
36 new_CHECK = [-1] * add_size
37 new_NEXT = [-1] * add_size
38 self.CHECK.extend(new_CHECK)
39 self.NEXT.extend(new_NEXT)
40
41
42 def find_offset(self, node):
43 """
44 nodeを格納できるずらし幅を見つける
45
46 Parameters
47 ----------
48 node : TrieNode
49 格納するnode
50
51 Returns
52 -------
53 offsets : int
54 見つけたずらし幅
55 """
56 def find_left_node():
57 """
58 nodeの一番左側の要素のindexを返す
59 """
60 for i in range(len(node.children)):
61 if node.children[i] != -1:
62 return i
63 return -1
64
65 def find_right_node():
66 """
67 nodeの一番右側の要素のindexを返す
68 なかったら-1
69 """
70 for i in range(len(node.children)-1, 0, -1):
71 if node.children[i] != -1:
72 return i
73 return -1
74
75 def check(tmp_offset, node):
76 """
77 tmp_offsetでnodeを挿入可能かたしかめる
78 """
79 for i in range(len(node.children)):
80 # nodeの全部のに対して一つずつNEXTのすでにある要素とぶつからないかを調べる
81 if node.children[i] != -1 and self.NEXT[i+tmp_offset] != -1:
82 return False
83
84 return True
85
86 def update_tmp_offset(tmp_offset):
87 """
88 tmp_offsetを更新する
89 """
90 # 今回は+1するだけだが、NEXTの空の位置を記録したりすることで構築時間を短縮することができる
91 return tmp_offset + 1
92
93
94
95
96 tmp_offset = - find_left_node()
97 inserted = False
98 node_last = find_right_node() + 1
99 while inserted == False:
100 # ぶつからないところが見つかるまでずらしていく
101
102 if node_last + tmp_offset > len(self.NEXT):
103 # もしNEXTのサイズが足りなかったら増やす
104 self.resize_arraies(len(self.NEXT) * 2)
105 continue
106
107 if check(tmp_offset, node): # 挿入可能かどうかをcheck
108 # tmp_offsetで挿入可能ならreturn
109 return tmp_offset
110
111 tmp_offset = update_tmp_offset(tmp_offset)
112
113 def update_arraies(self, offset, parent_id, node):
114 """
115 CHECK, NEXT, OFFSETS配列を更新する
116
117 Parameters
118 ----------
119 offset : int
120 ずらし幅
121
122 parent_id : int
123 挿入するノードのid
124
125 node : TrieNode
126 挿入するノード
127 """
128
129 for i in range(len(node.children)):
130 insert_index = i + offset
131 if node.children[i] != -1:
132 # ちゃんと挿入できるか一応再チェック
133 if self.NEXT[insert_index] != -1:
134 print("ERROR:NEXT[{}] is not empty".format(insert_index), file=sys.stderr)
135 exit(1)
136 if self.CHECK[insert_index] != -1:
137 print("ERROR:CHECK[{}] is not empty".format(insert_index), file=sys.stderr)
138 exit(1)
139 # 挿入
140 self.NEXT[insert_index] = node.children[i]
141 self.CHECK[insert_index] = parent_id
142 self.OFFSETS[parent_id] = offset基本的には、1ノードずつずらし幅を見つけて（find_offset）、挿入する（update_arraies）だけなので、トリプルアレイの仕組みが理解できていれば問題ないと思います。
コード中にかなり詳しくコメントを書いたので参考にしてください。
トリプルアレイ実装(検索部分)
続いて、検索を行うquery() を実装していきます。
こちらは、検索文字列を一文字ずつループすることで、トリプルアレイを遷移していきます。
最後のノードにたどり着いたら、items に格納されているそのノードに対応する要素を返します。
1class TripleArray:
2
3 .
4 .
5 .
6
7 def query(self, word):
8 """
9 検索する
10
11 Parameters
12 ----------
13 word : str
14 検索したい単語
15
16 Returns
17 -------
18 item :str or None
19 検索結果
20 見つからなかった場合はNone
21 """
22
23 def get_char_num(c):
24 """
25 文字のidを返す
26 aが0, bが1, ..., zが25となる
27 """
28 return ord(c) - ord('a')
29
30 tmp_index = 0
31 tmp_node = 0
32 tmp_offset = 0
33 for c in word:
34 char_num = get_char_num(c)
35
36 offset = self.OFFSETS[tmp_node] # ずらし幅をget
37 tmp_index = offset + char_num # NEXT, CHECKのindexを計算
38 if not(0 <= tmp_index < len(self.CHECK)):
39 # tmp_indexがCHECKのインデックスの範囲に無いっていない場合はただ遷移でないのでNone
40 return None
41
42 if self.CHECK[tmp_index] != tmp_node:
43 # 正しい遷移でない場合そのwordは格納されていないのでNoneを返す
44 return None
45
46 tmp_node = self.NEXT[tmp_index] # 遷移先のノードをget
47
48 return self.items[tmp_node]トリプルアレイの実装(全体)
ここまでで、トリプルアレイを用いた辞書の実装が完了です。
すべてのコードをまとめたものが以下になります。
コード
1import sys
2import trie as tr # 以前の記事で作成したTRIEクラス
3
4
5class TripleArray:
6 """
7 トリプルアレイクラス
8
9 Attributes
10 ----------
11 NEXT : list
12 遷移先を格納するNEXT配列
13
14 CHECK : list
15 遷移元を格納するCHECK配列
16
17 OFFSETS : list
18 ずらし幅を格納するOFFSETS配列
19
20 items : list
21 登録された単語の読み方
22 単語終端ノード以外の場合はNone
23
24 trie : Trie
25 トリプルアレイの元となるTrie木
26
27 """
28
29 def __init__(self, trie):
30 self.CHECK = [-1] * 2
31 self.NEXT = [-1] * 2
32 # オフセットは-(VOCAB_SIZE)以下になることはない
33 # 少し余裕をもたせて-(VOCAB_SIZE+10)で初期化する
34 self.OFFSETS = [-(tr.VOCAB_SIZE+10)] * len(trie.nodes)
35 self.items = [None] * len(trie.nodes)
36
37 self.trie = trie
38 self.make_triple_array()
39
40
41
42 def make_triple_array(self):
43 """
44 トリプルアレイを構築する
45 """
46 def is_have_child(node):
47 """
48 nodeが子ノードを持っているかを調べる
49 """
50 tmp = [i for i in node.children if i != -1]
51 if len(tmp) > 0:
52 return True
53 else:
54 return False
55
56 node_id = 0
57 for node in self.trie.nodes:
58 self.items[node_id] = node.item # itemの登録
59 if is_have_child(node):
60 # 子ノードを持ってるノードだったら
61 offset = self.find_offset(node)
62 self.update_arraies(offset, node_id, node)
63 node_id = node_id + 1
64
65 def resize_arraies(self, new_size):
66 """
67 CHECKとNEXTのサイズをnew_sizeにする
68 """
69 now_size = len(self.CHECK)
70 add_size = new_size - now_size
71 new_CHECK = [-1] * add_size
72 new_NEXT = [-1] * add_size
73 self.CHECK.extend(new_CHECK)
74 self.NEXT.extend(new_NEXT)
75
76
77 def find_offset(self, node):
78 """
79 nodeを格納できるずらし幅を見つける
80
81 Parameters
82 ----------
83 node : TrieNode
84 格納するnode
85
86 Returns
87 -------
88 offsets : int
89 見つけたずらし幅
90 """
91 def find_left_node():
92 """
93 nodeの一番左側の要素のindexを返す
94 """
95 for i in range(len(node.children)):
96 if node.children[i] != -1:
97 return i
98 return -1
99
100 def find_right_node():
101 """
102 nodeの一番右側の要素のindexを返す
103 なかったら-1
104 """
105 for i in range(len(node.children)-1, 0, -1):
106 if node.children[i] != -1:
107 return i
108 return -1
109
110 def check(tmp_offset, node):
111 """
112 tmp_offsetでnodeを挿入可能かたしかめる
113 """
114 for i in range(len(node.children)):
115 # nodeの全部のに対して一つずつNEXTのすでにある要素とぶつからないかを調べる
116 if node.children[i] != -1 and self.NEXT[i+tmp_offset] != -1:
117 return False
118
119 return True
120
121 def update_tmp_offset(tmp_offset):
122 """
123 tmp_offsetを更新する
124 """
125 # 今回は+1するだけだが、NEXTの空の位置を記録したりすることで構築時間を短縮することができる
126 return tmp_offset + 1
127
128
129
130
131 tmp_offset = - find_left_node()
132 inserted = False
133 node_last = find_right_node() + 1
134 while inserted == False:
135 # ぶつからないところが見つかるまでずらしていく
136
137 if node_last + tmp_offset > len(self.NEXT):
138 # もしNEXTのサイズが足りなかったら増やす
139 self.resize_arraies(len(self.NEXT) * 2)
140 continue
141
142 if check(tmp_offset, node): # 挿入可能かどうかをcheck
143 # tmp_offsetで挿入可能ならreturn
144 return tmp_offset
145
146 tmp_offset = update_tmp_offset(tmp_offset)
147
148 def update_arraies(self, offset, parent_id, node):
149 """
150 CHECK, NEXT, OFFSETS配列を更新する
151
152 Parameters
153 ----------
154 offset : int
155 ずらし幅
156
157 parent_id : int
158 挿入するノードのid
159
160 node : TrieNode
161 挿入するノード
162 """
163
164 for i in range(len(node.children)):
165 insert_index = i + offset
166 if node.children[i] != -1:
167 # ちゃんと挿入できるか一応再チェック
168 if self.NEXT[insert_index] != -1:
169 print("ERROR:NEXT[{}] is not empty".format(insert_index), file=sys.stderr)
170 exit(1)
171 if self.CHECK[insert_index] != -1:
172 print("ERROR:CHECK[{}] is not empty".format(insert_index), file=sys.stderr)
173 exit(1)
174 # 挿入
175 self.NEXT[insert_index] = node.children[i]
176 self.CHECK[insert_index] = parent_id
177 self.OFFSETS[parent_id] = offset
178
179 def query(self, word):
180 """
181 検索する
182
183 Parameters
184 ----------
185 word : str
186 検索したい単語
187
188 Returns
189 -------
190 item :str or None
191 検索結果
192 見つからなかった場合はNone
193 """
194
195 def get_char_num(c):
196 """
197 文字のidを返す
198 aが0, bが1, ..., zが25となる
199 """
200 return ord(c) - ord('a')
201
202 tmp_index = 0
203 tmp_node = 0
204 tmp_offset = 0
205 for c in word:
206 char_num = get_char_num(c)
207
208 offset = self.OFFSETS[tmp_node] # ずらし幅をget
209 tmp_index = offset + char_num # NEXT, CHECKのindexを計算
210 if not(0 <= tmp_index < len(self.CHECK)):
211 # tmp_indexがCHECKのインデックスの範囲に無いっていない場合はただ遷移でないのでNone
212 return None
213
214 if self.CHECK[tmp_index] != tmp_node:
215 # 正しい遷移でない場合そのwordは格納されていないのでNoneを返す
216 return None
217
218 tmp_node = self.NEXT[tmp_index] # 遷移先のノードをget
219
220 return self.items[tmp_node]トリプルアレイの構築、検索
最後に、トリプルアレイの構築、検索を行います。
1trie = tr.Trie()
2
3trie.insert("a", "エー")
4trie.insert("ab", "エービー")
5trie.insert("abc", "エービーシー")
6trie.insert("b", "ビー")
7trie.insert("bc", "ビーシー")
8trie.insert("c", "シー")
9
10## ここまででtrie木を作成
11
12triple_array = TripleArray(trie) # トリプルアレイの構築
13
14print(triple_array.query("a"))
15print(triple_array.query("abc"))
16print(triple_array.query("bc"))
17print(triple_array.query("abcd"))結果
これを実行すると、以下のような結果になります。
1エー
2エービーシー
3ビーシー
4None辞書に insert した単語は、きちんと読み方が表示され、そうでない単語は None となっていることがわかります。
さいごに
お疲れさまでした！
トリプルアレイは、ダブルアレイに比べると簡単ですが、それでもきちんと理解するのは難しいかもしれません。
それでも、一度きちんと実装してみれば、必ず理解できるはずです。
また、トリプルアレイさえ理解できれば、ダブルアレイの理解も簡単になるので、ぜひチャレンジしてみてください！
こちらの記事もオススメ！
2020.07.17ライトコード的「やってみた！」シリーズ「やってみた！」を集めました！（株）ライトコードが今まで作ってきた「やってみた！」記事を集めてみました！※作成日が新し...
2020.07.30Python 特集実装編※最新記事順Responder + Firestore でモダンかつサーバーレスなブログシステムを作ってみた！P...
関連記事
2019.08.08トライ木で高速な辞書を作ってみた！トライ木で高速な辞書を作りたい！トライ木（英: trie）というデータ構造を知ってますか？トライ木はテキストを扱う際に...
2020.01.15トリプルアレイで軽量で高速な辞書を作ってみた！軽量で高速に検索できる辞書システムをつくるトリプルアレイというデータ構造をご存知でしょうか？「ダブルアレイ」は聞いたこ...
2020.01.28ダブルアレイで高速でコンパクトな辞書を実装してみた！ダブルアレイを使って辞書を実装してみるダブルアレイは、トライ木を表現することができるデータ構造で、コンパクトで高速に辞...
ライトコードでは、エンジニアを積極採用中！
ライトコードでは、エンジニアを積極採用しています！社長と一杯しながらお話しする機会もご用意しております。そのほかカジュアル面談等もございますので、くわしくは採用情報をご確認ください。
採用情報へ
「好きを仕事にするエンジニア集団」の（株）ライトコードです！ ライトコードは、福岡、東京、大阪、名古屋の４拠点で事業展開するIT企業です。 現在は、国内を代表する大手IT企業を取引先にもち、ITシステムの受託事業が中心。 いずれも直取引で、月間PV数1億を超えるWebサービスのシステム開発・運営、インフラの構築・運用に携わっています。 システム開発依頼・お見積もり大歓迎！ また、現在「WEBエンジニア」「モバイルエンジニア」「営業」「WEBデザイナー」を積極採用中です！ インターンや新卒採用も行っております。 以下よりご応募をお待ちしております！ https://rightcode.co.jp/recruit
おすすめ記事
