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