辞書検索のデータ構造

はじめに

Sudachi をはじめとするおおくの形態素解析器は辞書に語の情報を記録することで分割や品詞、読み、表記の正規化などの情報を提供しています。この辞書の中で実装上もっとも重要なのが、語の表記をキーとしその語の情報 (へのポインタ) を値とする key-value store です。辞書を利用する形態素解析では、解析時間のおおくをこの key-value store の検索についやすため、その実装にはさまざまな工夫がなされてきました。

TRIE

TRIE は木構造をつかった検索のためのデータ構造です。木のルートからはじめてキーにしたがって枝をたどり、末端にある葉に到達すれば検索成功で、葉から値を得ることができます。

上の図では「す」「すだち」「すだち酢」「すだつ」「酢」「酢橘」が格納されています (「#」は文字列の終端をあらわす特殊記号とします)。辞書型の形態素解析では入力の先頭から可能性のある語をすべて列挙しますが (共通接頭辞検索; common prefix search)、このような構造であれば「す」→「だ」→「ち」→「酢」とたどるだけで (途中で終端記号の確認をすれば) 「す」「すだち」「すだち酢」をえることができます。

TRIE の実装あれこれ

木構造を実装する際、そのままノードや枝をデータ構造におこすとかなり冗長になります。そのため配列などを利用するのがするのが一般的です。各ノードを配列であらわし配列の i 番目にそのノードからラベル i で遷移する先のノードのポインタをいれておけば、ノード数×ラベル数のサイズの配列で TRIE を実装することができます。

ラベル数は枝をたどるときにキーをどのぐらいずつみるかでかわってきます。1ビットずつ区切ると2分木になり木としての圧縮率はたかくなりますがノードがおおくなり検索速度がおちます。文字単位で区切ると Unicode であれば32ビットずつなので4,294,967,296分木になり、かなりスパースになります。1バイトずつ区切ると256分木で圧縮率も検索速度もそれほどわるくありません。

この方法だと n 分木の n がおおきくなると遷移のないラベルがおおくかなり空間がむだになりますが、空いている部分に他のノードを埋め込むことでうまく圧縮することに成功したのがダブル配列です。Sudachi や MeCab、ChaSen はダブル配列を TRIE に利用しています。

また TRIE 構造の末端付近は分岐のない1本道になりがちなので、その部分は TRIE とはべつの構造としてもつ (tail とよびます) 手法もあります。末端だけでなく分岐のない部分はすべて圧縮して分岐のある部分だけをのこしたパトリシア (Patricia) 木は ChaSen の旧版や kuromoji (実装は FST) でもちいられています。ほかにも簡潔データ構造で TRIE を表現した LOUDS も利用されています。

DAG

Sudachi で利用している Darts-clone は木構造だけではなく、有向非循環グラフ (directed acyclic graph; DAG) がつかえるように実装されています。木構造と DAG はかならずルートから葉にむかうところはおなじですが、木構造がいちどわかれたらそのまま交わらないのにたいして、DAG は枝分かれのあと再合流可能なところがちがいます。非循環なのでおなじノードにもどってはいけません。

上の図は「引っ越し」「引越し」「引越」「引っ越」「ひっこし」「引っこし」「ひっ越し」「ひっ越」がおなじ値をもつ key-value store になっています。このように部分木が共有されるので木構造にくらべてコンパクトに表現することができます。仮名へのひらき、送り仮名の有無など異表記がおおい日本語ではとくに効果を発揮します¹。

この構造は木構造にくらべて末端側におなじ部分木がおおいほど効率がよくなるので、n-gram 頻度の格納のようにキーの数にくらべて値のバリエーションがすくない場合はさらに効果的です。

オートマトン

さらに、循環をみとめてオートマトンにすることもできます。

オートマトンをつかうと構造がコンパクトになるというメリットだけでなく、キーに正規表現をつかえるようになり表現できる範囲が一段ひろくなります。たとえば上の図のように「はい」「はーい」「はーーい」「はーーーーーーーーーーーーーい」などすべて列挙できないような場合でも「はー*い」だけで表現できるようになります²。

AC 法

辞書をつかった形態素解析では TRIE のところでのべたように共通接頭辞検索をもちいて可能性のある語をすべて列挙しますが、その際、先頭から1文字ずつずらしながら何度も共通接頭辞検索をおこないます。辞書に {徳島, 徳島研究所, 研究, 研究所} だけが格納されているとして、入力「徳島研究所」にたいして0文字目からみて {徳島, 徳島研究所} を取得、つぎに1文字目からみて { }、2文字目から {研究, 研究所}、3文字目以降は { } とすすむわけですが、辞書にどんな語がはいっているのかがわかっていれば0文字目と2文字目以外の共通接頭辞検索が失敗するのは最初の走査の段階で自明になります。こういった場合 Aho-Corasick 法 (AC 法) をつかって検索を高速化することが可能です³。AC 法では検索に失敗したときの遷移を工夫することで入力文字列を1回走査するだけですべての候補をえることができます。

くわえて、AC 法を決定性有限オートマトン (DFA) に変換することでさらに高速化できることがしられています⁴。さすがにここまでくるとかなり慎重に実装しないと大変そうですが、単語分割器 Vaporetto は n-gram 素性の列挙のためにダブル配列をつかって DFA と同程度の速度で AC 法を実現しています (daachorse)。すごい。

さいごに

辞書引きの検索構造として TRIE、DAG、オートマトンをみてきました。ほかにも単語 bigram のように大規模な辞書のための構造としてハッシュ関数をつかった Bloom filter 系の確率的アルゴリズムなども実用されています。

Sudachi では保守の問題やユーザー辞書の存在もあって、検索のためのデータ構造は比較的単純な TRIE にとどまっています。ただ解析時間のかなりの割合がこの辞書検索についやされているのはたしかなので、こんごも工夫をつづけていきたいところです。

ではよい Sudachi life を。

1. Sudachi では異表記間で語情報を共有できない (「辞書ソースのつかっていないカラムの話 その1」参照) ので DAG ではなく木構造をつかっています。 ↩

2. kuromoji の辞書は FST (finite state transducer) で実装されていますが正規表現を格納する機能はありません。 ↩

3. Hiroshi Maruyama, Backtracking-free dictionary access method for Japanese morphological analysis, COLING '94: Proceedings of the 15th conference on Computational linguistics, Vol. 1, pp. 208–213, 1994, https://doi.org/10.3115/991886.991921 ↩

4. 森信介, DFA による形態素解析の高速化, 情報処理学会研究報告. NL,自然言語処理研究会報告, Vol. 114, pp. 101-107, 1996, https://cir.nii.ac.jp/crid/1570291227269265792 ↩