nx_library_search.nx source

1// nx_library_search.nx -- S-class search/retrieval over a LIBRARY of information (not one source). 2// The Researcher recognizes an index page as a LIBRARY, harvests every doc it lists, then answers a 3// SEARCH PROMPT by RANKING the whole corpus -- TF-IDF style, which exceeds naive substring search: 4// * substring search can only say present/absent in one blob and cannot rank or pick the best doc 5// * this ranks N docs by sum over query terms of tf(term,doc) * idf(term), where RARER terms (low 6// document-frequency) weigh MORE -- so a doc that matches the distinctive query terms wins over a 7// doc that merely mentions a common one. That is the retrieval quality real search engines use. 8// Corpus is held as parallel arrays: ptrs[k] = (doc text *u8 stored as i64), lens[k] = its length. 9// license_tier: ORIGINAL Pairs with nx_research_extract (re_count/re_has/re_find) + nx_library_cache. 10 11import "nx_research_extract.nx" // re_count / re_has / re_find / re_strlen 12import "nx_bm25.nx" // the Engineer-wired production ranker (supersedes ls_best's TF-IDF) 13import "nx_syscalls.nx" 14 15// ---- library detection + harvest (read the index, follow each entry) ---------------------------- 16 17// is this page a LIBRARY (an index of many docs) rather than a single source? >=3 "[doc]" entries. 18func ls_is_library(text: *u8, n: i64) -> i64 { if re_count(text, n, "[doc] " as *u8) >= 3 { return 1 } return 0 } 19func ls_entry_count(text: *u8, n: i64) -> i64 { return re_count(text, n, "[doc] " as *u8) } 20 21// write the k-th doc PATH listed in the index into out[0..cap); return its length or -1. 22// entries look like: [doc] /abandonment Abandonment and load time research. 23func ls_entry_path(text: *u8, n: i64, k: i64, out: *u8, cap: i64) -> i64 { 24 let mlen: i64 = 6 // strlen("[doc] ") 25 var start: i64 = 0; var cnt: i64 = 0; var found: i64 = 0 - 1; var searching: i64 = 1 26 while searching == 1 { 27 let rel: i64 = re_find(text + start, n - start, "[doc] " as *u8) 28 if rel < 0 { searching = 0 } else { 29 let at: i64 = start + rel 30 if cnt == k { found = at + mlen; searching = 0 } else { cnt = cnt + 1; start = at + mlen } 31 } 32 } 33 if found < 0 { return 0 - 1 } 34 var i: i64 = found; var j: i64 = 0; var copying: i64 = 1 35 while copying == 1 { 36 if i >= n { copying = 0 } else { 37 let c: i64 = text[i] 38 if c == 32 { copying = 0 } else { if c == 10 { copying = 0 } else { if j < cap { out[j] = c; j = j + 1 } i = i + 1 } } 39 } 40 } 41 return j 42} 43 44// ---- ranked retrieval over the corpus ----------------------------------------------------------- 45 46func ls_doc(ptrs: *i64, k: i64) -> *u8 { return ptrs[k] as *u8 } 47 48// term frequency: occurrences of `term` in doc k. 49func ls_tf(ptrs: *i64, lens: *i64, k: i64, term: *u8) -> i64 { return re_count(ls_doc(ptrs, k), lens[k], term) } 50 51// document frequency: in how many of the ndocs docs does `term` appear at least once? 52func ls_df(ptrs: *i64, lens: *i64, ndocs: i64, term: *u8) -> i64 { 53 var c: i64 = 0; var i: i64 = 0 54 while i < ndocs { if re_has(ls_doc(ptrs, i), lens[i], term) == 1 { c = c + 1 } i = i + 1 } 55 return c 56} 57 58// idf-lite: rarer term => higher weight. w = ndocs - df + 1 (df>=1 when present). 59func ls_idf(ndocs: i64, df: i64) -> i64 { return ndocs - df + 1 } 60 61// score doc k for a query of nq terms (qterms[t] = a *u8 needle stored as i64). 62func ls_score(ptrs: *i64, lens: *i64, ndocs: i64, k: i64, qterms: *i64, nq: i64) -> i64 { 63 var s: i64 = 0; var t: i64 = 0 64 while t < nq { 65 let term: *u8 = qterms[t] as *u8 66 let tf: i64 = ls_tf(ptrs, lens, k, term) 67 if tf > 0 { s = s + tf * ls_idf(ndocs, ls_df(ptrs, lens, ndocs, term)) } 68 t = t + 1 69 } 70 return s 71} 72 73// the best-ranked doc index for the query (-1 if no doc scores > 0). [original TF-IDF ranker] 74func ls_best(ptrs: *i64, lens: *i64, ndocs: i64, qterms: *i64, nq: i64) -> i64 { 75 var best: i64 = 0 - 1; var bestscore: i64 = 0; var i: i64 = 0 76 while i < ndocs { 77 let sc: i64 = ls_score(ptrs, lens, ndocs, i, qterms, nq) 78 if sc > bestscore { bestscore = sc; best = i } 79 i = i + 1 80 } 81 return best 82} 83 84// the Engineer-WIRED upgrade: same interface as ls_best, but ranks with production BM25 (tf-saturation 85// + length-normalization). Computes doc lengths from the corpus so it is a true drop-in replacement. 86func ls_best_bm25(ptrs: *i64, lens: *i64, ndocs: i64, qterms: *i64, nq: i64) -> i64 { 87 let dls: *i64 = sys_mmap(8 * 256) as *i64 88 var total: i64 = 0; var i: i64 = 0 89 while i < ndocs { dls[i] = bm_token_count(ptrs[i] as *u8, lens[i]); total = total + dls[i]; i = i + 1 } 90 var avgdl: i64 = 1 91 if ndocs > 0 { avgdl = total / ndocs } 92 if avgdl <= 0 { avgdl = 1 } 93 return bm_best(ptrs, lens, dls, ndocs, avgdl, qterms, nq) 94}