記憶量とアクセス時間を考慮してデータ圧縮するための近似アルゴリズム

松下 浩明  丸岡 章  木村 正行  

誌名
電子情報通信学会論文誌 D   Vol.J63-D   No.8   pp.626-633
発行日: 1980/08/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(665.5KB)>>
論文を購入




あらまし: 
同一構造の類似したレコードからなる集合(データ)を電子計算機の記憶装置に格納するとき,それに要する記憶量は各レコードをそのままの形で格納するよりも,基準となるレコード及び各々のレコード間の相違に関する情報を格納する方がより少なくて済む.しかし,一般にこのようなレコードを再構成して記憶量を少なくしようとすればする程,各レコードをアクセスするために要する時間は長くなる.本論文では,この相容れない記憶量およびアクセス時間に対する要請を共に満足するよう,レコードを再構成する問題を考察する.すなわち最悪の場合でも,各レコードはある一定時間(ι単位時間)以下でアクセス可能であるという条件のもとで,記憶量のなるべく少ないレコードの再構成の方法を考察する.そのような条件のもとで記憶量を最小にする再構成問題はNP完全であるので,本論文ではまずon3)及びon2)時間で動作する二つの近似アルゴリズムを提案する.ここで,nはレコードの個数を表す.次に二つの近似アルゴリズムが出力する近似解と最適解のコスト(記憶量)の比の上限が共に(ιm)/(ι+1)であることを示す.ここで,mはレコード1個を格納するのに要する記憶量を表す.