28. Deduplicate Near-Identical Prompts via Hashing

Problem

A lab's prompt-logging pipeline ingests millions of user prompts a day for offline analysis. Storing full text just to check for duplicates is wasteful at that scale (and sometimes undesirable for privacy), so the pipeline canonicalizes each prompt and compares fixed-size hash fingerprints instead of raw strings.

Given prompts in arrival order, keep only the first occurrence of each near-duplicate, preserving arrival order and each surviving prompt's exact original text. Two prompts are near-identical if they're equal after lowercasing and collapsing any run of whitespace to a single space. Punctuation is not normalized, so prompts differing only in punctuation stay distinct.

Source: src/28_dedupe_near_duplicate_prompts.py

def dedupe_prompts(prompts: list[str]) -> list[str]:
    ...

Examples:
>>> dedupe_prompts(["What is the capital of France?", "what is the capital of france?", "Explain gradient descent."])
['What is the capital of France?', 'Explain gradient descent.']

>>> dedupe_prompts(["  Hello   world  ", "Hello world", "hello world"])
['  Hello   world  ']

Step-by-Step Approach

1. Define a canonicalization step first: strip leading/trailing whitespace, lowercase, and collapse any internal whitespace run to a single space. This is the "near" in near-identical.
2. Hash the canonical form, not the raw text, into a fixed-size fingerprint (e.g. SHA-256 hex digest) — this is what a real pipeline would store instead of full text.
3. Walk the prompts in arrival order, maintaining a set of fingerprints already seen.
4. For each prompt, compute its fingerprint; if it's new, keep the prompt's original (non-canonicalized) text in the output and record the fingerprint as seen; if it's already in the set, drop the prompt.
5. Return the kept prompts in their original arrival order — the output is a filtered view of the input, not a re-sorted one.
6. Handle the empty-input edge case (empty list in, empty list out) and confirm punctuation differences are intentionally preserved as distinct prompts, since canonicalization only touches case and whitespace.

The key insight is separating "what decides duplication" (the canonical form) from "what gets stored/emitted" (the hash for comparison, the original text for output) — a single pass with a hash set does both in O(n) time without ever comparing raw strings pairwise.

Reference solution

import hashlib


def _fingerprint(prompt: str) -> str:
    # canonicalize: strip ends, lowercase, collapse any whitespace run to one space
    canonical = " ".join(prompt.strip().lower().split())
    # fixed-size fingerprint -- the pipeline can store/compare this instead of raw text
    return hashlib.sha256(canonical.encode("utf-8")).hexdigest()


def dedupe_prompts(prompts: list[str]) -> list[str]:
    # O(n * m) time (m = avg prompt length, for hashing), O(n) space for the seen set
    seen: set[str] = set()
    result: list[str] = []
    for prompt in prompts:
        fingerprint = _fingerprint(prompt)
        if fingerprint not in seen:
            seen.add(fingerprint)
            result.append(prompt)
    return result

Key Functions & Tricks

• " ".join(prompt.strip().lower().split()) — canonicalize whitespace and case in one line; str.split() with no args splits on any whitespace run, including newlines/tabs
• hashlib.sha256(...).hexdigest() — deterministic fixed-size fingerprint of the canonical text
• set[str] of fingerprints — O(1) average membership check, avoids O(n) pairwise string comparisons
• Canonicalize-then-hash — the general pattern for "near-duplicate" (not exact-duplicate) detection at scale
• Emitting the original text while deduplicating on the canonical form — keeps output faithful to the input

How to Recognize This Pattern