N.M-gram: Implementation of Inverted Index Using N-gram with Hash Values
Mikio Hirabayashi, Koichiro Eto · IEICE Technical Report; IEICE Tech. Rep. · 2006
全文検索システムの転置インデックスを実現するにあたり,テキストデータから N-gram 法によっ て切り出したトークンを検索キーにする手法が広く用いられている.この手法には,言語中立性や再 現率の完全性という利点がある反面,検索対象の文書群から抽出するトークンの数が膨大になるため に,転置インデックスのサイズが肥大化して空間効率が悪化するという欠点がある.検索の際にクエ リから切り出した各トークンが対象文書のテキスト内でも連接しているかどうかを判断するためには, 転置インデックス内にトークンの文書内での出現位置を記録しておくことが必要となるが,この位置 情報が転置インデックスの肥大化の一因となっている.本稿では,N-gram 法の欠点である転置イン デックスの空間効率を改善する手法として,N.M-gram 法を提案する.N.M-gram 法では,各トーク ンの文書内での位置情報のかわりに後続のトークンのハッシュ値を用いることによって,N-gram 法 の利点である言語中立性や再現率の完全性を保持したまま,空間効率を改善することができる.