LangExtract.Alignment.Aligner (LangExtract v0.11.0)

Copy Markdown View Source

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:

  1. 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.
  2. Exact — the extraction's tokens appear contiguously in the source (linear scan, first occurrence wins). Status :exact.
  3. 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.
  4. 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

align(source, extractions, opts \\ [])

@spec align(String.t(), [String.t()], keyword()) :: [LangExtract.Span.t()]