1. HOME
  2. ブログ
  3. IT技術
  4. トライ木をビットスライスとパトリシア木でコンパクトにしてみた!

トライ木をビットスライスとパトリシア木でコンパクトにしてみた!

「ビットスライス」「パトリシア木」を用いて、トライ木の問題点を解決したい!

前回の記事では、トライ木というデータ構造を紹介し、トライ木を用いた辞書の実装を行いました。

トライ木は、非常に高速で文字列を検索できる優れたデータ構造ですが、問題点もあります。

本記事では、まず、トライ木の問題点について説明します。

その後、その解決方法である「ビットスライス」「パトリシア木」を用いて、前回と同様の辞書システムを実装します。

前回の記事

このトライ木の問題点

前回の記事で実装したトライ木には、サイズが大きくなりやすいという問題点があります。

前回の実装にて、トライ木の1つのノードは、以下のように定義されていました。

このうち、問題となるのは、子ノードのリストである children です。

前回の実装では、 children はアルファベット数分のサイズを持つリスト(配列)として保持されていました。

これにより、トライ木全体のサイズは少なくとも「ノード数 × アルファベット数」となります。

前回は、ascii文字のみの対応だったため、アルファベット数は「128」でした。

しかし…例えば日本語に対応しようとした場合、「ひらがな」「カタカナ」「漢字」と、アルファベット数は「数千」、あるいは「数万」にもなります。

これは、とてもメモリ上に保持できるサイズではありません。

そこで今回は、このトライ木のサイズを削減するためにビットスライスという手法と、パトリシア木という木構造を紹介します。

ビットスライス

まずは1つ目の手法である、ビットスライスを紹介します。

この手法は、トライ木のサイズ(ノード数 × アルファベット数)のうち、アルファベット数を少なくするための手法です。

コンピュータ上では、「a」や「b」といった文字は、ビット列として表現されています。

そこで、「a」や「b」といった文字をビット列に分解し、分解されたビットを文字の代わりにアルファベットとして用いることで、アルファベット数を少なくすることができます。

1ビットで表現できるのは「0」と「1」ですから、この手法によりアルファベット数は「2」となります。

上の図は、「a」という単語が格納されたトライ木をビットスライスにするものです。

上の図において、左のシンプルなトライ木を、「a」が「0001」というビット列で表されると仮定して、ビットスライスしています。

ビットスライスの問題点

アルファベット数を大幅に減らすことができるビットスライスですが、この手法にも問題点があります。

先程の図を見た時点でお気づきの方もいらっしゃるかと思いますが、ビットスライスを用いるとアルファベット数が減るかわりにノード数が増えます

本来1文字である「a」という文字をビット列で表すと、(4ビットで表されていた場合)「0001」という様に4文字分になります。

これにより、アルファベット数は「2」になりますが、ノード数は4倍になってしまいます。

このノード数が増加してしまうという問題を解決するために、パトリシア木というデータ構造を用います。

パトリシア木

パトリシア木は、Trie木のノード数を削減できるデータ構造です。

トライ木では、1つのノードには1つのアルファベットが対応していました。

しかし、パトリシア木では下の図のように分岐がないノードを省略し、1つのノードに複数のアルファベットを対応させることでノード数を削減しています。

パトリシア木の実装(準備)

それでは、実際にパトリシア木を実装し、辞書システムを作っていきます。

言語は、「Python(パイソン)」を用います。

要件

トライ木の記事のときの要件に、サイズに関する要件が加わりました。

  1. 単語とその読み方のペアを登録する
  2. 単語を入力することで読み方を出力する
  3. 単語に使える文字はasciiのみ
  4. ビットスライス、パトリシア木を用い、できるだけサイズを小さくする

単語とその読み方のペアとして、今回も前回同様以下のデータを用います。

では、準備段階としてパトリシア木の実装に用いる構造体から作っていきましょう。

  1. パトリシア木のノードを表すPatriciaNodeクラス
  2. パトリシア木の実体を表すPatriciaクラス

今回は、パトリシア木のノードを表すPatriciaNodeクラスと、パトリシア木の実体を表すPatriciaクラスを用います。

PatriciaNodeクラス

まずは、PatriciaNodeクラスについて紹介していきます。

PatriciaNodeクラスは、3つの変数を持ちます。

item

item は、辞書引きを行った際にとってきたい情報です。

今回は、読み方を引いてくる辞書なので、itemには登録する単語の読み方が入ります。

children

children は、どの文字でどのノードに遷移するかを表したリストです。

今回は、アルファベット数(VOCAV_SIZE)が2なので大きさは2となります。

sub_str

sub_str は、トライ木では必要なかった新たな変数です。

パトリシア木では、1つのノードに複数のアルファベット(ビットスライスの場合はビットとなる)が対応するため、何ビット目をチェックすれば良いのか分からなくなってしまいます。

そこで、 sub_str として対応するアルファベットを保持しておくことで、どのビットを比較すれば良いかが分かるようにします。

Patriciaクラス

続いて、Patriciaクラスの説明を行います。

Patriciaクラスは、パトリシア木の実体を表すクラスで、 nodes という変数を持ちます。

nodes

nodes は、PatriciaNodeのリストとなります。

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

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

が、先に「挿入」「検索」どちらの処理でも共通して使う __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 となっていることが分かります。

まとめ

お疲れ様でした!

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

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

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

こちらの記事もオススメ!


関連記事

書いた人はこんな人

広告メディア事業部
広告メディア事業部
「好きを仕事にするエンジニア集団」の(株)ライトコードです!

ライトコードは、福岡、東京、大阪の3拠点で事業展開するIT企業です。
現在は、国内を代表する大手IT企業を取引先にもち、ITシステムの受託事業が中心。
いずれも直取引で、月間PV数1億を超えるWebサービスのシステム開発・運営、インフラの構築・運用に携わっています。

システム開発依頼・お見積もり大歓迎!

また、現在「WEBエンジニア」「モバイルエンジニア」「営業」「WEBデザイナー」「WEBディレクター」を積極採用中です!
インターンや新卒採用も行っております。

以下よりご応募をお待ちしております!
https://rightcode.co.jp/recruit

関連記事

採用情報

\ あの有名サービスに参画!? /

バックエンドエンジニア

\ クリエイティブの最前線 /

フロントエンドエンジニア

\ 世界を変える…! /

Androidエンジニア

\ みんなが使うアプリを創る /

iOSエンジニア