1. HOME
  2. ブログ
  3. IT技術
  4. トリプルアレイで軽量で高速な辞書を作ってみた!

トリプルアレイで軽量で高速な辞書を作ってみた!

軽量で高速に検索できる辞書システムをつくる

トリプルアレイというデータ構造をご存知でしょうか?

「ダブルアレイ」は聞いたことがあっても、「トリプルアレイ」は知らないという方も多いのではないかと思います。

トリプルアレイは、ダブルアレイの元となったデータ構造で、ダブルアレイ同様トライ木を表現することができます。

基本的なアイデアは、トリプルアレイもダブルアレイも一緒です。

ただ、性能はダブルアレイのほうが良いです。

しかし、実装の簡単さから、トリプルアレイが適当な場合もあるかと思います。

そこで、今回は、トリプルアレイを用いて、軽量で高速に検索できる辞書システムを実装してみたいと思います。

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


関連記事

トリプルアレイとダブルアレイ

元々、トリプルアレイは「YACC」や「LEX」といったツールで使われていた技術です。

これを検索に特化し改良したものとして、「ダブルアレイ」が生まれました。

※詳しくは『An Efficient Digital Search Algorithm by Using a Double-Array Structure(JI-Aoe.1989)』という論文に書かれています。

ただ、トリプルアレイも、Trie木を表現できるデータ構造なので、辞書検索に利用することができます。

ダブルアレイ

ダブルアレイの方がメモリ効率が良く、検索速度もトリプルアレイと同等であるため、できればダブルアレイを用いたほうが良いです。

しかし、その分、仕組みがやや複雑になるため、理解、実装するのがやや難しいという面があります。

トリプルアレイ

一方、トリプルアレイは、メモリ効率はダブルアレイに劣りますが、仕組みはダブルアレイほど複雑でないため、理解、実装が比較的簡単にできます。

トリプルアレイでは、その名の通り3本の配列を利用することでトライ木を表現します。

下記図の左側、配列で表現されたトライ木では無駄な要素が多く、メモリ効率が非常に悪いです。

右側のトリプルアレイでは、この隙間を無くし、よりコンパクトにトライ木を格納することができます。

以前の記事はこちら

トライ木の配列表現がよく分からない方は、以前の記事を参照してください。

トリプルアレイ構築方法

それでは、トリプルアレイの構築方法について解説していきます。

トリプルアレイは、トライ木の配列表現を利用して構築していきます。

まず、トライ木の配列表現の各行を、要素がぶつからないようにずらし、潰して一本の配列にします。

この配列が、トリプルアレイの一本目の配列、NEXT配列になります。

また、この際に各行のずらし幅を2本目の配列、OFFSET配列として記録しておきます。

ここで、このトライ木において、ノード1 にいる状態で「c」を入力し、ノード3 に遷移する場合を考えます。

配列表現においては、まず ノード1 の行をみます。

この ノード1 の配列を TRIE[1] と表すことにします。

入力される文字「c」の単語idは「2」です。

ここから、遷移先は TRIE[1][2] に格納されていることが分かります。

ここにある数字が3なので、ノード3 の行に遷移する となります。

NEXT配列とOFFSET配列を用いて、同様の遷移をすることを考える

まずは、NEXT配列 のなかで、ノード1 に対応する場所を見つける必要があります。

NEXT配列は、配列表現の各行をずらして潰した配列ですので、ノード1 の行のずらし幅が分かれば、ノード1 が NEXT配列 においてどこから始まるのかが分かります。

ノード1 のずらし幅は、OFFSET配列の1の位置(OFFSET[1])に入っています。

OFFSET[1] をみると、ずらし幅は「-1」です。

ここから、ノード1 は NEXT[-1] から始まることがわかります。

(ノード1 の配列が-1の位置からはじまるというだけで、実際には NEXT[-1] に要素は保存されていません。)

次に、ノード1 において「c」が入力された場合に対応する位置を探します。

NEXT配列 を作成する際に各行をずらしましたが、各行内での要素の位置関係は変わっていません。

そのため、「c」の単語idである「2」をずらし幅に足した NEXT[-1+2] に遷移先が格納されています。

NEXT[1] の要素は「3」ですので、ノード3 に遷移することがわかります。

このように、「NEXT配列」と「OFFSET配列」があれば、トライ木を遷移していくことが可能です。

問題点

しかし、この2本だけでは1つ問題点があります。

例)
ノード1において、今度はこのトライ木格納されていない「d」が入力された場合を考えます。
先程と同様に、OFFSET配列 からずらし幅が「-1」であることがわかり、これに「d」の単語idである「3」を足した NEXT[2] に遷移先の情報が入っていることがわかります。
NEXT[2] は、「2」となっています。

これはおかしいです。

ノード1 における「d」、は本来格納されていない単語なので、どこにも遷移できないはずですが、ノード2 に遷移することになっています。

この「2」というのは実は、ノード0 において「c」が入力された際に遷移する先です。

このように、NEXT配列 と OFFSET配列 だけで遷移すると、NEXT配列 の要素がどのノードからの遷移情報であるかが分からないため、誤った場所に遷移してしまいます。

この問題を解決するために、CHECK配列を導入します。

CHECK配列

CHECK配列 には、NEXT配列 の同じ位置にある要素が、どのノードからの遷移情報を表しているかを格納しておきます。

CHECK配列 を導入した状態でもう一度、ノード1 で「d」が入力された場合を考えます。

先程同様、OFFSETと「d」のidから、NEXT[2] に遷移先の情報が入っていることが分かります。

ここで、CHECK[2] をみると、「0」となっています。

いまは、ノード1 からの遷移をしようとしており、ノード0ではありません。

ここから、ノード1 から「d」では遷移できない。

つまり、この単語は格納されていないということが分かります。

以上、「NEXT配列」「OFFSET配列」「 CHECK配列」でトリプルアレイの構築は完了です。

トリプルアレイの実装(準備)

いよいよ、実際にトリプルアレイを実装し、辞書システムを作っていきましょう!

言語は、Python を用います。

要件

要件は、トライ木、パトリシア木のときと同様です。

  1. 単語とその読み方のペアを登録する
  2. 単語を入力することで読み方を出力する
  3. 単語に使える文字はasciiのみ

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

単語読み方
aエー
abエービー
acエーシー
abcエービーシー
bcビーシー

構造体を作る

まずは、準備段階として、構造体から作っていきます。

TripleArrayクラス

今回は、 TripleArray というクラスを作成します。

なお、トリプルアレイは、トライ木を元に作成するため、以前の記事で作成したTrieクラスを用いています。

TripleArrayクラスは、「NEXT配列」「CHECK配列」「OFFSETS配列」と「items」「 trie」の5つの変数を持ちます。

NEXT配列とCHECK配列

NEXT配列 と CHECK配列 は、構築するまでどのくらいの長さになるのか分かりません。

そのため、まずは 長さ2 で初期化し、構築中に長さが足りなくなったら伸ばすというようにします。

OFFSETS配列

OFFSETS(ずらし幅)は、負の値になることもあるので、要素が入っているかどうかを判断するために十分小さな値で初期化します。

実装

__init__() 関数の最後の行で、後に説明する make_triple_array() を呼び出し、trie を元にトリプルアレイを構築します。

トリプルアレイ実装(構築部分)

Trieクラスからトリプルアレイを構築する make_triple_array() を実装していきます。

このメソッドは、trieのノードに一つずつ以下の処理を適応することで、3つの配列を構築していきます。

  1. 要素がぶつからないずらし幅を見つける(find_offset)
  2. 見つかったずらし幅で、3つの配列に挿入する(update_arraies)
  3. NEXTの長さが足りない場合は、倍に増やす(resize_arraies)

コード

基本的には、1ノードずつずらし幅を見つけて(find_offset)挿入する(update_arraies)だけなので、トリプルアレイの仕組みが理解できていれば問題ないと思います。

コード中にかなり詳しくコメントを書いたので参考にしてください。

トリプルアレイ実装(検索部分)

続いて、検索を行う query() を実装していきます。

こちらは、検索文字列を一文字ずつループすることで、トリプルアレイを遷移していきます。

最後のノードにたどり着いたら、items に格納されているそのノードに対応する要素を返します。

トリプルアレイの実装(全体)

ここまでで、トリプルアレイを用いた辞書の実装が完了です。

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

コード

トリプルアレイの構築、検索

最後に、トリプルアレイの構築、検索を行います。

結果

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

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

さいごに

お疲れさまでした!

トリプルアレイは、ダブルアレイに比べると簡単ですが、それでもきちんと理解するのは難しいかもしれません。

それでも、一度きちんと実装してみれば、必ず理解できるはずです。

また、トリプルアレイさえ理解できれば、ダブルアレイの理解も簡単になるので、ぜひチャレンジしてみてください!

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


関連記事

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

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

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

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

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

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

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

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

採用情報はこちら

書いた人はこんな人

ライトコードメディア編集部
ライトコードメディア編集部
「好きなことを仕事にするエンジニア集団」の(株)ライトコードのメディア編集部が書いている記事です。

関連記事

採用情報

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

バックエンドエンジニア

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

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

\ 世界はお前の手の中に・・・ /

モバイルエンジニア

\ サービスの守り神! /

インフラエンジニア