Day 160-Q3 — 2026-09-25 — 内容定義チャンク分割（Gear ハッシュ・FastCDC の境界判定）で、1 バイト挿入しても重複排除が崩れないバックアップを作る

問題

バイト列 $S$（旧版）と $T$（新版）、パラメータ $mn, bits, mx$ が与えられる。$G[c]=\mathrm{sm}(c)$（$c=0..255$、$\mathrm{sm}$ は splitmix64 の finalizer）、$\mathrm{MASK}$ を **上位 $bits$ ビットだけが 1** の 64 ビット値とし、バイト列 $D$（長さ $n$）を次の手順で塊（チャンク）に切る。

• 現在位置 $s$ から、残り $n-s\le mn$ なら残り全部を 1 塊にして終わる
• そうでなければ $fp=0$ とし、$i=s+mn,\ s+mn+1,\dots,\ \min(n,s+mx)-1$ の順に

$fp\leftarrow(2\cdot fp+G[D_i])\bmod 2^{64}$ を計算し、$fp\ \&\ \mathrm{MASK}=0$ となった最初の $i$ で $D[s..i]$ を 1 塊とする

• 見つからなければ長さ $\min(n-s,mx)$ で切る。次の $s$ は塊の直後

$S$ を切った塊をすべて保存済みとする。$T$ を切った塊を先頭から順に見て、保存済みの塊と内容が一致しないものを新たに保存する（保存したものは以後保存済み）。$S$ の塊数、$T$ の塊数、新たに保存したバイト数の合計を出力せよ。

入力形式

mn bits mx
S
T

制約

入出力例

4 2 16
djicfjhjbjaheiddhiihgcdcigabcjaeaehjgggjhcfbachdegegigjfijgj
djicfjhjbjaheiddhiihgcdciXgabcjaeaehjgggjhcfbachdegegigjfijgj

10 10 24

（$T$ は $S$ の 26 文字目に X を 1 文字挿入したもの。塊の長さは $S$: 5,5,5,11,7,5,5,5,10,2、$T$: 5,5,5,11,5,8,5,5,10,2。挿入を含む塊 dhiihgcdciX と、境界がずれた gabcj・aeaehjgg の 3 塊（11+5+8=24 バイト）だけが新規で、その後は gjhcf から境界が再び一致する。同じ入力を 6 バイト固定長で切ると、挿入位置以降が全部ずれて 61 バイト中 37 バイトが新規になる）

Gear ハッシュによる境界判定は Xia ら「FastCDC: a Fast and Efficient Content-Defined Chunking Approach for Data Deduplication」（USENIX ATC 2016、https://www.usenix.org/conference/atc16/technical-sessions/presentation/xia 、2026-09-25 参照）の Algorithm 1（最小長の読み飛ばし＋上位ビットのマスク）を簡略化したもの。論文はオープンソースの Rabin 方式 CDC より約 10 倍速いと報告している。

概念図：内容定義チャンクと固定長の比較

ヒント（クリックで段階的に開示）

mask = ((1 << bits) - 1) << (64 - bits)
fp = 0; cut = end
for i in range(s + mn, end):
    fp = ((fp << 1) + GEAR[data[i]]) & M64
    if fp & mask == 0:
        cut = i + 1; break
# 保存: set(bytes) に入れ、T の塊が無ければ len を足して追加

模範解答 (Python)

📋 コピーimport sys

M64 = (1 << 64) - 1


def splitmix64(x):
    x = (x + 0x9E3779B97F4A7C15) & M64
    x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & M64
    x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & M64
    return x ^ (x >> 31)


GEAR = [splitmix64(c) for c in range(256)]


def chunks(data, mn, bits, mx):
    mask = ((1 << bits) - 1) << (64 - bits)   # 上位 bits ビット（直近 64 バイトに依存）
    n = len(data)
    out = []
    s = 0
    while s < n:
        rem = n - s
        if rem <= mn:
            out.append(data[s:]); break
        end = s + min(rem, mx)
        fp = 0
        cut = end
        for i in range(s + mn, end):          # 先頭 mn バイトは読み飛ばす（cut-point skipping）
            fp = ((fp << 1) + GEAR[data[i]]) & M64
            if fp & mask == 0:
                cut = i + 1
                break
        out.append(data[s:cut])
        s = cut
    return out


def main():
    it = sys.stdin.buffer.read().split()
    mn, bits, mx = int(it[0]), int(it[1]), int(it[2])
    S, T = it[3], it[4]
    cs, ct = chunks(S, mn, bits, mx), chunks(T, mn, bits, mx)
    stored = set(cs)
    new_bytes = 0
    for c in ct:
        if c not in stored:
            new_bytes += len(c)
            stored.add(c)                     # T の中で繰り返す塊も 1 回だけ保存
    print(len(cs), len(ct), new_bytes)


main()

Step-by-Step 解説

迷った他案と採らなかった理由

前提が変わったら: 平均長 $2^{bits}$ は「重複排除率」と「索引の大きさ」のトレードオフ。小さくすると細かく一致を拾えるが、塊の数（＝指紋の数）が増える。何 TB を何 GB の索引で扱うか、という運用の制約から逆算して決める（本問の 10 KiB は 4 MB の実験用の値で、実運用の推奨値ではない）。

よくあるミス

次のステップ

• 発展1: 正規化チャンキング（$mn\le$ 長さ $<$ 平均 では $bits+2$ ビット、平均以上では $bits-2$ ビット）を入れ、塊の長さの標準偏差と重複排除率を本問版と比べる
• 発展2: 100 箇所のランダム挿入で新規が 30.4%（実測）になった。平均長を 2 KiB／10 KiB／64 KiB と変えて、新規バイト数と塊数の積（索引コスト）の関係をグラフにする
• 扱わなかった範囲: 指紋の衝突（SHA-256 で実質無視）、塊の圧縮と暗号化、削除された塊のガベージコレクション

自己評価

自分の回答

気づき・メモ