【前編】トライ木で高速な辞書を実装する
2019.08.08
はじめに〜前編〜
皆さんはトライ木（英: 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 41 | Python 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] |
後編に続く
【後編】の記事は、こちらです。
ライトコードよりお知らせ
にゃんこ師匠
ミツオカにゃんこ師匠ミツオカにゃんこ師匠ミツオカ一緒に働いてくれる仲間を募集しております！
ライトコードでは、仲間を募集しております！
当社のモットーは「好きなことを仕事にするエンジニア集団」「エンジニアによるエンジニアのための会社」。エンジニアであるあなたの「やってみたいこと」を全力で応援する会社です。
また、ライトコードは現在、急成長中！だからこそ、あなたにお任せしたいやりがいのあるお仕事は沢山あります。「コアメンバー」として活躍してくれる、あなたからのご応募をお待ちしております！
なお、ご応募の前に、「話しだけ聞いてみたい」「社内の雰囲気を知りたい」という方はこちらをご覧ください。
ライトコードでは一緒に働いていただける方を募集しております！
採用情報はこちら書いた人はこんな人
関連記事
採用情報
\ クリエイティブの最前線 /
フロントエンドエンジニア
\ 世界はお前の手の中に・・・ /
モバイルエンジニア
\ サービスの守り神！ /
インフラエンジニア
\ センスで挑め！ /
UI/UXデザイナー
\ 世界を震撼させろ！ /
WEB開発ディレクター
\ 妄想野郎カモン！ /
ゲームプランナー
\ ゲーム好き集合ー！ /
ゲームエンジニア
