はじめに

業務で自然言語処理をしていて何かと高速化を求められる場面が多く、辞書引きアルゴリズムという言葉に行き着いた。
自然言語処理界隈で深層学習が幅を利かせすぎているせいか、辞書引きアルゴリズムと聞いても同じようにピンとこない人の方が多そう。

辞書引きアルゴリズムとは

テキスト中の有り得る全ての部分文字列から辞書にある単語を引いてくるアルゴリズムのこと。
形態素解析とかの処理の裏側を支えている。
この道を極めるとMeCabとかJumanとかが作れるらしい。
例えば、abcという文字列が与えられた場合、部分文字列は以下のようになる。

これらの部分文字列が辞書にあるかどうかを調べていく。
要するに文字列の中から辞書内の単語を引っ張ってくるアルゴリズム、といった感じである。

この部分文字列の列挙の計算量は$O(N^2)$であるが、この時点でアプリケーションとして実用化には程遠い。($O(N)$が望ましい)

ちなみに、辞書はハッシュと呼ばれることもあるが、文字列のハッシュ値の計算に$O(N)$を要するので、結局$O(N^3)$かかってしまう。

そこで、何とか高速化しないといけない。
例として$共通接頭辞検索$というものがある。

これは「公務執行妨害」という文に対して

という同じ接頭辞を持つ文のうち、辞書に登録されている単語を引っ張ってくる処理である。

これはトライ木というデータ構造を用いて高速化されている。
(トライ木については、ここを参照)

 公
 |---end 
 務
 |---end
執行
 |---end
妨害
 |
end

「公」という文字が出てきたら、こんな感じに部分文字列をたどって検索できるようにしておく。
(endが出てきたらその時点で１単語として登録されている)

このトライ木の検索の計算量は$O(K)$である。(K：平均単語長)

共通接頭辞検索を用いることで、「大学辞めたい」という文章に対して、

こんな感じで辞書引きができる。
これは$O(NK)$である。

MeCabの中でもトライ木は使われているらしく、ダブル配列という最速のトライ木の実装方法が使用されているらしい。(リンク先はダブル配列のわかりやすいスライド)
DartsというC++のライブラリが公開されており、簡単にダブル配列が使えるようになっている。

次は、辞書を引いた後の処理にも焦点を当てたい。