【JavaScript】 ランレングス圧縮(RLE、連長圧縮)とは
更新日：2024/02/27
先日ランレングス圧縮という言葉を目にしました。
データ量を減らすランレングス圧縮というアルゴリズムだそうです。
内容を見ると、３０年位前にデータを圧縮しようとして自分で考えてやっていたのを思い出しました、
考えることはみんな同じのようです。
今回は、ランレングス圧縮の簡単な解説と、JavaScriptコードを紹介したいと思います。
ランレングス圧縮とは
ランレングス圧縮（連長圧縮）は、与えられたデータ内の連続する値に着目して圧縮するアルゴリズムの一種です。
英語ではrun length encodingなので、RLEと略されることもあります。
考え方は非常に単純で、例えば "AAAABBBBB"のようなデータを、"A4B5"のように値と繰り返し回数で表現することでデータ量を削減します。
しかし連続するデータが少ないとデータ量が増加するという欠点があります。
例えば"ABBCD"は"A1B2C1D1"となり、増加しています。
この欠点を補うために、考え方を発展させて様々な方式が考案されています。
それでもデータ量が増えてしまうときは、圧縮せずに元のデータのまま利用するか、他の圧縮アルゴリズムを選択することになります。
なお、例では"A4"のように値の後に繰り返す回数を記述していますが、順番が決められているわけではありません。
受け渡し側と受け取る側で、決める必要があります。
コード例
ランレングス圧縮は、基本的にはバイトデータとして扱います。
そこで、最初に次のようなバイト単位のデータを用意しました。
バイトデータの準備
const data = "131111222222222234567777777777777777777777777777777788889022311";
const byteData = Uint8Array.from( {length:data.length}
, (e,index) => parseInt(data.charAt(index)));
console.log( byteData );
// Uint8Array(63) [
// 1, 3, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2,
// 2, 2, 2, 2, 3, 4, 5, 6, 7, 7, 7, 7,
// 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
// 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
// 7, 7, 7, 7, 8, 8, 8, 8, 9, 0, 2, 2,
// 3, 1, 1
// ]
このデータで、ランレングス圧縮をしてみます。
なお、繰り返し回数もバイトで表すので、1から255回の範囲です。
圧縮（エンコード）
const rle_encode = u8Array =>{
const result = [];
let count = 1;
let beforeCode = u8Array[0]
for( let i = 1 ; i < u8Array.length ; i ++ ){
const code = u8Array[i];
if( beforeCode === code && count < 256 ) count ++;
else {
result.push( beforeCode ,count );
beforeCode = code; count = 1;
}
}
result.push( beforeCode ,count );
return new Uint8Array(result);
}
const encode = rle_encode( byteData );
console.log( encode );
// Uint8Array(30) [
// 1, 1, 3, 1, 1, 4, 2, 10, 3,
// 1, 4, 1, 5, 1, 6, 1, 7, 32,
// 8, 4, 9, 1, 0, 1, 2, 2, 3,
// 1, 1, 2
// ]
複合（デコード）
const rle_decode = u8Array =>{
const result = [];
for( let i = 0 ; i < u8Array.length ; i += 2 ) {
const code = u8Array[i];
const count = u8Array[i+1];
for( countLoop = 0 ; countLoop < count ; countLoop ++ )
result.push( code );
}
return new Uint8Array(result);
}
const decode = rle_decode( encode );
console.log( decode );
// Uint8Array(63) [
// 1, 3, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2,
// 2, 2, 2, 2, 3, 4, 5, 6, 7, 7, 7, 7,
// 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
// 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
// 7, 7, 7, 7, 8, 8, 8, 8, 9, 0, 2, 2,
// 3, 1, 1
// ]
// byteData(元データ） と decode の一致チェック
console.log( byteData.every( (e,index)=>e ===decode[index] ) );
// true
エンコードとデコード共に、配列に出力するデータを格納してから、ArrayBufferにセットしています。
データ量が多い場合は、配列を使用しない方法を考えた方がいいかもしれません。
例えば、最初にエンコードまたはデコード後に必要なバッファ量のカウントだけ行い、バッファ確保後に、実際にデータをセットするなどです。
また、入力値の型や長さなどのチェックを行っていないので、実際に使用するなら追加してください。
PickBits方式
PickBits方式は、ランレングス圧縮で不連続な値によるデータ量増加を抑えるための手法の一つです。
不連続値の前に、後に続く不連続データの個数をマイナス値でセットしておきます。
数値を読み取ってプラス値なら、その後に続く一文字をプラス値だけ繰り返します。
マイナス値なら、その後にその数分だけ文字を抜き出します。
例えば、"4A-5bcdef"なら "AAAAbcdef" となります。
この方式は、数値を先に解釈する必要があるため、値よりも繰り返し回数が先にセットされます。
またマイナス値を取り扱うので、使用できる範囲は-128～127です。
したがって、繰り返し回数は127回まで。
不連続は128個まで表すことができます。
PickBits方式 圧縮（エンコード）
const PickBits_encode = u8Array =>{
const result = [];
// 不連続データの出力
const discontinuityRelease = ()=>{
if( discontinuity.length === 1 )
result.push(1 , discontinuity[0]);
else
result.push(256 - discontinuity.length , ...discontinuity); // ①
discontinuity.length = 0;
};
let count = 1;
let beforeCode = u8Array[0];
let discontinuity = []; // 不連続データ格納用配列
for( let i = 1 ; i < u8Array.length ; i ++ ){
const code = u8Array[i];
if( beforeCode === code && count < 127 ) { // 連続は127回まで
if( discontinuity.length > 0 )
discontinuityRelease();
count ++;
}
else {
if( count === 1 ) {
discontinuity.push( beforeCode );
if( discontinuity.length > 127 ) // 不連続は128回まで
discontinuityRelease( );
}
else result.push( count , beforeCode );
beforeCode = code; count = 1;
}
}
// 一文だけ字残っていて不連続データがあるなら不連続データとして処理
if( count === 1 && discontinuity.length > 0 ) {
discontinuity.push( beforeCode );
discontinuityRelease( );
}
else result.push( count , beforeCode );
return new Uint8Array(result);
}
const encode = PickBits_encode( byteData );
console.log( encode );
// Uint8Array(25) [
// 254, 1, 3, 4, 1, 10, 2, 252,
// 3, 4, 5, 6, 32, 7, 4, 8,
// 254, 9, 0, 2, 2, 1, 3, 2,
// 1
// ]
上の例の元データ(byteData)は、rle_encode()で使用したものと同じです。
①の箇所でマイナス値をセットしていますが、コードは256からマイナスしています。
これは、バイト単位で-1はFF(255)、-128は80(128)になるからです。
実際にはマイナス値のままセットしても問題ありません。
Uint8Arrayは、2バイト以上をカットします。
-1は FFFF・・・FFFF で FF、-128 はFFFF・・・ FF80 で 80 がセットされます。
このコードは上の件を含めて、改良の余地がかなりありますね。
不連続データを配列に格納していますが、開始位置を記憶しておくだけでもよさそうです。
PickBits方式 複合（デコード）
const PickBits_decode = u8Array =>{
const result = [];
let count = 0;
for( let i = 0 ; i < u8Array.length ; i ++ ) {
const code = u8Array[i]
if( count === 0 ) count =code <= 127 ? code : code - 256;
else{
if( count > 0 ){
for( countLoop = 0 ; countLoop < count ; countLoop ++ )
result.push( code );
count = 0;
}else{
result.push( code );
count ++;
}
}
}
return new Uint8Array(result);
}
const decode = PickBits_decode( encode );
console.log( decode );
// Uint8Array(63) [
// 1, 3, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2,
// 2, 2, 2, 2, 3, 4, 5, 6, 7, 7, 7, 7,
// 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
// 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
// 7, 7, 7, 7, 8, 8, 8, 8, 9, 0, 2, 2,
// 3, 1, 1
// ]
// byteData(元データ） と decode の一致チェック
console.log( byteData.every( (e,index)=>e ===decode[index] ) );
// true
デコードは、規則に従ってデータを組み立てていくだけです。
更新日：2024/02/27
関連記事
スポンサーリンク
記事の内容について
こんにちはけーちゃんです。
説明するのって難しいですね。
「なんか言ってることおかしくない？」
たぶん、こんなご意見あると思います。
裏付けを取りながら記事を作成していますが、僕の勘違いだったり、そもそも情報源の内容が間違えていたりで、正確でないことが多いと思います。
そんなときは、ご意見もらえたら嬉しいです。
掲載コードについては事前に動作確認をしていますが、貼り付け後に体裁を整えるなどをした結果動作しないものになっていることがあります。
生暖かい視線でスルーするか、ご指摘ください。
ご意見、ご指摘はこちら。
https://note.affi-sapo-sv.com/info.php
このサイトは、リンクフリーです。大歓迎です。
