LZ圧縮をRustでやってみようとした。 [プログラミング]
前回、ランレングスをRustでやってみたんだけど、圧縮率としても微妙だし、本気でやりだすとファイルフォーマットとか色々考えないといけなくなるので、エンコードするところで止めました。元々ランレングスを使っているファイルフォーマットは、BMPの圧縮ぐらいにしか使われていないので、実際のデータとして検証するのが難しいところもある。そのため、わりに実装しやすいけど、実用的ではないということでやめました。
ファイル圧縮というと他にLZ法があるなとは思っていましたが、そこまで真剣に調べたことがありませんでした。仮に使うとしてもすでにライブラリがあったりで、中身を云々することなくファイルを指定してあげる程度で使えていたはずです。とりあえず、今回LZ法の色々とその方法を調べておくことにしました。そこそこボリュームがありそうなので、実際に実装するのはだいぶ後になりそう。
LZ法全体を舐めた後でZIPとか実装して、その後Linuxとかで使われるアーカイバをソースから探っていくことにしましょうかね。そこまで続けてできるかどうかわからんけど、C言語を置換していく一つのケースワークとしてやっていこうと思っています。まぁ途中で投げ出す可能性が高いですけどね。ランレングスも当初考えていたよりも、きっちりと決まっているものではなかったから、途中でやめてしまったし。
ともあれ、LZ法は圧縮方法としてはメジャーだと思うので、実装しておいてもいいかなと思ったりしている。現在のLZ法は既に確立したファイルフォーマットとして確立しているので、生の原理を知るのはいいかなと。
まずLZ法にはLZ77とLZ78があるらしい。これはググった説明ページのどこにも書かれていた。77の方がSliding Window、78の方が辞書の方法で圧縮をかけているようだ。今のところ、何のことやらわからない。
細かい圧縮法の違いは以下のサイトに出ている。LZ法と書かれているところだけど、こういう図はとてもありがたい。ついでに#でジャンプできるようにしておいてほしいｗ。
https://service.plan-b.co.jp/blog/tech/10282/
LZ77系にはDeflateとLZSSがあり
LZ78系にはLZWがある
形式名を言われたところでなんのこっちゃだけど、使われているファイル形式を見るとそのまんまなので直接的にわかりやすい。今の使われている感じとしてはZIPなどのDeflateが総本山な気がするけれども、なんとなく昔GIFで問題になったLZWを最初にやりたい気がしている。
若い人にはGIFの問題と言われてわからない人もいるかと思いますが、GIFの圧縮方法の特許で一悶着あったのです。ユニシスが他の買収した会社の特許で、フリーに使えていたGIFの使用料を取り始めたので、インターネット全体から大ブーイングになったという話です。
https://www.tohoho-web.com/wwwxx051.htm
https://www.gnu.org/philosophy/gif.ja.html
元々GIFは特にお金を払わずとも使えていたのですが、それを作るソフトに特許料を支払えと言い出したために、新しくPNGというフォーマットが生まれたと認識しています。なおPNGはDeflateを使っているのでLZWの特許には触れないわけですね。ともあれLZWの特許はとっくに切れているので、心置きなく使えるようにはなっています。ファイルフォーマットも一般的なので検証とかには比較的楽に使えそうな気はします。
とりあえず道筋はできました。今回もソースなどの提示はしません、すいません。そのうち書きます。LZの基礎をやって、LZWとDeflateをやってみる、でいきたいと思います。なかなか遠い道のりだとは思いますが、GitHubにソースを置いてやってみたいと思います。さてサンプルコードはないかな、と。Deflateのzlibとかは普通にそのままあるんだろうけど、LZWとかはきつそうな気がする。毎回最初はRustどうでもいい話になっちゃってすいません。
ファイル圧縮というと他にLZ法があるなとは思っていましたが、そこまで真剣に調べたことがありませんでした。仮に使うとしてもすでにライブラリがあったりで、中身を云々することなくファイルを指定してあげる程度で使えていたはずです。とりあえず、今回LZ法の色々とその方法を調べておくことにしました。そこそこボリュームがありそうなので、実際に実装するのはだいぶ後になりそう。
LZ法全体を舐めた後でZIPとか実装して、その後Linuxとかで使われるアーカイバをソースから探っていくことにしましょうかね。そこまで続けてできるかどうかわからんけど、C言語を置換していく一つのケースワークとしてやっていこうと思っています。まぁ途中で投げ出す可能性が高いですけどね。ランレングスも当初考えていたよりも、きっちりと決まっているものではなかったから、途中でやめてしまったし。
ともあれ、LZ法は圧縮方法としてはメジャーだと思うので、実装しておいてもいいかなと思ったりしている。現在のLZ法は既に確立したファイルフォーマットとして確立しているので、生の原理を知るのはいいかなと。
まずLZ法にはLZ77とLZ78があるらしい。これはググった説明ページのどこにも書かれていた。77の方がSliding Window、78の方が辞書の方法で圧縮をかけているようだ。今のところ、何のことやらわからない。
細かい圧縮法の違いは以下のサイトに出ている。LZ法と書かれているところだけど、こういう図はとてもありがたい。ついでに#でジャンプできるようにしておいてほしいｗ。
https://service.plan-b.co.jp/blog/tech/10282/
LZ77系にはDeflateとLZSSがあり
LZ78系にはLZWがある
形式名を言われたところでなんのこっちゃだけど、使われているファイル形式を見るとそのまんまなので直接的にわかりやすい。今の使われている感じとしてはZIPなどのDeflateが総本山な気がするけれども、なんとなく昔GIFで問題になったLZWを最初にやりたい気がしている。
若い人にはGIFの問題と言われてわからない人もいるかと思いますが、GIFの圧縮方法の特許で一悶着あったのです。ユニシスが他の買収した会社の特許で、フリーに使えていたGIFの使用料を取り始めたので、インターネット全体から大ブーイングになったという話です。
https://www.tohoho-web.com/wwwxx051.htm
https://www.gnu.org/philosophy/gif.ja.html
元々GIFは特にお金を払わずとも使えていたのですが、それを作るソフトに特許料を支払えと言い出したために、新しくPNGというフォーマットが生まれたと認識しています。なおPNGはDeflateを使っているのでLZWの特許には触れないわけですね。ともあれLZWの特許はとっくに切れているので、心置きなく使えるようにはなっています。ファイルフォーマットも一般的なので検証とかには比較的楽に使えそうな気はします。
とりあえず道筋はできました。今回もソースなどの提示はしません、すいません。そのうち書きます。LZの基礎をやって、LZWとDeflateをやってみる、でいきたいと思います。なかなか遠い道のりだとは思いますが、GitHubにソースを置いてやってみたいと思います。さてサンプルコードはないかな、と。Deflateのzlibとかは普通にそのままあるんだろうけど、LZWとかはきつそうな気がする。毎回最初はRustどうでもいい話になっちゃってすいません。
タグ：RUST
2021-12-14 09:47
コメント(0)
コメント 0