EeBlog(テクニカルブログ)
:アルゴリズム
LZ77 という圧縮アルゴリズムがあります。Lempel と Ziv という人が1977年に発表したアルゴリズムなのでこのように呼ばれています。辞書式圧縮とも呼ばれます。
圧縮対象のデータを先頭から順番に見ていき、手前に存在する部分データと一致する部分のポインタと次の不一致文字として符号化することで圧縮を行うアルゴリズムです。一致する部分へのポインタは一致しているデータの長さと現在の位置からの距離として表現します。
比較的簡単で、割と圧縮率の良いアルゴリズムです。 (さらに…)
2010年10月26日 | カテゴリー:アルゴリズム
ランレングス符号化の次はハフマン符号化を実装してみます。
ハフマン符号化は連続する固定長のデータを可変長のデータに変換することで圧縮を行うアルゴリズムです。固定長のデータから可変長のデータへの変換に用いる変換規則は、データの出現率から最適なものを生成します。
出現率の高いデータを短い可変長のデータに、出現率の低いデータを長い可変長データに変換するので、データに偏りがあるほど圧縮率は高まります。
データ全体を調べて変換規則を生成してから圧縮を行う方法を静的ハフマン符号化といいます。最適な変換規則を生成できるので圧縮の効率がよいのですが、ストリームで処理するのに向いていません。 (さらに…)
2010年10月3日 | カテゴリー:アルゴリズム
可逆圧縮アルゴリズムのひとつであるランレングス圧縮を実装してみます。
ランレングス圧縮は連続するデータをその一つのデータとそのデータが連続している長さの組に変換します。
この圧縮は同じ値が連続するデータをく含んでいる場合には変換後のデータのサイズを小さくできますが、バラバラな値を多く含んでいる場合には逆に大きくなってしまいます。実際にこのアルゴリズムが使われる場合には、連続しないデータを含んでいてもそれほど圧縮率が下がらないような工夫がされます。 (さらに…)
2010年8月3日 | カテゴリー:アルゴリズム