順序保存符号とその情報検索への応用

概要

論文の詳細を見る
大容量半導体ディスクが実用化され,それを利用してデータベースが構築されることも夢ではないと考えられる.その場合にも記憶コストを考慮すればデータ圧縮は必要である.一般に,符号化されたデータを利用する場合には復号操作が必要になるが,その時間はファイルのアクセス時間に比べて小さいため,これまでは問題視されなかった.しかし半導体ディスク上に置かれた圧縮ファイルを扱う場合には,ファイルのアクセス回数とともにデータ復号時間が検索時間に大きな影響を及ぼす.本稿では復号操作なしにレコード検索が実現できる順序保存符号を提案する.まずNakatsu,1991の結果を拡張し,r元順序保存符号が存在するための必要十分条件を与え,最適r元順序保存符号の平均符号語長とハフマン符号の平均符号語長を理論的に比較する.次に2元符号化について,データ圧縮しない場合・ハフマン符号化・最適順序保存符号化を行った場合のデータ量,検索時間の実験結果を固定長ファイルの場合,可変長ファイルの場合についてそれぞれ報告する.この結果順序保存符号について,圧縮率はハフマン符号と同程度で約60%を達成し,検索時間はハフマン符号化を行った場合の1/5(データ圧縮しない場合と同程度)であるということがわかり,検索対象となる属性の符号としてきわめて有効な符号であることが確かめられた.
一般社団法人情報処理学会の論文
1993-02-15

順序保存符号とその情報検索への応用

スポンサーリンク

概要

著者

関連論文

スポンサーリンク