stringmetric

Documentation

Overview

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.

Problem

Exact string equality is too strict for many real-world tasks: user input contains typos, transposed characters, missing letters, or small variations in formatting. Systems that need "close enough" matching (search suggestions, deduplication, record linkage, typo-tolerant lookups) require a metric that quantifies how different two strings are.

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.

Why Damerau-Levenshtein

Compared to plain Levenshtein distance, Damerau-Levenshtein treats adjacent character swaps as a single edit (for example "act" vs "cat"), which better matches common human typing errors and usually yields more intuitive fuzzy-match scores.

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. That makes it suitable for the short-to-medium strings typical in API, search, and validation workflows rather than very long inputs.

Usage

d := stringmetric.DLDistance("a cat", "a act") // 1 (adjacent transposition)
if d <= 2 {
    // treat as likely typo match
}

Use the returned distance as a ranking signal or apply a threshold tuned to your domain (for example strict thresholds for identifiers, looser thresholds for free-text names).

Index

• func DLDistance(sa, sb string) int

Examples

• DLDistance

Functions

func DLDistance

func DLDistance(sa, sb string) int

DLDistance computes Damerau-Levenshtein edit distance between two rune-based strings, counting insertion/deletion/substitution/transposition operations.

Example

package main

import (
	"fmt"

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

func main() {
	d := stringmetric.DLDistance("a cat", "a abct")

	// "a cat" (one transposition)-> "a act" (one insertion)-> "a abct"

	fmt.Println(d)

}

Output:
2