Table of contents
Part of nurago, a collection of independent Go packages for backend services.
import "github.com/tecnickcom/nurago/pkg/stringmetric"
Package stringmetric provides string distance functions for approximate text matching, comparison, and fuzzy search.
This package currently implements the Damerau-Levenshtein edit distance via
DLDistance, which measures the minimum number of edit operations required to
transform one string into another.
What It Computes
DLDistance returns an integer distance where:
- 0 means the strings are identical.
- Higher values mean less similarity.
- Allowed operations are insertion, deletion, substitution, and adjacent transposition.
The implementation is rune-based (not byte-based), so it handles Unicode text correctly and does not break on multi-byte UTF-8 characters.
Distance is measured over Unicode code points, so canonically-equivalent but differently-normalized strings compare as different: NFC “é” (one rune) and NFD “e” + combining accent (two runes) render identically yet have distance 1. Callers that want visual equivalence should normalize both inputs (for example to NFC) before calling.
Guarantees
DLDistance is a true metric. For all strings a, b, c it is non-negative,
returns 0 if and only if a == b, is symmetric (DLDistance(a, b) equals
DLDistance(b, a)), is bounded above by max(len(a), len(b)) counted in runes, and
satisfies the triangle inequality (DLDistance(a, c) <= DLDistance(a, b) +
DLDistance(b, c)). It is a pure function and safe for concurrent use.
Implementation Notes
The algorithm uses dynamic programming with:
- an alphabet index map for tracking prior rune positions,
- a distance matrix initialized with sentinel boundaries,
- transition costs for substitution, insertion, deletion, and transposition.
This delivers deterministic O(|a||b|) time and O(|a||b|) memory: the full matrix must be retained because the transposition term can reference any earlier row, so the two-row optimization used for plain Levenshtein does not apply.
Usage
d := stringmetric.DLDistance("a cat", "a act") // 1 (adjacent transposition)
if d <= 2 {
// treat as likely typo match
}
When To Use
- Search results are ranked by closeness rather than exact match.
- Typos in user input should still find the intended record.
Example
d := stringmetric.DLDistance("a cat", "a abct")
// "a cat" (one transposition)-> "a act" (one insertion)-> "a abct"
fmt.Println(d)
// Output:
// 2
Full source is in example_stringmetric_test.go. More runnable examples are on pkg.go.dev.
Dependencies
This package reaches no external module: it uses only the Go standard library.