連長圧縮とは? わかりやすく解説

Weblio 辞書 > 同じ種類の言葉 > 情報 > 記法 > 圧縮 > 連長圧縮の意味・解説 

れんちょう‐あっしゅく〔レンチヤウ‐〕【連長圧縮】


連長圧縮

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/10/13 20:51 UTC 版)

ナビゲーションに移動 検索に移動

連長圧縮(れんちょうあっしゅく)は、データ圧縮アルゴリズムの一つで、可逆圧縮に分類される。ランレングス圧縮RLE (Run Length Encoding) とも呼ばれる。

符号化の原理

連長圧縮では、ある連続したデータを、そのデータ一つ分と連続した長さで表現することで圧縮している。

例えば、「A A A A A B B B B B B B B B A A A」は「A 5 B 9 A 3」と表せる。これは、Aが5回続き、そのあとにBが9回、そしてAが3回続いていることを表している(連続回数を、元のデータを表す符号の前に記録することもある。その場合、符号化した後は「5 A 9 B 3 A」と表される)。

さらに、データがこの2種類(AとB)だけで、最初にAが来ることにしておけば、「5 9 3」だけで表せる。このルールに従ったときにBが最初に見つかった場合は、最初にAが0回連続していることにすれば良い。例えば、「B B B A A A A A B B B B B A A A」は「0 3 5 5 3」で表せることになる。

こういったことから、白と黒以外にほとんど情報がないモノクロファクシミリでよく使われている。

連長圧縮の欠点とその解決方法

連長圧縮の欠点は、データが連続していないと、符号化後のデータが元のデータより膨らんでしまうという点である。例えば、「A B C D A B C A B A B C D E」は「A 1 B 1 C 1 D 1 A 1 B 1 C 1 A 1 B 1 A 1 B 1 C 1 D 1 E 1」となる。この場合の圧縮率は200%となり、圧縮データが元のデータの2倍あるということになる。また、伸長時にメモリの確保を容易にするために元のデータのサイズを記録する場合はさらに膨らんでしまうことになる。

それを防ぐ方法はいくつかあるが、その中でも最も単純なのが、ある一定数だけ同じデータが繰り返した場合にだけ連長圧縮を施すという方法である。次の例では、8バイト(8文字)必要だったものが6バイトで済むようになる。

元のデータ ABCDDDD = A B C DDDD
通常の符号化方法 A1B1C1D4 A1 B1 C1 D4
対策済みの符号化 ABCDD2 A B C DD2

PackBits

ところが、この方法では逆に連続するデータの圧縮率が低下する場合がある。次の例では、全体としては圧縮率が上がっているが、前半の連続するデータの部分の圧縮率は下がっている。

元のデータ AAAABBCCCCCCDEFG = AAAA BB CCCCCC DEFG
通常の符号化方法 A4B2C6D1E1F1G1 A4 B2 C6 D1E1F1G1
上記の符号化方法 AA2BB1CC3DEFG AA2 BB1 CC3 DEFG

そこで、このような圧縮率の低下を回避するため、連続しないデータが見つかった場合は、連続するデータが現れるまでの長さを記録していくことにする。先の例に適用すると、次のようになる。

元のデータ AAAABBCCCCCCDEFG = AAAA BB CCCCCC DEFG
符号化したデータ 4A2B6C-4DEFG 4A 2B 6C -4DEFG

- が付いた(負の)長さデータは連続しないデータの長さを表し、この例では「"A" が4、"B" が2、"C" が6ずつ続き、圧縮できない "DEFG" の4文字がある」と符号化されたことになる。この方法をPackBitsと言い、TIFFPICTなどで使われている。

Switched Run Length Encoding

しかし、PackBitsでは、データの長さを表す符号が連続するデータの長さのものであるか連続しないデータの長さのものであるかをその正負によって判別しているので、表現できるデータの長さが半分までになる。データの長さには通常1バイトを割り当てるので、PackBitsで表現できるデータの長さは128までとなる。通常はそこまで連続することはなかなかないが、色数の少ない画像などでは十分に考え得る。この対策として、コードの変わり目で連続データとして扱うか非連続データとして扱うかを交互に切り替えていくSwitched Run Length Encodingがある。

データ「A B C D E E E E F F F F F F F」を例として、圧縮の方法を解説する。

  1. まずは非連続データとして扱い、PackBits同様に連続したデータが現れるまでの長さを記録し、その後ろに非連続データをそのまま出力する
    A B C D E E E E F F F F F F F→5 A B C D E
  2. 連続したデータに出会ったら、次に連続しないデータに出会うまでの長さを記録する
    A B C D E E E E F F F F F F F→5 A B C D E 3
  3. 再度、連続したデータが現れるまでの長さを記録し、その後ろに非連続データをそのまま出力する
    A B C D E E E E F F F F F F F→5 A B C D E 3 1 F
  4. 2と3をデータの末尾まで交互に繰り返していく
    A B C D E E E E F F F F F F F→5 A B C D E 3 1 F 6

また、復号の方法は以下のようになる。

  1. まずは非連続データとして扱い、最初の1文字を読み込んで長さを求めた後、後ろに続く非連続データをそのまま出力する
    5 A B C D E 3 1 F 6 → A B C D E
  2. 復号し終えたら連続データとして扱うように切り替え、1文字だけ読み込んで連続する長さを求めた後、復号した最後の文字をその長さだけ繰り返し出力する。
    5 A B C D E 3 1 F 6 → A B C D E E E E
  3. 再度非連続データとして扱い、1文字読み込んで長さを求めた後、続く非連続データをそのまま出力する
    5 A B C D E 3 1 F 6 → A B C D E E E E F
  4. 2と3をデータの末尾まで交互に繰り返していく
    5 A B C D E 3 1 F 6 → A B C D E E E E F F F F F F F

PackBitsとは違い、フラグビット[1]が必要ないため、Switched Run Length Encodingでは256程度までの長さを表現できる。

脚注

  1. ^ ここでは、PackBitsにおいて長さを表す符号の正負を表す1ビットで、非連続データか連続データかを区別するビット。符号付数値表現も参照

関連項目

  • 差分圧縮
  • BMP - 標準では無圧縮だが、4ビット(16色)・8ビット(256色)のカラーパレット形式において、連長圧縮を適用することができる。



連長圧縮と同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「連長圧縮」の関連用語

1
連長符号化 デジタル大辞泉
100% |||||

2
アール‐エル‐イー デジタル大辞泉
100% |||||

3
ランレングス圧縮 デジタル大辞泉
100% |||||

4
ランレングス法 デジタル大辞泉
100% |||||

5
ランレングス符号化 デジタル大辞泉
100% |||||





10
52% |||||

連長圧縮のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



連長圧縮のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
デジタル大辞泉デジタル大辞泉
(C)Shogakukan Inc.
株式会社 小学館
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの連長圧縮 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS