前回はLZ77という圧縮アルゴリズムを実装してみました。今回はLZ77を改良したLZSSというアルゴリズムを実装してみます。
LZ77ではすでに処理された文字列の中に一致する部分があれば、そこを指すポインタ(長さと位置)を生成し、次にその後の一文字を出力する、ということを繰り返す形式でした。 この形式だと、すでに処理された文字列の中に一致する部分がなくても、ポインタを置かなければなりませんでした。 LZSSでは最初の1bitでその後に続くビット列がポインタであるか、文字であるかを表すように改良しています。 (さらに…)
2010年11月10日 | カテゴリー：アルゴリズム
LZ77 という圧縮アルゴリズムがあります。Lempel と Ziv という人が１９７７年に発表したアルゴリズムなのでこのように呼ばれています。辞書式圧縮とも呼ばれます。
圧縮対象のデータを先頭から順番に見ていき、手前に存在する部分データと一致する部分のポインタと次の不一致文字として符号化することで圧縮を行うアルゴリズムです。一致する部分へのポインタは一致しているデータの長さと現在の位置からの距離として表現します。
比較的簡単で、割と圧縮率の良いアルゴリズムです。 (さらに…)
2010年10月26日 | カテゴリー：アルゴリズム
ランレングス符号化の次はハフマン符号化を実装してみます。
ハフマン符号化は連続する固定長のデータを可変長のデータに変換することで圧縮を行うアルゴリズムです。固定長のデータから可変長のデータへの変換に用いる変換規則は、データの出現率から最適なものを生成します。
出現率の高いデータを短い可変長のデータに、出現率の低いデータを長い可変長データに変換するので、データに偏りがあるほど圧縮率は高まります。
データ全体を調べて変換規則を生成してから圧縮を行う方法を静的ハフマン符号化といいます。最適な変換規則を生成できるので圧縮の効率がよいのですが、ストリームで処理するのに向いていません。 (さらに…)
2010年10月3日 | カテゴリー：アルゴリズム
