nx_editdist.nx source
↩ module page · 41 lines · 1652 B
1// nx_editdist.nx -- INTEGER bounded Levenshtein for the typo/did-you-mean rung. Classic two-row DP over
2// byte strings (our index terms are lowercased alnum runs <= 32 bytes, so bytes == characters here).
3// ed_bounded returns the edit distance, or bound+1 the moment it can prove distance > bound (early-out:
4// the length gap alone decides most rejects at O(1)). No floats, no allocation beyond two 40-cell rows.
5// license_tier: ORIGINAL
6import "nx_syscalls.nx"
7
8func ed_bounded(a: *u8, an: i64, b: *u8, bn: i64, bound: i64) -> i64 {
9 var gap: i64 = an - bn
10 if gap < 0 { gap = 0 - gap }
11 if gap > bound { return bound + 1 }
12 if an == 0 { return bn }
13 if bn == 0 { return an }
14 let prev: *i64 = sys_mmap(40 * 8) as *i64
15 let cur: *i64 = sys_mmap(40 * 8) as *i64
16 var j: i64 = 0
17 while j <= bn { prev[j] = j; j = j + 1 }
18 var i: i64 = 1
19 while i <= an {
20 cur[0] = i
21 var rowmin: i64 = i
22 j = 1
23 while j <= bn {
24 var cost: i64 = 1
25 if a[i - 1] == b[j - 1] { cost = 0 }
26 var v: i64 = prev[j - 1] + cost // substitute / match
27 let del: i64 = prev[j] + 1 // delete from a
28 if del < v { v = del }
29 let ins: i64 = cur[j - 1] + 1 // insert into a
30 if ins < v { v = ins }
31 cur[j] = v
32 if v < rowmin { rowmin = v }
33 j = j + 1
34 }
35 if rowmin > bound { return bound + 1 } // the whole row exceeded the bound -> can only grow
36 j = 0
37 while j <= bn { prev[j] = cur[j]; j = j + 1 }
38 i = i + 1
39 }
40 return prev[bn]
41}