levenshteindemo.gno
4.94 Kb · 148 lines
1// Package levenshteindemo is a small gnoweb demo of the Levenshtein edit-distance
2// library provided by [p/moul/x/daily/levenshtein](/p/moul/x/daily/levenshtein/v0):
3// it renders an explanation, worked examples, and an interactive distance
4// calculator with the full dynamic-programming table.
5//
6// It contains no distance logic of its own — everything comes from
7// `levenshtein.Distance`, `levenshtein.Matrix` and `levenshtein.Similarity`.
8package levenshteindemo
9
10import (
11 "strconv"
12 "strings"
13
14 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/ui/v0"
15 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/md/v0"
16 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/levenshtein/v0"
17)
18
19// Render implements the gnoweb view.
20//
21// - "" or "/" : explanation + examples.
22// - "/<a>/<b>" : distance between a and b, with the DP table.
23func Render(path string) string {
24 path = strings.TrimPrefix(path, "/")
25 if path == "" {
26 return renderHome()
27 }
28
29 parts := strings.SplitN(path, "/", 2)
30 if len(parts) != 2 {
31 var sb strings.Builder
32 sb.WriteString("# Levenshtein\n\n")
33 sb.WriteString("Provide two words as `/<a>/<b>`, e.g. [`/kitten/sitting`](/r/moul/x/daily/levenshteindemo/v1:kitten/sitting).\n\n")
34 sb.WriteString("[← back](/r/moul/x/daily/levenshteindemo/v1)\n")
35 return sb.String()
36 }
37
38 a := parts[0]
39 b := parts[1]
40 dist := levenshtein.Distance(a, b)
41 sim := levenshtein.Similarity(a, b)
42
43 var sb strings.Builder
44 sb.WriteString("# Levenshtein distance\n\n")
45 sb.WriteString("Transforming **" + md.InlineCode(a) + "** → **" + md.InlineCode(b) + "**\n\n")
46 sb.WriteString("- **Edit distance:** `")
47 sb.WriteString(strconv.Itoa(dist))
48 sb.WriteString("` single-character edits (insert / delete / substitute)\n")
49 sb.WriteString("- **Similarity:** `")
50 sb.WriteString(strconv.Itoa(sim))
51 sb.WriteString("%`\n\n")
52
53 sb.WriteString("## DP table\n\n")
54 sb.WriteString("Each cell `d[i][j]` is the distance between the first *i* runes of ")
55 sb.WriteString(md.InlineCode(a))
56 sb.WriteString(" and the first *j* runes of ")
57 sb.WriteString(md.InlineCode(b))
58 sb.WriteString(". The bottom-right cell is the answer.\n\n")
59 sb.WriteString(renderTable(a, b))
60 sb.WriteString("\n[← back](/r/moul/x/daily/levenshteindemo/v1)\n")
61 return sb.String()
62}
63
64func renderHome() string {
65 var sb strings.Builder
66 sb.WriteString("# Levenshtein edit distance\n\n")
67 sb.WriteString("Demo of the [`p/moul/x/daily/levenshtein`](/p/moul/x/daily/levenshtein/v0) library. ")
68 sb.WriteString("The **Levenshtein distance** between two strings is the minimum number of ")
69 sb.WriteString("single-character edits — *insertions*, *deletions*, or *substitutions* — ")
70 sb.WriteString("needed to turn one string into the other. The library implements the classic ")
71 sb.WriteString("dynamic-programming algorithm (à la Go's `agext/levenshtein`) fully rune-aware and on-chain.\n\n")
72
73 sb.WriteString("## Try it\n\n")
74 sb.WriteString("Append two words as `/<a>/<b>`:\n\n")
75 examples := [][2]string{
76 {"kitten", "sitting"},
77 {"flaw", "lawn"},
78 {"sunday", "saturday"},
79 {"gno", "gnoland"},
80 }
81 for _, ex := range examples {
82 a, b := ex[0], ex[1]
83 d := levenshtein.Distance(a, b)
84 sb.WriteString("- [`/")
85 sb.WriteString(a)
86 sb.WriteString("/")
87 sb.WriteString(b)
88 sb.WriteString("`](/r/moul/x/daily/levenshteindemo/v1:")
89 sb.WriteString(a)
90 sb.WriteString("/")
91 sb.WriteString(b)
92 sb.WriteString(") → distance **")
93 sb.WriteString(strconv.Itoa(d))
94 sb.WriteString("**\n")
95 }
96
97 sb.WriteString("\n## The classic example\n\n")
98 sb.WriteString("`kitten` → `sitting` = **3**:\n\n")
99 sb.WriteString("1. `kitten` → `sitten` (substitute *k* → *s*)\n")
100 sb.WriteString("2. `sitten` → `sittin` (substitute *e* → *i*)\n")
101 sb.WriteString("3. `sittin` → `sitting` (insert *g* at the end)\n\n")
102
103 sb.WriteString("## API\n\n")
104 sb.WriteString("- `Distance(a, b string) int` — the edit distance.\n")
105 sb.WriteString("- `Matrix(a, b string) [][]int` — the full DP matrix.\n")
106 sb.WriteString("- `Similarity(a, b string) int` — a 0..100 similarity percentage.\n")
107 return sb.String()
108}
109
110// renderTable formats the DP matrix as a Markdown table with a and b as headers.
111func renderTable(a, b string) string {
112 ra := []rune(a)
113 rb := []rune(b)
114 d := levenshtein.Matrix(a, b)
115
116 var sb strings.Builder
117 // Header row: blank | "" | each rune of b.
118 sb.WriteString("| | ε |")
119 for _, r := range rb {
120 sb.WriteString(" ")
121 sb.WriteString(ui.Cell(string(r)))
122 sb.WriteString(" |")
123 }
124 sb.WriteString("\n")
125 // Separator.
126 sb.WriteString("|---|")
127 for j := 0; j <= len(rb); j++ {
128 sb.WriteString("---|")
129 }
130 sb.WriteString("\n")
131 // Data rows.
132 for i := 0; i <= len(ra); i++ {
133 if i == 0 {
134 sb.WriteString("| **ε** |")
135 } else {
136 sb.WriteString("| **")
137 sb.WriteString(ui.Cell(string(ra[i-1])))
138 sb.WriteString("** |")
139 }
140 for j := 0; j <= len(rb); j++ {
141 sb.WriteString(" ")
142 sb.WriteString(strconv.Itoa(d[i][j]))
143 sb.WriteString(" |")
144 }
145 sb.WriteString("\n")
146 }
147 return sb.String()
148}