N.M-gram：ハッシュ値付きN-gram索引による全文検索の一手法

情報処理学会 Web Site 参考文献12件

書誌事項

タイトル別名
  • N M gram ハッシュチ ツキ N gram サクイン ニ ヨル ゼンブン ケンサク ノ イチ シュホウ
  • N.M-gram: A Method of Full-text Search by N-gram Index with Hash Values

この論文をさがす

抄録

全文検索システムの転置索引を実現するにあたり，テキストデータから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 index file becomes large. The tokens extracted from documents tend to be enormous. The system needs to record each offset of tokens into the index file because the offset is used for checking adjacency of tokens. The index file 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.

収録刊行物

参考文献 (12)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ