uniqコマンドでランレングス圧縮できるって本当?

7-1.ファイル・アーカイブ


アニメ『不機嫌なモノノケ庵』(2016)

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

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

uniqコマンドは、重複する行を検出できるコマンドです。このコマンドを使って簡単なランレングス圧縮をしてみましょう。

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

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

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

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

takk~$ 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
takk~$ 
takk~$ bc <<< 'scale=3;204/294'
.693
takk~$ 

圧縮率は70%弱でした。

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

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

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

takk~$ 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
takk~$ cmp a.txt b.txt
takk~$ 

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

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

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

uniqで圧縮してみます。

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

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

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

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

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

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

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

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

コメント

タイトルとURLをコピーしました