`zettelkasten.reconcile`¶

zettelkasten.reconcile ¶

Pure overlap-reconcile primitive for stable structural identity.

When a synthesis structure (table rows, induced columns, depth nodes) is re-materialized, its members can be renamed, reordered, or drift by a member or two. If identity were keyed on position or name, every re-run would orphan the prior durable id and mint a fresh one. Instead we derive identity from member-set overlap against the prior materialized structure: a proposed set that substantially overlaps a prior set inherits that prior id.

This module is the shared, pure core of that reconciliation:

:func:jaccard — set-overlap similarity, total over empty sets.
:func:reconcile_ids — OPTIMAL (maximum-total-overlap) one-to-one assignment of prior ids to proposed member-sets, minting a new id when no prior set overlaps enough.

Everything here is pure: no graph, no IO, no global state, no randomness. The id-minting policy is injected by the caller via id_factory so this module never decides what a new id looks like.

jaccard ¶

jaccard(a: set[str], b: set[str]) -> float

Return the Jaccard overlap |a∩b| / |a∪b| of two member sets.

Defined as 0.0 whenever the union is empty (jaccard(∅, ∅) == 0.0) and 0.0 when exactly one side is empty (jaccard(x, ∅) == 0.0): an empty set carries no usable overlap signal, so it never matches. No division by zero is possible.

Source code in zettelkasten/reconcile.py

def jaccard(a: set[str], b: set[str]) -> float:
    """Return the Jaccard overlap ``|a∩b| / |a∪b|`` of two member sets.

    Defined as ``0.0`` whenever the union is empty (``jaccard(∅, ∅) == 0.0``)
    and ``0.0`` when exactly one side is empty (``jaccard(x, ∅) == 0.0``): an
    empty set carries no usable overlap signal, so it never matches. No
    division by zero is possible.
    """
    if not a or not b:
        return 0.0
    intersection = len(a & b)
    union = len(a | b)
    return intersection / union

reconcile_ids ¶

reconcile_ids(prior: dict[str, set[str]], proposed: list[set[str]], *, threshold: float = 0.5, id_factory: Callable[[set[str], int], str]) -> list[str]

Assign a durable id to each proposed member-set by OPTIMAL overlap matching.

We consider EVERY (proposed set, prior id) pair whose :func:jaccard overlap clears threshold as a candidate edge, then choose the ONE-TO-ONE matching that maximizes the TOTAL overlap summed over the matched pairs (an optimal maximum-weight bipartite assignment, via the Hungarian algorithm). A proposed set left unmatched MINTS a fresh id via id_factory(member_set, index) where index is the position of the set in proposed.

This is GLOBALLY OPTIMAL, not order-greedy and not the earlier descending-overlap ½-approximation: the assignment maximizes reuse of prior durable ids across the whole contest, so it never orphans a prior id that a different pairing could have preserved. Example: prior = {P1:{a,b,c,d}, P2:{a,b,c,e,f}} with proposed = [{a,b,c}, {a,b,c,d,x,y,z}] reuses BOTH prior ids ([P2, P1]) — the greedy variant would have bound {a,b,c} to its single best P1 and then orphaned P2 entirely.

Semantics:

Optimal, one-to-one. Each prior id is reused at most once and each proposed set claims at most one prior id; the chosen matching maximizes the total overlap of all matched pairs (so it maximizes durable-id reuse).
Deterministic. For fixed inputs the result is stable across runs: prior columns are processed in sorted prior_id order and proposed sets in list order, and the matching is computed by a deterministic algorithm, so ties among equally-optimal matchings always resolve the same way.
Greenfield contract. When prior == {} (or no pair clears the threshold) there are no candidate edges, so every proposed set is minted in order and the result is exactly [id_factory(s, i) for i, s in enumerate(proposed)]. Downstream byte-identity depends on this.
Total. Empty prior, empty proposed, and empty member-sets are all handled without crashing. An empty proposed set has overlap 0 with everything and therefore always mints.

The returned list has one id per proposed set, IN THE SAME ORDER as proposed.

Complexity is O(P·K) to score the pairs plus O(N³) for the Hungarian assignment over N = max(P, K) (only when at least one pair clears the threshold), which is acceptable for typical row/column counts; this is not a perf-critical path.

Source code in zettelkasten/reconcile.py

def reconcile_ids(
    prior: dict[str, set[str]],
    proposed: list[set[str]],
    *,
    threshold: float = 0.5,
    id_factory: Callable[[set[str], int], str],
) -> list[str]:
    """Assign a durable id to each proposed member-set by OPTIMAL overlap matching.

    We consider EVERY ``(proposed set, prior id)`` pair whose :func:`jaccard`
    overlap clears ``threshold`` as a candidate edge, then choose the ONE-TO-ONE
    matching that maximizes the TOTAL overlap summed over the matched pairs (an
    optimal maximum-weight bipartite assignment, via the Hungarian algorithm). A
    proposed set left unmatched MINTS a fresh id via
    ``id_factory(member_set, index)`` where ``index`` is the position of the set
    in ``proposed``.

    This is GLOBALLY OPTIMAL, not order-greedy and not the earlier
    descending-overlap ½-approximation: the assignment maximizes reuse of prior
    durable ids across the whole contest, so it never orphans a prior id that a
    different pairing could have preserved. Example: ``prior = {P1:{a,b,c,d},
    P2:{a,b,c,e,f}}`` with ``proposed = [{a,b,c}, {a,b,c,d,x,y,z}]`` reuses BOTH
    prior ids (``[P2, P1]``) — the greedy variant would have bound ``{a,b,c}`` to
    its single best ``P1`` and then orphaned ``P2`` entirely.

    Semantics:

    * **Optimal, one-to-one.** Each prior id is reused at most once and each
      proposed set claims at most one prior id; the chosen matching maximizes the
      total overlap of all matched pairs (so it maximizes durable-id reuse).
    * **Deterministic.** For fixed inputs the result is stable across runs:
      prior columns are processed in sorted ``prior_id`` order and proposed sets
      in list order, and the matching is computed by a deterministic algorithm,
      so ties among equally-optimal matchings always resolve the same way.
    * **Greenfield contract.** When ``prior == {}`` (or no pair clears the
      threshold) there are no candidate edges, so every proposed set is minted in
      order and the result is exactly
      ``[id_factory(s, i) for i, s in enumerate(proposed)]``. Downstream
      byte-identity depends on this.
    * **Total.** Empty ``prior``, empty ``proposed``, and empty member-sets are
      all handled without crashing. An empty proposed set has overlap ``0`` with
      everything and therefore always mints.

    The returned list has one id per proposed set, IN THE SAME ORDER as
    ``proposed``.

    Complexity is ``O(P·K)`` to score the pairs plus ``O(N³)`` for the Hungarian
    assignment over ``N = max(P, K)`` (only when at least one pair clears the
    threshold), which is acceptable for typical row/column counts; this is not a
    perf-critical path.
    """
    # Deterministic column order: prior ids sorted lexicographically.
    prior_ids = sorted(prior)
    prior_sets = [prior[k] for k in prior_ids]

    # Candidate edges: (proposed_index, prior_index) -> overlap, clearing threshold.
    weights: dict[tuple[int, int], float] = {}
    for i, member_set in enumerate(proposed):
        for j, prior_set in enumerate(prior_sets):
            overlap = jaccard(prior_set, member_set)
            if overlap >= threshold:
                weights[(i, j)] = overlap

    # No candidate edges (greenfield, or nothing overlaps enough): mint in order.
    # This is what keeps downstream first-run output byte-identical.
    if not weights:
        return [id_factory(member_set, i) for i, member_set in enumerate(proposed)]

    matched = _max_weight_matching(weights, len(proposed), len(prior_ids))

    out: list[str] = []
    for i, member_set in enumerate(proposed):
        j = matched.get(i)
        if j is not None and (i, j) in weights:
            out.append(prior_ids[j])
        else:
            out.append(id_factory(member_set, i))
    return out

zettelkasten.reconcile¶