【前編】トリプルアレイで軽量で高速な辞書をつくる～準備～
2020.01.15
軽量で高速に検索できる辞書システムをつくる
トリプルアレイというデータ構造をご存知でしょうか。
「ダブルアレイ」は聞いたことがあっても、「トリプルアレイ」は知らないという方も多いのではないかと思います。
トリプルアレイは、ダブルアレイの元となったデータ構造で、ダブルアレイ同様トライ木を表現することができます。
基本的なアイデアは、トリプルアレイもダブルアレイも一緒です。
ただ、性能はダブルアレイのほうが良いです。
しかし、実装の簡単さから、トリプルアレイが適当な場合もあるかと思います。
そこで、今回は、トリプルアレイを用いて、軽量で高速に検索できる辞書システムを実装してみたいと思います。
トリプルアレイとダブルアレイ
元々、トリプルアレイは「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 を用います。
要件
要件は、トライ木、パトリシア木のときと同様です。
- 単語とその読み方のペアを登録する
- 単語を入力することで読み方を出力する
- 単語に使える文字は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 を元にトリプルアレイを構築します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | class TripleArray: """ トリプルアレイクラス Attributes ---------- NEXT : list 遷移先を格納するNEXT配列 CHECK : list 遷移元を格納するCHECK配列 OFFSETS : list ずらし幅を格納するOFFSETS配列 items : list 登録された単語の読み方 単語終端ノード以外の場合はNone trie : Trie トリプルアレイの元となるTrie木 """ def __init__(self, trie): self.CHECK = [-1] * 2 self.NEXT = [-1] * 2 # オフセットは-(VOCAB_SIZE)以下になることはない # 少し余裕をもたせて-(VOCAB_SIZE+10)で初期化する # (VOCAB_SIZEはTRIEクラスの方で定義されています) self.OFFSETS = [-(tr.VOCAB_SIZE+10)] * len(trie.nodes) self.items = [None] * len(trie.nodes) self.trie = trie self.make_triple_array() |
【後編】へ続く
以上で、準備が終わりました。
後半では、完成に向けて、実装していきたいと思います。
ライトコードよりお知らせ
にゃんこ師匠
ミツオカにゃんこ師匠ミツオカにゃんこ師匠ミツオカ一緒に働いてくれる仲間を募集しております！
ライトコードでは、仲間を募集しております！
当社のモットーは「好きなことを仕事にするエンジニア集団」「エンジニアによるエンジニアのための会社」。エンジニアであるあなたの「やってみたいこと」を全力で応援する会社です。
また、ライトコードは現在、急成長中！だからこそ、あなたにお任せしたいやりがいのあるお仕事は沢山あります。「コアメンバー」として活躍してくれる、あなたからのご応募をお待ちしております！
なお、ご応募の前に、「話しだけ聞いてみたい」「社内の雰囲気を知りたい」という方はこちらをご覧ください。
ライトコードでは一緒に働いていただける方を募集しております！
採用情報はこちら書いた人はこんな人
関連記事
採用情報
\ クリエイティブの最前線 /
フロントエンドエンジニア
\ 世界はお前の手の中に・・・ /
モバイルエンジニア
\ サービスの守り神！ /
インフラエンジニア
\ センスで挑め！ /
UI/UXデザイナー
\ 世界を震撼させろ！ /
WEB開発ディレクター
\ 妄想野郎カモン！ /
ゲームプランナー
\ ゲーム好き集合ー！ /
ゲームエンジニア
