compare_parts: skip residue comparisons that cannot produce a paired cluster

Search for the compare_parts and align_person_name_order implementations and trace their callers before choosing the exact lower-bound checks. Run the 100-query parity set before and after; done means all alignments remain identical, followed by timing compare_parts on the org and many-alias cases.

Problem

In the logic-v2 matcher, compare_parts (and align_person_name_order before it for person names) is called for every remaining part set of every name pair. Measured over 100 varied queries × 50 candidates against a 4.27M-entity index:

• 46,606 compare_parts calls with both sides non-empty.
• 40,778 of them (87%) return no paired cluster with a score above 0.0, i.e. every part ends up as a solo cluster. These calls take 846 of 1,000 ms of compare_parts time (85%).
• compare_parts is 40–75% of pair-loop time on heavy cases (53 of 72 ms for an org query, 56 of 104 ms for a many-alias person query), and align_person_name_order another 11 ms on the person case.

The DP runs over the joined comparable strings regardless of whether any part pair can possibly stay within budget.

Two cheap predictors were tested on the same 46,606 calls:

So a safe heuristic exists but is weak, and a strong heuristic is not safe. An exact bound is preferable.

Proposal

Add a pre-check inside compare_parts (so every caller benefits) that returns the all-solo result without running the DP when no part pair can score above zero. The budget for a cluster is log_base(max(len − short_floor, 1)) × tolerance per side and the score is zero once total cost exceeds it, so a lower bound on the edit cost between two parts that exceeds the budget for that pair rules the pair out. Cheap lower bounds that respect the cost model: absolute length difference × the cheapest insertion cost, and half the bag distance over characters (with the separator-drop and confusable costs taken as the minimum possible cost per operation). If every (query part, result part) pair is ruled out, skip the DP.

The same check applies before the Damerau–Levenshtein loop in align_person_name_order, where the SCORE_FLOOR of 0.3 gives the cutoff.

Secondary, same function: the DP allocates cost and back as row-of-Vecs (up to 385 separate allocations at the 384-char cap) and re-evaluates edit_cost on the traceback; a flat buffer and a stored op per cell would remove that.

Related: the matcher-side pair pruning is opensanctions/nomenklatura#364.

Verification

Run the 100-query parity set through the matcher before and after; all alignments must be identical. Then measure compare_parts time on the org and many-alias cases.