Lodestar.Text 0.5.0. This page is frozen at that release. Read the current documentation for what main says now. A link to a decision or a migration page follows main, and leaves the archive.

String indexing — Lodestar.Text.Indexing

Comparing a query against every entry in a dictionary is O(n) per lookup, and that cost is paid again for every query. Lodestar.Text.Indexing holds a metric index built once and queried many times: a Burkhard-Keller tree that answers "everything within edit distance k" and "the n nearest" without a full scan, on any distance that satisfies the triangle inequality.

BkTree is the whole namespace. It carries the measured cost of the pruning — worth using at a radius of 1, measurably slower than a length-filtered scan past it — and the table of which distances in Lodestar.Text.Distances are admissible. Read it before choosing a radius or a factory method.

Types

Type	What it is
BkTree	A metric index over strings: everything within edit distance k, without scanning the corpus.
BkTreeMatch	One hit from a BkTree query: the item, and how far it is.

See also

• Lodestar.Text.Distances — the distances a tree is built over, and the triangle inequality that decides which ones qualify.