トライ木で高速な辞書を作ってみた！
2021.12.20
トライ木で高速な辞書を作りたい！
トライ木（英: 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のリストになります。
コード
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 | VOCAB_SIZE = 128 # 語彙数(今回はasciiのみの対応なので128) class TrieNode: """ Trie木の1ノードを表すクラス Attributes ---------- item : str 登録された単語の読み方 単語終端ノード以外の場合はNone children : list 遷移先のリスト """ def __init__(self, item = None): self.item = item self.children = [-1 for i in range(VOCAB_SIZE)] def __str__(self): ret = "" ret = ret + "item = {}\n".format(self.item) ret = ret + "children = \n{}".format(self.children) return ret class Trie: """ Trie木を表すクラス Attributes ---------- nodes : TrieNode ノードのリスト """ def __init__(self): root = TrieNode() self.nodes = [root] |
トライ木の実装(構築部分)
前章で作ったTrieクラスに単語を登録し、トライ木を構築するための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 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 | class Trie: """ Trie木を表すクラス Attributes ---------- nodes : TrieNode ノードのリスト """ def __init__(self): root = TrieNode() self.nodes = [root] def __add_node(self, node): """ nodesにノードを追加する 追加したノードのインデックスを返す Parameters ---------- node : TrieNode 追加するノード Returns ------- index : int 追加したノードのインデックス """ self.nodes.append(node) return len(self.nodes) - 1 def __get_char_num(self, c): """ 文字のidを返す aが1, bが2, ..., zが26となる Parameters ---------- c : char idを取得したいしたい文字 Returns ------- id : int 文字のid """ return ord(c) - ord('a') def insert(self ,word, item, char_index=0, node_index=0): """ Trieに新しい単語を登録する Parameters ---------- word : str 登録する単語 item : str wordに対応する読み方 char_index : int 現在着目している文字の位置 node_index : int 現在着目しているノードの位置 """ char_num = self.__get_char_num(word[char_index]) next_node_index = self.nodes[node_index].children[char_num] if next_node_index == -1: # 現在のノードにword[char_index]での遷移がなかった場合 new_node = TrieNode() next_node_index = self.__add_node(new_node) self.nodes[node_index].children[char_num] = next_node_index if char_index == len(word) - 1: # 最後の文字だった場合 self.nodes[next_node_index].item = item else: 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メソッドを実装します。
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 | class Trie: """ Trie木を表すクラス Attributes ---------- nodes : TrieNode ノードのリスト """ def __init__(self): root = TrieNode() self.nodes = [root] # - # - 中略 # - def query(self, word): """ 作ったTrieを検索する Parameters ---------- word : str 検索したい単語 Returns ------- item : str or None 検索結果 見つからなかった場合はNone """ node_index = 0 for c in word: char_num = self.__get_char_num(c) tmp_node = self.nodes[node_index] node_index = tmp_node.children[char_num] if node_index == -1: return None return self.nodes[node_index].item |
queryメソッドは、入力された単語を一文字ずつ見て、トライ木を辿っていきます。
最終的に、単語の終端となるノードのインデックスを取得し、そのノードに保存された item を返します。
コード解説
まず、1行目で現在着目しているノードを表すnode_indexを先頭文字のノードである0に初期化します。
次に、3行目から始まるループで、単語を1文字ずつ見ていきます。
5行目では、現在着目している文字に対応するノードである tmp_node を取得しています。
7行目で、次に遷移するべきノードの index を取得します。
このとき、遷移すべきノードがなかった場合は、その単語が辞書に登録されていないことになるので、Noneを返します。(8行目の分岐)
トライ木の実装(全体)
ここまでで、トライ木を用いた辞書の実装が終わりました。
構築部分と検索部分をまとめたコードは以下のようになります。
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 | import sys VOCAB_SIZE = 128 # 語彙数(今回はasciiのみの対応なので128) class TrieNode: """ Trie木の1ノードを表すクラス Attributes ---------- item : str 登録された単語の読み方 単語終端ノード以外の場合はNone children : list 子ノードのリスト """ def __init__(self, item = None): self.item = item self.children = [-1 for i in range(VOCAB_SIZE)] def __str__(self): ret = "" ret = ret + "item = {}\n".format(self.item) ret = ret + "children = \n{}".format(self.children) return ret class Trie: """ Trie木を表すクラス Attributes ---------- nodes : TrieNode ノードのリスト """ def __init__(self): root = TrieNode() self.nodes = [root] def __add_node(self, node): """ nodesにノードを追加する 追加したノードのインデックスを返す Parameters ---------- node : TrieNode 追加するノード Returns ------- index : int 追加したノードのインデックス """ self.nodes.append(node) return len(self.nodes) - 1 def __get_char_num(self, c): """ 文字のidを返す aが1, bが2, ..., zが26となる Parameters ---------- c : char idを取得したいしたい文字 Returns ------- id : int 文字のid """ return ord(c) - ord('a') def insert(self ,word, item, char_index=0, node_index=0): """ Trieに新しい単語を登録する Parameters ---------- word : str 登録する単語 item : str wordに対応する読み方 char_index : int 現在着目している文字の位置 node_index : int 現在着目しているノードの位置 """ char_num = self.__get_char_num(word[char_index]) next_node_index = self.nodes[node_index].children[char_num] if next_node_index == -1: # 現在のノードにword[char_index]での遷移がなかった場合 new_node = TrieNode() next_node_index = self.__add_node(new_node) self.nodes[node_index].children[char_num] = next_node_index if char_index == len(word) - 1: # 最後の文字だった場合 self.nodes[next_node_index].item = item else: self.insert(word, item, char_index+1, next_node_index) def query(self, word): """ 作ったTrieを検索する Parameters ---------- word : str 検索したい単語 Returns ------- item : str or None 検索結果 見つからなかった場合はNone """ node_index = 0 for c in word: char_num = self.__get_char_num(c) tmp_node = self.nodes[node_index] node_index = tmp_node.children[char_num] if node_index == -1: return None return self.nodes[node_index].item |
登録・検索
最後に、Trieクラスを利用して単語の登録、検索を行います。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | trie = Trie() trie.insert("a", "エー") trie.insert("ab", "エービー") trie.insert("abc", "エービーシー") trie.insert("b", "ビー") trie.insert("bc", "ビーシー") trie.insert("c", "シー") print(trie.query("a")) print(trie.query("abc")) print(trie.query("bc")) print(trie.query("abcd")) |
実行
このコードを実行すると、以下のような結果になります。
エー
エービーシー
ビーシー
None
辞書に登録した3単語はきちんと読み方が返ってきて、登録していない「abcd」という単語はNoneが返ることがわかります。
さいごに
トライ木は一見難しそうですが、一度理解してしまえば実装は、さほど難しくなかったと思います。
トライ木を用いると今回のような辞書だけでなく、「形態素解析機」「オートコンプリート」など、様々な分野に応用がきく便利なデータ構造です。
この期にぜひマスターしてみてください。
また、今回の実装では配列を用いた実装ということで、サイズがとても大きくなっています。
実際に使う際には「パトリシア木」「LOUDS」「ダブルアレイ」といった、サイズを小さくする工夫、実装を行います。
これについても、近いうちに記事にできたらと思います！
この記事の続き
こちらの記事もオススメ！
関連記事
書いた人はこんな人
- 「好きを仕事にするエンジニア集団」の（株）ライトコードです！
ライトコードは、福岡、東京、大阪の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エンジニア
