ZIPはなぜ圧縮できるのか 簡単な圧縮・解凍CLIをRustで作ってみる
SENKEN「サイズでかいなー。zip 使うかー。」
「...」
「...そもそもなんで zip で圧縮できるんだっけ。あれ？俺圧縮のあの字も知らなくね？？？」
とふと思ったので、とりあえず圧縮・解凍の原理理解だけする CLI を、Rust の勉強も兼ねて作ってみる
SENKEN筆者の前提知識
- なんか知らんが zip コマンドでファイルを小さくできる
- なんか知らんが unzip でもとに戻せる
- 圧縮アルゴリズムやツールが色々あることは知ってる
- zip ならだいたい半分くらいになる（ほんと？）
- Rust 初学者
やらないこと
- ZIP の詳しい説明
- 圧縮アルゴリズムの詳しい説明
SENKENまずは ChatGPT に圧縮の原理を聞いてみる
（会話内容は適宜添削している）
ワイ「zip 使うとなんで圧縮できるの？そもそもなんでサイズが減らせるのか、というところからよくわかってないんだけど」
🤖「ZIP などの圧縮形式がファイルサイズを小さくできる理由は、データの冗長性（繰り返しやパターン）をうまく利用しているからです。
たとえば、「AAAAAAAAAABBBCCCC」というデータがあったとします。このままでは 18 文字ありますが、圧縮アルゴリズムはこれを「10A3B4C」のように、同じ文字の繰り返しをカウントして短く表現できます。これは「ランレングス符号化」という圧縮方法の一例です。」
ワイ「あーなるほどね、わかりやすい。これなら俺でもできそう」
今回はアルゴリズムを突き詰めるのは諦め、この方式でやってみることにします。
となると解凍が気になる。
ワイ「じゃあなんで解凍もできるの？あと、解凍に必要な情報も含めるだろうから結果的にサイズ増えちゃわない？」
🤖「圧縮アルゴリズムは、圧縮時に必要な情報をヘッダーなどに含めて保存しています。解凍時にはこの情報を使って元のデータに戻します。追加情報は少量にして効率的に記録することで、全体的な圧縮効果が大きくなります。」
ワイ「ふむ」
ワイ「極論を言えば記録の仕方を誤ったら圧縮後のサイズが増えることもあるってことだよね」
🤖「その通りです[1]。 極論を言えば、圧縮の方法が不適切だったり、データの性質に合わなかった場合、圧縮後のファイルサイズが逆に増えることもあります。
例えば：
- すでに圧縮されているデータ
- ランダムなデータ
- 不適切な圧縮方法
などが挙げられます。」
ワイ「確かにランダムだと増えそうなイメージ。おけ、大体わかったわ」
-
「その通りです。」って言われると相手 AI でもちょっと嬉しくなっちゃうよね（単純） ↩︎
SENKENランレングス符号化の実装
以下の文章を "dodosuko.txt", UTF-8 で保存。
ドドスコスコスコドドスコスコスコドドスコスコスコラブ注入
いかにも圧縮しやすそう
サイズは 28 文字 * 3 B = 84 B
SENKEN独自ランレングス符号化の実装
単純にランレングス符号化を実装するだけだとつまらないから、ドドスコ特化のドドスコ ZIP を実装してみる。
「ドドスコスコスコ」をカウントするといい感じになりそう。つまり 8 字ずつカウントしてみる。
つまり、
3ドドスコスコスコ1ラブ注入
となり、サイズは 1 B * 2 文字 + 3 B * 12 文字 = 38 B （元：84 B） になる想定。
圧縮ファイル拡張子は .dodosuko_zip とする
use std::{
fs::File,
io::{Read, Write},
};
fn main() {
let src_file = "data_files/dodosuko.txt";
let dist_file = "data_files/dodosuko.run_length_zip";
// read contents
let mut f = File::open(src_file).expect("file not found");
let mut contents = String::new();
f.read_to_string(&mut contents)
.expect("something went wrong reading the file");
// run-length encoding
let chunk_size = 8;
let chunks: Vec<String> = contents
.chars()
.collect::<Vec<_>>()
.chunks(chunk_size)
.map(|chunk| chunk.iter().collect())
.collect();
let reset_count = 1;
let mut count = 0;
let mut output = "".to_string();
let mut previous = chunks[0].clone();
for (i, chunk) in chunks.iter().enumerate() {
if &previous == chunk {
count += 1;
continue;
}
output.push_str(&count.to_string());
output.push_str(&previous);
count = reset_count;
previous = chunk.to_string();
if i == chunks.len() - 1 {
output.push_str(&count.to_string());
output.push_str(&previous);
}
}
// write to file
let mut buf = File::create(dist_file).expect("cannot create file");
buf.write(output.as_bytes()).expect("cannot write to file");
}
❯ cargo run --bin dodosuko_zip
Compiling dodosuko-zip v0.1.0 (/home/senken/personal/dodosuko-zip)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/dodosuko_zip`
❯ ll data_files
total 8
-rw-rw-r-- 1 senken senken 38 Sep 15 04:38 dodosuko.run_length_zip
-rw-rw-r-- 1 senken senken 84 Sep 15 04:35 dodosuko.txt
38 Bに圧縮された
SENKENzip と比較する
❯ zip data_files/dodosuko.zip data_files/dodosuko.txt
adding: data_files/dodosuko.txt (deflated 67%)
❯ ll data_files
total 12
-rw-rw-r-- 1 senken senken 38 Sep 15 04:38 dodosuko.run_length_zip
-rw-rw-r-- 1 senken senken 84 Sep 15 04:35 dodosuko.txt
-rw-rw-r-- 1 senken senken 224 Sep 15 04:43 dodosuko.zip
やったーzipに勝ったー
SENKEN解凍する
use std::{
fs::File,
io::{Read, Write},
};
use regex::Regex;
fn main() {
let src_file = "data_files/dodosuko.txt";
let dist_file = "data_files/dodosuko.run_length_zip";
// read contents
let mut f = File::open(dist_file).unwrap();
let mut contents = String::new();
f.read_to_string(&mut contents).unwrap();
// run-length decoding
let mut src = "".to_string();
let count_re = Regex::new(r"\d").unwrap();
for (i, char) in contents.chars().enumerate() {
if let Some(caps) = count_re.captures(&char.to_string()) {
let chunk: String = contents.chars().skip(i + 1).take(i + 8).collect();
let chunk_num: u8 = caps[0].parse().unwrap();
for _ in 0..chunk_num {
src.push_str(&chunk);
}
}
}
// write to file
let mut buf = File::create(src_file).expect("cannot create file");
buf.write(src.as_bytes()).expect("cannot write to file");
}
❯ cargo run --bin dodosuko_unzip
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.73s
Running `target/debug/dodosuko_unzip`
❯ cat data_files/dodosuko.txt
ドドスコスコスコドドスコスコスコドドスコスコスコラブ注入
できました！
SENKENちなみにドドスコ以外だと、、、
❯ cat dodosuko.txt
雨ニモマケズ
風ニモマケズ
雪ニモ夏ノ暑サニモマケヌ
丈夫ナカラダヲモチ
慾ハナク
決シテ瞋ラズ
イツモシヅカニワラッテヰル
一日ニ玄米四合ト
味噌ト少シノ野菜ヲタベ
アラユルコトヲ
ジブンヲカンジョウニ入レズニ
ヨクミキキシワカリ
ソシテワスレズ
野原ノ松ノ林ノ※(「「蔭」の「陰のつくり」に代えて「人がしら／髟のへん」、第4水準2-86-78)ノ
小サナ萓ブキノ小屋ニヰテ
東ニ病気ノコドモアレバ
行ッテ看病シテヤリ
西ニツカレタ母アレバ
行ッテソノ稲ノ朿ヲ［＃「朿ヲ」はママ］負ヒ
南ニ死ニサウナ人アレバ
行ッテコハガラナクテモイヽトイヒ
北ニケンクヮヤソショウガアレバ
ツマラナイカラヤメロトイヒ
ヒドリノトキハナミダヲナガシ
サムサノナツハオロオロアルキ
ミンナニデクノボートヨバレ
ホメラレモセズ
クニモサレズ
サウイフモノニ
ワタシハナリタイ
❯ ll data_files
total 12
-rw-rw-r-- 1 senken senken 1105 Sep 15 05:17 dodosuko.run_length_zip
-rw-rw-r-- 1 senken senken 1057 Sep 15 05:16 dodosuko.txt
-rw-rw-r-- 1 senken senken 789 Sep 15 05:17 dodosuko.zip
結論：zip はつよかった