検索効率を考慮した転置ファイルの圧縮(<特集>システムLSIの設計技術と設計自動化)
スポンサーリンク
概要
- 論文の詳細を見る
キーワードを用いた文献検索システムでは,検索を高速化するために転置ファイルを利用する.本論文ではAND検索を行う際の転置ファイルの新たな圧縮・復号方式を提案する.提案方式の特徴はキーワード検索を効率良く実行するために,シンドローム情報源符号化を用いて2段階で圧縮・復号を行うことである.ここで,圧縮は第1段階の符号化とシンドローム情報源符号化による第2段階の符号化からなる.まず,転置ファイルをベルヌイモデルで表現し,圧縮ファイルおよび復号木を格納するのに要するメモリ量と復号・検索に要する計算量によりシステムを評価する.次に,シンドローム情報源符号化の性能を示す符号の限界式(VG限界式)を満足するパラメータに対してメモリ量と計算量を評価し,いくつかの重要な性質とともに提案する方式が優れた性能を持つことを示す.その結果,(1)2つの評価基準はトレード・オフの関係にあり,わずかなメモリ量の増加に対して計算量が大きく低減すること,(2)提案アルゴリズムの計算量は従来の2段階アルゴリズムより著しく低減すること,(3)検索キーワード数が小さい場合には高頻度で出現するキーワードに対するほど提案アルゴリズムの性能が良くなること,(4)転置ファイルの大きさとともに検索システムの性能が良くなることが明らかになった.
- 一般社団法人情報処理学会の論文
- 2002-05-15