Deflate



LZ77とLZSS


    ・LZ 符号は、辞書に基づく符号化方式 (辞書法 / dictionary-based coding)です。
    ・LZ 符号は、前もって辞書を用意しない適応型辞書法 (adaptive dictionary method) を使います。
    ・LZ77 符号は、スライド辞書法を使います。( LZ78は動的辞書法 )

    ・LZ77では、記号列を一致があった場合もなかった場合も、
         (一致位置、一致長、次の不一致記号)という3つの値に置き換えます。

    ・LZSSはLZ77の改良版で、一致があった場合は(1、一致位置、一致長)とし、
         一致がなかった場合は(0、不一致記号)とすることで圧縮率の向上を図ったもの。


ハフマン符号


    ・他の算術符号やその他の高効率の符号化法と異なり、特許の問題が無いのが特徴

    ・同じ記号の集合に出現頻度に応じた符号を割り当てることでデータを圧縮します。
       出現頻度が高い記号に短い符号が割り当てられます。


動的ハフマン符号と静的ハフマン符号


    ・圧縮しながら逐次ハフマン木を再構築する動的ハフマン符号 -> Deflate で利用

    ・データをすべて調査したうえでハフマン木を構築し、圧縮する静的ハフマン符号 -> LHA で利用

    ・より複雑で効率的な bzip2 の原型の bzip は圧縮アルゴリズムに算術符号を利用しているため、
       特許による制約があります。

概要


    LZ 符号もハフマン符号も圧縮アルゴリズムです。
    それぞれがどのように組み合わされるのかがポイントです。

情報源




戻る

TOP