gno.land/p/moul/x/daily/levenshtein/v0⧉

1// Package levenshtein ports the classic Levenshtein edit-distance algorithm2// (as found in Go libraries like agext/levenshtein) to gno — as a reusable pure3// package.4//5// The core is the textbook dynamic-programming matrix: the minimum number of6// single-character insertions, deletions, or substitutions to turn string a7// into string b. It is fully rune-aware and pure (deterministic), so it runs8// happily on-chain.9//10// A live demo of this package (an interactive distance calculator with the DP11// table) is at [r/moul/x/daily/levenshteindemo](/r/moul/x/daily/levenshteindemo/v0).12package levenshtein1314// Distance returns the Levenshtein edit distance between a and b.15//16// It counts single-rune insertions, deletions, and substitutions and works on17// runes (not bytes), so multi-byte UTF-8 input is handled correctly. The18// classic two-row DP is used, so memory is O(min(len)) and time is O(len(a)*len(b)).19func Distance(a, b string) int {20	ra := []rune(a)21	rb := []rune(b)2223	// Keep the shorter slice as the inner (column) dimension.24	if len(ra) < len(rb) {25		ra, rb = rb, ra26	}27	n := len(ra)28	m := len(rb)29	if m == 0 {30		return n31	}3233	// prev[j] = distance between ra[:i] and rb[:j].34	prev := make([]int, m+1)35	for j := 0; j <= m; j++ {36		prev[j] = j37	}38	curr := make([]int, m+1)3940	for i := 1; i <= n; i++ {41		curr[0] = i42		for j := 1; j <= m; j++ {43			cost := 144			if ra[i-1] == rb[j-1] {45				cost = 046			}47			curr[j] = min3(48				curr[j-1]+1,    // insertion49				prev[j]+1,      // deletion50				prev[j-1]+cost, // substitution / match51			)52		}53		prev, curr = curr, prev54	}55	return prev[m]56}5758// Matrix returns the full (len(a)+1) x (len(b)+1) DP matrix used by Distance.59// matrix[i][j] is the edit distance between the first i runes of a and the60// first j runes of b. The bottom-right cell equals Distance(a, b).61func Matrix(a, b string) [][]int {62	ra := []rune(a)63	rb := []rune(b)64	n := len(ra)65	m := len(rb)6667	d := make([][]int, n+1)68	for i := 0; i <= n; i++ {69		d[i] = make([]int, m+1)70		d[i][0] = i71	}72	for j := 0; j <= m; j++ {73		d[0][j] = j74	}75	for i := 1; i <= n; i++ {76		for j := 1; j <= m; j++ {77			cost := 178			if ra[i-1] == rb[j-1] {79				cost = 080			}81			d[i][j] = min3(d[i][j-1]+1, d[i-1][j]+1, d[i-1][j-1]+cost)82		}83	}84	return d85}8687// Similarity returns a 0..100 percentage of how similar a and b are, defined as88// (1 - distance/maxLen) * 100 rounded to the nearest integer. Two empty strings89// are considered 100% similar.90func Similarity(a, b string) int {91	la := len([]rune(a))92	lb := len([]rune(b))93	maxLen := la94	if lb > maxLen {95		maxLen = lb96	}97	if maxLen == 0 {98		return 10099	}100	dist := Distance(a, b)101	// Rounded percentage of matching characters.102	return ((maxLen-dist)*100 + maxLen/2) / maxLen103}104105func min3(a, b, c int) int {106	m := a107	if b < m {108		m = b109	}110	if c < m {111		m = c112	}113	return m114}115