nx_fuzzy.nx source

1// nx_fuzzy.nx -- R-UX-1 of the onsite-search S-class ladder: SOVEREIGN typo/fuzzy tolerance (LIBRARY). 2// A misspelled query ("divorse") should still find the right doc -- the canonical fuzzy-query capability 3// (cited srch_lucene.raw: Lucene's fuzzy query). Implemented as exact Levenshtein edit distance (two-row DP), 4// integer, deterministic. Search use: when a query term has zero exact postings, accept vocab terms within a 5// small edit-distance bound (BK-tree makes that sub-linear -- the named scaling extension). 6// 7// exports: vr_fuzzy (edit distance), vr_fuzzy_within (bounded match). license_tier: ORIGINAL 8import "nx_syscalls.nx" 9 10// Levenshtein edit distance between a[0..na) and b[0..nb). two-row DP, O(na*nb) time, O(nb) space. 11func vr_fuzzy(a: *u8, na: i64, b: *u8, nb: i64) -> i64 { 12 let prev: *i64 = sys_mmap(8*(nb+2)) as *i64 13 let cur: *i64 = sys_mmap(8*(nb+2)) as *i64 14 var j: i64 = 0 15 while j <= nb { prev[j] = j; j = j + 1 } 16 var i: i64 = 1 17 while i <= na { 18 cur[0] = i 19 var k: i64 = 1 20 while k <= nb { 21 var cost: i64 = 1 22 if a[i-1] == b[k-1] { cost = 0 } 23 var m: i64 = prev[k] + 1 // deletion 24 let d: i64 = cur[k-1] + 1 // insertion 25 if d < m { m = d } 26 let r: i64 = prev[k-1] + cost // substitution / match 27 if r < m { m = r } 28 cur[k] = m 29 k = k + 1 30 } 31 var c: i64 = 0 32 while c <= nb { prev[c] = cur[c]; c = c + 1 } 33 i = i + 1 34 } 35 return prev[nb] 36} 37 38// 1 if edit distance(a,b) <= bound, else 0 39func vr_fuzzy_within(a: *u8, na: i64, b: *u8, nb: i64, bound: i64) -> i64 { 40 if vr_fuzzy(a, na, b, nb) <= bound { return 1 } 41 return 0 42}