1. HOME
  2. ブログ
  3. IT技術
  4. ダブルアレイで高速でコンパクトな辞書を実装してみた!

ダブルアレイで高速でコンパクトな辞書を実装してみた!

ダブルアレイを使って辞書を実装してみる

ダブルアレイは、トライ木を表現することができるデータ構造で、コンパクトで高速に辞書検索が行えるという特徴を持っています。

小さなサイズで、高速に辞書検索を行うことができるという特徴を持っています。

有名な形態素解析エンジンである「mecab」でも用いられています。

2本の配列を用いることでトライ木を表現

上の図のように、2本の配列を用いることでトライ木を表現します。

今回は、このダブルアレイについて解説をし、実際に辞書を実装、コードの解説も行っていきたいと思います!

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

以前の記事では、トリプルアレイについて紹介をしました。

ダブルアレイは、このトリプルアレイを元に、配列を一本取り除くことで、検索速度は(ほぼ)そのままで、よりコンパクトにトライ木を格納することができます。

※ダブルアレイとトリプルアレイの関係について、詳しくはダブルアレイの元論文である『An Efficient Digital Search Algorithm by Using a Double-Array Structure(JI-Aoe.1989)』に書かれています

ダブルアレイも、トリプルアレイと元となるアイデアは同じなので、トリプルアレイが理解できていればダブルアレイの理解も簡単です。

今回は、トリプルアレイの仕組みが理解できているという前提で、ダブルアレイについて解説していきます。

トリプルアレイについて自信のない方は、以前の記事を参考にしてください。

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


トリプルアレイの復習

ダブルアレイの元となるトリプルアレイについて、少しだけ確認をしておきます。

トリプルアレイは、以下の図のように構築されるもので、3本の配列でトライ木を表現します。

3本の配列でトライ木を表現

3本の配列には「NEXT」「CHECK」「OFFSET」という名前がつけられており、それぞれ以下のような役割を担っています。

NEXT : 次に遷移するノードを格納する
CHECK : 正しい遷移であることを確認するために遷移元(親ノード)のidを格納する
OFFSET : 各ノードのずらし幅を格納する

このうち、「NEXT」と「CHECK」は同じ大きさとなります。

「OFFSET」だけ異なり、ノード数分の大きさとなります。

ダブルアレイ構築方法

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

今回は以前解説した、「トリプルアレイ」を利用して構築していきます。

トリプルアレイについては、以前の記事を参照してください。

トリプルアレイを2本の配列で表現するために、OFFSETを削除することを考えます。

そのためにまず、OFFSETが遷移の際にどんな役割をしているかを見てみましょう。

OFFSETの役割

この図から、OFFSETは「ノードのずらし幅を得るため」に使われていることがわかります。

このため、もしOFFSETを用いずにNEXTから直接ずらし幅が得ることができれば、OFFSETは不要となります。

NEXTから直接ずらし幅を得る」というのは実はとても簡単で、NEXTにノードidではなくそのノードのずらし幅を直接格納しておけばよいのです。

このノードidの代わりにずらし幅を格納されたNEXTは、BASE配列とよばれます。

ここまでで、OFFSETを削除することができました。

CHECK配列について

しかし、これによりノードidの情報が失われてしまったので、ノードidによって正しい遷移であることを確認していたCHECK配列の方に問題がおきてしまいます。

これもさほど難しくなく、以下の図のようにCHECK配列にノードidの代わりにBASE配列上での遷移元のindexを保存しておけばよいです。

これは元のCHECK配列の要素を、NEXT配列のおなじ要素があるindexに置き換えることでできます。

ここまでで、ダブルアレイは完成です。

遷移が可能かの確認

実際に、遷移が可能かどうかを確認しましよう。

単語idが「0」である「a」と単語idが「2」である「c"」いう単語が順に入力された場合の遷移を考えます。

最初は、ルートノードにいます。

(1) ルートノードのずらし幅は0ですので、index = 0+(aの単語id) = 0+0 = 0

(2) CHECK[0]をみると、CHECK[0] = -1です。
-1はルートノードを表すことにしているので、正しく遷移できています。

(3) BASE[0]をみます。
BASE[0] = -1 ですので、次のずらし幅は-1ということがわかります。

ここまでで、「a」の入力の処理が終わり、現時点でindexは「0」となります。

「c」の入力の処理

続いて、「c」の入力の処理に移ります。

(4) index = -1 + (cの単語id) = -1 + 2 = 1
CHECK[1]をみると、CHECK[1] = 0です。

(5) 前のindexは0だったので、正しく遷移できています。
cの次は入力が無いのでindex = 1の位置で終了です。

以上でBASEとCHECK配列で、ダブルアレイの構築は完了です。

ダブルアレイの実装(準備)

それでは、実際に、ダブルアレイを実装し、辞書システムを作っていきましょう!

言語は、Pythonを用います。

ダブルアレイの実装にはいくつか方法がありますが、今回は「トリプルアレイが構築された状態から、ダブルアレイに変換する」という方法で実装します。

要件

要件は以下です。

トリプルアレイのときと同様です。

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

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

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

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

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

なお、ダブルアレイでは以前の記事で作成した、TripleArrayクラスを用いています。

DoubleArrayクラスは、BASECHECKitemsという3つの変数を持ちます。

BASEは、トリプルアレイのオフセットと同じ長さとなるので、TripleArrayのOFFSETSと同じ長さで初期化します。

CHECK、itemsは、トリプルアレイのCHECKと同じ長さで初期化します。

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

ダブルアレイ実装(構築部分)

TripleArrayクラス から、ダブルアレイを構築する make_double_array() を実装していきます。

このメソッドは、TripleArray の NEXT、CHECK配列を書き換えることでダブルアレイを構築していきます。

トリプルアレイで、ずらす処理などは終わっているので、以下の2つの処理をすれば完了です。

1.  NEXT をノードidではなく、ずらし幅に変更して BASE を作成
2.  CHECK をノードidでなく、index に変更

コード

解説

1ループ目で TripleArray の OFFSETS から BASE を作成、また items も作成します。

さらに、後に CHECK を作成する際に、ノードid からそのノードを表す NEXT の index を得やすいように node_to_index という配列を作成しておきます。

2ループ目では、 node_to_index から新しい CHECK配列 を作成しています。

ダブルアレイ実装(検索部分)

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

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

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

コード

ダブルアレイの実装(全体)

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

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

全体のコード

構築、検索の実験

最後に、ダブルアレイの構築、検索の実験を行います。

結果

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

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

さいごに

お疲れさまでした!

ダブルアレイを理解するのはかなり難しいかもしれませんが、非常に実用的なデータ構造です。

トリプルアレイから理解していけば、ダブルアレイも必ず理解できるようになるはずです。

ぜひチャレンジしてみてくださいね!

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


関連記事

書いた人はこんな人

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

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

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

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

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

関連記事

採用情報

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

バックエンドエンジニア

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

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

\ 世界を変える…! /

Androidエンジニア

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

iOSエンジニア