トライ木をビットスライスとパトリシア木でコンパクトにしてみた！
2021.12.20
「ビットスライス」「パトリシア木」を用いて、トライ木の問題点を解決したい！
前回の記事では、トライ木というデータ構造を紹介し、トライ木を用いた辞書の実装を行いました。
トライ木は、非常に高速で文字列を検索できる優れたデータ構造ですが、問題点もあります。
本記事では、まず、トライ木の問題点について説明します。
その後、その解決方法である「ビットスライス」「パトリシア木」を用いて、前回と同様の辞書システムを実装します。
前回の記事
このトライ木の問題点
前回の記事で実装したトライ木には、サイズが大きくなりやすいという問題点があります。
前回の実装にて、トライ木の1つのノードは、以下のように定義されていました。
1 2 3 4 5 6 7 8 9 10 11 12 13 | class TrieNode: """ Trie木の1ノードを表すクラス Attributes ---------- item : str 登録された単語の読み方 単語終端ノード以外の場合はNone children : list 子ノードのリスト """ |
このうち、問題となるのは、子ノードのリストである children です。
前回の実装では、 children はアルファベット数分のサイズを持つリスト(配列)として保持されていました。
これにより、トライ木全体のサイズは少なくとも「ノード数 × アルファベット数」となります。
前回は、ascii文字のみの対応だったため、アルファベット数は「128」でした。
しかし…例えば日本語に対応しようとした場合、「ひらがな」「カタカナ」「漢字」と、アルファベット数は「数千」、あるいは「数万」にもなります。
これは、とてもメモリ上に保持できるサイズではありません。
そこで今回は、このトライ木のサイズを削減するためにビットスライスという手法と、パトリシア木という木構造を紹介します。
ビットスライス
まずは１つ目の手法である、ビットスライスを紹介します。
この手法は、トライ木のサイズ(ノード数 × アルファベット数)のうち、アルファベット数を少なくするための手法です。
コンピュータ上では、「a」や「b」といった文字は、ビット列として表現されています。
そこで、「a」や「b」といった文字をビット列に分解し、分解されたビットを文字の代わりにアルファベットとして用いることで、アルファベット数を少なくすることができます。
1ビットで表現できるのは「0」と「1」ですから、この手法によりアルファベット数は「2」となります。
上の図は、「a」という単語が格納されたトライ木をビットスライスにするものです。
上の図において、左のシンプルなトライ木を、「a」が「0001」というビット列で表されると仮定して、ビットスライスしています。
ビットスライスの問題点
アルファベット数を大幅に減らすことができるビットスライスですが、この手法にも問題点があります。
先程の図を見た時点でお気づきの方もいらっしゃるかと思いますが、ビットスライスを用いるとアルファベット数が減るかわりにノード数が増えます。
本来1文字である「a」という文字をビット列で表すと、(4ビットで表されていた場合)「0001」という様に4文字分になります。
これにより、アルファベット数は「2」になりますが、ノード数は4倍になってしまいます。
このノード数が増加してしまうという問題を解決するために、パトリシア木というデータ構造を用います。
パトリシア木
パトリシア木は、Trie木のノード数を削減できるデータ構造です。
トライ木では、1つのノードには1つのアルファベットが対応していました。
しかし、パトリシア木では下の図のように分岐がないノードを省略し、1つのノードに複数のアルファベットを対応させることでノード数を削減しています。
パトリシア木の実装(準備)
それでは、実際にパトリシア木を実装し、辞書システムを作っていきます。
言語は、「Python（パイソン）」を用います。
要件
トライ木の記事のときの要件に、サイズに関する要件が加わりました。
- 単語とその読み方のペアを登録する
- 単語を入力することで読み方を出力する
- 単語に使える文字はasciiのみ
- ビットスライス、パトリシア木を用い、できるだけサイズを小さくする
単語とその読み方のペアとして、今回も前回同様以下のデータを用います。
1 2 3 4 5 6 | 単語:読み方 a:エー ab:エービー ac:エーシー abc:エービーシー bc:ビーシー |
では、準備段階としてパトリシア木の実装に用いる構造体から作っていきましょう。
- パトリシア木のノードを表すPatriciaNodeクラス
- パトリシア木の実体を表すPatriciaクラス
今回は、パトリシア木のノードを表すPatriciaNodeクラスと、パトリシア木の実体を表すPatriciaクラスを用います。
PatriciaNodeクラス
まずは、PatriciaNodeクラスについて紹介していきます。
PatriciaNodeクラスは、3つの変数を持ちます。
item
item は、辞書引きを行った際にとってきたい情報です。
今回は、読み方を引いてくる辞書なので、itemには登録する単語の読み方が入ります。
children
children は、どの文字でどのノードに遷移するかを表したリストです。
今回は、アルファベット数（VOCAV_SIZE）が2なので大きさは2となります。
sub_str
sub_str は、トライ木では必要なかった新たな変数です。
パトリシア木では、1つのノードに複数のアルファベット(ビットスライスの場合はビットとなる)が対応するため、何ビット目をチェックすれば良いのか分からなくなってしまいます。
そこで、 sub_str として対応するアルファベットを保持しておくことで、どのビットを比較すれば良いかが分かるようにします。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | VOCAB_SIZE = 2 # アルファベット数 class PatriciaNode: """ Patricia木の1ノードを表すクラス Attributes ---------- item : str 登録された単語の読み方 単語終端ノード以外の場合はNone children : list 子ノードのリスト sub_str : str そのノードに対応する部分文字列 """ def __init__(self, item = None, sub_str = ""): self.item = item self.children = [-1 for i in range(VOCAB_SIZE)] self.sub_str = sub_str |
Patriciaクラス
続いて、Patriciaクラスの説明を行います。
Patriciaクラスは、パトリシア木の実体を表すクラスで、 nodes という変数を持ちます。
nodes
nodes は、PatriciaNodeのリストとなります。
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Patricia: """ Patricia木を表すクラス Attributes ---------- nodes : PatriciaNode ノードのリスト """ def __init__(self): root = PatriciaNode() self.nodes = [root] |
パトリシア木実装(補助メソッド)
それでは、パトリシア木の中身を実装していきます。
が、先に「挿入」「検索」どちらの処理でも共通して使う __search_longest_match() というメソッドの解説を行います。
__search_longest_match() についての解説
- __search_longest_match() は、Patriciaクラスのクラスメソッド
このメソッドは、検索文字列をビット列に変換したものを入力として、パトリシア木の探索を行います。
前編で説明したとおりパトリシア木では、1つのノードが複数のアルファベットに対応しています。
そのため、あるノードまで遷移してきた場合でも、検索文字列がそのノードに対応するアルファベット列の全てと一致するとは限りません。
そこで、 __search_longest_match() では、入力文字列をもちいて、一致する最後のノード（node_index）まで探索を行い、そのノードのアルファベット列のどこまで一致したのかを表す match_str と、また、一致しなかった部分を表す rest_str を返します。
上の図は、「a」「b」「abc」という3単語を格納したパトリシア木において、ab（0001 0000）を検索したときのそれぞれの変数の値です。
この場合、id=4 のノードまで遷移してきているので、node_index は 4 となります。
また、id=4 のノードの中でも、「0000」というビット列までは一致しており、「1011」は一致していないので、 match_str は 0000、 rest_str は 1011 となります。
__search_longest_match() の実装を単純にするために、2つの文字列が先頭から何文字目まで一致しているかを調べる __match() メソッドも作成しています。
コード
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 | class Patricia: def __match(self, word_b1, word_b2): """ word_1がword_2に先頭から何文字目まで一致しているかを調べる Parameters ---------- word_1 : str 比較対象ビット列 word_2 : str 比較元ビット列 Returns ------- index : int 何ビット目まで一致していたか """ l = len(word_b1) k = 0 for i in range(l): if len(word_b2) <= i or word_b1[i] != word_b2[i]: break k = k + 1 return k def __search_longest_match(self, word_b, node_index=0): """ Patriciaを巡回して最長一致を求める Parameters ---------- word_b : str 検索したいビット列 node_index : int 検索開始位置のindex Returns ------- node_index : int 一致した最後のnodeのインデックス rest_str : str 残りbit列 match_str : str 最後のnodeと一致したbit列 """ sub_str = self.nodes[node_index].sub_str match_num = self.__match(word_b, sub_str) if match_num == len(word_b): return node_index, "", word_b rest_str = word_b[match_num:] match_str = word_b[:match_num] # ここまでで現在のノードに対するmatch_str、rest_strが求まる next_node = self.nodes[node_index].children[int(rest_str[0])] if next_node == -1: return node_index, rest_str, match_str return self.__search_longest_match(rest_str, next_node) |
コード解説
__search_longest_match() メソッドのコードを少し解説します。
__search_longest_match() は、一度呼び出されるごとにノードを1つ巡り、再帰的に呼び出されることで最後のノードまで巡ります。
まず、 match_str = word_b[:match_num] までで、現在着目しているノードが対応するアルファベット列( sub_str )に対して、 match_str と rest_str を求めます。
（ match_str と rest_str は、先程説明したとおり、検索文字列が sub_str に対して一致した部分と、一致しなかった部分を表します。）
このとき、 match_str が検索文字列である word_b と完全に一致した場合、そのノードで丁度探索が終了したことになるので、その時点の node_index 、 rest_str 、 match_str を返します。
続いて、現在のノードの情報と、残りの検索文字列を用いて、次のノードへの遷移を行います。
このとき、次のノードが存在しなかった場合は、パトリシア木の末端まで探索し終わったことになるので、この時点で return します。
遷移に成功した場合は、 __search_longest_match() を再帰的に呼び出します。
パトリシア木実装(挿入部分)
パトリシア木に単語を挿入するための insert() メソッドを実装していきます。
パトリシア木における挿入処理は、分岐のないノードを省略するために、やや複雑な処理を必要とします。
パトリシア木の挿入処理は、大きく2パターンに分けられます。
- 1つ目は、挿入の際に既存のノードの変更が必要なもの。
- 2つ目は、既存のノードの変更が必要ないものです。
図を用いて説明していきます。
パターン１
上の図は、単語「a」, 「b」, 「abc」が格納されているパトリシア木に「ab」というノードを追加するものです。
この場合は、既存のノードの変更が必要な場合になります。
この場合、新たな「ab」のノードは、「a」のノードと「abc」のノードの間に挿入されることになります。
「ab」のノードを「a」のノードの下に挿入したとき、「a」のノードの遷移先は「abc」のノードから変更されることになります。
また、「ab」のノードの下につく「abc」のノードについても、 sub_str を変更する必要があります。
一方、既存のノードに変更が必要ない場合もあります。
パターン２
上の図は、先程のパトリシア木に「ba」という単語を追加するものです。
この場合、以下の図のように、既存ノードを変更する必要なく挿入することができます。
このようにパトリシア木では、単語を挿入する際に、ただノードを追加するだけでなく、既存のノードを変更する必要が生じる場合もあります。
コード
これを踏まえて、insert()メソッドのコードを見ていきましょう。
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 | class Patricia: """ Patricia木を表すクラス Attributes ---------- nodes : PatriciaNode ノードのリスト """ def insert(self, word, item): """ Patriciaに新しい単語を登録する Parameters ---------- word : str 登録する単語 item : str wordに対応する読み方 """ word_b = self.__word_2_bit(word) node_index, rest_str, match_str = self.__search_longest_match(word_b) node_rest_str = self.nodes[node_index].sub_str[len(match_str):] # node_index : 最後のノードのindex # node_rest_str : ノードの文字列の挿入文字列と一致しなかった部分 # rest_str : 挿入文字列のノードの文字列と一致しなかった部分 # match_str : 挿入文字列のノードの文字列と一致した部分 if node_rest_str != '': # 新しいノードを付け加える new_node_index = self.__add_node() self.nodes[new_node_index].item = self.nodes[node_index].item self.nodes[new_node_index].children = list(self.nodes[node_index].children) self.nodes[new_node_index].sub_str = node_rest_str # 既存のノードを変更する self.nodes[node_index].item = None self.nodes[node_index].children[int(node_rest_str[0])] = new_node_index self.nodes[node_index].sub_str = match_str if rest_str != '': # 新しいノードを付け加える new_node_index = self.__add_node() self.nodes[new_node_index].item = item self.nodes[new_node_index].sub_str = rest_str self.nodes[node_index].children[int(rest_str[0])] = new_node_index |
コード解説
まずは、 node_index 、 node_rest_str 、 rest_str 、 match_str を求めます。
それぞれの変数の意味は、コメントに書いてあるとおりです。
次に、条件分岐からノードを追加していきます。
条件に当てはまる場合は、ノードを追加するだけでなく既存のノードの変更を必要とします。
条件に当てはまる場合（rest_strがある場合）は、さらに新しいノードを付け加える必要があります。
パトリシア木の実装(検索部分)
続いて、検索部分の実装を行っていきます。
とはいえ、 __search_longest_match() の実装が終わっているので、ここは簡単です。
コード
こちらがコードとなります。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | def query(self, word): """ Patriciaを検索する Parameters ---------- word : str 検索したい単語 Returns ------- item : str or None 検索結果 見つからなかった場合はNone """ word_b = self.__word_2_bit(word) node_index, rest_str, match_str = self.__search_longest_match(word_b) node_str = self.nodes[node_index].sub_str if match_str == node_str and rest_str == "": return self.nodes[node_index].item return None |
コード解説
__search_longest_match() を実行し、 node_index 、 rest_str 、 match_str と、 node_rest_str を取得しています。
検索単語が存在する場合というのは、条件にあるように、 node_rest_str と rest_str が空のとき、つまり、ノードの文字列と検索文字列が完全に一致したときです。
よって、このときのみ対応する item を return し、それ以外の場合は単語が存在しないので None を return します。
パトリシア木の実装(全体)
ここまでで、パトリシア木を用いた辞書の実装が終わりました。
すべてのコードをまとめたものが以下になります。
コード
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 | import sys VOCAB_SIZE = 2 # アルファベット数 class PatriciaNode: """ Patricia木の1ノードを表すクラス Attributes ---------- item : str 登録された単語の読み方 単語終端ノード以外の場合はNone children : list 子ノードのリスト sub_str : str そのノードに対応する部分文字列 """ def __init__(self, item = None, sub_str = ""): self.item = item self.children = [-1 for i in range(VOCAB_SIZE)] self.sub_str = sub_str class Patricia: """ Patricia木を表すクラス Attributes ---------- nodes : PatriciaNode ノードのリスト """ def __init__(self): root = PatriciaNode() self.nodes = [root] def __add_node(self, node=None): """ nodesにノードを追加する 追加したノードのインデックスを返す Parameters ---------- node : TrieNode 追加するノード Returns ------- index : int 追加したノードのインデックス """ if node is None: node = PatriciaNode() self.nodes.append(node) return len(self.nodes) - 1 def __word_2_bit(self, word): """ 文字列をビット列に変換する """ word_b = "" for c in word: word_b = word_b + format((ord(c) - ord('a')), '08b') return word_b def __match(self, word_b1, word_b2): """ word_1がword_2に先頭から何文字目まで一致しているかを調べる Parameters ---------- word_1 : str 比較対象ビット列 word_2 : str 比較元ビット列 Returns ------- index : int 何ビット目まで一致していたか """ l = len(word_b1) k = 0 for i in range(l): if len(word_b2) <= i or word_b1[i] != word_b2[i]: break k = k + 1 return k def __search_longest_match(self, word_b, node_index=0): """ Patriciaを巡回して最長一致を求める Parameters ---------- word_b : str 検索したいビット列 node_index : int 検索開始位置のindex Returns ------- node_index : int 一致した最後のnodeのインデックス rest_str : str 残りbit列 match_str : str 最後のnodeと一致したbit列 """ sub_str = self.nodes[node_index].sub_str match_num = self.__match(word_b, sub_str) if match_num == len(word_b): return node_index, "", word_b rest_str = word_b[match_num:] match_str = word_b[:match_num] # ここまでで現在のノードに対するmatch_str、rest_strが求まる next_node = self.nodes[node_index].children[int(rest_str[0])] if next_node == -1: return node_index, rest_str, match_str return self.__search_longest_match(rest_str, next_node) def insert(self, word, item): """ Patriciaに新しい単語を登録する Parameters ---------- word : str 登録する単語 item : str wordに対応する読み方 """ word_b = self.__word_2_bit(word) node_index, rest_str, match_str = self.__search_longest_match(word_b) node_rest_str = self.nodes[node_index].sub_str[len(match_str):] # node_index : 最後のノードのindex # node_rest_str : ノードの文字列の挿入文字列と一致しなかった部分 # rest_str : 挿入文字列のノードの文字列と一致しなかった部分 # match_str : 挿入文字列のノードの文字列と一致した部分 if node_rest_str != '': # 新しいノードを付け加える new_node_index = self.__add_node() self.nodes[new_node_index].item = self.nodes[node_index].item self.nodes[new_node_index].children = list(self.nodes[node_index].children) self.nodes[new_node_index].sub_str = node_rest_str # 既存のノードを変更する self.nodes[node_index].item = None self.nodes[node_index].children[int(node_rest_str[0])] = new_node_index self.nodes[node_index].sub_str = match_str if rest_str != '': # 新しいノードを付け加える new_node_index = self.__add_node() self.nodes[new_node_index].item = item self.nodes[new_node_index].sub_str = rest_str self.nodes[node_index].children[int(rest_str[0])] = new_node_index def query(self, word): """ Patriciaを検索する Parameters ---------- word : str 検索したい単語 Returns ------- item : str or None 検索結果 見つからなかった場合はNone """ word_b = self.__word_2_bit(word) node_index, rest_str, match_str = self.__search_longest_match(word_b) node_rest_str = self.nodes[node_index].sub_str[len(match_str):] if node_rest_str == "" and rest_str == "": return self.nodes[node_index].item return None |
最後に、Patriciaクラスを利用して単語の登録、検索を行います。
1 2 3 4 5 6 7 8 9 10 11 12 | patricia = Patricia() patricia.insert("a", "エー") patricia.insert("ab", "エービー") patricia.insert("abc", "エービーシー") patricia.insert("b", "ビー") patricia.insert("bc", "ビーシー") patricia.insert("c", "シー") print(patricia.query("a")) print(patricia.query("abc")) print(patricia.query("bc")) print(patricia.query("abcd")) |
これを実行すると、以下のような結果になります。
エー
エービーシー
ビーシー
None
辞書に insert した単語は、きちんと読み方が表示され、そうでない単語は None となっていることが分かります。
まとめ
お疲れ様でした！
パトリシア木は、トライ木に比べるとやや複雑で理解しにくかったかもしれません。
しかし、一度理解し使えるようになれば、高速でサイズの小さい使い勝手の良いデータ構造です。
トライ木がわかっていればそこまで難しくないと思うので、ぜひチャレンジしてみてください。
こちらの記事もオススメ！
関連記事
書いた人はこんな人
- 「好きを仕事にするエンジニア集団」の（株）ライトコードです！
ライトコードは、福岡、東京、大阪の3拠点で事業展開するIT企業です。
現在は、国内を代表する大手IT企業を取引先にもち、ITシステムの受託事業が中心。
いずれも直取引で、月間PV数1億を超えるWebサービスのシステム開発・運営、インフラの構築・運用に携わっています。
システム開発依頼・お見積もり大歓迎！
また、現在「WEBエンジニア」「モバイルエンジニア」「営業」「WEBデザイナー」「WEBディレクター」を積極採用中です！
インターンや新卒採用も行っております。
以下よりご応募をお待ちしております！
https://rightcode.co.jp/recruit
ライトコードの日常12月 1, 2023ライトコードクエスト〜東京オフィス歴史編〜- ITエンタメ10月 13, 2023Netflixの成功はレコメンドエンジン？
- ライトコードの日常8月 30, 2023退職者の最終出社日に密着してみた！
- ITエンタメ8月 3, 2023世界初の量産型ポータブルコンピュータを開発したのに倒産!?アダム・オズボーン
関連記事
採用情報
\ あの有名サービスに参画!? /
バックエンドエンジニア
\ クリエイティブの最前線 /
フロントエンドエンジニア
\ 世界を変える…！ /
Androidエンジニア
\ みんなが使うアプリを創る /
iOSエンジニア
