Rustでランレングスから始めよう。とした

自分がモデムで電話回線を使ってインターネットを始めた頃には、いろいろ圧縮方法があって今みたいにOSに付いているzipでいいやというわけにはいかなかった。回線が細い頃には、少しでも圧縮率が高い方式が尊ばれて、実際ダウンロード時間を削ってくれた良いことであったし、解凍できない時にはダウンロードデータが間違っていることも分かったりしていた。

圧縮方式としてランレングスという方法が一般的だということは知っていた。でも、実際に使ったことはなかった。というか、大体の技術は使っていても間接的であるということなのだが、暗号化にしてもAPIにしたがっていればそれなりの事ができて用は足りていたわけだ。そんなわけで詳しくは知らない。多分続いているデータを束ねて圧縮するものっぽいことぐらいしか分かっていない。

ここに各種圧縮法とランレングスの実際が書かれている。わかりやすい。

http://www.snap-tck.com/room03/c02/comp/comp01.html

ただランレングスの実際としては、データが日本語であるという事は限定的すぎる。説明のためにわかりやすくという事なんだろうけど、なんのデータに対しても使えるやり方にしたい。

話はちょっと違うけど、パソコン通信の時代にはアスキー文字に符号化して圧縮する方式があったとか。どういう名前かは忘れた。そもそもメールもアスキー文字しか使っちゃいけなかったんだよね。Base64とかQuoted-Printableとかで送るのが基本なんだけど、一時期バイナリメールとかもあったね。初期の頃の通信はアスキー文字を使うという基本があったのかもね、よく知らんけど。


ランレングスと言えばFAXだろうと思ってググってみた。

http://www.infonet.co.jp/ueyama/ip/binary/run_len.html

ここで疑問に思ったのが、ランレングス法と書いてあるけど、やっている事はハフマン符号化じゃないかという事だった。ランレングスは連続したビットを数えてまとめることをやっているわけだけど、Modified Huffman codingと書いてある通り、ハフマン符号化じゃないかと。

思っていたランレングスは連続したビットの数を交互に示すものだった。下のような感じ。

https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q12174226402

分かりやすいけど、連続する数を示すときのビットの切れ目とかどうするんだと思ってしまう。
先のFAXのランレングスを再度見ると、連続したビットを示していることに変わりはないみたい。だからランレングスであり符号化でもあるという事なのかな？

http://www.infonet.co.jp/ueyama/ip/binary/mh_coding.html

それとG3 FAXという事で、別の方式の圧縮方法もありそうな気がする。理解のためには圧縮率が低くてもアルゴリズムが単純な方がいい。

https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%AF%E3%82%B7%E3%83%9F%E3%83%AA

むー、G1で無圧縮で6分機とか言っているから、間の単純なランレングスとかはなさそうだな。FAXから離れて純粋にランレングスを改めて調べましょう。実際にあるものをやった方がいいと思ったけど、汎用技術ではなくて一つの規格になっているので、細かく見ていくとしんどくなりそうだし。


元々FAXなどで使われていて、二値データを圧縮するために使われていたわけだけど、プログラミングのサンプルとしてはバイト単位で続いているデータを圧縮するというのが多くて、デジタルデータ全般への汎用性はかなり落ちる。

C#でちょっと長たらしい。
https://algoful.com/Archive/Algorithm/RLE

Rubyがわかれば端的で良い。
https://mi-chan-nel.com/run-length-encoding/

今回は長くなったのでソースは書かないが、次回はRubyのソースを元にRustのソースを提示しようと思う。でも、ソースが短いので関数にわけないので、Rustで面倒な引数の渡し方を示す事がしにくいかもしれない。逆にRustどうでもいいソースになりそうだけど、はじめなので簡単なものにします。

タグ：RUST