levenshtein.gno

  1// Package levenshtein ports the classic Levenshtein edit-distance algorithm
  2// (as found in Go libraries like agext/levenshtein) to gno — as a reusable pure
  3// package.
  4//
  5// The core is the textbook dynamic-programming matrix: the minimum number of
  6// single-character insertions, deletions, or substitutions to turn string a
  7// into string b. It is fully rune-aware and pure (deterministic), so it runs
  8// happily on-chain.
  9//
 10// A live demo of this package (an interactive distance calculator with the DP
 11// table) is at [r/moul/x/daily/levenshteindemo](/r/moul/x/daily/levenshteindemo/v0).
 12package levenshtein
 13
 14// Distance returns the Levenshtein edit distance between a and b.
 15//
 16// It counts single-rune insertions, deletions, and substitutions and works on
 17// runes (not bytes), so multi-byte UTF-8 input is handled correctly. The
 18// 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)
 22
 23	// Keep the shorter slice as the inner (column) dimension.
 24	if len(ra) < len(rb) {
 25		ra, rb = rb, ra
 26	}
 27	n := len(ra)
 28	m := len(rb)
 29	if m == 0 {
 30		return n
 31	}
 32
 33	// 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] = j
 37	}
 38	curr := make([]int, m+1)
 39
 40	for i := 1; i <= n; i++ {
 41		curr[0] = i
 42		for j := 1; j <= m; j++ {
 43			cost := 1
 44			if ra[i-1] == rb[j-1] {
 45				cost = 0
 46			}
 47			curr[j] = min3(
 48				curr[j-1]+1,    // insertion
 49				prev[j]+1,      // deletion
 50				prev[j-1]+cost, // substitution / match
 51			)
 52		}
 53		prev, curr = curr, prev
 54	}
 55	return prev[m]
 56}
 57
 58// 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 the
 60// 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)
 66
 67	d := make([][]int, n+1)
 68	for i := 0; i <= n; i++ {
 69		d[i] = make([]int, m+1)
 70		d[i][0] = i
 71	}
 72	for j := 0; j <= m; j++ {
 73		d[0][j] = j
 74	}
 75	for i := 1; i <= n; i++ {
 76		for j := 1; j <= m; j++ {
 77			cost := 1
 78			if ra[i-1] == rb[j-1] {
 79				cost = 0
 80			}
 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 d
 85}
 86
 87// Similarity returns a 0..100 percentage of how similar a and b are, defined as
 88// (1 - distance/maxLen) * 100 rounded to the nearest integer. Two empty strings
 89// are considered 100% similar.
 90func Similarity(a, b string) int {
 91	la := len([]rune(a))
 92	lb := len([]rune(b))
 93	maxLen := la
 94	if lb > maxLen {
 95		maxLen = lb
 96	}
 97	if maxLen == 0 {
 98		return 100
 99	}
100	dist := Distance(a, b)
101	// Rounded percentage of matching characters.
102	return ((maxLen-dist)*100 + maxLen/2) / maxLen
103}
104
105func min3(a, b, c int) int {
106	m := a
107	if b < m {
108		m = b
109	}
110	if c < m {
111		m = c
112	}
113	return m
114}