最小コスト法に基づく形態素解析におけるCPUキャッシュの効率化

形態素解析は、自然言語を入力とし、形態素の列を返す処理である。日本語の情報検索やテキストマイニングなどの自然言語処理において、形態素解析は重要な前処理である。形態素解析を実現する代表的な手法の1つに最小コスト法[1]があり、MeCab[2]やSudachi[3]などの形態素解析器で利用されている。最小コスト法の時間的ボトルネックの一つに、辞書の肥大化に伴うCPUキャッシュ効率の低下が挙げられる。単語列挙のための木構造の探索や、コスト計算のための行列参照では、メモリ上のランダムアクセスが頻繁に発生する。巨大な辞書では、このランダムアクセスがキャッシュミスを引き起こし、速度低下の原因となる。本稿では、参照の局所性の良いデータ構造を設計し、キャッシュ効率を改善することで最小コストの高速化を達成する。IPADIC[4]やNeologd[5]、UniDic[6,7]を使った実験により、その有効性を実証する。実験の結果、提案法を適用しなかった場合と比べて、提案法は40%程度の高速化を達成した。1）https://github.com/daac-tools/vibrato10473になっ26962322動詞3144118808311550011923447121125512904BOS元気名詞に動詞なっ動詞た助動詞EOS4304に助詞-518-927ス。太線はコストの和が最小となる経路を表す。また、提案法を実装した形態素解析器Vibratoを新たに開発した。実験により、VibratoはMeCabの