fbpx
  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のリストとなります。

後編に続く

次回(後編)は、実際に「実装」していきたいと思っております。

後編に続きます!

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

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

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

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

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

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

採用情報はこちら

関連記事