levenshtein.gno
6.69 Kb · 249 lines
1// Package levenshtein ports the classic Levenshtein edit-distance algorithm
2// (as found in Go libraries like agext/levenshtein) to a gno.land realm.
3//
4// The core is the textbook dynamic-programming matrix: the minimum number of
5// single-character insertions, deletions, or substitutions to turn string a
6// into string b. It is fully rune-aware and pure (deterministic), so it runs
7// happily on-chain.
8package levenshtein
9
10import (
11 "strconv"
12 "strings"
13)
14
15// Distance returns the Levenshtein edit distance between a and b.
16//
17// It counts single-rune insertions, deletions, and substitutions and works on
18// runes (not bytes), so multi-byte UTF-8 input is handled correctly. The
19// classic two-row DP is used, so memory is O(min(len)) and time is O(len(a)*len(b)).
20func Distance(a, b string) int {
21 ra := []rune(a)
22 rb := []rune(b)
23
24 // Keep the shorter slice as the inner (column) dimension.
25 if len(ra) < len(rb) {
26 ra, rb = rb, ra
27 }
28 n := len(ra)
29 m := len(rb)
30 if m == 0 {
31 return n
32 }
33
34 // prev[j] = distance between ra[:i] and rb[:j].
35 prev := make([]int, m+1)
36 for j := 0; j <= m; j++ {
37 prev[j] = j
38 }
39 curr := make([]int, m+1)
40
41 for i := 1; i <= n; i++ {
42 curr[0] = i
43 for j := 1; j <= m; j++ {
44 cost := 1
45 if ra[i-1] == rb[j-1] {
46 cost = 0
47 }
48 curr[j] = min3(
49 curr[j-1]+1, // insertion
50 prev[j]+1, // deletion
51 prev[j-1]+cost, // substitution / match
52 )
53 }
54 prev, curr = curr, prev
55 }
56 return prev[m]
57}
58
59// Matrix returns the full (len(a)+1) x (len(b)+1) DP matrix used by Distance.
60// matrix[i][j] is the edit distance between the first i runes of a and the
61// first j runes of b. The bottom-right cell equals Distance(a, b).
62func Matrix(a, b string) [][]int {
63 ra := []rune(a)
64 rb := []rune(b)
65 n := len(ra)
66 m := len(rb)
67
68 d := make([][]int, n+1)
69 for i := 0; i <= n; i++ {
70 d[i] = make([]int, m+1)
71 d[i][0] = i
72 }
73 for j := 0; j <= m; j++ {
74 d[0][j] = j
75 }
76 for i := 1; i <= n; i++ {
77 for j := 1; j <= m; j++ {
78 cost := 1
79 if ra[i-1] == rb[j-1] {
80 cost = 0
81 }
82 d[i][j] = min3(d[i][j-1]+1, d[i-1][j]+1, d[i-1][j-1]+cost)
83 }
84 }
85 return d
86}
87
88// Similarity returns a 0..100 percentage of how similar a and b are, defined as
89// (1 - distance/maxLen) * 100 rounded to the nearest integer. Two empty strings
90// are considered 100% similar.
91func Similarity(a, b string) int {
92 la := len([]rune(a))
93 lb := len([]rune(b))
94 maxLen := la
95 if lb > maxLen {
96 maxLen = lb
97 }
98 if maxLen == 0 {
99 return 100
100 }
101 dist := Distance(a, b)
102 // Rounded percentage of matching characters.
103 return ((maxLen-dist)*100 + maxLen/2) / maxLen
104}
105
106func min3(a, b, c int) int {
107 m := a
108 if b < m {
109 m = b
110 }
111 if c < m {
112 m = c
113 }
114 return m
115}
116
117// renderTable formats the DP matrix as a Markdown table with a and b as headers.
118func renderTable(a, b string) string {
119 ra := []rune(a)
120 rb := []rune(b)
121 d := Matrix(a, b)
122
123 var sb strings.Builder
124 // Header row: blank | "" | each rune of b.
125 sb.WriteString("| | ε |")
126 for _, r := range rb {
127 sb.WriteString(" `")
128 sb.WriteString(string(r))
129 sb.WriteString("` |")
130 }
131 sb.WriteString("\n")
132 // Separator.
133 sb.WriteString("|---|")
134 for j := 0; j <= len(rb); j++ {
135 sb.WriteString("---|")
136 }
137 sb.WriteString("\n")
138 // Data rows.
139 for i := 0; i <= len(ra); i++ {
140 if i == 0 {
141 sb.WriteString("| **ε** |")
142 } else {
143 sb.WriteString("| **`")
144 sb.WriteString(string(ra[i-1]))
145 sb.WriteString("`** |")
146 }
147 for j := 0; j <= len(rb); j++ {
148 sb.WriteString(" ")
149 sb.WriteString(strconv.Itoa(d[i][j]))
150 sb.WriteString(" |")
151 }
152 sb.WriteString("\n")
153 }
154 return sb.String()
155}
156
157// Render implements the gnoweb view.
158//
159// - "" or "/" : explanation + examples.
160// - "/<a>/<b>" : distance between a and b, with the DP table.
161func Render(path string) string {
162 path = strings.TrimPrefix(path, "/")
163 if path == "" {
164 return renderHome()
165 }
166
167 parts := strings.SplitN(path, "/", 2)
168 if len(parts) != 2 {
169 var sb strings.Builder
170 sb.WriteString("# Levenshtein\n\n")
171 sb.WriteString("Provide two words as `/<a>/<b>`, e.g. [`/kitten/sitting`](/r/moul/x/daily/levenshtein:kitten/sitting).\n\n")
172 sb.WriteString("[← back](/r/moul/x/daily/levenshtein)\n")
173 return sb.String()
174 }
175
176 a := parts[0]
177 b := parts[1]
178 dist := Distance(a, b)
179 sim := Similarity(a, b)
180
181 var sb strings.Builder
182 sb.WriteString("# Levenshtein distance\n\n")
183 sb.WriteString("Transforming **`")
184 sb.WriteString(a)
185 sb.WriteString("`** → **`")
186 sb.WriteString(b)
187 sb.WriteString("`**\n\n")
188 sb.WriteString("- **Edit distance:** `")
189 sb.WriteString(strconv.Itoa(dist))
190 sb.WriteString("` single-character edits (insert / delete / substitute)\n")
191 sb.WriteString("- **Similarity:** `")
192 sb.WriteString(strconv.Itoa(sim))
193 sb.WriteString("%`\n\n")
194
195 sb.WriteString("## DP table\n\n")
196 sb.WriteString("Each cell `d[i][j]` is the distance between the first *i* runes of `")
197 sb.WriteString(a)
198 sb.WriteString("` and the first *j* runes of `")
199 sb.WriteString(b)
200 sb.WriteString("`. The bottom-right cell is the answer.\n\n")
201 sb.WriteString(renderTable(a, b))
202 sb.WriteString("\n[← back](/r/moul/x/daily/levenshtein)\n")
203 return sb.String()
204}
205
206func renderHome() string {
207 var sb strings.Builder
208 sb.WriteString("# Levenshtein edit distance\n\n")
209 sb.WriteString("The **Levenshtein distance** between two strings is the minimum number of ")
210 sb.WriteString("single-character edits — *insertions*, *deletions*, or *substitutions* — ")
211 sb.WriteString("needed to turn one string into the other. This realm reimplements the classic ")
212 sb.WriteString("dynamic-programming algorithm (à la Go's `agext/levenshtein`) fully rune-aware and on-chain.\n\n")
213
214 sb.WriteString("## Try it\n\n")
215 sb.WriteString("Append two words as `/<a>/<b>`:\n\n")
216 examples := [][2]string{
217 {"kitten", "sitting"},
218 {"flaw", "lawn"},
219 {"sunday", "saturday"},
220 {"gno", "gnoland"},
221 }
222 for _, ex := range examples {
223 a, b := ex[0], ex[1]
224 d := Distance(a, b)
225 sb.WriteString("- [`/")
226 sb.WriteString(a)
227 sb.WriteString("/")
228 sb.WriteString(b)
229 sb.WriteString("`](/r/moul/x/daily/levenshtein:")
230 sb.WriteString(a)
231 sb.WriteString("/")
232 sb.WriteString(b)
233 sb.WriteString(") → distance **")
234 sb.WriteString(strconv.Itoa(d))
235 sb.WriteString("**\n")
236 }
237
238 sb.WriteString("\n## The classic example\n\n")
239 sb.WriteString("`kitten` → `sitting` = **3**:\n\n")
240 sb.WriteString("1. `kitten` → `sitten` (substitute *k* → *s*)\n")
241 sb.WriteString("2. `sitten` → `sittin` (substitute *e* → *i*)\n")
242 sb.WriteString("3. `sittin` → `sitting` (insert *g* at the end)\n\n")
243
244 sb.WriteString("## API\n\n")
245 sb.WriteString("- `Distance(a, b string) int` — the edit distance.\n")
246 sb.WriteString("- `Matrix(a, b string) [][]int` — the full DP matrix.\n")
247 sb.WriteString("- `Similarity(a, b string) int` — a 0..100 similarity percentage.\n")
248 return sb.String()
249}
