はじめに

以前、RustでWASMを触った際(マンデルブロ集合でJSと速度比較する記事)、「大量データをJSとWASMの間で頻繁にやり取りするとコピーのコストが無視できない」という課題が残りました。

今回はその反省を踏まえて、**「ファイルを1回だけWASMに渡し、圧縮処理は全部WASM内で完結させる」**という設計で、実用的なファイル圧縮ツールを自作します。アルゴリズムはLZ77(繰り返しパターンを過去への参照に置き換える)とハフマン符号(頻度に応じて短いビット列を割り当てる)を組み合わせた、gzipなどの基礎になっている手法です。

この記事では:

LZ77 + ハフマン符号をRustでゼロから実装
同じアルゴリズムをJSでも実装し、処理速度を比較
ブラウザでファイルをアップロードして試せるデモを用意

というところまでを扱います。

全体像

ユーザーがファイルを選択
        ↓
  ファイルを1回だけWASMメモリにコピー ← 前回の反省を踏まえた設計
        ↓
  WASM内で LZ77 → ハフマン符号 の順に圧縮(JSに戻らない)
        ↓
  圧縮後バイナリだけをJS側が受け取る

比較対象として、同じロジックのJS実装も用意し、同じファイルに対する処理時間を並べて確認できるようにします。

環境

Rust 1.75+ / wasm-bindgen 0.2
wasm-pack(WASMへのビルド用)
ブラウザ(ES Modules / WebAssemblyが使える最近のもの)

この記事のRustコード自体は検証環境(ネイティブビルド + cargo test)で動作確認済みですが、WASMへの実際のビルド(wasm-pack build)は手元の環境で行ってください。検証に使った環境がサンドボックス化されており、wasm32-unknown-unknownターゲット用のRust標準ライブラリを取得できなかった(rustupが使う配布サーバーへのアクセスが制限されていた)ため、WASM化そのものはこの記事の中では検証できていません。ロジック自体はネイティブ環境で十分にテストしているので、wasm-pack buildは素直に通るはずです。

プロジェクトの作成

まずライブラリクレートを作成します。

cargo new --lib wasm-compress
cd wasm-compress

wasm-bindgenを依存関係に追加します。

cargo add wasm-bindgen

この検証中、サンドボックス環境のrustc(1.75)に対してwasm-bindgenの最新版(0.2.127時点)が「rustc 1.77以上が必要」と拒否してくるケースに遭遇しました。手元のRustが最新なら気にする必要はありませんが、同様のエラーが出た場合はcargo add wasm-bindgen@=0.2.92のようにバージョンを指定するか、rustcを更新してください。

Cargo.tomlに、WASM向けの出力形式(cdylib)と、サイズ最適化の設定を追加します。

[package]
name = "wasm-compress"
version = "0.1.0"
edition = "2021"

[lib]
crate-type = ["cdylib", "rlib"]

[dependencies]
wasm-bindgen = "0.2"

[profile.release]
opt-level = "s"   # サイズ優先で最適化(WASMはファイルサイズもロード時間に直結するため)
lto = true        # リンク時最適化で不要なコードを削る

crate-typeにrlibも含めているのは、cargo testのようなネイティブ向けのビルド・実行もできるようにするためです(cdylibだけだとcargo testが使えません)。この後の「ネイティブ環境での検証」は、この設定があってはじめて可能になります。

続いてsrc/lz77.rs・src/huffman.rsを作成し、src/lib.rsからmodで読み込む形にします。この時点でのファイル構成は以下の通りです(空ファイルでOK、中身はこのあと埋めていきます)。

touch src/lz77.rs src/huffman.rs

wasm-compress/
├─ Cargo.toml        ← 上で編集した
└─ src/
    ├─ lib.rs         ← 自動生成されたもの。後で③の内容に書き換える
    ├─ lz77.rs         ← 今回touchで作成。①の内容を書く
    └─ huffman.rs      ← 今回touchで作成。②の内容を書く

実装1: LZ77

書き込み先: src/lz77.rs

過去に出現したバイト列と同じ並びが見つかったら、「何バイト前から何バイト分」という参照(オフセット・長さ)に置き換えます。以下はsrc/lz77.rsの全文です(テストコードは別のコードブロックとして後述しているので、両方をこのファイルに含めてください)。

トークンは「0x00 + リテラル1byte」か「0x01 + オフセット2byte + 長さ1byte」のどちらかで、マッチが3byte未満なら素直にリテラルとして出力します(短すぎるマッチは参照の方が高くつくため)。復号は逆に、参照が出てきたら「もう出力済みのバイト列」を指定分コピーするだけです。

const WINDOW_SIZE: usize = 4096;
const MIN_MATCH: usize = 3;
const MAX_MATCH: usize = 255;

/// 入力バイト列から、直前最大WINDOW_SIZEバイトの範囲で最長一致を探す
fn find_longest_match(data: &[u8], pos: usize) -> Option<(usize, usize)> {
    let window_start = pos.saturating_sub(WINDOW_SIZE);
    let max_len = (data.len() - pos).min(MAX_MATCH);
    if max_len < MIN_MATCH {
        return None;
    }

    let mut best_len = 0;
    let mut best_offset = 0;

    // 素朴な総当たり探索(教育目的の実装。大きいファイルでは遅くなる点に注意)
    for start in window_start..pos {
        let mut len = 0;
        while len < max_len && data[start + len] == data[pos + len] {
            len += 1;
        }
        if len > best_len {
            best_len = len;
            best_offset = pos - start;
        }
    }

    if best_len >= MIN_MATCH {
        Some((best_offset, best_len))
    } else {
        None
    }
}

pub fn compress(data: &[u8]) -> Vec<u8> {
    let mut out = Vec::new();
    let mut pos = 0;

    while pos < data.len() {
        match find_longest_match(data, pos) {
            Some((offset, length)) => {
                out.push(0x01);
                out.push((offset & 0xff) as u8);
                out.push(((offset >> 8) & 0xff) as u8);
                out.push(length as u8);
                pos += length;
            }
            None => {
                out.push(0x00);
                out.push(data[pos]);
                pos += 1;
            }
        }
    }

    out
}

pub fn decompress(data: &[u8]) -> Vec<u8> {
    let mut out = Vec::new();
    let mut i = 0;

    while i < data.len() {
        let marker = data[i];
        if marker == 0x00 {
            out.push(data[i + 1]);
            i += 2;
        } else {
            let offset = data[i + 1] as usize | ((data[i + 2] as usize) << 8);
            let length = data[i + 3] as usize;
            let start = out.len() - offset;
            for k in 0..length {
                let byte = out[start + k];
                out.push(byte);
            }
            i += 4;
        }
    }

    out
}

正しさは以下のテストで確認しています(これもsrc/lz77.rsの一部として、上のコードの末尾に追記してください)。

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn round_trip_repetitive() {
        let input = b"abcabcabcabcabcabcabcabcabcabcabc".to_vec();
        let compressed = compress(&input);
        let restored = decompress(&compressed);
        assert_eq!(input, restored);
        assert!(compressed.len() < input.len(), "繰り返しが多いデータは圧縮されるはず");
    }

    #[test]
    fn round_trip_random_like() {
        let input: Vec<u8> = (0..200).map(|i| ((i * 37 + 11) % 256) as u8).collect();
        let compressed = compress(&input);
        let restored = decompress(&compressed);
        assert_eq!(input, restored);
    }

    #[test]
    fn round_trip_empty() {
        let input: Vec<u8> = vec![];
        let compressed = compress(&input);
        let restored = decompress(&compressed);
        assert_eq!(input, restored);
    }

    #[test]
    fn round_trip_single_byte() {
        let input = vec![42u8];
        let compressed = compress(&input);
        let restored = decompress(&compressed);
        assert_eq!(input, restored);
    }
}

実装2: ハフマン符号

書き込み先: src/huffman.rs

LZ77が出力したトークン列(バイト列)に対して、出現頻度の高いバイトほど短いビット列を割り当てます。木の構築は優先度付きキュー(最小ヒープ)で頻度の低い2つを繰り返し統合する、教科書通りのアルゴリズムです。以下はsrc/huffman.rsの全文です(テストコードは別のコードブロックとして後述)。

use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Debug, Clone)]
enum Node {
    Leaf(u8),
    Internal(Box<Node>, Box<Node>),
}

struct HeapItem {
    freq: u64,
    order: u64, // 同じ頻度のときに決定的な順序をつけるためのタイブレーク用
    node: Node,
}

impl PartialEq for HeapItem {
    fn eq(&self, other: &Self) -> bool {
        self.freq == other.freq && self.order == other.order
    }
}
impl Eq for HeapItem {}
impl Ord for HeapItem {
    fn cmp(&self, other: &Self) -> Ordering {
        // BinaryHeapは最大値を先頭に取るため、最小値(=最も優先度が高い)を先頭にしたい
        // ここでは逆順にして「頻度が小さい方が大きい」ことにする(=最小ヒープ化)
        other.freq.cmp(&self.freq).then(other.order.cmp(&self.order))
    }
}
impl PartialOrd for HeapItem {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn build_frequency_table(data: &[u8]) -> Vec<(u8, u64)> {
    let mut counts = [0u64; 256];
    for &b in data {
        counts[b as usize] += 1;
    }
    let mut freqs: Vec<(u8, u64)> = counts
        .iter()
        .enumerate()
        .filter(|&(_, &c)| c > 0)
        .map(|(sym, &c)| (sym as u8, c))
        .collect();
    freqs.sort_by_key(|&(sym, _)| sym); // 決定的な順序にする
    freqs
}

fn build_tree(freqs: &[(u8, u64)]) -> Node {
    let mut heap = BinaryHeap::new();
    for (order, &(sym, freq)) in freqs.iter().enumerate() {
        heap.push(HeapItem { freq, order: order as u64, node: Node::Leaf(sym) });
    }

    let mut next_order = freqs.len() as u64;
    while heap.len() > 1 {
        let a = heap.pop().unwrap();
        let b = heap.pop().unwrap();
        let combined = HeapItem {
            freq: a.freq + b.freq,
            order: next_order,
            node: Node::Internal(Box::new(a.node), Box::new(b.node)),
        };
        next_order += 1;
        heap.push(combined);
    }

    heap.pop().unwrap().node
}

fn generate_codes(node: &Node, prefix: &mut Vec<bool>, table: &mut [Option<Vec<bool>>; 256]) {
    match node {
        Node::Leaf(sym) => {
            // 単一シンボルしかない場合(prefixが空)は便宜上1ビットのコード"0"を割り当てる
            let code = if prefix.is_empty() { vec![false] } else { prefix.clone() };
            table[*sym as usize] = Some(code);
        }
        Node::Internal(left, right) => {
            prefix.push(false);
            generate_codes(left, prefix, table);
            prefix.pop();
            prefix.push(true);
            generate_codes(right, prefix, table);
            prefix.pop();
        }
    }
}

struct BitWriter {
    bytes: Vec<u8>,
    current: u8,
    filled: u8,
}

impl BitWriter {
    fn new() -> Self {
        BitWriter { bytes: Vec::new(), current: 0, filled: 0 }
    }
    fn push_bit(&mut self, bit: bool) {
        self.current = (self.current << 1) | (bit as u8);
        self.filled += 1;
        if self.filled == 8 {
            self.bytes.push(self.current);
            self.current = 0;
            self.filled = 0;
        }
    }
    fn push_bits(&mut self, bits: &[bool]) {
        for &b in bits {
            self.push_bit(b);
        }
    }
    fn total_bits(&self) -> u32 {
        (self.bytes.len() as u32) * 8 + self.filled as u32
    }
    fn finish(mut self) -> Vec<u8> {
        if self.filled > 0 {
            self.current <<= 8 - self.filled;
            self.bytes.push(self.current);
        }
        self.bytes
    }
}

struct BitReader<'a> {
    bytes: &'a [u8],
    bit_pos: u32,
}

impl<'a> BitReader<'a> {
    fn new(bytes: &'a [u8]) -> Self {
        BitReader { bytes, bit_pos: 0 }
    }
    fn read_bit(&mut self) -> bool {
        let byte = self.bytes[(self.bit_pos / 8) as usize];
        let shift = 7 - (self.bit_pos % 8);
        let bit = (byte >> shift) & 1 == 1;
        self.bit_pos += 1;
        bit
    }
}

fn write_u32(out: &mut Vec<u8>, v: u32) {
    out.extend_from_slice(&v.to_le_bytes());
}
fn read_u32(data: &[u8], pos: &mut usize) -> u32 {
    let v = u32::from_le_bytes(data[*pos..*pos + 4].try_into().unwrap());
    *pos += 4;
    v
}

pub fn compress(data: &[u8]) -> Vec<u8> {
    let mut out = Vec::new();
    write_u32(&mut out, data.len() as u32);

    if data.is_empty() {
        write_u32(&mut out, 0); // num_symbols = 0
        return out;
    }

    let freqs = build_frequency_table(data);
    write_u32(&mut out, freqs.len() as u32);
    for &(sym, freq) in &freqs {
        out.push(sym);
        out.extend_from_slice(&freq.to_le_bytes());
    }

    let tree = build_tree(&freqs);
    let mut table: [Option<Vec<bool>>; 256] = std::array::from_fn(|_| None);
    generate_codes(&tree, &mut Vec::new(), &mut table);

    let mut writer = BitWriter::new();
    for &b in data {
        let code = table[b as usize].as_ref().unwrap();
        writer.push_bits(code);
    }
    let bit_len = writer.total_bits();
    let bitstream = writer.finish();

    write_u32(&mut out, bit_len);
    out.extend_from_slice(&bitstream);

    out
}

pub fn decompress(data: &[u8]) -> Vec<u8> {
    let mut pos = 0;
    let original_len = read_u32(data, &mut pos) as usize;
    let num_symbols = read_u32(data, &mut pos) as usize;

    if original_len == 0 || num_symbols == 0 {
        return Vec::new();
    }

    let mut freqs = Vec::with_capacity(num_symbols);
    for _ in 0..num_symbols {
        let sym = data[pos];
        pos += 1;
        let freq = u64::from_le_bytes(data[pos..pos + 8].try_into().unwrap());
        pos += 8;
        freqs.push((sym, freq));
    }

    if num_symbols == 1 {
        // 単一シンボルのみ: ビットストリームを読まずにそのまま埋める
        return vec![freqs[0].0; original_len];
    }

    let bit_len = read_u32(data, &mut pos);
    let bitstream = &data[pos..];

    let tree = build_tree(&freqs);
    let mut reader = BitReader::new(bitstream);
    let mut out = Vec::with_capacity(original_len);

    let mut bits_read = 0u32;
    while out.len() < original_len && bits_read < bit_len {
        let mut node = &tree;
        loop {
            match node {
                Node::Leaf(sym) => {
                    out.push(*sym);
                    break;
                }
                Node::Internal(left, right) => {
                    let bit = reader.read_bit();
                    bits_read += 1;
                    node = if bit { right } else { left };
                }
            }
        }
    }

    out
}

正しさは以下のテストで確認しています(src/huffman.rsの末尾に追記してください)。

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn round_trip_text() {
        // 24byteの小さい入力。ヘッダー(頻度表)のオーバーヘッドの方が大きくなるため、
        // ここでは正しさ(round-trip)だけを確認し、サイズ比較はより大きい入力のテストで行う
        let input = b"aaaaaaaaabbbbbbccccddde".to_vec();
        let compressed = compress(&input);
        let restored = decompress(&compressed);
        assert_eq!(input, restored);
    }

    #[test]
    fn compression_shrinks_larger_skewed_input() {
        // 十分大きく、頻度に偏りがあるデータならヘッダー分を差し引いても圧縮されるはず
        let input = "a".repeat(500) + &"b".repeat(300) + &"c".repeat(100) + &"d".repeat(20) + "e";
        let compressed = compress(input.as_bytes());
        let restored = decompress(&compressed);
        assert_eq!(input.as_bytes(), restored);
        assert!(compressed.len() < input.len(), "十分大きい入力ならヘッダーオーバーヘッドを吸収して圧縮されるはず");
    }

    #[test]
    fn round_trip_single_symbol() {
        let input = vec![7u8; 50];
        let compressed = compress(&input);
        let restored = decompress(&compressed);
        assert_eq!(input, restored);
    }

    #[test]
    fn round_trip_empty() {
        let input: Vec<u8> = vec![];
        let compressed = compress(&input);
        let restored = decompress(&compressed);
        assert_eq!(input, restored);
    }

    #[test]
    fn round_trip_two_symbols() {
        let input = vec![1u8, 2, 1, 2, 1, 1, 1, 2];
        let compressed = compress(&input);
        let restored = decompress(&compressed);
        assert_eq!(input, restored);
    }

    #[test]
    fn round_trip_all_byte_values() {
        let input: Vec<u8> = (0..=255u8).collect();
        let compressed = compress(&input);
        let restored = decompress(&compressed);
        assert_eq!(input, restored);
    }
}

頻度が同じシンボルが複数あるとヒープの取り出し順が曖昧になり、エンコード時とデコード時で違う木が組まれてしまうと復号できません。そのためorder(挿入順)をタイブレークに使い、同じ頻度分布からは常に同じ木が再構築されるようにしています。

圧縮結果のフォーマットはこうしました。

[4byte: 元データの長さ]
[4byte: 出現する異なるバイトの種類数(num_symbols)]
[num_symbols個の (1byte symbol, 8byte 頻度) の組]  ← ここがヘッダー
[4byte: ビットストリームのビット数]
[ビットストリーム本体]

デコード側は、この頻度表からエンコード時と全く同じ手順で木を再構築することで、ハフマン木そのものを保存せずに復号できるようにしています。

実装3: 組み合わせてWASMエクスポート

書き込み先: src/lib.rs(cargo newで自動生成された内容を、以下で丸ごと置き換える)

mod huffman;
mod lz77;

use wasm_bindgen::prelude::*;

/// LZ77でパターンを短い参照に置き換えたあと、ハフマン符号でビット単位まで詰める
#[wasm_bindgen]
pub fn compress(data: &[u8]) -> Vec<u8> {
    let lz77_tokens = lz77::compress(data);
    huffman::compress(&lz77_tokens)
}

/// compress()の逆操作
#[wasm_bindgen]
pub fn decompress(data: &[u8]) -> Vec<u8> {
    let lz77_tokens = huffman::decompress(data);
    lz77::decompress(&lz77_tokens)
}

#[wasm_bindgen]を関数に付けるだけで、JS側からcompress(bytes) / decompress(bytes)として呼べるようになります。ポイントは、JSとやり取りするのはこの2関数だけということです。LZ77とハフマン符号の間でデータがJS側に戻ることは一切なく、WASMメモリ内で完結します。

動作確認(ネイティブ環境での検証)

wasm_bindgenのマクロは、コンパイル対象がWASMでなくても(ネイティブ向けにビルドしても)問題なく機能するので、cargo testでロジックそのものの正しさを検証できます。

#[cfg(test)]
mod tests {
    use super::*;

    fn round_trip_check(input: &[u8]) {
        let compressed = compress(input);
        let restored = decompress(&compressed);
        assert_eq!(input, restored.as_slice());
    }

    #[test]
    fn round_trip_repetitive_text() {
        let input = "the quick brown fox jumps over the lazy dog. \
                      the quick brown fox jumps over the lazy dog again."
            .as_bytes();
        round_trip_check(input);
    }
    // ...他、JSON風データ・空データ・バイナリ風データなど計15ケース
}

$ cargo test
running 15 tests
test huffman::tests::compression_shrinks_larger_skewed_input ... ok
test huffman::tests::round_trip_all_byte_values ... ok
test huffman::tests::round_trip_empty ... ok
test huffman::tests::round_trip_single_symbol ... ok
test huffman::tests::round_trip_text ... ok
test huffman::tests::round_trip_two_symbols ... ok
test lz77::tests::round_trip_empty ... ok
test lz77::tests::round_trip_random_like ... ok
test lz77::tests::round_trip_repetitive ... ok
test lz77::tests::round_trip_single_byte ... ok
test tests::compression_actually_shrinks_repetitive_data ... ok
test tests::round_trip_binary_like ... ok
test tests::round_trip_empty ... ok
test tests::round_trip_json_like ... ok
test tests::round_trip_repetitive_text ... ok

test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

最初、24byteの短いテキストで「圧縮後の方が小さくなるはず」というテストを書いたところ失敗しました。原因を調べると、ヘッダー(頻度表: シンボルごとに1byte+8byte)だけで57byteになっており、入力が小さいとヘッダーのオーバーヘッドの方が大きくなるという、この実装の素朴さゆえの制約に気づきました。round-trip(可逆性)自体は問題なく、サイズ比較のテストケースをより大きい入力に差し替えて対応しています。この「小さいファイルは逆に膨らむことがある」という性質は、後述のベンチマークでも実際に確認できます。

もう少し実データに近いサンプルでも検証しました(Rustネイティブ・releaseビルド)。後述の「動作確認用のサンプルファイルを作る」で生成するsample-log.txt / sample-data.json / sample-prose.txt / sample-random.binが、それぞれ以下の4行に対応しています。

繰り返しの多いログ風テキスト(sample-log.txt):    元=27000 byte, 圧縮後=727 byte, 削減率=97.3%
JSON風データ(sample-data.json):                 元=12380 byte, 圧縮後=4081 byte, 削減率=67.0%
自然文の繰り返し(sample-prose.txt):              元=9840 byte, 圧縮後=810 byte, 削減率=91.8%
疑似ランダムバイト列(sample-random.bin):          元=5000 byte, 圧縮後=8534 byte, 削減率=-70.7%

繰り返しの多いデータほどよく効き、逆にランダムに近いデータでは圧縮後の方が大きくなることが分かります。これはLZ77がマッチを一切見つけられず全バイトがリテラル(2byteに膨張)になり、ハフマン符号も一様に近い分布では圧縮効果がほぼゼロになるためです。「何でも圧縮すれば小さくなる」わけではない、というのが実装して初めて数字で確認できたポイントでした。

処理時間のスケール感も確認しています(反復の多いテキストでの計測)。

10KB(実際9768byte) -> 圧縮後623byte, 所要時間=916.795µs
50KB(実際48972byte) -> 圧縮後811byte, 所要時間=5.358421ms
100KB(実際97944byte) -> 圧縮後1027byte, 所要時間=11.014924ms
200KB(実際195888byte) -> 圧縮後1449byte, 所要時間=21.942307ms

反復が少ないデータでは、LZ77の総当たり探索(素朴な実装)のコストが効いてきて、もっと時間がかかります。

5KB(疑似ランダム) -> 圧縮後8686byte, 所要時間=19.389849ms
10KB(疑似ランダム) -> 圧縮後15079byte, 所要時間=51.161779ms
20KB(疑似ランダム) -> 圧縮後27826byte, 所要時間=113.785049ms
40KB(疑似ランダム) -> 圧縮後53335byte, 所要時間=243.874905ms

このLZ77実装はウィンドウ内を毎回総当たりで探索するシンプルな作りなので、繰り返しの少ないデータやサイズの大きいファイルでは処理時間が伸びやすい点は、実用上の制約として明記しておきます(ハッシュテーブルで候補を絞り込むなどの最適化は今回のスコープ外にしています)。

JS版の実装と比較

書き込み先: index.html内の<script type="module">ブロック(デモページに直接埋め込む形。単体のJSファイルとして扱いたい場合はcompress.jsなどに切り出してもOKです)

同じアルゴリズム・同じバイナリフォーマットで、JS版も実装しました。ロジックはRust版と1対1で対応させています。LZ77部分だけ雰囲気を見ると、こんな感じです(全文は後述の「ブラウザデモの使い方」でindex.htmlとして掲載します)。

function lz77Compress(data) {
  const out = [];
  let pos = 0;
  while (pos < data.length) {
    const windowStart = Math.max(0, pos - WINDOW_SIZE);
    const maxLen = Math.min(data.length - pos, MAX_MATCH);
    let bestLen = 0, bestOffset = 0;
    if (maxLen >= MIN_MATCH) {
      for (let start = windowStart; start < pos; start++) {
        let len = 0;
        while (len < maxLen && data[start + len] === data[pos + len]) len++;
        if (len > bestLen) { bestLen = len; bestOffset = pos - start; }
      }
    }
    if (bestLen >= MIN_MATCH) {
      out.push(0x01, bestOffset & 0xff, (bestOffset >> 8) & 0xff, bestLen);
      pos += bestLen;
    } else {
      out.push(0x00, data[pos]);
      pos += 1;
    }
  }
  return Uint8Array.from(out);
}

Rust版のfind_longest_match + compressをそのままJSに移植した形です。

buildFrequencyTable → buildTree → generateCodes → BitWriter/BitReader という構成は、Rust版のhuffman.rsと1対1で対応しています。ヒープの実装だけはBinaryHeapが無い分、配列を毎回ソートする素朴なMinHeapクラスにしていますが(同点時のタイブレークとしてorderを使うのも同じ)、アルゴリズムとしては同一です。

Node.jsで同じテストケースを実行すると、圧縮率はRust版と完全に一致しました(アルゴリズムが同一なので当然ですが、実装ミスがないことの確認になります)。

OK   繰り返しログ風: 元=27000byte 圧縮後=727byte 削減率=97.3%
OK   JSON風データ: 元=12380byte 圧縮後=4081byte 削減率=67.0%
OK   自然文の繰り返し: 元=9840byte 圧縮後=810byte 削減率=91.8%
OK   疑似ランダムバイト列: 元=5000byte 圧縮後=7023byte 削減率=-40.5%
OK   空データ: 元=0byte 圧縮後=8byte 削減率=-Infinity%
OK   単一バイト: 元=1byte 圧縮後=31byte 削減率=-3000.0%
OK   0-255全バイト値: 元=256byte 圧縮後=2635byte 削減率=-929.3%

「疑似ランダムバイト列」の削減率がRust版(-70.7%)とJS版(-40.5%)で異なりますが、これはバグではなく生成した疑似乱数の値そのものが違うためです。同じ線形合同法の式(seed * 1103515245 + 12345)を使っていますが、Rustはu32のwrapping演算で正確に計算できるのに対し、JSのNumber型は掛け算の途中で2^53を超える桁が発生し得るため、ビット演算(&, >>>)適用前に精度が失われます。テキストベースのテスト(繰り返しログ・JSON・自然文)は文字列→UTF-8バイト列という決定的な変換なので数値が完全一致しており、疑似乱数生成部分だけがJS特有の制約に引っかかった形です。乱数を使うテストをJS/Rust間で厳密に一致させたい場合は、XorShiftなど32bit範囲に収まる演算だけで構成されるアルゴリズムに変える必要があります。

処理時間はNode.js(V8)上でこうなりました。

繰り返しの多いログ風テキスト: 圧縮=17.15ms
JSON風データ: 圧縮=13.50ms
自然文の繰り返し: 圧縮=0.93ms

--- サイズごとのスケーリング(反復テキスト) ---
10KB -> 所要時間=1.60ms
50KB -> 所要時間=14.65ms
100KB -> 所要時間=16.94ms
200KB -> 所要時間=33.25ms

Rustのネイティブreleaseビルドと比べると、同じ処理でおおよそ2〜7倍程度Rust側が高速という結果でした。

ここで比較しているのは「Rustのネイティブbuild」対「Node.js(V8)」であり、実際にブラウザ上で動くWASM対ブラウザのJSエンジンの比較ではありません。この検証環境ではwasm32ターゲットのビルドができなかったため、ここではあくまで参考値として扱ってください。実際にブラウザで計測した結果は、この後の「ブラウザ実機での実測結果」セクションで解説します(結論から言うと、ここでのネイティブ同士の比較とは違う結果になりました)。

ブラウザデモの使い方

ここまでの手順で、以下のファイル構成になっているはずです(index.htmlはCargo.tomlと同じ階層、つまりwasm-compressプロジェクトのルートに置きます)。

wasm-compress/
  ├─ Cargo.toml
  ├─ index.html          ブラウザデモ(WASM版とJS版を両方動かして比較)
  └─ src/
      ├─ lib.rs           wasm_bindgenのエクスポート
      ├─ lz77.rs
      └─ huffman.rs

書き込み先: index.html(wasm-compressプロジェクトのルート。Cargo.tomlと同じ階層)

以下が全文です。CSS・ファイルアップロードUI・WASM/JS両方の読み込みと実行・結果表示まで、これ1ファイルで完結します。JS版の圧縮ロジック(LZ77+ハフマン符号)も<script type="module">内にそのまま含まれています。

<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>LZ77 + ハフマン圧縮 - WASM vs JS 比較デモ</title>
<style>
  :root {
    --bg: #0f1117;
    --panel: #1a1d27;
    --border: #2a2e3a;
    --text: #e5e7eb;
    --muted: #8b93a7;
    --accent-wasm: #3b82f6;
    --accent-js: #f59e0b;
    --good: #34d399;
    --bad: #f87171;
    --mono: "SFMono-Regular", Consolas, "Liberation Mono", Menlo, monospace;
  }
  * { box-sizing: border-box; }
  body {
    margin: 0;
    background: var(--bg);
    color: var(--text);
    font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", "Hiragino Sans", sans-serif;
    padding: 32px 20px 80px;
  }
  .wrap { max-width: 760px; margin: 0 auto; }
  h1 {
    font-size: 22px;
    font-weight: 700;
    margin: 0 0 6px;
    letter-spacing: -0.01em;
  }
  .subtitle {
    color: var(--muted);
    font-size: 14px;
    margin: 0 0 32px;
    line-height: 1.6;
  }
  .panel {
    background: var(--panel);
    border: 1px solid var(--border);
    border-radius: 12px;
    padding: 24px;
    margin-bottom: 20px;
  }
  .panel h2 {
    font-size: 13px;
    text-transform: uppercase;
    letter-spacing: 0.06em;
    color: var(--muted);
    margin: 0 0 16px;
    font-weight: 600;
  }
  .drop {
    border: 1.5px dashed var(--border);
    border-radius: 10px;
    padding: 28px;
    text-align: center;
    cursor: pointer;
    transition: border-color 0.15s ease, background 0.15s ease;
  }
  .drop:hover, .drop.dragover {
    border-color: var(--accent-wasm);
    background: rgba(59, 130, 246, 0.06);
  }
  .drop-label { font-size: 14px; color: var(--text); margin-bottom: 4px; }
  .drop-sub { font-size: 12px; color: var(--muted); }
  input[type="file"] { display: none; }

  .file-info {
    display: none;
    margin-top: 16px;
    font-size: 13px;
    font-family: var(--mono);
    color: var(--muted);
  }
  .file-info.show { display: block; }

  button.run {
    margin-top: 18px;
    width: 100%;
    padding: 12px;
    background: var(--accent-wasm);
    color: #fff;
    border: none;
    border-radius: 8px;
    font-size: 14px;
    font-weight: 600;
    cursor: pointer;
    transition: opacity 0.15s ease;
  }
  button.run:disabled { opacity: 0.4; cursor: not-allowed; }
  button.run:not(:disabled):hover { opacity: 0.9; }

  .status {
    font-size: 13px;
    color: var(--muted);
    margin-top: 12px;
    font-family: var(--mono);
    white-space: pre-wrap;
    min-height: 18px;
  }

  table.results {
    width: 100%;
    border-collapse: collapse;
    font-size: 13px;
    margin-top: 4px;
  }
  table.results th, table.results td {
    text-align: left;
    padding: 10px 8px;
    border-bottom: 1px solid var(--border);
  }
  table.results th {
    color: var(--muted);
    font-weight: 600;
    font-size: 11px;
    text-transform: uppercase;
    letter-spacing: 0.04em;
  }
  table.results td.num { font-family: var(--mono); text-align: right; }
  .badge {
    display: inline-block;
    padding: 2px 8px;
    border-radius: 999px;
    font-size: 11px;
    font-weight: 600;
  }
  .badge.wasm { background: rgba(59,130,246,0.15); color: var(--accent-wasm); }
  .badge.js { background: rgba(245,158,11,0.15); color: var(--accent-js); }
  .ratio.good { color: var(--good); }
  .ratio.bad { color: var(--bad); }

  .bars { margin-top: 20px; }
  .bar-row { margin-bottom: 12px; }
  .bar-label {
    display: flex;
    justify-content: space-between;
    font-size: 12px;
    color: var(--muted);
    margin-bottom: 4px;
    font-family: var(--mono);
  }
  .bar-track {
    height: 8px;
    background: var(--border);
    border-radius: 4px;
    overflow: hidden;
  }
  .bar-fill { height: 100%; border-radius: 4px; }
  .bar-fill.wasm { background: var(--accent-wasm); }
  .bar-fill.js { background: var(--accent-js); }

  .note {
    font-size: 12px;
    color: var(--muted);
    line-height: 1.7;
    margin-top: 20px;
    padding-top: 16px;
    border-top: 1px solid var(--border);
  }
  .note code {
    background: rgba(255,255,255,0.06);
    padding: 1px 5px;
    border-radius: 4px;
    font-family: var(--mono);
    font-size: 11px;
  }
  .warn {
    background: rgba(245, 158, 11, 0.08);
    border: 1px solid rgba(245, 158, 11, 0.3);
    border-radius: 8px;
    padding: 12px 14px;
    font-size: 12px;
    color: #fbbf24;
    line-height: 1.6;
    margin-bottom: 20px;
  }
</style>
</head>
<body>
<div class="wrap">
  <h1>LZ77 + ハフマン圧縮: WASM vs JS</h1>
  <p class="subtitle">
    同じ圧縮アルゴリズム(LZ77 + ハフマン符号、自前実装)を、Rust→WASM版とJS版の両方で動かして
    処理時間・圧縮率を比較するデモです。ファイルはアップロード後、ブラウザ内だけで処理され、外部には送信されません。
  </p>

  <div id="wasm-warning" class="warn">
    ⚠️ WASMモジュール(<code>./pkg/wasm_compress.js</code>)が読み込めていません。
    <code>wasm-pack build --target web</code> でビルドし、<code>pkg</code> フォルダをこのHTMLと同じ階層に置いてください
    (詳細は下部の「セットアップ」参照)。JS版のみでも動作確認できます。
  </div>

  <div class="panel">
    <h2>1. ファイルを選択</h2>
    <div class="drop" id="drop">
      <div class="drop-label">クリックしてファイルを選択、またはドラッグ&ドロップ</div>
      <div class="drop-sub">テキスト・JSON・画像など何でも試せます</div>
    </div>
    <input type="file" id="file-input">
    <div class="file-info" id="file-info"></div>
    <button class="run" id="run-btn" disabled>圧縮を実行(WASM / JS 両方)</button>
    <div class="status" id="status"></div>
  </div>

  <div class="panel" id="results-panel" style="display:none;">
    <h2>2. 結果</h2>
    <table class="results">
      <thead>
        <tr>
          <th></th>
          <th class="num">圧縮後サイズ</th>
          <th class="num">削減率</th>
          <th class="num">圧縮時間</th>
          <th class="num">解凍時間</th>
        </tr>
      </thead>
      <tbody id="results-body"></tbody>
    </table>

    <div class="bars" id="bars"></div>
  </div>

  <div class="panel note">
    <strong style="color:var(--text)">セットアップ</strong><br>
    このHTMLはES Modulesとfetch(WASM読み込み)を使うため、<code>file://</code>では動きません。
    同じフォルダで簡易サーバーを立ててアクセスしてください。<br><br>
    <code>cargo install wasm-pack</code> を実行後、このHTMLと同じ<code>wasm-compress</code>ディレクトリで<code>wasm-pack build --target web</code>を実行すると<code>pkg/</code>が生成されます。<br>
    <code>uv run python -m http.server 8080</code> → <code>http://localhost:8080</code> にアクセスしてください。
  </div>
</div>

<script type="module">
// ============================================================
// JS版: LZ77 + ハフマン符号(Rust/WASM版と同一アルゴリズム・同一バイナリフォーマット)
// ============================================================
const WINDOW_SIZE = 4096;
const MIN_MATCH = 3;
const MAX_MATCH = 255;

function lz77Compress(data) {
  const out = [];
  let pos = 0;
  while (pos < data.length) {
    const windowStart = Math.max(0, pos - WINDOW_SIZE);
    const maxLen = Math.min(data.length - pos, MAX_MATCH);
    let bestLen = 0, bestOffset = 0;
    if (maxLen >= MIN_MATCH) {
      for (let start = windowStart; start < pos; start++) {
        let len = 0;
        while (len < maxLen && data[start + len] === data[pos + len]) len++;
        if (len > bestLen) { bestLen = len; bestOffset = pos - start; }
      }
    }
    if (bestLen >= MIN_MATCH) {
      out.push(0x01, bestOffset & 0xff, (bestOffset >> 8) & 0xff, bestLen);
      pos += bestLen;
    } else {
      out.push(0x00, data[pos]);
      pos += 1;
    }
  }
  return Uint8Array.from(out);
}

function lz77Decompress(data) {
  const out = [];
  let i = 0;
  while (i < data.length) {
    if (data[i] === 0x00) {
      out.push(data[i + 1]);
      i += 2;
    } else {
      const offset = data[i + 1] | (data[i + 2] << 8);
      const length = data[i + 3];
      const start = out.length - offset;
      for (let k = 0; k < length; k++) out.push(out[start + k]);
      i += 4;
    }
  }
  return Uint8Array.from(out);
}

class MinHeap {
  constructor() { this.items = []; }
  push(item) {
    this.items.push(item);
    this.items.sort((a, b) => (a.freq - b.freq) || (a.order - b.order));
  }
  pop() { return this.items.shift(); }
  get length() { return this.items.length; }
}

function buildFrequencyTable(data) {
  const counts = new Array(256).fill(0);
  for (const b of data) counts[b]++;
  const freqs = [];
  for (let sym = 0; sym < 256; sym++) if (counts[sym] > 0) freqs.push([sym, counts[sym]]);
  return freqs;
}

function buildTree(freqs) {
  const heap = new MinHeap();
  freqs.forEach(([sym, freq], order) => heap.push({ freq, order, node: { leaf: sym } }));
  let nextOrder = freqs.length;
  while (heap.length > 1) {
    const a = heap.pop(), b = heap.pop();
    heap.push({ freq: a.freq + b.freq, order: nextOrder++, node: { left: a.node, right: b.node } });
  }
  return heap.pop().node;
}

function generateCodes(node, prefix, table) {
  if ("leaf" in node) {
    table[node.leaf] = prefix.length > 0 ? prefix.slice() : [0];
    return;
  }
  generateCodes(node.left, [...prefix, 0], table);
  generateCodes(node.right, [...prefix, 1], table);
}

class BitWriter {
  constructor() { this.bytes = []; this.current = 0; this.filled = 0; }
  pushBit(bit) {
    this.current = (this.current << 1) | bit;
    this.filled++;
    if (this.filled === 8) { this.bytes.push(this.current); this.current = 0; this.filled = 0; }
  }
  pushBits(bits) { for (const b of bits) this.pushBit(b); }
  totalBits() { return this.bytes.length * 8 + this.filled; }
  finish() {
    if (this.filled > 0) { this.current <<= (8 - this.filled); this.bytes.push(this.current); }
    return Uint8Array.from(this.bytes);
  }
}

class BitReader {
  constructor(bytes) { this.bytes = bytes; this.bitPos = 0; }
  readBit() {
    const byte = this.bytes[Math.floor(this.bitPos / 8)];
    const bit = (byte >> (7 - (this.bitPos % 8))) & 1;
    this.bitPos++;
    return bit;
  }
}

function writeU32(arr, v) { arr.push(v & 0xff, (v >> 8) & 0xff, (v >> 16) & 0xff, (v >> 24) & 0xff); }
function readU32(data, posRef) {
  const p = posRef.pos;
  const v = data[p] | (data[p + 1] << 8) | (data[p + 2] << 16) | (data[p + 3] << 24);
  posRef.pos += 4;
  return v >>> 0;
}

function huffmanCompress(data) {
  const out = [];
  writeU32(out, data.length);
  if (data.length === 0) { writeU32(out, 0); return Uint8Array.from(out); }
  const freqs = buildFrequencyTable(data);
  writeU32(out, freqs.length);
  for (const [sym, freq] of freqs) { out.push(sym); writeU32(out, freq); writeU32(out, 0); }
  const tree = buildTree(freqs);
  const table = new Array(256);
  generateCodes(tree, [], table);
  const writer = new BitWriter();
  for (const b of data) writer.pushBits(table[b]);
  const bitLen = writer.totalBits();
  const bitstream = writer.finish();
  writeU32(out, bitLen);
  return Uint8Array.from([...out, ...bitstream]);
}

function huffmanDecompress(data) {
  const posRef = { pos: 0 };
  const originalLen = readU32(data, posRef);
  const numSymbols = readU32(data, posRef);
  if (originalLen === 0 || numSymbols === 0) return Uint8Array.from([]);
  const freqs = [];
  for (let i = 0; i < numSymbols; i++) {
    const sym = data[posRef.pos]; posRef.pos += 1;
    const freqLow = readU32(data, posRef);
    readU32(data, posRef);
    freqs.push([sym, freqLow]);
  }
  if (numSymbols === 1) return new Uint8Array(originalLen).fill(freqs[0][0]);
  const bitLen = readU32(data, posRef);
  const bitstream = data.slice(posRef.pos);
  const tree = buildTree(freqs);
  const reader = new BitReader(bitstream);
  const out = new Uint8Array(originalLen);
  let outLen = 0, bitsRead = 0;
  while (outLen < originalLen && bitsRead < bitLen) {
    let node = tree;
    while (!("leaf" in node)) { const bit = reader.readBit(); bitsRead++; node = bit ? node.right : node.left; }
    out[outLen++] = node.leaf;
  }
  return out;
}

function jsCompress(data) { return huffmanCompress(lz77Compress(data)); }
function jsDecompress(data) { return lz77Decompress(huffmanDecompress(data)); }

// ============================================================
// WASM版のロード(wasm-packの出力を想定)
// ============================================================
let wasmModule = null;
try {
  const mod = await import("./pkg/wasm_compress.js");
  await mod.default();
  wasmModule = mod;
  document.getElementById("wasm-warning").style.display = "none";
} catch (e) {
  console.warn("WASMモジュールの読み込みに失敗しました。JS版のみ利用可能です。", e);
}

// ============================================================
// UI配線
// ============================================================
const dropEl = document.getElementById("drop");
const fileInput = document.getElementById("file-input");
const fileInfoEl = document.getElementById("file-info");
const runBtn = document.getElementById("run-btn");
const statusEl = document.getElementById("status");
const resultsPanel = document.getElementById("results-panel");
const resultsBody = document.getElementById("results-body");
const barsEl = document.getElementById("bars");

let currentFile = null;

dropEl.addEventListener("click", () => fileInput.click());
dropEl.addEventListener("dragover", (e) => { e.preventDefault(); dropEl.classList.add("dragover"); });
dropEl.addEventListener("dragleave", () => dropEl.classList.remove("dragover"));
dropEl.addEventListener("drop", (e) => {
  e.preventDefault();
  dropEl.classList.remove("dragover");
  if (e.dataTransfer.files.length > 0) setFile(e.dataTransfer.files[0]);
});
fileInput.addEventListener("change", () => {
  if (fileInput.files.length > 0) setFile(fileInput.files[0]);
});

function setFile(file) {
  currentFile = file;
  fileInfoEl.textContent = `${file.name} (${formatBytes(file.size)})`;
  fileInfoEl.classList.add("show");
  runBtn.disabled = false;
  resultsPanel.style.display = "none";
  statusEl.textContent = "";
}

function formatBytes(n) {
  if (n < 1024) return `${n} B`;
  if (n < 1024 * 1024) return `${(n / 1024).toFixed(1)} KB`;
  return `${(n / 1024 / 1024).toFixed(2)} MB`;
}

function bytesEqual(a, b) {
  if (a.length !== b.length) return false;
  for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) return false;
  return true;
}

runBtn.addEventListener("click", async () => {
  if (!currentFile) return;
  runBtn.disabled = true;
  statusEl.textContent = "ファイルを読み込み中...";

  const buf = new Uint8Array(await currentFile.arrayBuffer());
  const rows = [];

  // --- JS版 ---
  statusEl.textContent = "JS版で圧縮中...";
  await new Promise((r) => setTimeout(r, 0)); // UIを一度更新させる
  const jsResult = runOne("JS", jsCompress, jsDecompress, buf);
  rows.push(jsResult);

  // --- WASM版(あれば) ---
  if (wasmModule) {
    statusEl.textContent = "WASM版で圧縮中...";
    await new Promise((r) => setTimeout(r, 0));
    const wasmResult = runOne("WASM", wasmModule.compress, wasmModule.decompress, buf);
    rows.push(wasmResult);
  }

  renderResults(buf.length, rows);
  statusEl.textContent = "完了";
  runBtn.disabled = false;
});

function runOne(label, compressFn, decompressFn, buf) {
  const t0 = performance.now();
  const compressed = compressFn(buf);
  const t1 = performance.now();
  const restored = decompressFn(compressed);
  const t2 = performance.now();
  const ok = bytesEqual(buf, restored);
  return {
    label,
    compressedSize: compressed.length,
    compressTime: t1 - t0,
    decompressTime: t2 - t1,
    ok,
  };
}

function renderResults(originalSize, rows) {
  resultsPanel.style.display = "block";
  resultsBody.innerHTML = "";
  barsEl.innerHTML = "";

  const maxTime = Math.max(...rows.map((r) => r.compressTime), 1);

  for (const r of rows) {
    const ratio = 100 * (1 - r.compressedSize / originalSize);
    const ratioClass = ratio >= 0 ? "good" : "bad";
    const badgeClass = r.label === "WASM" ? "wasm" : "js";

    const tr = document.createElement("tr");
    tr.innerHTML = `
      <td><span class="badge ${badgeClass}">${r.label}</span>${r.ok ? "" : " ⚠️round-trip不一致"}</td>
      <td class="num">${formatBytes(r.compressedSize)}</td>
      <td class="num ratio ${ratioClass}">${ratio >= 0 ? "-" : "+"}${Math.abs(ratio).toFixed(1)}%</td>
      <td class="num">${r.compressTime.toFixed(2)} ms</td>
      <td class="num">${r.decompressTime.toFixed(2)} ms</td>
    `;
    resultsBody.appendChild(tr);

    const barClass = r.label === "WASM" ? "wasm" : "js";
    const pct = Math.max(2, (r.compressTime / maxTime) * 100);
    const barRow = document.createElement("div");
    barRow.className = "bar-row";
    barRow.innerHTML = `
      <div class="bar-label"><span>${r.label} 圧縮時間</span><span>${r.compressTime.toFixed(2)} ms</span></div>
      <div class="bar-track"><div class="bar-fill ${barClass}" style="width:${pct}%"></div></div>
    `;
    barsEl.appendChild(barRow);
  }

  if (rows.length === 2) {
    const [a, b] = rows;
    const faster = a.compressTime < b.compressTime ? a : b;
    const slower = a.compressTime < b.compressTime ? b : a;
    const speedup = (slower.compressTime / faster.compressTime).toFixed(2);
    statusEl.textContent = `${faster.label}の方が${speedup}倍高速でした(このファイル・このブラウザでの結果)`;
  }
}
</script>
</body>
</html>

ポイントだけ補足します。

冒頭で./pkg/wasm_compress.jsをimportしていますが、try/catchで囲んであるので、まだwasm-pack buildしていない段階でもエラーにならずJS版のみで動作します(画面上部に警告バナーが出ます)
runOne()関数が、WASM版・JS版どちらの呼び出しにも使い回せる共通の実行ロジックです。渡すcompress/decompress関数が違うだけで、計測・比較のコードは共通化しています
ドラッグ&ドロップとファイル選択ダイアログ、両方に対応しています

1. WASMをビルドする

まずwasm-pack本体をインストールします(未インストールの場合)。

cargo install wasm-pack

この検証環境(apt経由でインストールしたrustc 1.75)では、wasm-packのビルドにedition2024という比較的新しいCargoの機能が必要で、「feature edition2024 is required」というエラーになり、cargo install wasm-pack自体を最後まで検証できませんでした。rustupで最新のRustを入れている環境であれば問題なく通るはずです。もし同じエラーが出た場合は、OSのパッケージマネージャ(apt等)ではなくrustupでRustを入れ直すか、rustup updateで最新化してみてください。

インストールできたら、wasm-compressディレクトリ(Cargo.tomlがある場所)でビルドします。まだcdしていない場合はcd wasm-compressで移動してください。

wasm-pack build --target web

ビルドが成功するとwasm-compress/pkg/にJSバインディングと.wasmファイルが生成されます。index.htmlも同じwasm-compress/直下に置いてあるので、./pkgへの相対パスはこのままで参照でき、ファイルをコピーする必要はありません。

2. 動作確認用のサンプルファイルを作る

検証で使ったのと同じ4種類のファイルを生成するPythonスクリプトです。wasm-compressディレクトリ(index.htmlと同じ階層)にgenerate_samples.pyとして保存してください。

書き込み先: wasm-compress/generate_samples.py

# 検証と同じ4種類のサンプルファイルを生成する

# 1. 繰り返しの多いログ風テキスト(27,000 byte)
with open("sample-log.txt", "w") as f:
    for _ in range(500):
        f.write("2026-08-16 12:00:00 INFO request completed status=200\n")

# 2. JSON風データ(12,380 byte)
with open("sample-data.json", "w") as f:
    for i in range(300):
        f.write('{"id":%d,"name":"user%d","active":true},' % (i, i))

# 3. 自然文の繰り返し(9,840 byte)
with open("sample-prose.txt", "w") as f:
    text = (
        "The quick brown fox jumps over the lazy dog. "
        "Pack my box with five dozen liquor jugs. "
        "How vexingly quick daft zebras jump! "
    ) * 80
    f.write(text)

# 4. 疑似ランダムバイナリ(5,000 byte、圧縮すると逆に膨らむ実演用)
with open("sample-random.bin", "wb") as f:
    seed = 12345
    out = bytearray()
    for _ in range(5000):
        seed = (seed * 1103515245 + 12345) & 0xffffffff
        out.append((seed >> 16) & 0xff)
    f.write(out)

print("4つのサンプルファイルを生成しました")

実行はこちらです(OS問わずuvがあれば同じコマンドで動きます)。

uv run python generate_samples.py

wasm-compressディレクトリ直下にsample-log.txt / sample-data.json / sample-prose.txt / sample-random.binの4つが生成されます。

デモページ(index.html)にこれらのファイルをドラッグ&ドロップすると、上記の検証結果と同じ傾向が再現できます。特にsample-random.binは「圧縮したのにファイルが大きくなる」パターンの実演用です。

3. ローカルサーバーで開く

ES Modules・WASMの読み込みはfile://では動かないため、簡易サーバーを立てます。

uv run python -m http.server 8080

http://localhost:8080にアクセスし、ファイルをドラッグ&ドロップすれば、WASM版・JS版それぞれの圧縮時間・削減率がその場で表示されます。pkgフォルダが無い場合はJS版のみで動作し、画面上部に注意書きが表示されます。

ブラウザ実機での実測結果

Brave(Chromium系)で、opt-level = "s"(サイズ優先)とopt-level = 3(速度優先)の2パターンでビルドし直して計測しました。

ファイル	JS(opt="s")	WASM(opt="s")	JS(opt=3)	WASM(opt=3)
sample-log.txt	8.00 ms	7.10 ms	4.70 ms	4.50 ms
sample-data.json	7.80 ms	12.00 ms	10.80 ms	12.90 ms
sample-prose.txt	0.60 ms	0.90 ms	0.80 ms	0.80 ms
sample-random.bin	22.80 ms	36.90 ms	31.50 ms	36.20 ms

「WASMの方が速いはず」という予想に反して、4ファイル中3ファイルでJSの方が速いという結果になりました。しかもopt-levelを"s"(サイズ優先)から3(速度優先)に変えても傾向は変わらず、最適化レベルが原因ではないことが分かります。

繰り返しの多い最大のファイル(sample-log.txt)だけは両方の最適化レベルでWASMがわずかに上回りましたが、それ以外(JSON・自然文・疑似ランダム)はJSと同等かJSの方が速い結果でした。

考えられる理由:

JS↔WASM間のデータの往復コスト: compress()を呼ぶたびに、入力のUint8ArrayをWASM線形メモリにコピーし、戻り値のVec<u8>もコピーして返しています。今回のファイルサイズ(5〜27KB)では、この往復コストが無視できない割合を占めている可能性があります
V8のJITがこの手の処理を得意としている: 今回の処理は型付き配列への素朴なループ・分岐が中心で、ブランチ予測やインライン化が効きやすいパターンです。「WASMなら何でも速い」わけではなく、V8のTurboFanが強い領域だと差が縮む、あるいは逆転することがある、というのが実機で確認できた結果でした

「WASMだから速いはず」を無条件に信じるのではなく、実際に計測して確かめることの重要性を、身をもって実感した結果になりました。

まとめ

前回の「JS-WASM間のデータ往復コスト」という課題を踏まえ、今回はファイルを1回だけ渡し、圧縮処理はWASM内で完結させる設計にした
LZ77 + ハフマン符号を自前実装し、ネイティブ環境で15ケースのround-tripテストを通して正しさを確認した
圧縮効果はデータの性質に大きく左右され、繰り返しの多いデータには強い一方、ランダムに近いデータではむしろサイズが増えることを実測で確認した
JS版も同一アルゴリズムで実装し、テキストベースのテストでは圧縮結果が完全に一致することを確認した(実装の正しさの相互検証になった)
ロジックはネイティブ環境で検証し、実機のブラウザ(Brave)で改めて速度を測定したところ、「WASMの方が速いはず」という予想に反して、4ファイル中3ファイルでJSの方が速いという結果になった。opt-levelを変えても傾向は変わらず、JS↔WASM間のデータコピーコストや、V8のJITがこの種の処理を得意としていることが要因として考えられる

「大きいデータをどう扱うか」を意識して設計しても、素朴な総当たりLZ77探索のような別のボトルネックが残っていることや、「WASMなら速い」という前提そのものが今回のワークロードでは成り立たなかったことに、実際にベンチマークを取って初めて気づけました。次にこのテーマを触るなら、ハッシュテーブルでマッチ候補を絞り込むLZ77の高速化(zlib等が実際に使っている手法)に加えて、JS↔WASM間のデータコピー回数を減らす設計(WASM側のメモリを直接参照するなど)を試して、WASMが優位になる条件をもっと掘り下げてみたいところです。