levenshtein.nx source
↩ module page · 84 lines · 2926 B
1// levenshtein.nx -- Levenshtein edit distance.
2//
3// Computes the minimum number of single-character edits
4// (insertions, deletions, substitutions) needed to transform
5// string A into string B. Used for: typo correction, fuzzy
6// search, near-duplicate detection, "did you mean" suggestions.
7//
8// Wagner-Fischer dynamic programming (1974). O(m * n) time,
9// O(min(m, n)) space using the two-row optimisation.
10//
11// Invariants:
12// LV1 Symmetric: distance(a, b) == distance(b, a)
13// LV2 distance(a, "") == len(a); identity-distance is 0
14// LV3 Triangle inequality holds: distance(a, c) <=
15// distance(a, b) + distance(b, c)
16// LV4 Byte-level (not codepoint-level). ASCII text behaves
17// as expected; multi-byte UTF-8 counts each byte as a
18// distinct symbol -- callers wanting codepoint distances
19// decode to int sequences first.
20
21import "syscalls.nx"
22
23// Min of three i64s.
24func lv_min3(a: i64, b: i64, c: i64) -> i64 {
25 var m: i64 = a
26 if b < m { m = b }
27 if c < m { m = c }
28 return m
29}
30
31// Compute Levenshtein distance using the two-row method.
32func levenshtein(a: *u8, a_len: i64, b: *u8, b_len: i64) -> i64 {
33 // Edge cases.
34 if a_len == 0 { return b_len }
35 if b_len == 0 { return a_len }
36
37 // Two rolling rows of (b_len + 1) entries.
38 let row_size: i64 = b_len + 1
39 let prev_raw: *u8 = sys_mmap(row_size * 8 + 16)
40 let curr_raw: *u8 = sys_mmap(row_size * 8 + 16)
41 let prev: *i64 = prev_raw as *i64
42 let curr: *i64 = curr_raw as *i64
43
44 // Initial row: distance from "" to b[0..j] is j.
45 var j: i64 = 0
46 while j <= b_len { prev[j] = j; j = j + 1 }
47
48 var i: i64 = 1
49 while i <= a_len {
50 curr[0] = i
51 let ai: i64 = a[i - 1]
52 j = 1
53 while j <= b_len {
54 let bj: i64 = b[j - 1]
55 var cost: i64 = 1
56 if ai == bj { cost = 0 }
57 // Three candidates: deletion, insertion, substitution.
58 curr[j] = lv_min3(curr[j - 1] + 1, // insert
59 prev[j] + 1, // delete
60 prev[j - 1] + cost) // sub / match
61 j = j + 1
62 }
63 // Swap rows: prev <- curr, curr becomes new working row.
64 // Cheap: swap by copying since we don't have ptr-swap easily.
65 var k: i64 = 0
66 while k <= b_len { prev[k] = curr[k]; k = k + 1 }
67 i = i + 1
68 }
69 return prev[b_len]
70}
71
72// Compile-only smoke.
73func main() -> i64 {
74 // "kitten" -> "sitting" = 3 (k->s, e->i, +g)
75 let r1: i64 = levenshtein("kitten", 6, "sitting", 7)
76 if r1 != 3 { return 1 }
77 // identity = 0
78 let r2: i64 = levenshtein("hello", 5, "hello", 5)
79 if r2 != 0 { return 2 }
80 // empty strings
81 let r3: i64 = levenshtein("", 0, "abc", 3)
82 if r3 != 3 { return 3 }
83 return 0
84}