String Matching Algorithm に基づく有歪み圧縮について

• 小幡 洋昭

  早稲田大学理工学部経営システム工学科

• 後藤 正幸

  早稲田大学理工学部経営システム工学科

• 平澤 茂一

  早稲田大学理工学部経営システム工学科

書誌事項

タイトル別名

• On Lossy Compression based on String Matching Algorithm

抄録

Z.Zhang and V.K.Weiの提案したGold Washingアルゴリズムは, ある一定の確率分布で発生させたランダムな系列で辞書を逐次更新することにより, 有限アルファペットの無記憶情報源に対し, 確率分布が未知であっても漸近的にRate-Distortion関数に収束することが証明されている. 一方, Y.Steinberg and M.GutmanはLZ77符号に用いられるString Matchingを有歪み圧縮に応用したアルゴリズムを提案した. このアルゴリズムは, 有限アルファベットの無記憶情報源に対し, 情報源から定まる最適な符号語の分布により発生させたランダムな系列で辞書を更新することにより, 漸近的にRate-Distortion関数に収束することが証明されている. そこで, 本稿ではGold Washingアルゴリズムの考えを用いたString Matchingアルゴリズムに基づくアルゴリズムを提案し, シミュレーションによりそれぞれのアルゴリズムの特性を考察する.

収録刊行物

• 電子情報通信学会技術研究報告. IT, 情報理論

  電子情報通信学会技術研究報告. IT, 情報理論 96 (494), 79-84, 1997-01-24

  一般社団法人電子情報通信学会

キーワード

• 有歪み圧縮
• Gold Washing Algorithm
• String Matching Algorithm
• Rate-Distortion

詳細情報

• CRID: 1570854177377582848
• NII論文ID: 110003197176
• NII書誌ID: AN10013083
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles