nx_simhash.nx source
↩ module page · 136 lines · 5302 B
1// nx_simhash.nx -- SimHash near-duplicate / content-novelty kernel.
2//
3// module: nishi-core.search.simhash
4// depends: fx.nx (Q16.16), nx_search_inverted.nx (reuse FNV-1a + tokenizer)
5// capability: CORE_COMPUTE
6// wired_status: FULLY_WIRED
7//
8// genealogy_id: charikar_2002_simhash + manku_2007_nearduplicate
9//
10// WHY (operator cardinal 2026-05-29 -- deliver info, additive, NO prejudging):
11// the SEO-resistance + anti-junk mechanism must be EARNED and MEASURED, never
12// assumed from a domain or title keyword. SimHash measures CONTENT overlap: a
13// page that merely re-copies a higher-quality source (the dominant SEO-spam
14// pattern -- mass-produced/templated/scraped content) collapses onto the
15// canonical original, while genuinely UNIQUE content (Comic-Con pics, candids,
16// original reporting) keeps a large Hamming distance and is preserved + valued.
17// To escape demotion an adversary must actually add unique information -- which
18// is exactly the point. Deterministic: token FNV-1a -> per-bit accumulate ->
19// 64-bit fingerprint -> Hamming distance. Integer-only, no floats.
20
21import "fx.nx"
22import "syscalls.nx"
23import "nx_search_inverted.nx"
24import "nx_bits.nx"
25
26// 64-bit SimHash fingerprint of a text, using alphanumeric tokens (>=2 chars)
27// as features (Charikar STOC 2002). For each token: FNV-1a-hash to 64 bits, and
28// for each bit position add +1 if the bit is set, -1 if clear. The final
29// fingerprint bit is 1 iff its accumulator is positive. Near-duplicate texts
30// share most tokens, so their fingerprints differ in few bits.
31func nx_simhash_fingerprint(text: *u8, n: i64) -> i64 {
32 let acc: *i64 = sys_mmap(64 * 8) as *i64
33 var b: i64 = 0
34 while b < 64 { acc[b] = 0; b = b + 1 }
35
36 var i: i64 = 0
37 while i < n {
38 if nx_inv_is_token_char(text[i] as i64) == 0 {
39 i = i + 1
40 } else {
41 let start: i64 = i
42 var run: i64 = 1
43 while run == 1 {
44 run = 0
45 if i < n {
46 if nx_inv_is_token_char(text[i] as i64) == 1 {
47 i = i + 1
48 run = 1
49 }
50 }
51 }
52 let len: i64 = i - start
53 if len >= 2 {
54 let tok: *u8 = ((text as i64) + start) as *u8
55 let h: i64 = nx_inv_hash_bytes_lower(tok, len)
56 var bit: i64 = 0
57 while bit < 64 {
58 if ((h >> bit) & 1) == 1 { acc[bit] = acc[bit] + 1 }
59 else { acc[bit] = acc[bit] - 1 }
60 bit = bit + 1
61 }
62 }
63 }
64 }
65
66 var fp: i64 = 0
67 var bit2: i64 = 0
68 while bit2 < 64 {
69 if acc[bit2] > 0 { fp = fp | (1 << bit2) }
70 bit2 = bit2 + 1
71 }
72 return fp
73}
74
75// Hamming distance (popcount of XOR) between two 64-bit fingerprints: the
76// number of differing bits, 0 (identical) .. 64 (opposite).
77func nx_simhash_hamming(a: i64, b: i64) -> i64 {
78 // SWAR popcount of the XOR (Hacker's Delight), byte-identical to the prior
79 // 64-iteration bit-test loop but a constant ~12 ops. Reuses the in-tree
80 // primitive so phash + the crawler dedup loops heal too (SPD-ALG-SEARCH-01).
81 return nx_bits_popcount64_soft(a ^ b)
82}
83
84// Near-duplicate iff Hamming distance <= threshold (Manku et al. WWW 2007 use
85// k=3 for 64-bit fingerprints over web-scale corpora).
86func nx_simhash_is_near_dup(a: i64, b: i64, threshold: i64) -> i64 {
87 if nx_simhash_hamming(a, b) <= threshold { return 1 }
88 return 0
89}
90
91// Content similarity in Q16.16: (64 - hamming)/64, FX_ONE == identical.
92func nx_simhash_similarity_q16(a: i64, b: i64) -> i64 {
93 let ham: i64 = nx_simhash_hamming(a, b)
94 return fx_from_frac(64 - ham, 64)
95}
96
97// Novelty signal: minimum Hamming distance from `fp` to any already-seen
98// fingerprint (large == novel/unique content; 0 == exact duplicate). Returns 64
99// for an empty seen-set (maximally novel). This is the ADDITIVE ranking signal:
100// a doc earns rank by how much NEW content it brings vs what is already surfaced.
101func nx_simhash_min_hamming(fp: i64, seen: *i64, n_seen: i64) -> i64 {
102 if n_seen <= 0 { return 64 }
103 var best: i64 = 64
104 var i: i64 = 0
105 while i < n_seen {
106 let h: i64 = nx_simhash_hamming(fp, seen[i])
107 if h < best { best = h }
108 i = i + 1
109 }
110 return best
111}
112
113// Cluster a corpus by near-duplication. cluster_of[i] = the index of the
114// EARLIEST doc within `threshold` Hamming of doc i (its canonical original), or
115// i itself if none. The canonical (earliest) doc represents the cluster; later
116// near-duplicates point back to it -- the bits-up "demote copies, keep the
117// canonical original" mechanism, earned from measured content overlap.
118func nx_simhash_cluster(fps: *i64, n: i64, threshold: i64, cluster_of: *i64) -> i64 {
119 var i: i64 = 0
120 while i < n {
121 var assigned: i64 = 0 - 1
122 var j: i64 = 0
123 while j < i {
124 if assigned < 0 {
125 if nx_simhash_hamming(fps[i], fps[j]) <= threshold {
126 assigned = cluster_of[j]
127 }
128 }
129 j = j + 1
130 }
131 if assigned < 0 { cluster_of[i] = i }
132 else { cluster_of[i] = assigned }
133 i = i + 1
134 }
135 return 0
136}