N．M-gram：ハッシュ値付きN－gram法による転置インデックスの実現

摘要

全文検索システムの転置インデックスを実現するにあたり，テキストデータからN-gram法によって切り出したトークンを検索キーにする手法が広く用いちれている．この手法には，言語中立性や再現率の完全性という利点がある反乱　 検索対象の文讃群から抽出するトークンの数が膨大になるために．転置インデックスのサイズが肥大化して,凧効率が脚ヒするという欠点がある．検索の既にクエリから切り出した各トークンが対象文誤のテキスト内でも連接しているかどうかを判断するためには，転置インデックス内にトークンの支署内での山現佗置を記録しておくことが必要となるが，この位置情報が転置インデックスの肥大化の一因となっている．本稿では，N-gram法の欠点である転置インデックスの空偶効率を改善する手法として．N．M－gram法を提案する．N．M－gram法では，各トークンの文督内でのイ部隊情報のかわりに後続のトークンのハッシュ値を用いることによって，N－gram法の利点である言語中立性や再現率の完全性を保持したまま，空間効率を改善することができる．