nx_bm25f.nx source

1// nx_bm25f.nx -- BM25F: fielded BM25 (Robertson/Zaragoza "Simple BM25 extension to multiple weighted fields", 2// CIKM'04 -- cited sovereign-fetched lib_bm25.txt: "BM25F defines each type of field as a stream, applying a 3// per-stream weighting"). The honest relevance rung above plain BM25: a query term in the TITLE field should 4// outrank the same term buried in the BODY. The fix is exactly what nx_bm25's own header predicted -- "a thin 5// extension via a weight table". Two fields here (title, body); adding more (url/anchor/tags) = more rows in 6// the weight table, no formula change (Cardinal 11/22). 7// 8// SIMPLE BM25F (the correct form -- length-normalize + weight PER FIELD, then saturate ONCE over the combined 9// pseudo-frequency, so a title hit isn't double-counted): 10// pseudo_tf(t,d) = SUM_f w_f * tf(t,f,d) / ( 1 - b + b * dl_f/avgdl_f ) 11// score(d,q) = SUM_t IDF(t) * pseudo_tf*(k1+1) / ( k1 + pseudo_tf ) 12// Integer/fixed-point throughout (reuses nx_bm25's bm_idf_micro keystone), x1e6 scale like bm_score. 13// license_tier: ORIGINAL 14import "nx_bm25.nx" // bm_idf_micro / bm_token_count / re_count / bm_best (+ syscalls, re_*) 15 16const BMF_K1_X1000: i64 = 1200 // k1 = 1.2 (tf saturation) 17const BMF_B_X1000: i64 = 750 // b = 0.75 (length normalization) 18const BMF_W_TITLE: i64 = 3 // title-field boost inside the per-field pseudo-tf (weight table) 19const BMF_W_BODY: i64 = 1 // body-field boost 20// TITLE-MATCH topical bonus (additive, OUTSIDE the saturation): a query term that occurs in the page TITLE 21// signals the page is ABOUT that term, so it should not be swamped by a rival page that merely repeats one 22// rare body term many times. Without this, BM25 tf-saturation flattens magnitude so a single high-IDF body 23// term wins (e.g. "NIST STEM maturity": roadmap's body maturity x5 beat the nist_stem page whose TITLE is 24// literally "nist stem"). The bonus is IDF-weighted (a title hit on a rare term matters more) and additive, 25// so it can only LIFT a page whose title matches -- it never demotes an existing body-only winner. 26const BMF_TITLE_MATCH_MULT: i64 = 2 // each title-matched query term adds (BMF_TITLE_MATCH_MULT * IDF) to score 27 28// per-field weighted + length-normalized pseudo-tf contribution, x1000: w * tf / (1 - b + b*dl/avgdl) 29func bmf_contrib(w: i64, tf: i64, dl: i64, avgdl: i64) -> i64 { 30 if tf <= 0 { return 0 } 31 var avd: i64 = avgdl 32 if avd <= 0 { avd = 1 } 33 let norm_x1000: i64 = (1000 - BMF_B_X1000) + (BMF_B_X1000 * dl) / avd // (1-b)+b*dl/avgdl, x1000 34 if norm_x1000 <= 0 { return 0 } 35 return (w * tf * 1000 * 1000) / norm_x1000 // w*tf/(norm), as x1000 36} 37 38// document frequency of `term` across N docs, counting a doc if the term is in its TITLE OR BODY field. 39func bmf_df(titles: *i64, tlens: *i64, bodies: *i64, blens: *i64, N: i64, term: *u8) -> i64 { 40 var c: i64 = 0; var i: i64 = 0 41 while i < N { 42 var has: i64 = 0 43 if re_count(titles[i] as *u8, tlens[i], term) > 0 { has = 1 } 44 if re_count(bodies[i] as *u8, blens[i], term) > 0 { has = 1 } 45 if has == 1 { c = c + 1 } 46 i = i + 1 47 } 48 return c 49} 50 51// BM25F score of doc k (title+body fields) for an nq-term query. x1e6 scale. 52func bmf_score(titles: *i64, tlens: *i64, dlt: *i64, 53 bodies: *i64, blens: *i64, dlb: *i64, 54 N: i64, k: i64, avgt: i64, avgb: i64, 55 qterms: *i64, nq: i64) -> i64 { 56 var s: i64 = 0; var t: i64 = 0 57 while t < nq { 58 let term: *u8 = qterms[t] as *u8 59 let tf_t: i64 = re_count(titles[k] as *u8, tlens[k], term) 60 let tf_b: i64 = re_count(bodies[k] as *u8, blens[k], term) 61 let ptf_x1000: i64 = bmf_contrib(BMF_W_TITLE, tf_t, dlt[k], avgt) + bmf_contrib(BMF_W_BODY, tf_b, dlb[k], avgb) 62 if ptf_x1000 > 0 { 63 let df: i64 = bmf_df(titles, tlens, bodies, blens, N, term) 64 let idf: i64 = bm_idf_micro(N, df) // x1e6 65 let num_x1000: i64 = ((BMF_K1_X1000 + 1000) * ptf_x1000) / 1000 // (k1+1)*ptf, x1000 66 let den_x1000: i64 = BMF_K1_X1000 + ptf_x1000 // k1 + ptf, x1000 67 if den_x1000 > 0 { 68 let sat_x1000: i64 = (num_x1000 * 1000) / den_x1000 // x1000 69 s = s + (idf * sat_x1000) / 1000 // keep x1e6 70 } 71 // additive title-match topical bonus (IDF-weighted, outside saturation): the page is ABOUT this term. 72 if tf_t > 0 { s = s + BMF_TITLE_MATCH_MULT * idf } 73 } 74 t = t + 1 75 } 76 return s 77} 78 79// best-ranked doc index for the query under BM25F (-1 if nothing matches). 80func bmf_best(titles: *i64, tlens: *i64, dlt: *i64, 81 bodies: *i64, blens: *i64, dlb: *i64, 82 N: i64, avgt: i64, avgb: i64, qterms: *i64, nq: i64) -> i64 { 83 var best: i64 = 0 - 1; var bs: i64 = 0; var i: i64 = 0 84 while i < N { 85 let sc: i64 = bmf_score(titles, tlens, dlt, bodies, blens, dlb, N, i, avgt, avgb, qterms, nq) 86 if sc > bs { bs = sc; best = i } 87 i = i + 1 88 } 89 return best 90}