辞書引きアルゴリズム入門 - Qiita

はじめに 業務で自然言語処理をしていて何かと高速化を求められる場面が多く、辞書引きアルゴリズムという言葉に行き着いた。 自然言語処理界隈で深層学習が幅を利かせすぎているせいか、辞書引きアルゴリズムと聞いても同じようにピンとこない人の方が多そう。 辞書引きアルゴリズムとは テキスト中の有り得る全ての部分文字列から辞書にある単語を引いてくるアルゴリズムのこと。 形態素解析とかの処理の裏側を支えている。 この道を極めるとMeCabとかJumanとかが作れるらしい。 例えば、abcという文字列が与えられた場合、部分文字列は以下のようになる。 a b c ab bc abc これらの部分文字列が辞書にあるかどうかを調べていく。 要するに文字列の中から辞書内の単語を引っ張ってくるアルゴリズム、といった感じである。 この部分文字列の列挙の計算量は$O(N^2)$であるが、この時点でアプリケーションとして