N.M-gram: ハッシュ値付きN-gram 法による転置インデックスの実現 N.M-gram: Implementation of Inverted Index Using N-gram 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 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.

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.

収録刊行物

  • 情報処理学会研究報告データベースシステム(DBS)

    情報処理学会研究報告データベースシステム(DBS) 2006(78(2006-DBS-140)), 215-222, 2006-07-13

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

参考文献:  11件中 1-11件 を表示

被引用文献:  1件中 1-1件 を表示

各種コード

  • NII論文ID(NAID)
    110004849355
  • NII書誌ID(NCID)
    AN10112482
  • 本文言語コード
    JPN
  • 資料種別
    Technical Report
  • ISSN
    09196072
  • NDL 記事登録ID
    8005476
  • NDL 雑誌分類
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL 請求記号
    Z14-1121
  • データ提供元
    CJP書誌  CJP引用  NDL  NII-ELS  IPSJ 
ページトップへ