1. HOME
  2. ブログ
  3. IT技術
  4. 【後編】トライ木で高速な辞書を実装する

【後編】トライ木で高速な辞書を実装する

はじめに〜後編〜

今回は、前編に引き続き、最終的に単語とその読み方を入力としたトライ木を構築し、単語を入力することでその読み方を出力する辞書システムを作成したいと思います。

トライ木は、テキストを扱う際に良く用いられているデータ構造で、文字列を非常に高速に検索することができるため、辞書の実装などに利用されています。

【前編】の記事は、こちらです。

トライ木の実装(構築部分)

前章で作ったTrieクラスに単語を登録し、トライ木を構築するためのinsertメソッドを実装します。

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メソッドを実装します。

queryメソッドは、入力された単語を一文字ずつ見て、トライ木を辿っていきます。

最終的に、単語の終端となるノードのインデックスを取得し、そのノードに保存された item を返します。

コード解説

まず、1行目で現在着目しているノードを表すnode_indexを先頭文字のノードである0に初期化します。

次に、3行目から始まるループで、単語を1文字ずつ見ていきます。

5行目では、現在着目している文字に対応するノードである tmp_node を取得しています。

7行目で、次に遷移するべきノードの index を取得します。

このとき、遷移すべきノードがなかった場合は、その単語が辞書に登録されていないことになるので、Noneを返します。(8行目の分岐)

トライ木の実装(全体)

ここまでで、トライ木を用いた辞書の実装が終わりました

構築部分と検索部分をまとめたコードは以下のようになります。

登録・検索

最後に、Trieクラスを利用して単語の登録、検索を行います。

実行

このコードを実行すると、以下のような結果になります。

エー
エービーシー
ビーシー
None

辞書に登録した3単語はきちんと読み方が返ってきて、登録していない「abcd」という単語はNoneが返ることがわかります。

終わりに

お疲れ様でした。

トライ木は一見難しそうですが、一度理解してしまえば実装は、さほど難しくなかったと思います。

トライ木を用いると今回のような辞書だけでなく、「形態素解析機」「オートコンプリート」など、様々な分野に応用がきく便利なデータ構造です。

この期にぜひマスターしてみてください。

また、今回の実装では配列を用いた実装ということで、サイズがとても大きくなっています。

実際に使う際には「パトリシア木」「LOUDS」「ダブルアレイ」といった、サイズを小さくする工夫、実装を行います。

これについても、近いうちに記事にできたらと思います。

ライトコードよりお知らせ

にゃんこ師匠にゃんこ師匠
システム開発のご相談やご依頼はこちら
ミツオカミツオカ
ライトコードの採用募集はこちら
にゃんこ師匠にゃんこ師匠
社長と一杯飲みながらお話してみたい方はこちら
ミツオカミツオカ
フリーランスエンジニア様の募集はこちら
にゃんこ師匠にゃんこ師匠
その他、お問い合わせはこちら
ミツオカミツオカ
   
お気軽にお問い合わせください!せっかくなので、別の記事もぜひ読んでいって下さいね!

一緒に働いてくれる仲間を募集しております!

ライトコードでは、仲間を募集しております!

当社のモットーは「好きなことを仕事にするエンジニア集団」「エンジニアによるエンジニアのための会社」。エンジニアであるあなたの「やってみたいこと」を全力で応援する会社です。

また、ライトコードは現在、急成長中!だからこそ、あなたにお任せしたいやりがいのあるお仕事は沢山あります。「コアメンバー」として活躍してくれる、あなたからのご応募をお待ちしております!

なお、ご応募の前に、「話しだけ聞いてみたい」「社内の雰囲気を知りたい」という方はこちらをご覧ください。

ライトコードでは一緒に働いていただける方を募集しております!

採用情報はこちら

関連記事