ここでは，可逆圧縮のひとつである「ランレングス法」のアルゴリズムについて学習していきましょう。
教科書や参考書などを参照しながら，以下の空欄に当てはまる語句を調べましよう。
スライドの解説
同じデータが連続して出現するデータにおいて，連続する部分をまとめる圧縮をランレングス法といいます。ランレングス法という名称は，連続する同じデータの並び(run・ラン)を，その繰り返し回数，長さ(length・レングス)に置き換える手法に由来しています。
例えば，文字列「AAAABBBBBBBAAABBBBBB」をランレングス法により圧縮してみましょう。
文字列「AAAA BBBBBBB AAA BBBBBB (20文字)」は，Aが4回，Bが7回，Aが3回，Bが6回連続しているから，ランレングス法により「A4B7A3B6」と圧縮することができます。また，文字列は必ずAから始まり，AとBが交互に出現するものとすれば，AとBを取り除いて「4736」とさらに省略することができます。
また，圧縮前および圧縮後のデータ量は，それぞれ次のとおりになります。
圧縮前のデータ量：各文字はAまたはBの2種類であるから，1bitで表現できます。よって，文字列全体のデータ量は，1(bit) × 20(文字)＝20(bit)となります。
圧縮後のデータ量：「4736」の4個の数値のうち最大値は7であるから，3bitで表現できます。よって，文字列全体のデータ量はは，3(bit) × 4(文字)＝12(bit)となります。
したがって，圧縮率は「圧縮後のデータ量/圧縮前のデータ量×100」で求められるから，12(bit)/20(bit) × 100＝60(%)となります。
最後に，文字列「ABCDE」をランレングス法により圧縮することを考えてみましょう。
文字列「ABCDE」は，Aが1個，Bが1個，Cが1個，Dが1個，Eが1個連続しているから，ランレングス法により「A1B1C1D1E1」と圧縮することができます。圧縮前と圧縮後の文字数を比較すると，圧縮前は5文字に対し，圧縮後は10文字と圧縮したにも関わらず文字数が2倍になってしまいました。
つまり，ランレングス法は同じデータが続いているものに適していると言えます。