STEP 1661 · 2026-09-02 · rei-aios · 掛谷 arc A-1
NCD clustering + 差分保存
単一 archive を 上回れなかった (反証記録)
「類似 file を NCD (正規化圧縮距離) で clustering して cluster ごと に solid 圧縮する と、
単一 file 圧縮 の 総和 を 大きく 上回る」 という 仮説 を Wikipedia 200 記事 (1.2 MB) で 実測。
判定軸 = 「NCD cluster + solid の 総サイズ が 全 concat + xz -9e (STEP 1656 相当) を 下回るか」。
結論: NO — best cluster (k=1 = 全 concat) の 389,000 bytes に 対し、
参照 solid + xz -9e は 377,680 bytes で xz -9e が 3% 勝ち。 clustering の 追加価値 = 検出できず。
結果 一覧 (200 記事 = 1,234,799 bytes)
| # | 戦略 | 総サイズ (bytes) | 比率 | bpc | 備考 |
|---|
| A | 個別 zstd -19 | 551,165 | 0.4464 | 3.5709 | 各 file 独立圧縮 の 総和 |
| B | Dedup + zstd -19 | 557,565 | 0.4515 | 3.6123 | 200/200 = 全 unique、 map 6.4KB overhead で 個別より 悪化 |
| C | Solid + zstd -19 | 389,000 | 0.3150 | 2.5202 | 全 concat + zstd -19 (E k=1 と 同値) |
| D | Zstd dict (訓練 + 個別) | 494,508 | 0.4005 | 3.2038 | dict 112 KB overhead が 効かず、 個別 A より やや良い 程度 |
| E | NCD cluster k=5 + solid | 391,311 | 0.3169 | 2.5352 | k=1 (C) より 0.6% 悪 |
| E | NCD cluster k=10 + solid | 395,895 | 0.3206 | 2.5649 | |
| E | NCD cluster k=20 + solid | 406,019 | 0.3288 | 2.6305 | |
| E | NCD cluster k=40 + solid | 432,400 | 0.3502 | 2.8014 | |
| F | Solid + xz -9e (参照) | 377,680 | 0.3059 | 2.4469 | ★ 最良、 全 concat + xz -9e |
bpc 帯 (短いほど良い)
オレンジ = 最良、 青 = clustering 系 (C/E)、 赤 = clustering しても 個別より 悪化 する 群 (A/B/D)
要点 3 件
- 全 concat + 強圧縮 (solid xz -9e) が 単純最良。 cluster に 分割する と cross-cluster redundancy を 失い、 xz が 見ていた 大域構造 が 消える。
- NCD cluster k=1 = 全 concat 単一 cluster、 これ が E 系列 で 最良 = clustering の 追加価値 ゼロ。 k を 上げる ほど 悪化 (k=200 = A 個別)。 clustering が 意味 を 持つ 領域 は 「file が 明確に 別 domain の 混合」 のみ、 均質 Wikipedia 200 記事 は 該当しない。
- Zstd dict (D) は 期待外れ — dict 112 KB overhead が 効かず、 個別 zstd より 良い が clustering 系 に 負ける。 200 記事 の 均質性 に 対し dict の adaptation 幅 が 不足。 dict base 圧縮 が 効く の は 「多数 の 小 file」 (数 KB × 数千個) の 領域。
反証 の 意義
「集合圧縮 が xz -9e 単体 を 上回る」 仮説 は 反証 = 前 turn A/B/C 分類 の A-1 判定軸 「xz -9e 単体 を 上回るか」 に NO。
これ は 掛谷 arc B/C 分類 の 判断 に 影響:
- B-4 (Tang Nano 9K LZ4 encoder): A-1 が xz -9e を 上回れなかった ため、 「圧縮率 で 勝つ 路線」 は 現時点 断念、 throughput 特化 (LZ4 の 元来 利点) を 前面に。
- B-5 (CM/NN 予測器 並列化): cmix の 0.14 bpc は xz -9e の 1.99 bpc を 14x 圧縮率で 上回る = 「超圧縮 chip」 の 意義 は 残る、 但し 実装コスト 桁違い。
- C-6 (Stitch/DreamCoder + D-FUMT): 記述長 minimization 系 は clustering と 直交 = 別 dimension で 攻める 意義 変わらず、 但し 「記述長 gain が xz -9e より 1 order 良い」 を 実測前提 に する 必要 (現時点 予想値 なし)。
Honest scope
- Corpus 選択 が 効く — 均質 Wikipedia 200 記事 は 「clustering が 効かない 側」 の 実例。 別 domain (源 code / log file / 電子回路 image 群) で 結果 逆転 の 可能性 は 残る。
- Zstd dict は default settings のみ 試行、 dict サイズ tuning + 訓練 corpus 選択 で 改善余地。 但し 「clustering + dict」 の 組合せ は 未試行。
- NCD 計算 は zlib DEFLATE (fast approx)、 zstd/xz で 計算した NCD で clustering する と 別 結果 の 可能性 (但し 相対順位 は 保存される 想定)。
- Single-linkage clustering のみ、 average/complete/Ward 等 で 別 clustering 得られる が、 均質 corpus では 大差 なし の 予想。
- 200 記事 × 8 KB は 中 scale、 大 scale (10^6 file) で clustering の overhead / benefit が 逆転 の 可能性 は 別 実測 必要。
掛谷 arc 内 の 位置
成果物
data/ncd-clustering/results-step1661.json — A/B/C/D/E/F 全結果scripts/ncd-clustering/run-ncd.py — 実装 (~250 行)- 本 site page +
dist-renderer/tools/ mirror force-track