collision_analysis.py

"""Collision analysis for USBN-13.

Two things this script does:

  1. Computes the analytic birthday-bound collision probability across
     a grid of corpus sizes and hash bit budgets (48, 50, 55, 60, 64),
     so we can compare the original draft (48 bits), the intermediate
     shrink options, and the final USBN-13 design (60 bits).

  2. Runs an empirical collision probe: generates a synthetic book
     corpus by enumerating (title template, author template, year) and
     reports the observed number of USBN collisions, confirming the
     implementation matches the theoretical prediction at small N.

Run from repo root:
    python code/collision_analysis.py

Writes results/collision_analysis.json and prints a summary table.
"""
from __future__ import annotations

import itertools
import json
import math
import random
from pathlib import Path

from usbn import generate_usbn


# ---------------------------------------------------------------------------
# Theoretical birthday bound
# ---------------------------------------------------------------------------
def collision_probability(n_items: int, hash_bits: int) -> float:
    """Approximate probability of at least one collision via the
    birthday formula P = 1 - exp(-n^2 / (2 * 2^bits))."""
    if n_items < 2:
        return 0.0
    exponent = -(n_items ** 2) / (2 * (2 ** hash_bits))
    return 1.0 - math.exp(exponent)


def birthday_50pct(hash_bits: int) -> float:
    """Return the corpus size at which collision probability reaches 50%."""
    return math.sqrt(math.log(2) * 2 ** (hash_bits + 1))


# ---------------------------------------------------------------------------
# Empirical probe
# ---------------------------------------------------------------------------
WORDS_TITLE = [
    "Outline", "History", "Elements", "Principles", "Studies", "Theory",
    "Practice", "Introduction", "Survey", "Handbook", "Companion",
    "Anatomy", "Methods", "Origins", "Foundations", "Chronicles",
    "Essays", "Reflections", "Meditations", "Notes", "Letters",
    "Poems", "Tales", "Stories", "Lectures", "Dialogues", "Discourse",
]
WORDS_AUTHOR_FIRST = [
    "James", "Mary", "John", "Elizabeth", "Robert", "Margaret",
    "William", "Dorothy", "Henry", "Alice", "Charles", "Florence",
    "George", "Helen", "Thomas", "Ruth", "Frederick", "Edith",
]
WORDS_AUTHOR_LAST = [
    "Smith", "Jones", "Brown", "Taylor", "Wilson", "Clark",
    "Robinson", "Walker", "Wright", "Green", "Hall", "Wood",
    "Carter", "Mitchell", "Perez", "Roberts", "Turner", "Phillips",
]


def synthetic_corpus(n: int, seed: int = 1234):
    """Yield n distinct (title, author, year) tuples deterministically.

    We want each tuple to be unique so that any USBN collision reflects
    a hash collision and not duplicate input.
    """
    rng = random.Random(seed)
    seen = set()
    # Combinatorial space is large: |title|^2 * |first| * |last| * |years|
    # so for n up to a few hundred thousand we never exhaust.
    while len(seen) < n:
        t1 = rng.choice(WORDS_TITLE)
        t2 = rng.choice(WORDS_TITLE)
        article = rng.choice(["The", "A", "On", "Of", ""])
        title = " ".join(x for x in (article, t1, "of", t2) if x)
        author = f"{rng.choice(WORDS_AUTHOR_FIRST)} {rng.choice(WORDS_AUTHOR_LAST)}"
        year = rng.randint(1450, 1969)
        key = (title, author, year)
        if key in seen:
            continue
        seen.add(key)
        yield key


def empirical_collisions(n: int) -> dict:
    """Generate a synthetic corpus of size n and count USBN collisions."""
    usbns = {}
    collisions = 0
    for title, author, year in synthetic_corpus(n):
        u = generate_usbn(title, author, year)
        if u in usbns:
            collisions += 1
        else:
            usbns[u] = (title, author, year)
    return {
        "n_items": n,
        "observed_collisions": collisions,
        "expected_prob_collision": collision_probability(n, 60),
    }


# ---------------------------------------------------------------------------
# Main
# ---------------------------------------------------------------------------
def main() -> None:
    # Analytic grid across bit budgets and corpus sizes.
    corpus_sizes = [
        ("1 K", 1_000),
        ("10 K", 10_000),
        ("100 K", 100_000),
        ("1 M", 1_000_000),
        ("10 M", 10_000_000),
        ("60 M (pre-ISBN)", 60_000_000),
        ("130 M (Google 2010)", 130_000_000),
        ("150 M (ISBNdb 2023)", 150_000_000),
        ("1 B (10x headroom)", 1_000_000_000),
    ]
    bit_budgets = [48, 50, 55, 60, 64]

    print("Analytic birthday-bound collision probability P(>=1 collision)")
    print()
    header = f"{'corpus':<25}" + "".join(f"{str(b)+'b':>14}" for b in bit_budgets)
    print(header)
    print("-" * len(header))
    analytic_table = []
    for label, n in corpus_sizes:
        row = {"corpus": label, "n": n}
        line = f"{label:<25}"
        for bits in bit_budgets:
            p = collision_probability(n, bits)
            row[f"bits_{bits}"] = p
            if p < 1e-4:
                cell = f"{p*100:.2e}%"
            elif p < 1:
                cell = f"{p*100:.3g}%"
            else:
                cell = ">100%"  # shouldn't happen
            line += f"{cell:>14}"
        print(line)
        analytic_table.append(row)

    print()
    print("50% birthday-collision thresholds:")
    for bits in bit_budgets:
        n50 = birthday_50pct(bits)
        print(f"  {bits} bits: ~{n50:>18,.0f} entries")

    # Empirical probe (kept modest to be quick; at 60 bits, we do not
    # expect to see collisions in a 100 K corpus).
    print()
    print("Empirical probe (USBN-13, 60 bits):")
    empirical = []
    for n in (1_000, 10_000, 100_000):
        row = empirical_collisions(n)
        empirical.append(row)
        print(
            f"  n = {n:>7,}: observed {row['observed_collisions']} "
            f"collision(s), expected P ~ {row['expected_prob_collision']:.2e}"
        )

    # Save results.
    out_path = Path(__file__).resolve().parent.parent / "results" / "collision_analysis.json"
    out_path.parent.mkdir(exist_ok=True)
    with out_path.open("w", encoding="utf-8") as f:
        json.dump(
            {
                "analytic": analytic_table,
                "empirical": empirical,
                "bit_budgets": bit_budgets,
                "birthday_50pct": {
                    str(b): birthday_50pct(b) for b in bit_budgets
                },
            },
            f,
            indent=2,
        )
    print(f"\nWrote {out_path}")


if __name__ == "__main__":
    main()