CFBC64B75637F5…EBE7926E8C26

Arguments · 9

1. #1levenshtein
2. #2README.md
3. #3# `gno.land/p/moul/x/daily/levenshtein/v0` **Levenshtein edit-distance** — `Distance`, `Matrix`, `Similarity`. The minimum number of single-character insertions, deletions, or substitutions to turn one string into another. Fully rune-aware, pure (deterministic), two-row DP (`O(min(len))` memory). Ported from Go's `agext/levenshtein`. ```go import "gno.land/p/moul/x/daily/levenshtein/v0" d := levenshtein.Distance("kitten", "sitting") // 3 m := levenshtein.Matrix("kitten", "sitting") // full (7 x 8) DP matrix s := levenshtein.Similarity("kitten", "sitting") // 57 (a 0..100 percentage) ``` **Live demo:** [`r/moul/x/daily/levenshteindemo`](https://github.com/moul/gno-contracts/tree/main/r/moul/x/daily/levenshteindemo/v0) · render it at [`/r/moul/x/daily/levenshteindemo/v0`](https://gno.land/r/moul/x/daily/levenshteindemo/v0). <!-- BEGIN GNOCONTRACTS FOOTER (generated by `make readmes`; do not edit below) --> --- Part of **[moul/gno-contracts](https://github.com/moul/gno-contracts)** — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage. > 🧪 **Highly experimental — potentially vibe-coded.** Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: [DISCLAIMER](https://github.com/moul/gno-contracts/blob/main/DISCLAIMER.md). <!-- END GNOCONTRACTS FOOTER -->
4. #4gnomod.toml
5. #5module = "gno.land/p/moul/x/daily/levenshtein/v0" gno = "0.9"
6. #6levenshtein.gno
7. #7// Package levenshtein ports the classic Levenshtein edit-distance algorithm // (as found in Go libraries like agext/levenshtein) to gno — as a reusable pure // package. // // The core is the textbook dynamic-programming matrix: the minimum number of // single-character insertions, deletions, or substitutions to turn string a // into string b. It is fully rune-aware and pure (deterministic), so it runs // happily on-chain. // // A live demo of this package (an interactive distance calculator with the DP // table) is at [r/moul/x/daily/levenshteindemo](/r/moul/x/daily/levenshteindemo/v0). package levenshtein // Distance returns the Levenshtein edit distance between a and b. // // It counts single-rune insertions, deletions, and substitutions and works on // runes (not bytes), so multi-byte UTF-8 input is handled correctly. The // classic two-row DP is used, so memory is O(min(len)) and time is O(len(a)*len(b)). func Distance(a, b string) int { ra := []rune(a) rb := []rune(b) // Keep the shorter slice as the inner (column) dimension. if len(ra) < len(rb) { ra, rb = rb, ra } n := len(ra) m := len(rb) if m == 0 { return n } // prev[j] = distance between ra[:i] and rb[:j]. prev := make([]int, m+1) for j := 0; j <= m; j++ { prev[j] = j } curr := make([]int, m+1) for i := 1; i <= n; i++ { curr[0] = i for j := 1; j <= m; j++ { cost := 1 if ra[i-1] == rb[j-1] { cost = 0 } curr[j] = min3( curr[j-1]+1, // insertion prev[j]+1, // deletion prev[j-1]+cost, // substitution / match ) } prev, curr = curr, prev } return prev[m] } // Matrix returns the full (len(a)+1) x (len(b)+1) DP matrix used by Distance. // matrix[i][j] is the edit distance between the first i runes of a and the // first j runes of b. The bottom-right cell equals Distance(a, b). func Matrix(a, b string) [][]int { ra := []rune(a) rb := []rune(b) n := len(ra) m := len(rb) d := make([][]int, n+1) for i := 0; i <= n; i++ { d[i] = make([]int, m+1) d[i][0] = i } for j := 0; j <= m; j++ { d[0][j] = j } for i := 1; i <= n; i++ { for j := 1; j <= m; j++ { cost := 1 if ra[i-1] == rb[j-1] { cost = 0 } d[i][j] = min3(d[i][j-1]+1, d[i-1][j]+1, d[i-1][j-1]+cost) } } return d } // Similarity returns a 0..100 percentage of how similar a and b are, defined as // (1 - distance/maxLen) * 100 rounded to the nearest integer. Two empty strings // are considered 100% similar. func Similarity(a, b string) int { la := len([]rune(a)) lb := len([]rune(b)) maxLen := la if lb > maxLen { maxLen = lb } if maxLen == 0 { return 100 } dist := Distance(a, b) // Rounded percentage of matching characters. return ((maxLen-dist)*100 + maxLen/2) / maxLen } func min3(a, b, c int) int { m := a if b < m { m = b } if c < m { m = c } return m }
8. #8/gno.MemPackageType
9. #9 MPUserProd