- 著者
-
平林 幹雄
江渡 浩一郎
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告データベースシステム(DBS) (ISSN:09196072)
- 巻号頁・発行日
- vol.2006, no.78, pp.215-222, 2006-07-13
- 被引用文献数
-
1
全文検索システムの転置インデックスを実現するにあたり,テキストデータからN-gram法によって切り出したトークンを検索キーにする手法が広く用いられている.この手法には,言語中立性や再現率の完全性という利点がある反面,検索対象の文書群から抽出するトークンの数が膨大になるために,転置インデックスのサイズが肥大化して空間効率が悪化するという欠点がある.検索の際にクエリから切り出した各トークンが対象文書のテキスト内でも連接しているかどうかを判断するためには,転置インデックス内にトークンの文書内での出現位置を記録しておくことが必要となるが,この位置情報が転置インデックスの肥大化の一因となっている.本稿では,N-gram法の欠点である転置インデックスの空間効率を改善する手法として,N.M-gram法を提案する.N.M-gram法では,各トークンの文書内での位置情報のかわりに後続のトークンのハッシュ値を用いることによって,N-gram法の利点である言語中立性や再現率の完全性を保持したまま,空間効率を改善することができる.When constructing inverted index for full-text search system, using N-gram is very popular for tokenizing text data of target documents. Although the method has many advantages like language neutrality and perfect recall ratio, it has also shortage that the inverted index becomes large. The tokens extracted from documents tend to be enormous. The system needs to record each offset of tokens into inverted index because the offset is used for checking adjacency of tokens. The inverted index tends to be large because of the offset. In this paper, we describe N.M-gram method, which improves space efficiency of N-gram. The method uses hash values of succeeding tokens instead of offset in each document. The method can improve space efficiency without losing advantages of N-gram.