2b:null 2c:["$","title",null,{"children":"Nilsimsa hashing | dleeftink | Observable"}] 31:T154a,class Nilsimsa { #B64 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-+'; #TRAN = [2, 214, 158, 111, 249, 29, 4, 171, 208, 34, 22, 31, 216, 115, 161, 172, 59, 112, 98, 150, 30, 110, 143, 57, 157, 5, 20, 74, 166, 190, 174, 14, 207, 185, 156, 154, 199, 104, 19, 225, 45, 164, 235, 81, 141, 100, 107, 80, 35, 128, 3, 65, 236, 187, 113, 204, 122, 134, 127, 152, 242, 54, 94, 238, 142, 206, 79, 184, 50, 182, 95, 89, 220, 27, 49, 76, 123, 240, 99, 1, 108, 186, 7, 232, 18, 119, 73, 60, 218, 70, 254, 47, 121, 28, 155, 48, 227, 0, 6, 126, 46, 15, 56, 51, 33, 173, 165, 84, 202, 167, 41, 252, 90, 71, 105, 125, 197, 149, 181, 244, 11, 144, 163, 129, 109, 37, 85, 53, 245, 117, 116, 10, 38, 191, 25, 92, 26, 198, 255, 153, 93, 132, 170, 102, 62, 175, 120, 179, 32, 67, 193, 237, 36, 234, 230, 63, 24, 243, 160, 66, 87, 8, 83, 96, 195, 192, 131, 64, 130, 215, 9, 189, 68, 42, 103, 168, 147, 224, 194, 86, 159, 217, 221, 133, 21, 180, 138, 39, 40, 146, 118, 222, 239, 248, 178, 183, 201, 61, 69, 148, 75, 17, 13, 101, 213, 52, 139, 145, 12, 250, 135, 233, 124, 91, 177, 77, 229, 212, 203, 16, 162, 23, 137, 188, 219, 176, 226, 151, 136, 82, 247, 72, 211, 97, 44, 58, 43, 209, 140, 251, 241, 205, 228, 106, 231, 169, 253, 196, 55, 200, 210, 246, 223, 88, 114, 78] initialise() { this.count = 0 this.acc = this.acc.fill(0) this.lastch0 = -1 this.lastch1 = -1 this.lastch2 = -1 this.lastch3 = -1 } constructor(data, dict) { this.acc = new Uint8ClampedArray(256)//.fill(0) this.initialise(); if (data) { this.update(data) } } static compare (hash1, hash2, encoding='Base64') { let buf1 = hash1 //Buffer.from(hash1, encoding) let buf2 = hash2 //Buffer.from(hash2, encoding) const POPC = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8] if (buf1.length != buf2.length || buf1.length != 32) { // 256 bits per hash //throw new RangeError('Invalid Nilsimsa hashes') buf1 = hash1.digest(); buf2 = hash2.digest(); } let bit_diff_sum = 0 for (let byte_idx = 32; byte_idx--;) { bit_diff_sum += POPC[buf1[byte_idx] ^ buf2[byte_idx]] } return 128 - bit_diff_sum } tran3(a, b, c, n) { return ((this.#TRAN[(a + n) & 255] ^ this.#TRAN[b] * (n + n + 1)) + this.#TRAN[c ^ this.#TRAN[n]]) & 255 } toUTF8Array (str) { var utf8 = str //unescape(encodeURIComponent(str)); var arr = []; for (var i = 0; i < utf8.length; i++) { arr.push(utf8.charCodeAt(i)); } return arr; } update(data) { const buffer = this.toUTF8Array(data) //Buffer.from(data) this.initialise(); //for (const ch of buffer.values()) { for (let i = 0; i < data.length; ++i) { let ch = buffer[i]; this.count += 1 if (this.lastch1 > -1) { this.acc[this.tran3(ch, this.lastch0, this.lastch1, 0)] += 1 } if (this.lastch2 > -1) { this.acc[this.tran3(ch, this.lastch0, this.lastch2, 1)] += 1 this.acc[this.tran3(ch, this.lastch1, this.lastch2 ,2)] += 1 } if (this.lastch3 > -1) { this.acc[this.tran3(ch, this.lastch0, this.lastch3, 3)] += 1 this.acc[this.tran3(ch, this.lastch1, this.lastch3 ,4)] += 1 this.acc[this.tran3(ch, this.lastch2, this.lastch3, 5)] += 1 this.acc[this.tran3(this.lastch3, this.lastch0, ch, 6)] += 1 this.acc[this.tran3(this.lastch3, this.lastch2, ch, 7)] += 1 } this.lastch3 = this.lastch2 this.lastch2 = this.lastch1 this.lastch1 = this.lastch0 this.lastch0 = ch } return this } digest(encoding,dict) { let total = 0 switch(this.count) { case 0: case 1: case 2: break case 3: total += 1 break case 4: total += 4 break default: total += (8 * this.count) - 28 } let code = new Uint8ClampedArray(32),//Array(32).fill(0), threshold = total / 256 for (let i = 0; i <= 255; i++) { const offset = i >> 3, current = code[offset] code[offset] = current + ((this.acc[i] > threshold ? 1 : 0 ) << (i & 7)) } //code.reverse() if(encoding == 'Base64') { let out = ''; let wrap = this.#B64.length - 1 for (let i = 0; i < 32; ++i) { out += this.#B64.charAt(parseInt(code[i] / 4))//& wrap) } return out } else if (encoding?.length) { let out = '' let wrap = encoding.length - 1; for (let i = 0; i < 32; ++i) { out += encoding.charAt(code[i] & wrap) } return out } else { return code //Buffer.from(code).toString(encoding) } } }32:T562,data = { let t1 = performance.now(); let dict = {}; let bins = temp.flat().slice(0,3); let n = new Nilsimsa() let win = 2; let r = [...corpus2[0],...corpus2[1]].map((d,i)=>{ let arr = n.update(d).digest() for (let j = 0; j < 32-win; ++j) { for (let n = 0; n < win - 1; n++) { // testing binned combos within window for (let m = n + 1; m < win; m++) { let a = parseInt(arr[j+n] /2) *2; let b = parseInt(arr[j+m] /2) *2 ; let key = a * b dict[key] ? dict[key]++ : dict[key] = 1; } } } return arr }) /*for (let i = 0; i < r.length; ++i) { let hash = r[i][1]; r[i] = Array(32); for (let j = 0; j < 32; ++j) { let val = hash[j]; for (let n = 0; n < 3; ++n) { var key = j + '_' + (val ^ bins[n]) dict[key] ? dict[key].push(i) : dict[key] = [i] /*dict[j] ? dict[j][key] ? dict[j][key].push(i) : dict[j][key] = [i] : dict[j] = {[key]:[i]}*/ /*} r[i][j] = dict[key] } }*/ // r = r.map(d=>[...d[1]].flatMap((d,i)=>(dict[i][d])).reduce((pool,item)=>(pool[item]? pool[item]++ : pool[item] =1,pool),{})) let [init,exit] = []//[r.slice(0,N),r.slice(N)] return { dict, t:performance.now()-t1, r,init,exit,bins, } }33:[] 2f:{"id":"f13477a7bebbcb49","slug":"nilsimsa-hashing","title":"Nilsimsa hashing","thumbnail":"ccb92610a18cb0498c28f68a98ea5af32f3ad5e9439ca8e057e371645ba5ea6f","access_level":"public","create_time":"$D2023-07-01T03:30:35.133Z","update_time":"$D2023-12-17T16:37:36.789Z","view_time":null,"first_public_time":"$D2023-07-01T03:30:35.133Z","fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"10e70264ea4e147e","login":"dleeftink","name":"","avatar_url":"https://avatars-next.observableusercontent.com/3700a558b99f2f54fb2542d09667aadabaae51f24e04e47e420c844503696b0e","tier":"starter_2024"},"version":2280,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"6cdb6324966da5d4","login":"dleeftink","name":"","avatar_url":"https://avatars-next.observableusercontent.com/3700a558b99f2f54fb2542d09667aadabaae51f24e04e47e420c844503696b0e","tier":null}],"members":[{"type":"individual","id":"6cdb6324966da5d4","login":"dleeftink","name":"","avatar_url":"https://avatars-next.observableusercontent.com/3700a558b99f2f54fb2542d09667aadabaae51f24e04e47e420c844503696b0e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"Nilsimsa hashing","cells":[{"id":0,"value":"# Nilsimsa hashing\n## Browser port for near-duplicate hashing","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":6,"value":"___","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":320,"value":"A browser port of the [node/nilsimsa](https://github.com/dsablic/node-nilsimsa) package omitting the Buffer dependency, based on Wilkins [initial implementation](https://github.com/jwilkins/nilsimsa) adapted from the [Damiani et al.](http://spdp.di.unimi.it/papers/pdcs04.pdf) (2002) paper. The Nilsimsa algorithm is able to generate hashes with a high collision rate for near duplicate input strings, useful for text dimensionality reduction tasks.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":325,"value":"___","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":262,"value":"hash1 = new Nilsimsa('The quicker brown fox jumps')//.split(' ').sort().join(''))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":265,"value":"hash2 = new Nilsimsa('the quickest brown fox sums'/*+crypto.randomUUID().slice(0,4)*/)//.split(' ').sort().join(''))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":332,"value":"___","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":337,"value":"The compare function produces a score out of 128 to determine duplicity:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":32,"value":"bitSum = Nilsimsa.compare(hash1,hash2) // out of 128","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":351,"value":"___","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":343,"value":"In addition, the `Base64` representation produces a 32 bit string useful for downstream comparison tasks (e.g. fuzzy many-to-many similarity):","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":85,"value":"hashes = [hash1.digest('Base64'),hash2.digest('Base64')]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":417,"value":"___\n\nAlternatively, you can provide the digest function a dictionary string (precision will be affected):","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":421,"value":"custom = [hash1.digest('01'),hash2.digest('01')]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":300,"value":"___\n\n### Port","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1197,"value":"temp = { \n let data = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8]\n let bins = data.reduce((pool,item,i)=> (pool[item] ? pool[item].push(i): pool[item] = [i],pool),{})\n return [bins[0] , bins[1] , bins[2]]\n \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":10,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":585,"value":"corpus = Array.from({length:5000},()=>crypto.randomUUID()/*+crypto.randomUUID()+crypto.randomUUID()+crypto.randomUUID()+crypto.randomUUID()+crypto.randomUUID()+crypto.randomUUID()*/)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":831,"value":"corpus2 = {\n let corpus = (await fetch('https://raw.githubusercontent.com/gabrielStanovsky/template-oie/master/examples/sentences.txt')).text()\n corpus = (await corpus).replace(/[^\\w\\s]+|\\d+/g,'').split('\\n')\n .map(str =>[...Array(2).keys()].map(i=>str.trim().toLowerCase()\n /* .split(' ').slice(parseInt(Math.random()*2),4+parseInt(Math.random()*7)).join(' ')\n /* .split(' ').sort(() => .5 - Math.random() ).join(' ')*/.replace(/\\s+/g,' ').trim()))//.filter(d=>d[0]!==d[1])\n\n .slice(0,N)\n \n return [\n corpus.map(d=>d[0].split(' ').slice(2,42).join(' ')),\n corpus.map((d,i)=>'['+i+']'+d[1].split(' ').slice(0,32).filter(()=>0.80>Math.random()).join(' '))//.sort(() => .5 - Math.random() )\n ]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":839,"value":"N = 5000","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1419,"value":"viewof slider = Inputs.range([0,255],{step:0.01,value:0})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1307,"value":"{ \n let data = Array.from({length:255},(_,i)=> i ^ slider )\n let bins = data.map((d,j)=>[d,j]).filter(d=>temp[1].slice(0,6).includes(d[0]) || d[0] == 0)\n .map(d=>[d[1],d[0]])\n\n let plot = Plot.plot({\n marks: [\n Plot.ruleY([0]),\n Plot.ruleX([slider]),\n Plot.lineY(data),\n Plot.dot(bins)\n ]\n })\n return plot //[bins.map(d=>d[0]).sort(),Array.from({length:6},(_,i)=>(slider^temp[1][i])).concat(slider).sort()]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2230,"value":"Object.keys(data.dict)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":606,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 30:"$2f:body"