Search Apps Documentation Source Content File Folder Download Copy Actions Download State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

v0 source pure

Package levenshtein ports the classic Levenshtein edit-distance algorithm (as found in Go libraries like agext/levens...

Readme View source

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.

1import "gno.land/p/moul/x/daily/levenshtein/v0"
2
3d := levenshtein.Distance("kitten", "sitting")   // 3
4m := levenshtein.Matrix("kitten", "sitting")     // full (7 x 8) DP matrix
5s := levenshtein.Similarity("kitten", "sitting") // 57 (a 0..100 percentage)

Live demo: r/moul/x/daily/levenshteindemo · render it at /r/moul/x/daily/levenshteindemo/v0.

Part of 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.

Overview

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).

Functions 3

func Distance 

1func Distance(a, b string) int
source

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 Matrix 

1func Matrix(a, b string) [][]int
source

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 Similarity 

1func Similarity(a, b string) int
source

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.

Source Files 3