uniqコマンドでランレングス圧縮


アニメ『不機嫌なモノノケ庵』
妖怪が見えるようになってしまった15歳の男子高校生、芦屋花繪が、安倍晴齋の奉公人として、妖怪のことを理解し彼らとの親交を深めていきます。安倍晴齋は花繪と同じく15歳高校生ですが、物怪庵の主で、現世と隠世を行き来する「扉」を開くことができます。それだけでなく、茶室(物怪庵)みたいな空間から、現世のいろいろな「扉」を介して、いろんな場所に行き来できます。学校の教室の扉を出ると茶室(物怪庵)であったり、茶室(物怪庵)を出るとどこかの家の押入れであったり。要するにどこでもドア。
苗字が安倍〜ってぐらいだから、陰陽師の妖怪払いを想像しますが、戦って退治するタイプではなく、妖怪に満足してもらって、妖怪の世界「隠世」へ帰ってもらうってものです。満足して心残りがなくなると、妖怪の体がものすごく小さくなってコンパクトになります。 このコンパクトな姿こそ、真の妖怪の姿のようです。モジャっていう白い犬?のような妖怪が可愛いので視聴継続予定です。

コンピュータを使う上でデータを圧縮してコンパクトにすることは、いろんなことの節約につながります。ファイルサイズが小さくなるので、メモリが節約できたり、転送する時の通信費の節約にもなりますね。とても大事な圧縮ですが、普段何気なくtar等でツールを使ってはいますが、圧縮の理屈についてはあまり考えていませんでした。今回は、圧縮アルゴリズムの入門の「扉」、ランレングス法を理解していきます。

uniqコマンドで簡単なランレングス圧縮をしてみましょう。

圧縮元データとしては、以下のテキストを用意しました。

~$ ls -l
合計 4
-rw-rw-r-- 1 takk takk 294  8月  8 21:22 a.txt
~$ cat a.txt
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
cccccccccccccccccccccccccccccc
dddddddddddddddddddddddddddddddddddddddd
eeeeeeeeeeeeeeeeeeeee
fffffffffffffffffffffffffffffffffffffffffffffff
gggggggggggggggggggggggggggggg
hhhhhhhhhhhhhh
iiiiiiiiiiiiiiiiiiiiiiiiiiii
~$ 

さっそく、uniqコマンドで圧縮してみます。
figure-uniq-title

uniqの-cオプションで連続する同値をカウントすることができます。
これこそがランレングス法の理屈かと思います(実用向きではありませんが)。
圧縮効率はいかがなものでしょうか。元ファイルと比較してみましょう。

~$ ls -l
合計 8
-rw-rw-r-- 1 takk takk 294  8月  8 21:22 a.txt
-rw-rw-r-- 1 takk takk 204  8月  8 21:36 a.z
~$ 
~$ bc <<< 'scale=3;204/294'
.693
~$ 

圧縮率は70%弱でした。

さて、圧縮というからには、伸長できなければなりません。ここではawkを使って伸長します。

~$ awk '{n=$1;while(n--){printf"%c",$2}}' <a.z > b.txt

a.zファイルを伸長したb.txtができました。果たしてa.txtと一致するでしょうか。

~$ ls -l
合計 12
-rw-rw-r-- 1 takk takk 294  8月  8 21:22 a.txt
-rw-rw-r-- 1 takk takk 204  8月  8 21:36 a.z
-rw-rw-r-- 1 takk takk 294  8月  8 21:45 b.txt
~$ cmp a.txt b.txt
~$ 

cmpの結果に何も表示されなかった、ということは、一致したということですね。

極端に圧縮効率の良いファイルを作ってみましょう。

~$ dd if=/dev/zero of=a.bin bs=1 count=1024
1024+0 レコード入力
1024+0 レコード出力
1024 バイト (1.0 kB) コピーされました、 0.00452106 秒、 226 kB/秒
~$ ls -lh a.bin
-rw-rw-r-- 1 takk takk 1.0K  8月  8 22:01 a.bin
~$ 

uniqで圧縮してみます。

~$ hexdump -ve '/1 "%d\n"' a.bin | uniq -c | tee a.bin.z
   1024 0
~$ 

サイズはこのとおり、10Byteです。

~$ ls -l a.bin.z
-rw-rw-r-- 1 takk takk 10  8月  8 22:01 a.bin.z
~$ 

伸長して、元ファイルと比べてみます。

~$ awk '{n=$1;while(n--){printf"%c",$2}}' <a.bin.z > b.bin
~$ cmp a.bin b.bin
~$ 
~$ 

伸長したファイルは元ファイルと一致しました。

~$ bc <<< 'scale=3;10/1024'
.009
~$ 

1KByteが10Byteなので、0.09%の圧縮率になりましたね。

One response to “uniqコマンドでランレングス圧縮

  1. Grade A stuff. I’m unuiostqenably in your debt.

Leave a Reply

Your email address will not be published. Required fields are marked *

CAPTCHA