Maps extraction strings to byte spans in source text.
Mirrors upstream langextract's WordAligner (v1.6.0 + #485) semantics in
four phases over downcased word tokens:
- Occurrence DP — over the whole extraction list in model output
order: selects at most one exact occurrence per extraction, keeping
selections order-preserving and non-overlapping while maximizing total
matched tokens; ties prefer the earliest-ending chain, so repeated
mentions resolve to successive occurrences. Status
:exact. Extractions the DP cannot place fall through to the phases below. - Exact — the extraction's tokens appear contiguously in the source
(linear scan, first occurrence wins). Status
:exact. - Lesser — difflib-style block decomposition: if a matching block is
anchored at the extraction's first token, its source run grounds the
extraction (upstream
MATCH_LESSER). Blocks elsewhere in the extraction do not qualify. Status:lesser. - LCS fuzzy — for extractions the lesser phase couldn't anchor
(no matching block at the extraction's first token), an LCS
subsequence match over lightly stemmed tokens, accepted when matched
tokens ≥
ceil(extraction tokens × :fuzzy_threshold)(upstream's coverage gate, float error included) and density (matched / span length) ≥:min_density, preferring the tightest span. Status:fuzzy.
Known divergence from upstream: our fallthrough phases treat each leftover extraction standalone, while upstream reruns difflib over the concatenated tokens of all sibling extractions — see @known_divergences in aligner_parity_test.exs for the observable consequences.
DP claims narrow only the lesser phase when :exact_algorithm is :dp
(the default). Token intervals are half-open [start, end) throughout.
Phase-0 placements seed the claim list; each successful leftover
reserves its interval for later items. Exact and LCS fallthrough ignore
claims: upstream grounds nested and contested mentions inside sibling
placements (see the dpnested* and dp_contested_overlap fixtures), so
rediscovering claimed tokens is correct there. The lesser phase is
"plain optimum, then claim-rescue" via accept_free_or_masked/3: the
plain difflib block stands when it lands on free source; a winner that
overlaps a claim reruns under a claimed-token mask, so a paraphrase of
an already-claimed repeat cannot ground its prefix inside the claim
(upstream returns not_found for those too).
With :exact_algorithm :first_occurrence, phase 0 is skipped and
claims stay empty.
Cost model: this module aligns whatever text it is handed, with no size
limit (same as upstream's WordAligner). The fallthrough phases are
super-linear in source tokens — per leftover extraction, the naive
lesser block search examines O(source × extraction) anchor pairs and
walks a run from each (repetitive text pushes it past that bound), and
LCS is O(source × extraction²) — so whole-document calls on
book-length text take real CPU time. That time is spent in the calling process only; BEAM
preemption keeps the rest of the system responsive. The chunked
pipeline (LangExtract.run/4) is the bounded document path; callers
who need a hard latency bound on a direct call wrap it in a task with
a timeout.
Summary
Functions
@spec align(String.t(), [String.t()], keyword()) :: [LangExtract.Span.t()]