Team TripleFalcon. http://www.triplefalcon.com/

概要

 連続する同一記号の列を、記号列の長さを示す数字で置き換えることで圧縮を行うことをランレングス圧縮といいます。

 ランレングス圧縮可逆圧縮の一種です。

 冗長な情報を思いつこうとして、おそらく最初に思いつくのが同じ文字の繰り返しでしょう。情報の内容が、例えば "うああああああああああああ・・・あ!" であり、最初の "う"に続けて同じ文字 "あ" が 100個も並んでいたとします。この文字列を紙に書く場合、"あ" を本当に 100 回列挙するよりも <"う"が1個 、 "あ" が100個 、"!" が1個> と工夫して書けば短い言葉で表現できます。

 ぴったり状況にはまれば役に立つ手法ですが、ランレングス圧縮が有効に活用できる場合というのは多くはありません。同じ記号が続かない場合は逆に冗長な文字列になります。

 例えば、画像に関して言えば、「白地に赤の日の丸」のような2色のデータではランレングス圧縮でとても小さくなる可能性が高いのですが、ほとんどの自然画像など多色データは、ランレングス圧縮で圧縮することは出来ないと思われます。

Team TripleFalcon. http://www.triplefalcon.com/

情報源の例

 情報源が、たまたま風向の観測データであったとします。簡単のため、風向を 8 方位で示したとしましょう。符号化のお話なので、 お約束で方位に符号を与えます。8記号として 3Bit の符号を与えます。 以下の方位と符号の対応は特に何らかの取り決めから求めたのではありません。筆者の思いついたままです。

表1 方位の符号

方位 北東 南東 南西 西 北西
符号 000 001 010 011 100 101 110 111

 長さにも符号を与えます。便宜上8までのランレングスを数えましょう。8記号なので 3Bit 与えられます。

表2 長さの符号

長さ 1 2 3 4 5 6 7 8
符号 000 001 010 011 100 101 110 111

Team TripleFalcon. http://www.triplefalcon.com/

圧縮の例

 さて、方位ばかりを出力する情報源から記号が15個出力され、記号列Aが与えられたとします。 実際に直接符号にした場合と、ランレングス圧縮を行った場合を比較しましょう。

 * 記号列A(長さ=15シンボル)

北西 北西 北西 北西 北西 北西

 各方位をそのまま符合に置き換えていくと、以下の様になります。15シンボルが45Bitに置き換わりました。

圧縮しない符号化(45Bit)

記号列 北 ,北, 北 ,北 ,東 ,東 ,東 ,北西,北西,北西,北西,北西,北西,北 ,北
符号化 000 000 000 000 010 010 010 111 111 111 111 111 111 000 000

 連続する同じ各方をひとまとめにして符合に置き換えていくと、以下の様になります。符号は、方位、長さ、方位、長さ、と続き、全部で24Bitに置き換わりました。

圧縮符号化(24Bit)

記号列 北,4,東,3,北西,6,北,2
符号化 000 011 010 010 111 101 000 001

確かに短くなりました。

Team TripleFalcon. http://www.triplefalcon.com/

工夫の例

 ここでは、絶対値を符号化してもうまくいかないけれども相対値で符号化するとうまくいくという事例を紹介します。 記号列Aは、都合よく同じ方位が続いていました。これは圧縮ができるようにわざと選んだ記号列なのですが、 記号列Bの様に並んでいたらどうでしょうか。

 * 記号列B(長さ=15シンボル)

北東 南東 南西 西 北西 北東 北東

 記号列Bの符号は(1)で、ランレングス圧縮は(1')ですが、記号数は22個に増えています。これでは圧縮になっていません。

 (1)記号列Bの符号化(長さ=45Bit)

記号列 北 ,北東,東 ,東 ,南東,南 ,南西,西 ,北西,北 ,北東,北東,北 ,北 ,北
符号化 000 001 010 010 011 100 101 110 111 000 001 001 000 000 000

 (1') 記号列Bの圧縮符号化(長さ=66Bit)

記号列 北,1,北東,1,東,2,南東,1,南,1,南西,1,西,1,北西,1,北,1,北東,2,北,3
符号化 000 000 001 000 010 001 011 000 100 000 101 000 110 000 111 000 000 000 001 001 000 010

 相対方向で表現してみるとどうなるでしょうか。 例えば、北を向くと北東は正面から右へ45度の方角に見えますが、東を向いた場合に北東は左45度の方角に見えます。 前回の向きから見て今回の向きがどの方角かを(1')に書いてみましょう。 最初の記号の「前の」記号は便宜上「北」とします。

 相対方向に符号を与えます。8記号なので 3Bit 与えられます。

方角 正面 右45° 右90° 右135° 後方 左135° 左90° 左45°
符号 000 001 010 011 100 101 110 111

 相対方向を記号とランレングスで表現し、それを符号化してみます。

 符号化(長さ=42Bit)

ランレングス 正面,1,右45°,2,正面,1,右45°,7,正面,1,左45°,1,正面,2
符号 000 000 001 001 000 000 001 110 000 000 001 000 000 001

 確かに短くなりました。

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/


Team TRIPLE FALCON

アクション&シミュレーション ゲーミングとゲーム製作を真面目に考える 新進気鋭の研究者集団

   
 
用語集TOP

ランレングス圧縮(runlength encoding)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
あ-お か-こ さ-そ た-と な-の
は-ほ ま-も や-よ ら-ろ わ-ん

数学、哲学、工学を横断する事典です。よろしければ活用してください。 ゲーム, アクション,シューティング,シミュレーション,リアルタイム, 計量経済学,計量心理学, コンピュータ,用語集,計算機科学用語集,コンピュータ用語集, 3DCG, グラフィックス,ゲームグラフィックス,美少女, 光反射,鏡面反射,拡散反射,屈折,散乱,異方性反射,影, シェーディング,レンダリング,透視変換, 発光,爆発,爆炎,煙, 物理, 人物,表情,表現,運動,力学,流体, 計算幾何学, グラフ,アフィン変換,アフィン写像,凸包,超平面,3D,3Dの数理, コンピュータサイエンス,コンピュータ, 計算機科学, チューリングマシン,チューリング機械,線形有界オートマトン,プッシュダウンオートマトン,有限オートマトン, オートマトン,状態遷移,遷移関数,対角線論法,文字列,記号, FA,NFA,PDA,NPDA,LBA,NLBA,TM, 計算量,P,NP,PSPACE,NP完全,NP困難,P完全,PSPACE完全,PP,APX,APX完全, 確率チューリング機械,確率オートマトン, 音声, 音階,音量,音律,和音,和声,無限上昇音,MIDI, 色彩, 表色系,顕色系,混色系,RGB,CMY,YCbCr,YUV,YIQ,CIE,L*a*b*, 符号, 圧縮,符号化,情報源符号化, 符号,ブロック符号,ストリーム符号,符号理論, 離散数学, 集合,写像,関数,全単写,単写,全写,対応関係,関係,反射,反射推移閉包, 代数系, 群,環,体,モノイド,半群,準同型写像,同型写像, 形式言語, 言語,正則言語,文脈自由言語,文脈依存言語,確率言語, 文法,正則文法,文脈自由文法,文脈依存文法,確率文脈自由言語, 文字,文字列, 3型言語,2型言語,1型言語,0型言語, 信号処理, 変換,フィルタ,信号処理,DFT,DCT,DST,FFT,Wavelet,フーリエ変換, 離散,コサイン変換,サイン変換,ウェーブレット, 基礎数学, 数学,応用数学,基礎数学,フィボナッチ数列, 解析学, 位相空間,線形空間,距離空間,ベクトル空間,vector,バナッハ空間,Banach,ヒルベルト空間,Hilbert,ユークリッド空間,Euclid, ノルム,内積,可算濃度,非可算濃度, 情報理論, 情報源,情報量,エントロピー,相互情報量,記号,記号列, 複雑系, カオス,フラクタル,フラクタル幾何学,カオス写像, インターネット, セキュリティ,HTTP,SMTP,FTP,プロトコル, その他理論,理論, 紅茶,自転車通勤,備忘録, 暗号, モンゴメリ演算,高速計算法,素因数分解,離散対数問題, 暗号,ブロック暗号,ストリーム暗号,楕円暗号, 乱数,乱数生成,共通鍵暗号,公開鍵暗号,公開鍵署名,鍵共有,鍵交換, 線形攻撃,差分攻撃,補間攻撃,スライド攻撃,量子暗号, 依頼計算,ゼロ知識対話証明,ハッシュ,

AES,Rijndael,RSA,ElGamal,Twofish,Serpent,

RC6,MARS,CAST,IDEA,GOST,

MQV,DH,EC-DH,EC-ElGamal,

終了,

フィリピンパブ
アミューズメント企画はお任せ
資産運用はお任せ
メール お問い合わせ お問い合わせ メール メール メール メール メール メール