stringmetric

Part of nurago, a collection of independent Go packages for backend services.

import "github.com/tecnickcom/nurago/pkg/stringmetric"

One function. DLDistance returns the Damerau-Levenshtein edit distance between two strings: the fewest insertions, deletions, substitutions and adjacent transpositions needed to turn one into the other.

Why Damerau and not plain Levenshtein

Transposition is the fourth operation. Plain Levenshtein scores teh against the as distance 2, reading it as a deletion plus an insertion. Damerau-Levenshtein scores it 1, because swapping two adjacent characters counts as one edit.

That matters because transposition is what human typing actually produces. Ranking teh as equally wrong as tth mis-sorts a suggestion list for the single most common class of typo.

It is a true metric, and that buys you something

The package guarantees the four properties, and they are tested rather than asserted:

• non-negative
• zero if and only if the strings are equal
• symmetric: DLDistance(a, b) == DLDistance(b, a)
• the triangle inequality: DLDistance(a, c) <= DLDistance(a, b) + DLDistance(b, c)

The triangle inequality has a practical consequence: it permits indexing strings in a metric tree such as a BK-tree, where a search prunes whole subtrees instead of scanning every candidate. Similarity scores that violate it cannot be indexed that way.

It is also bounded above by max(len(a), len(b)) in runes, which gives you a normalisation denominator if you want a 0-to-1 similarity ratio.

Pure function, no state, safe to call concurrently.

Runes, not bytes, and what that still does not fix

The implementation walks Unicode code points. A naive byte-based edit distance reports a distance of 2 between café and cafe because the accented character is two bytes; this one reports 1.

The caveat is one level deeper, and the package states it: distance is over code points, so normalisation form matters. NFC é is one rune. NFD e followed by a combining accent is two. They render identically on screen and have distance 1 between them.

Normalise both inputs to NFC before calling when they come from different sources. stringkey performs that step inside its own pipeline; keeping it out of this package is what allows stringmetric to reach no external module.

The cost is quadratic in both time and memory

Measured with go test -bench on Go 1.27.1, linux/amd64, Intel Core i7-1260P. Run go test -bench=. ./pkg/stringmetric/ to reproduce them on your own hardware; the absolute values will differ, the ratios much less so.

The two shortcuts at the top cost nothing: identical strings and an empty input are answered without building anything.

Everything else allocates a distance matrix. Going from short to medium input costs 13 times the time and 10 times the memory, which is the quadratic growth you would expect from O(len(a) * len(b)) in both. The Unicode row costs about 30% more than ASCII of similar length, for the rune decoding.

This bounds where the function belongs. On a 1,000-character input against another 1,000-character input, the matrix is a million cells. Calling it on user-supplied text of unbounded length is a denial-of-service vector, not a performance concern. Bound the input length before you call, and reject rather than truncate if the bound is exceeded.

For a suggestion list, filter candidates by length first: two strings whose lengths differ by more than your threshold cannot be within that distance, and the check is free.

Turning the distance into a ratio

DLDistance returns a raw count, so comparing across different string lengths needs normalising. The guaranteed upper bound gives the denominator:

d := stringmetric.DLDistance(a, b)
maxLen := max(utf8.RuneCountInString(a), utf8.RuneCountInString(b))

similarity := 1.0 - float64(d)/float64(maxLen)  // 1.0 identical, 0.0 maximally different

Because the bound is max(len(a), len(b)) in runes and the distance can never exceed it, the ratio always lands in [0, 1] without clamping. Count runes rather than bytes for the denominator, to match the unit the distance is measured in.

Example

d := stringmetric.DLDistance("kitten", "sitting")

fmt.Println(d)

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.

Links

• Reference documentation
• Source code
• Normalised hashing of text fields: stringkey
• All nurago packages