日本語形態素解析への複数ハッシュふるい分けの応用

概要

論文の詳細を見る
最近、大きなメモリが利用できるようになり、並列処理が普及しつつある。自然言語処理のアルゴリズムはこの変化を反映する必要がある。しかしメモリが大きくなっても、長い語長のキーをきわめて多数持つ辞書を、通常のハッシュ表にすることは、必ずしも常に可能ではない。本研究では「複数ハッシュふるい分け」の形態素解析への応用について述べる。「ふるい分け」とは、与えられたキーがあるデータ集合中に存在するかどうかを調べることである。複数ハッシュふるい分けでは、複数のハッシュアドレス生成に互いに独立なn個の異なるハッシュ関数を使用し、ハッシュ表の該当アドレスにはデータの存在を示す1ビットのフラグを置く。探索時には同じハッシュ関数のセットを用いて探索キーをハッシュし、すべてのアドレスの内容が1であれば、辞書中のキーと一致したとみなす。この方法ではハッシュ表が比較的小さくなり、また並列処理の適用が容易である。また、本研究では長い文字列を「畳み込む」ためのアルゴリズムについても検討する。
一般社団法人情報処理学会の論文
1993-09-27