１．参照文献
データ圧縮については他によいサイトがあるので、自分がわざわざ作らなくてもと思うんですが、データ圧縮についてのページがないと情報理論入門としてしまりが悪いんですね。というわけで次のサイトを参照に、より簡略化してページを作ることにします。冗長度との関係のところで、ちょっとだけ自分のオリジナリティが入ってます。
参照文献：ランレングス符号化の使い方とメリットを解説! － ITの学び
２．データ圧縮方式
前ページのおさらいになりますが、データが冗長（出現確率に偏りがある）だと情報量を（ほぼ）保持したままデータ量を削減できます。ただし必ず圧縮できるというわけではなくて、それぞれの圧縮方法ごとにメリット、デメリットがあります。
データ圧縮には大きく分けて次の二つの方法があります。
- 可逆圧縮：データ圧縮でサイズを小さくした後、元に戻すことが可能。Zipファイルなど。
- 非可逆圧縮：データ圧縮で可逆圧縮よりも小さいサイズにできるが、元には戻せない。jpg、mpeg、mp3など。
用途に応じて使い分けられているようです。画像、動画、音楽などは非可逆圧縮を使ってるんですね。人間の補完能力のおかげで、ちょっとぐらい情報量が飛んでも気づかないのかもしれません。
３．ランレングス符号化
このページでは可逆圧縮方式の中で理解しやすい、ランレングス符号化を紹介します。この方法は、同じ文字の繰り返し部分を、その回数で表現することで圧縮する方式です。図1に一例（例①）を示します。
図1に示すように同じ文字の繰り返しをその回数で表現することで、8文字列が6文字列に圧縮できています。しかし繰り返しが少ないとほとんど圧縮できなかったり、かえって文字列が長くなったりします。たとえば「ABCCBCCC」（例②）は図１の例と同じ8文字ですが、ランレングス符号化により「A1B1C2B1C3」の10文字に増えてしまいます。出現確率はP(A)=1/8、P(B)=1/4、P(C)=5/8であり、冗長度は下のように計算できます。
\begin{equation} H_{max}=-\sum_{n=1}^3 \frac{1}{3} \log_2 \frac{1}{3}= \log_2 3 \risingdotseq 1.58\\ H=-\frac{1}{8}\log_2 \frac{1}{8} -\frac{1}{4}\log_2 \frac{1}{4} -\frac{5}{8}\log_2 \frac{5}{8} \risingdotseq 1.29 \\ 冗長度r= 1 – \frac{H}{H_{max}}=1-\frac{1.29}{1.58} \risingdotseq 0.18 \end{equation}例①も例②も冗長度は変わりません。しかし例②のようにデータの性質と圧縮方法がかみ合わないと、冗長度がある程度あったとしても、データの圧縮ができないことになります。
<< 冗長度
コメント