code wiki / _hdl_build / nx_geo_places.nx
nx_geo_places.nx source
↩ module page · 61 lines · 2555 B
1// nx_geo_places.nx -- LIB: GEO-021 PLACES-SEARCH (fuzzy / typo-tolerant place lookup) via sovereign
2// Levenshtein edit distance. GEO-006 geocode does EXACT name match; this adds fuzzy ranking so "Tokio"
3// or "Chcago" still resolve. Rides the SAME gazetteer (here a NUL-separated name list; the GEO-006
4// store gazetteer can be flattened into one).
5//
6// THE EXCEED ANGLE: deterministic integer edit-distance ranking -- the best match and its score are
7// reproducible to the bit (no float similarity heuristic / nondeterministic tie-break). Sovereign, no
8// search API, no data hostage. The name list is "name1\0name2\0...\0\0" (double-NUL terminated).
9// license_tier: ORIGINAL
10import "nx_syscalls.nx"
11
12func geo_strlen(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } return n }
13func geo_min3(a: i64, b: i64, c: i64) -> i64 { var m: i64 = a; if b < m { m = b } if c < m { m = c } return m }
14
15// Levenshtein edit distance between two NUL-terminated strings (integer DP, one rolling row).
16func geo_levenshtein(a: *u8, b: *u8) -> i64 {
17 let la: i64 = geo_strlen(a)
18 let lb: i64 = geo_strlen(b)
19 let prev: *i64 = sys_mmap(8 * (lb + 1)) as *i64
20 let cur: *i64 = sys_mmap(8 * (lb + 1)) as *i64
21 var j: i64 = 0
22 while j <= lb { prev[j] = j; j = j + 1 }
23 var i: i64 = 1
24 while i <= la {
25 cur[0] = i
26 j = 1
27 while j <= lb {
28 var cost: i64 = 1
29 if a[i - 1] == b[j - 1] { cost = 0 }
30 cur[j] = geo_min3(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + cost)
31 j = j + 1
32 }
33 var k: i64 = 0
34 while k <= lb { prev[k] = cur[k]; k = k + 1 }
35 i = i + 1
36 }
37 return prev[lb]
38}
39
40// fuzzy search: lowest-edit-distance name in the NUL-separated list. Returns the matched name's index
41// (0-based); writes its edit distance to out_dist and its byte offset in the list to out_off.
42func geo_fuzzy_best(query: *u8, namelist: *u8, out_dist: *i64, out_off: *i64) -> i64 {
43 var off: i64 = 0
44 var idx: i64 = 0
45 var best: i64 = 0 - 1
46 var bestd: i64 = 0
47 var bestoff: i64 = 0
48 while namelist[off] != (0 as u8) {
49 let nm: *u8 = (namelist + off) as *u8
50 let d: i64 = geo_levenshtein(query, nm)
51 if best < 0 { best = idx; bestd = d; bestoff = off } else {
52 if d < bestd { best = idx; bestd = d; bestoff = off }
53 }
54 while namelist[off] != (0 as u8) { off = off + 1 }
55 off = off + 1
56 idx = idx + 1
57 }
58 out_dist[0] = bestd
59 out_off[0] = bestoff
60 return best
61}