Day 160-Q2 — 2026-09-25 — MinHash + LSH（帯分割）で近似重複の候補を絞り、厳密な Jaccard で検証する

問題

$N$ 個の整数集合 $S_1,\dots,S_N$ と、整数 $b,r$、しきい値 $\theta=p/q$ が与えられる。$k=b\cdot r$ とし、$P=2^{61}-1$ として $i=0,\dots,k-1$ のハッシュ関数を

$$h_i(x)=(a_i x+c_i)\bmod P,\quad a_i=1+(\mathrm{sm}(2i+1)\bmod (P-1)),\quad c_i=\mathrm{sm}(2i+2)\bmod P$$

で定める（$\mathrm{sm}$ は splitmix64 の finalizer。Day159-Q4 と同じ関数）。

1. 署名: $\mathrm{sig}_j[i]=\min_{x\in S_j}h_i(x)$（長さ $k$）
2. LSH: 署名を長さ $r$ の $b$ 本の帯に切る。ある帯 $t$ で $\mathrm{sig}_u[tr..tr+r-1]=\mathrm{sig}_v[tr..tr+r-1]$ となる組 $u<v$ を 候補 とする
3. 検証: 候補のうち厳密な Jaccard 係数 $J(S_u,S_v)=\frac{|S_u\cap S_v|}{|S_u\cup S_v|}\ge\theta$ を満たすものを数える

候補の組数 $C$ と、検証を通った組数 $D$ を出力せよ。

入力形式

N b r p q
m_1 e_{1,1} ... e_{1,m_1}
...
m_N e_{N,1} ... e_{N,m_N}

制約

入出力例

5 4 2 1 2
6 1 2 3 4 5 6
6 1 2 3 4 5 7
4 1 2 3 8
3 100 200 300
3 100 200 301

3 1

（厳密な Jaccard は $(1,2)$: 5/7=0.714、$(1,3),(2,3)$: 3/7=0.429、$(4,5)$: 2/4=0.5。$k=8$ 本の最小値の一致は $(1,2)$ が 7/8、$(1,3)$ が 4/8、$(4,5)$ が 2/8。帯（2 本ずつ 4 帯）が丸ごと一致したのは $(1,2)$ の 3 帯と $(1,3),(2,3)$ の 1 帯 → 候補 3 組。検証で $(1,3),(2,3)$ は落ち $D=1$。**$(4,5)$ は $J=0.5\ge\theta$ なのに候補にならなかった（偽陰性）**——これが LSH の代償）

MinHash は Broder「On the resemblance and containment of documents」（SEQUENCES 1997）で AltaVista の近似重複検出に使われた手法、帯分割は Leskovec・Rajaraman・Ullman『Mining of Massive Datasets』3 章（http://www.mmds.org/ 、2026-09-25 参照）の定式化に従う。

概念図：LSH の S 字曲線（理論と実測）

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

sig = [[min((a * x + c) % P for x in S) for a, c in zip(A, C)] for S in sets]
cand = set()
for t in range(b):
    buckets = {}
    for j in range(n):
        buckets.setdefault(tuple(sig[j][t*r:(t+1)*r]), []).append(j)
    for g in buckets.values():
        ...  # g の中の全組を cand に（帯をまたいだ重複は set で消える）
# 検証: q * |A∩B| >= p * |A∪B|（浮動小数を使わない）

模範解答 (Python)

📋 コピーimport sys

P = (1 << 61) - 1
MASK = (1 << 64) - 1


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


def main():
    data = sys.stdin.buffer.read().split()
    n, b, r, p, q = map(int, data[:5])
    k = b * r
    A = [1 + splitmix64(2 * i + 1) % (P - 1) for i in range(k)]
    C = [splitmix64(2 * i + 2) % P for i in range(k)]
    sets = []
    pos = 5
    for _ in range(n):
        m = int(data[pos]); pos += 1
        sets.append(set(map(int, data[pos:pos + m]))); pos += m

    # 1) MinHash 署名: sig[i] = min_x (A[i]*x + C[i]) mod P
    sigs = []
    for S in sets:
        sigs.append([min((a * x + c) % P for x in S) for a, c in zip(A, C)])

    # 2) LSH: 帯 t の r 個をキーにバケツへ。同じバケツの組が候補
    cand = set()
    for t in range(b):
        buckets = {}
        for j in range(n):
            key = tuple(sigs[j][t * r:(t + 1) * r])
            buckets.setdefault(key, []).append(j)
        for g in buckets.values():
            for x in range(len(g)):
                for y in range(x + 1, len(g)):
                    cand.add((g[x], g[y]))

    # 3) 候補だけ厳密な Jaccard で検証: |A∩B|/|A∪B| >= p/q  <=>  q*|A∩B| >= p*|A∪B|
    ok = 0
    for u, v in cand:
        inter = len(sets[u] & sets[v])
        union = len(sets[u]) + len(sets[v]) - inter
        if q * inter >= p * union:
            ok += 1
    print(len(cand), ok)


main()

Step-by-Step 解説

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

前提が変わったら: 偽陰性が許されない（法務の重複調査など）なら prefix filtering などの厳密法。データが 10^8 件なら署名を分散計算し帯ごとにシャッフルする（MapReduce）形が MMDS の標準構成。

よくあるミス

次のステップ

• 発展1: 帯のしきい値を $\theta$ に合わせる $(b,r)$ を、偽陽性の検証コストと偽陰性の損失の重み付き和が最小になるように選ぶ（MMDS 3.4.3）
• 発展2: 文書を文字 $k$-gram（shingle）に変換してから本問に流す。$k=5$ と $k=9$ で近似重複の検出率を比べる
• 扱わなかった範囲: 重み付き Jaccard（ICWS）、b-bit MinHash による署名の圧縮、LSH Forest

自己評価

自分の回答

気づき・メモ