著者

平林 幹雄 江渡 浩一郎

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告デジタルドキュメント(DD)

巻号頁・発行日

vol.2006, no.33, pp.7-14, 2006-03-22

---

全文検索システムの配置インデックスを生成するための主要な手法であるN-gram法には、言語中立性や再現率の完全性という利点がある反面、検索対象の文書群から抽出するトークンの数が膨大になるために、転置インデックスのサイズが肥大化して空間効率が悪化するという欠点がある。本稿では、N-gram法の欠点である配置インデックスの空間効率を改善する手法として、N.M-gram法を提案する。N.M-gram法では、各トークンの文書内でのオフセットのかわりに後続のトークンのハッシュ値を用いることによって、N-gram法の利点である言語中立性や再現率の完全性を保持したまま、空間効率を改善することができる。N-gram is a major method to construct inverted index for full-text search system. Although N-gram has advantages of language neutrality and perfect recall ratio, it has shortage that the inverted index becomes large because tokens extracted from documents are enormous. In this paper, we describe N.M-gram method, which improves space efficiency of N-gram. N.M-gram uses hash values of succeeding tokens instead of offset data in each document. N.M-gram can improve space efficiency without losing advantages of language neutrality and perfect recall ratio.