fbpx
  1. HOME
  2. ブログ
  3. IT技術
  4. 【後編】ビットスライスとパトリシア木でトライ木をコンパクトにする

【後編】ビットスライスとパトリシア木でトライ木をコンパクトにする

ビットスライスとパトリシア木でトライ木をコンパクトにする~後編~

後編では、いよいよ「実装」していきたいと思います。

前編はこちらになります。

パトリシア木実装(補助メソッド)

それでは、パトリシア木の中身を実装していきます。

が、先に「挿入」「検索」どちらの処理でも共通して使う __search_longest_match() というメソッドの解説を行います。

__search_longest_match() についての解説

  1. __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_str0000rest_str は 1011 となります。

__search_longest_match() の実装を単純にするために、2つの文字列が先頭から何文字目まで一致しているかを調べる __match() メソッドも作成しています。

コード

コード解説

__search_longest_match() メソッドのコードを少し解説します。

__search_longest_match() は、一度呼び出されるごとにノードを1つ巡り、再帰的に呼び出されることで最後のノードまで巡ります

まず、 match_str = word_b[:match_num] までで、現在着目しているノードが対応するアルファベット列( sub_str )に対して、 match_strrest_str を求めます。

match_strrest_str は、先程説明したとおり、検索文字列が sub_str に対して一致した部分と、一致しなかった部分を表します。)

このとき、 match_str が検索文字列である word_b と完全に一致した場合、そのノードで丁度探索が終了したことになるので、その時点の node_index 、 rest_strmatch_str を返します。

続いて、現在のノードの情報と、残りの検索文字列を用いて、次のノードへの遷移を行います。

このとき、次のノードが存在しなかった場合は、パトリシア木の末端まで探索し終わったことになるので、この時点で return します。

遷移に成功した場合は、 __search_longest_match() を再帰的に呼び出します。

パトリシア木実装(挿入部分)

パトリシア木に単語を挿入するための insert() メソッドを実装していきます。

パトリシア木における挿入処理は、分岐のないノードを省略するために、やや複雑な処理を必要とします。

パトリシア木の挿入処理は、大きく2パターンに分けられます。

  1. 1つ目は、挿入の際に既存のノードの変更が必要なもの。
  2. 2つ目は、既存のノードの変更が必要ないものです。

図を用いて説明していきます。

パターン1

上の図は、単語「a」, 「b」, 「abc」が格納されているパトリシア木に「ab」というノードを追加するものです。

この場合は、既存のノードの変更が必要な場合になります。

この場合、新たな「ab」のノードは、「a」のノードと「abc」のノードの間に挿入されることになります。

「ab」のノードを「a」のノードの下に挿入したとき、「a」のノードの遷移先は「abc」のノードから変更されることになります。

また、「ab」のノードの下につく「abc」のノードについても、 sub_str を変更する必要があります。

一方、既存のノードに変更が必要ない場合もあります。

パターン2

上の図は、先程のパトリシア木に「ba」という単語を追加するものです。

この場合、以下の図のように、既存ノードを変更する必要なく挿入することができます。

このようにパトリシア木では、単語を挿入する際に、ただノードを追加するだけでなく、既存のノードを変更する必要が生じる場合もあります。

コード

これを踏まえて、insert()メソッドのコードを見ていきましょう。

コード解説

まずは、 node_index 、 node_rest_strrest_strmatch_str を求めます。

それぞれの変数の意味は、コメントに書いてあるとおりです。

次に、条件分岐からノードを追加していきます。

条件に当てはまる場合は、ノードを追加するだけでなく既存のノードの変更を必要とします。

条件に当てはまる場合(rest_strがある場合)は、さらに新しいノードを付け加える必要があります。

パトリシア木の実装(検索部分)

続いて、検索部分の実装を行っていきます。

とはいえ、 __search_longest_match() の実装が終わっているので、ここは簡単です。

コード

こちらがコードとなります。

コード解説

__search_longest_match() を実行し、 node_indexrest_strmatch_str と、 node_rest_str を取得しています。

検索単語が存在する場合というのは、条件にあるように、 node_rest_strrest_str が空のとき、つまり、ノードの文字列と検索文字列が完全に一致したときです。

よって、このときのみ対応する item return し、それ以外の場合は単語が存在しないので None return します。

パトリシア木の実装(全体)

ここまでで、パトリシア木を用いた辞書の実装が終わりました

すべてのコードをまとめたものが以下になります。

コード

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

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

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

辞書に insert した単語は、きちんと読み方が表示され、そうでない単語は None となっていることが分かります。

終わりに

お疲れ様でした!

パトリシア木は、トライ木に比べるとやや複雑で理解しにくかったかもしれません。

しかし、一度理解し使えるようになれば、高速でサイズの小さい使い勝手の良いデータ構造です。

トライ木がわかっていればそこまで難しくないと思うので、ぜひチャレンジしてみてください。

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

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

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

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

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

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

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

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

採用情報はこちら

関連記事