Ｒｙｎのページ（商業高校情報教育研究室）

その１（ランレングス符号の一例）

同じものが続く場合に、データそのものではなく、何が幾つ続くかを数字であらわすことでデータ量を減らす。 簡単な例として、文字単位で、｢*｣を｢繰り返す回数を示す数の目印｣と規定すると、

すもももももももももももももいろいろ

というデータは、

すも*13いろいろ

となる。 連続するデータには有効だが、連続しないデータでは増えてしまう場合もある。

白黒のファックスの様に、２つの値が交互にあらわれると判っている場合は、何が、の部分が要らなくなるため、 データを少なくする事が出来る。 例えば、黒から始まり、左上から右横へ順に、とルールを決めておくと、 右図のａの場合は、
16.8.16.3.2.6.2.6.2.3
と、なり、 ｂの場合は、白から始まっているために、最初は黒が０ということにして、
0.16.8.16.3.2.6.2.6.2.3
と、なる。 ｃの市松模様の様に連続しない場合は、効果がない。

その２

同じパターンが繰り返しあらわれる場合に、 前に出たパターンの相対的な開始位置とパターンの範囲を数字であらわすことでデータ量を減らす。 簡単な例として、文字単位で、｢*｣を｢パターンの位置を示す数字の目印｣と規定すると、例えば、

だれかさんとだれかさんがむぎばたけ

というデータは、７～１１文字目｢だれかさん｣が６文字前から５文字分と同じなので、

だれかさんと*65がむぎばたけ

となり、同様に、

きしゃきしゃぽっぽぽっぽしゅっぽしゅっぽしゅっぽっぽ

というデータは、

きしゃ*33ぽっぽ*33しゅっぽ*44*44*22

となる。

その３

その２の変形。 同じパターンが繰り返しあらわれる場合に、 パターンを辞書に登録し、対応する記号を使用することでデータ量を減らす。 簡単な例として、文字単位で、｢*｣を｢登録されたパターンの記号を示す目印｣と規定すると、例えば、

きしゃきしゃぽっぽぽっぽしゅっぽしゅっぽしゅっぽっぽ

で、｢きしゃ｣をK、｢ぽっぽ｣をP、｢しゅっぽ｣をS、と辞書に登録していくと、

*K*K*P*P*S*S*Sっぽ

と変換する事が出来る。

その４（ハフマン符号の一例）

ハフマン符号は、1952年にデビット・ハフマン(David Huffman)によって考案された符号。 出現頻度によって文字コードのビット数を変えることでデータ量を減らす。 出現頻度が大きければビット数を少なく、小さければビット数を多くする。 簡単な例として、文字単位で、例えば、

きしゃきしゃぽっぽぽっぽしゅっぽしゅっぽしゅっぽっぽ

というデータを変換したい場合、
１．各文字の出現頻度を求める。
２．必要に応じて出現頻度で大きい順に並べ替える。
３．頻度の下位２つを二分木の子にしてつなぎ、親の出現頻度を２つの和にする。
　　下位２つがaとbの場合、(ab)と書くことにする。
４．２へ戻って繰り返す。

１回目の２	２回目の２	３回目の２	４回目の２	５回目の２	６回目の２
ぽ　８回 っ　６回 し　５回 ゅ　３回 き　２回 ゃ　２回	ぽ　　　８回 っ　　　６回 し　　　５回 (きゃ)　４回 ゅ　　　３回	ぽ　　　　　８回 ((きゃ)ゅ)　 ７回 っ　　　　　６回 し　　　　　５回	(っし)　　１１回 ぽ　　　　　８回 ((きゃ)ゅ) 　７回	(ぽ((きゃ)ゅ)) 　　　１５回 (っし) 　　　１１回	((ぽ((きゃ)ゅ))(っし)) 　　　　　　　　２６回

５．全ての文字が二分木につながったところで、根から、右向きなら１、左向きなら０、のビットを割り振っていく（逆でも良い）。

カッコを補足して書くと、

【 { ぽ } { [ ( き )( ゃ ) ] [ ゅ ] } 】【 { っ }{ し } 】

１ビット目は【 】、２ビット目は｛ ｝、３ビット目は［ ］、４ビット目は（ ）、と、外側のカッコのペアから、 右側にあれば１、左側にあれば０、と、たどっていくと、

ぽ　00　　　き　0100　　　ゃ　0101　　　ゅ　011　　　っ　10　　　し　11

---

「キーワード辞典」の目次へ