29:null 2a:["$","title",null,{"children":"Fast duplicate detection | dleeftink | Observable"}] 2f:Tae8,function nearest(init,exit,{} = {}) { let A = init, B = exit, t1 = performance.now(); let C = A.concat(B); let span = C.length; let size = 3, dict = {}, heap = new Array(span), link = {}; //C = C.map((str,i)=>{ for (let i = 0; i < span; ++i) { let str = process(C[i],{level:1})//.split(' ') // for words heap[i] = []//new Set(); for (var win = 2; win< size; ++win){ let prev; for (var j = 0; j < str.length-win; j++) { const hash = str.substring(j,(j+1)+win); //str[j]; //( dict[hash] ) ? ( dict[hash][i] ? ++dict[hash][i] : dict[hash][i] = 1 ) : //( dict[hash] = {}, dict[hash][i] = 1 ) /* if(dict[hash]) { if( i<= A.length ) { dict[hash][0].add(i) } else { dict[hash][1].add(i) } } else { dict[hash] = [new Set(),new Set()]}*/ ( dict[hash] ) ? dict[hash].add(i) : ( dict[hash] = new Set(), dict[hash].add(i) ) if(prev) { let tie = prev+'|'+hash; link[tie]? ++link[tie]: link[tie] = 1 } heap[i].push(hash); prev = hash; } } } let skip = Object.entries(link); skip = skip.sort((a,b)=>b[1]-a[1]).slice(0,parseInt(skip.length * 0.025)).map(d=>d[0].split('|')[1]); skip = new Set(skip); let keys = Object.keys(dict) for (var i = 0; i < keys.length; ++i) { //dict[keys[i]] = Object.keys(dict[keys[i]])//.sort((a,b)=>.025- Math.random()).slice(0,60) dict[keys[i]] = //[Array.from(dict[keys[i]][0]),Array.from(dict[keys[i]][1])]//.slice(0,32) //.sort((a,b)=>.5- Math.random()).slice(0,32) [ Array.from(dict[keys[i]]).filter(i=> i <= A.length), Array.from(dict[keys[i]]).filter(i=> i >= A.length)] } // TODO: iterate on max length, swap when init < exit // TODO: how to best splice arrays for (var i = 0; i < A.length; ++i) { let hash = heap[i] //Array.from(heap[i]??[]); let freq = Array(span); for (var j = 0; j < hash.length; ++j) { let entry = hash[j] if(skip.has(entry)) { continue } let locs = i < A.length ? dict[entry][1] : dict[entry][0] //dict[entry].filter((ref,j)=> i < A.length ? ref >= A.length : ref < A.length ) // implicit casting for (var n = 0; n < locs.length; ++n) { let idx = locs[n]; freq[idx] ? ++freq[idx] : freq[idx] = 1; } } heap[i] = //[C[i]].concat( freq.map((d,i)=>[i,d]) .filter(d=>d[1]>1 /*&& (i < A.length ? d[0] > span*0.5 : d[0] <= span*0.5)*/) .sort((a,b)=>b[1]-a[1]).slice(0,8) //.map((d)=>'['+d[0]+']'+[C[d[0]],d[1]][0]) .map((d)=>parseInt(C[d[0]].split(/[\[\]]/)[1])).includes(i) //) } return { dict,heap,link,skip, time: performance.now()-t1 } }30:T113f,// from https://github.com/huwenshuo/ctph.js ctph = (function () { var ctph = {}; var HASH_PRIME = 0x01000193; var HASH_INIT = 0x28021967; var B64 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-+'; // intuition is that size should equal string segment width let size = 3, iter = 16; let wrap = B64.length-1; function 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; } //FNV-1 hash function fnv (base, b) { return ((base * HASH_PRIME) ^ b) >>> 0; } function RollHash () { this.x = 0; this.y = 0; this.z = 0; this.c = 0; this.window = new Array(size); } RollHash.prototype.update = function (d) { this.y -= this.x; this.y += size* d; this.x += d; this.x -= this.window[this.c % size] || 0; this.window[this.c % size] = d; this.c++; this.z = (this.z << 5)>>>0; // `>>>0` for force unsigned this.z = (this.z ^ d)>>>0; }; RollHash.prototype.sum = function () { return (this.x + this.y + this.z) >>> 0; }; function piecewiseHash (bytes, triggerValue) { var signatures = ['','']; var h1 = HASH_INIT; var h2 = HASH_INIT; var rh = new RollHash(); var len = bytes.length; for (var i = 0; i < len; i++) { h1 = fnv(h1, bytes[i]); h2 = fnv(h2, bytes[i]); rh.update(bytes[i]); if (i === len - 1 || rh.sum() % triggerValue === (triggerValue - 1)) { signatures[0] += B64.charAt(h1&wrap); h1 = HASH_INIT; } if (i === len - 1 || rh.sum() % (triggerValue * 2) === (triggerValue * 2 - 1) ) { signatures[1] += B64.charAt(h2&wrap); h2 = HASH_INIT; } } return signatures; } //Context Triggered Piecewise Hash (CTPH) function digest (bytes) { var minb = 3; // was 3 var bi = Math.ceil(Math.log(bytes.length/(64*minb))/Math.log(2)); bi = Math.max(3, bi); var signatures = piecewiseHash(bytes, minb << bi); while (bi>0 && signatures[0].length < iter /*was 32*/ ){ signatures = piecewiseHash(bytes, minb << --bi); } return B64.charAt(bi) + ':' + signatures[0] + ':' + signatures[1]; } function matchScore (s1, s2) { var e = levenshtein(s1, s2); var r = 1 - e/Math.max(s1.length ,s2.length); return r * 100; } //Based on https://github.com/hiddentao/fast-levenshtein function levenshtein (str1, str2) { if (str1 === str2) return 0; if (str1.length === 0) return str2.length; if (str2.length === 0) return str1.length; var prevRow = new Array(str2.length + 1), curCol, nextCol, i, j, tmp; for (i=0; i tmp) { nextCol = tmp; } tmp = prevRow[j + 1] + 1; if (nextCol > tmp) { nextCol = tmp; } prevRow[j] = curCol; } prevRow[j] = nextCol; } return nextCol; } ctph.digest = function (data) { //if (typeof data === 'string') { data = toUTF8Array(data) //} return digest(data); }; ctph.similarity = function (d1, d2) { var b1 = B64.indexOf(d1.charAt(0)); var b2 = B64.indexOf(d2.charAt(0)); if (b1 > b2) return arguments.callee(d2, d1); // not available in strict mode if (Math.abs(b1-b2) > 1) { return 0; } else if (b1 === b2) { return matchScore(d1.split(':')[1], d2.split(':')[1]); } else { return matchScore(d1.split(':')[2], d2.split(':')[1]); } }; return ctph })();31:Tc64,function cluster(init,exit,{options = { lower:1, upper:2 }} = {}) { let dict = {}, link = [], freq = {}, rows = [], t1 = performance.now(); if (exit === undefined) { exit = Array(0) }; let affine = init.length == exit.length; let shrink = init.length >= exit.length, source = shrink ? init : exit; let expand = init.length < exit.length, target = expand ? init : exit; let S = source, T = target; // duplicate reference to inputs if ( shrink && exit.length === 0 ) { source = target = segment(source,dict,freq,{dest: null}); T = S } else { source = segment(source,dict,freq,{dest:'src'}); target = segment(target,dict,freq,{dest:'tgt'})} let skip = Object.entries(freq)//.sort((a,b)=>b[1]-a[1]) let flag = new Set() let knee = average(skip,[1]) * (4/3 /*0.5*/); // (4/3) * mu approximates y value at the CDF knee of a Zipf distribution // skip = skip//.sort((a,b)=>b[1]-a[1]).slice(0,parseInt(skip.length * 0.1725)) // skip 0.1725 first items seems emperically optimal // .filter(d=>d[1]>knee) // .map(d=>d[0]); // skip = new Set(skip); for (let i = 0; i < skip.length; ++i) { let val = skip[i] if(val[1]> knee) flag.add(val[0]) } skip = flag; let keys = Object.keys(dict); for (var i = 0; i < keys.length; ++i) { dict[keys[i]] = Array.from(dict[keys[i]].src); // [ Array.from(dict[keys[i]].src), Array.from(dict[keys[i]].tgt)] } let span = target.length; // let inum = Array.from(Array(256).keys()) // generate index once; TO DO: length from max hash length for (var i = 0; i < span; ++i) { let hash = target[i]//.map(d=> [d,freq[d]]).sort((a,b)=>a[1]-b[1]).map(d=>d[0]); let stat = new Uint8ClampedArray(span); // change array type based on max expected value; let run = 0; // slot for running total matches let sum = 0; // slot for summing match frequency let max = 0; // slot for keeping maximum matches let non = 0; // slot for keeping skipped entries let len = hash.length; // let bit = 0; // hash.filter(d=>!skip.has(d)).length; // random picks in case all hash elements are skipped (exceedingly rare); // let pick = spliced(len) // or shuffle(inum.slice(0,hash.length)) for (var j = 0; j < len; ++j) { let entry = hash[j]; // TO DO: randomly/priority iterate over hash signature, e.g. walkback if(skip.has(entry) && non/len < 0.95 ) { ++non;continue } let hits = dict[entry] for (var n = 0; n < hits.length; ++n) { let idx = hits[n]; stat[idx] ? ++stat[idx] : ( /*++run,*/ stat[idx] = 1 ); /*++sum;*/ if(stat[idx] > max) { max = stat[idx] } } } let ties = [{loc:i,tgt:T[i]}]; let top = max * (1/3); for(let k = 0; k< span; ++k) { let hit = stat[k] if(hit > 2 && hit == max) { let res = {loc:k,src:S[k],hit,max,non} ties.push(res) } } link.push(ties) } //shrink ? (init = source, exit = target) : (init = target, exit = source) return { //source,target, dict,freq,skip,link,knee, time: performance.now()-t1 } }32:T5ad,function segment(list,dict = {},freq={},{lower = 2, upper = 3, full = false, dest }={}) { let span = list.length let heap = new Array(span); if (full) { --lower,upper-- } for (let i = 0; i < span; ++i) { let str = // ctph.digest(list[i]) process(list[i],{level:1}); heap[i] = []; if(full) { str = str.split(' ').slice(1) } for (var win = lower; win < upper; ++win){ let prev; for (var j = 0; j < str.length-win; j++) { const hash = full ? str.slice(j,(j+1)+win).join(' ') : str.substring(j,(j+1)+win); // ( dict[hash] ) ? ( dict[hash][i] ? ++dict[hash][i] : dict[hash][i] = 1 ) : // ( dict[hash] = {}, dict[hash][i] = 1 ) // ( dict[hash] ) ? dict[hash].add(i) : ( dict[hash] = new Set(), dict[hash].add(i) ) // partitions input based on 'dest' if(dict[hash]) { dest !== 'tgt' ? dict[hash][dest||'src'].add(i) : null } // ^^ idea here is to skip tgt indexing completely, while keeping total freq below to keep track of shared occurance else { let copy; dict[hash] = dest === null ? {src:(copy = new Set(),copy),tgt:copy} : {src:new Set(),tgt:new Set()}; dict[hash][dest||'src'].add(i); } freq[hash]? ++freq[hash]: freq[hash] = 1; heap[i].push(hash); } } } return heap }33:T5b7,function recount(data) { // expects worker data as buffers const sets = new Uint32Array(data.sets); const rows = new Uint32Array(data.rows); const dict = new Uint32Array(data.dict); const locs = new Uint32Array(data.locs); const skip = new Set(new Uint32Array(data.skip)) const span = sets.length; const size = data.size; const rank = [] for (let i = 0; i < span; ++i) { let hash = rows.slice(sets[i],sets[i+1]||rows.length); let stat = new Uint32Array(size); // needs to have same dimensions as input array let run = 0; // slot for running total matches let sum = 0; // slot for summing match frequency let max = 0; // slot for keeping maximum matches let non = 0; // slot for keeping skipped entries let len = hash.length; let link = []; for (let j = 0; j < hash.length; ++j) { let entry = hash[j]; // TO DO -> random access; if(skip.has(entry) && non/hash.length < 0.95 ) { ++non;continue } let hits = dict.slice(locs[entry],locs[entry+1]||locs.length) for (var n = 0; n < hits.length; ++n) { let idx = hits[n]; stat[idx] ? ++stat[idx] : ( ++run, stat[idx] = 1 ); ++sum; if(stat[idx] > max) { max = stat[idx] } } } for(let k = 0; k< size; ++k) { let count = stat[k] if(!count) {continue} else if(count > 1 && count / max == 1) { link.push([k,count]) } } rank.push(link) } return rank }34:Te97,async function worker(init,exit,{options = { lower:2, upper:3 }} = {}) { let dict = {}, link = {}, freq = {}, rows = [], flat = [], locs = [], sets = [], flag = [],swap = {}, t1 = performance.now(); if (exit === undefined) { exit = Array(0) }; let affine = init.length == exit.length; let shrink = init.length >= exit.length, source = shrink ? init : exit; let expand = init.length < exit.length, target = expand ? init : exit; let S = source, T = target; // duplicate reference to inputs if ( shrink && exit.length === 0 ) { source = target = segment(source,dict,freq,{dest: null}); T = S } else { source = segment(source,dict,freq,{dest:'src'}); target = segment(target,dict,freq,{dest:'tgt'})} let skip = Object.entries(freq); let knee = average(skip,[1]) * (4/3); // (4/3) * mu approximates y value at the CDF knee of a Zipf distribution skip = skip //.sort((a,b)=>b[1]-a[1])//.slice(0,parseInt(skip.length * 0.1725)) // skip 0.1725 first items seems emperically optimal .filter(d=>d[1]>knee) .map(d=>d[0]); skip = new Set(skip); let keys = Object.keys(dict); let n = 0; locs = new Uint32Array(keys.length); for (var i = 0; i < keys.length; ++i) { let hits = Array.from(dict[keys[i]].src) let item = keys[i]; dict[item] = hits ; // [ Array.from(dict[keys[i]].src), Array.from(dict[keys[i]].tgt)] flat.push(...hits); locs[i] = n; n+=hits.length; swap[item] = i; } let span = target.length; n = 0; sets = new Uint32Array(span); for (var i = 0; i < span; ++i) { let size = target[i].length; for (let j = 0; j < size ; ++j) { rows.push(swap[target[i][j]]) } sets[i] = n; n+= size; } flat = new Uint32Array(flat); rows = new Uint32Array(rows); flag = Uint32Array.from(Array.from(skip).map(d=>swap[d])) let tasks = 4, pool = [], threads = [], view = []; sets = chunked(sets,tasks,{buffer:false}); for (let i = 0; i < tasks; ++i) { let start = sets[i][0], final = sets[i+1]?.[0]; pool.push({ rows:rows.slice(start,final).buffer, sets:sets[i].map(d=>d-start).buffer, skip:flag.slice(0).buffer, dict:flat.slice(0).buffer, locs:locs.slice(0).buffer}) } // view = pool.slice(0) // remove buffer reference above // pool = pool.map(d=> Object.fromEntries(Object.entries(d).map(d=>[d[0],d[1].slice(0).buffer]))) let code = `self.onmessage = function(e) { const t2 = performance.now(); ${recount.toString()} const data = recount(e.data); //const subarray = new Uint32Array(1).buffer; const t3 = performance.now(); self.postMessage({tt:~~(t3-t2), //subarray, data }, //[subarray] // transferable object ); }`; var blob = new Blob([code], { type: "text/javascript",}); for (let n = 0; n < tasks; ++n) { var objectURL = URL.createObjectURL(blob); var thread = new Worker(objectURL); threads.push(thread); } for (let t = 0; t < tasks; ++t) { let {rows,sets,skip,dict,locs} = pool[t]; threads[t].postMessage({rows,sets,skip,dict,locs,size:span},[rows,sets,skip,dict,locs]) } let queue = (Array.from({length:tasks},(_,i)=>new Promise((keep) => { threads[i].onmessage = function (e) { keep({tt:e.data.tt, //subarray:new Uint32Array(e.data.subarray), data:e.data.data}) threads[i].terminate(); }; }))) invalidation.then(() => { threads.forEach(thread=>thread.terminate()); }) let out = await Promise.all(queue) return { t:performance.now()-t1, r:out,view,pool,sets, } }35:T1064,atomic = { trig; // stable @v10431 // keep in mind that implicit references are used throughout let t1 = performance.now() let init = flat let N = init.length; let exit = []; let dict = {}; for (let i = 0; i < N; ++i) { let str = init[i] let line = str.replace(/[0-9\[\]]+/g,'').split(' ') // \b[\w]{1,5}\b for (let j = 0; j < line.length; ++j) { let item = line[j]; let data = dict[item]; // data ? data.at(-1) == i ? null : data.push(i) : dict[item] = [i]; // binary indices data? data.push(i) : dict[item] = [i]; // weighted indices line[j] = dict[item] //[line[j],dict[item]]; } exit.push(line) } let win = 3; let segs = {}; let divs = {}; let keys = Object.keys(dict); let vals = Object.values(dict); let size = keys.length; for (let i = 0; i < size; ++i) { let item = keys[i]; let data = vals[i]; if( data.length > 512 ) { data.length = 0 } // stopwords let slot = divs[item] = [] //[data]; if( win == 0 ) { slot.push(...data); continue } // pass regular document array else { let span = item.length; let nums = data.length; for (let j = 0; j < span-win+1; ++j) { let key = item.substring(j,j+win); let val = segs[key]; if(val) { val.push(i) // i == item in dictionary as integer } else { val = segs[key] = [i] // i == item in dictionary as integer }; slot.push(val) // push implicit reference } } } // skip segments freq > n // noop when window === 0 keys = Object.keys(segs); vals = Object.values(segs); size = keys.length; for (let i = 0; i < size; ++i) { let item = keys[i]; let data = vals[i]; let over = data.length //data[0] //.slice(0,1)[0]; let info = Math.log(size/over) // singleton arrays are automatically cast to numbers.. // if( info < 4 ) { data.length = 0 } // entropy like filtering // else { data[0] = new Uint16Array(data); data.length = 1; } // pre-build arrays or not? } // words are matched based on segments if(win) { let vecs = new Uint8ClampedArray(N); // static memory block for counting; keys = Object.keys(divs); vals = Object.values(divs); size = keys.length; for (let i = 0; i < size; ++i) { let item = keys[i]; let data = vals[i]; let span = data.length; if(span == 0) continue let size = 0; for (let j = 0; j < span;++j) { size+= data[j].length } let rows = new Uint16Array(size) // dynamically sized let last = 0; for (let j = 0; j < span; ++j) { let list = data[j] let iter = list.length if( iter == 0 ) continue rows.set(list,last) last += list.length; } /* // count logic let take = []; // set-like array of possible word matches let stat = vecs.fill(0); // static copy, resets every iteration span = rows.length; for (let n = 0; n < span; ++n) { let idx = rows[n]; if (idx == i) continue stat[idx] ? (take.push(idx),stat[idx]++) : stat[idx] = 1; } // fuzzy candidate list logic let freq = []; span = take.length let skip = new Set(); for (let n = 0; n < span; ++n) { let idx = take[n] if(skip.has(idx)) continue let val = stat[idx] let key = keys[idx] freq[val] ? freq[val].push(key) : freq[val] = [key] skip.add(idx) } // reciprocate fuzzy matches A <-> B freq = freq.at(-1) //let length = item.length if(freq) { span = freq.length; divs[item] = freq //new Set(freq) // freq//?.sort((a,b)=> Math.abs(a.length-length) - Math.abs(b.length-length)) for (let i = 0; i < span; ++i) { let term = freq[i] let near = Math.abs(term.length - item.length) < 1 if(divs[term] && near && typeof divs[term][0] == 'string') divs[term].push(item); } } else {divs[item] = null } */divs[item] = rows; } } return { t:performance.now()-t1, dict,segs,divs,exit } }36:[] 2d:{"id":"a224f2fe1b70a625","slug":null,"title":"Fast duplicate detection","thumbnail":"49e3b8e7b5c25c76853ac31b4ed41e895e2facb91573182f4e68e995d0ccb899","access_level":"public","create_time":"$D2023-06-21T02:31:01.644Z","update_time":"$D2023-10-02T04:58:26.354Z","view_time":null,"first_public_time":"$D2023-06-21T02:31:01.644Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"10e70264ea4e147e","login":"dleeftink","name":"","avatar_url":"https://avatars-next.observableusercontent.com/3700a558b99f2f54fb2542d09667aadabaae51f24e04e47e420c844503696b0e","tier":"starter_2024"},"version":12033,"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":false,"trashed":false,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Fast duplicate detection","cells":[{"id":0,"value":"# Fast duplicate detection\n## Many-to-many fuzzy substring hits\n\n___","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":68,"value":"matches.heap.slice(0,N).reduce((a,b)=>a+!!b,0)/N","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":186,"value":"simple = nearest(['abc','','def','','s'],['[0]','[0]abc','[2]','[2]def'])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":44,"value":"// matches = nearest(corpus[0],corpus[1])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":17,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2638,"value":" function areaUnderCurve ( func , start , end , delta = .001 ) {\n let area = 0; \n do { area += Math.abs ( func ( start ) ) * delta; start += delta; }\n while ( start <= end ); \n return area;\n }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1845,"value":"Plot.plot({\n //x:{type:'log'},\n marks: [\n Plot.ruleY([0]),\n Plot.lineY(real_dist),\n \n Plot.ruleY([inspect.knee]),\n\n /*Plot.ruleY([aprox_turn],{stroke:'red'}),\n Plot.lineY(aprox ,{stroke:'red'}),*/\n /*Plot.ruleX([aprox_index],{stroke:'red'}),\n Plot.lineY(aprox_cdf.map(d=>fmax*(d/Math.max(...aprox_cdf))) ,{stroke:'red'}),*/\n \n Plot.lineY(real_cdf.map(d=>fmax*(d/cmax)) ,{stroke:'blue'}),\n Plot.ruleX([real_cdf.findIndex(val=>val>real_cdfKnee)],{stroke:'blue'}),\n Plot.ruleY([fmax*(inspect.harmean/cmax)],{stroke:'blue'}),\n\n \n Plot.ruleX([real_cdf.length*0.19],{stroke:'orange'}),\n\n Plot.ruleY([inspect.knee],{stroke:'purple',strokeWidth:4,opacity:0.3}),\n Plot.ruleX([real_dist.findIndex(val=>val fmax*(0.1 * Math.E**(-0.1*(x+1)))),{stroke:'blue'})\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2666,"value":"real_dist = Object.values(inspect.freq).sort((a,b)=>b-a)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2816,"value":"real_cdf = real_dist.map((sum => value => sum += value)(0))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2832,"value":"real_cdfKnee = harmonicMean(real_cdf)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2662,"value":"real_func = x => real_dist[x]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2642,"value":"real_index = Object.values(inspect.freq).sort((a,b)=>b-a).findIndex(v=>v 1+Math.ceil((fmax*Math.ceil(((1/((x+1)**0.5)) - (1/((n.length)**0.5)))*100)/100))\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2313,"value":"aprox_cdf = aprox.map((sum => value => sum += value)(0))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2688,"value":"aprox_func = (x,i,n)=> 1+(fmax*((1/((x+1)**0.5)) - (1/((inspect.cumsum.length)**0.50))))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2315,"value":"aprox_knee = aprox[aprox_index]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2423,"value":"aprox_index = aprox_cdf.findIndex(val=>val>aprox_mean)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2310,"value":"aprox_mean = harmonicMean(aprox_cdf)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1867,"value":"cmax = Math.max(...real_cdf)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1935,"value":"fmax = Math.max(...real_dist)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1233,"value":"r = inspect.link.filter(d=>d.length>1).length/N","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":29,"value":"N = 5000-~~(Math.random()*10)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":296,"value":"inspect = cluster(corpus[0],corpus[1])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5965,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":287,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":313,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":40,"value":"function process(string, { level = 0, sort = false} = {}) {\n\n const pipe = (str,...rules) => rules.reduce((line,pipe,i) => rules[i-1] !== false && \n typeof pipe === 'function' ? pipe(line) : (pipe => pipe)(line), str) \n\n let padString = str => ' ' + str + ' '\n let dropConsec = str => str.replace(/([^])\\1+/g,'$1')\n \n let dropVowels = str => str.replace(/[aeoiu0-9]/g,'')\n let dropSingle = str => str.replace(/\\b\\S\\b/g,'')\n let keepBounds = str => str.replace(/(\\b\\S|\\S\\b)|[^.*]/g,'$1')\n \n //let sortChars = str => sort ? [...str].sort().join('') : str\n \n return dropConsec(padString(string)).replace(/[0-9\\[\\]]+/g,'')\n /*return pipe(string, padString, \n level > 1 , dropVowels,\n level > 0 , dropConsec,\n level > 2, dropSingle)*/\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3060,"value":"function shuffle(array) {\n let currentIndex = array.length, randomIndex;\n while (currentIndex != 0) {\n randomIndex = ~~(Math.random() * currentIndex);\n currentIndex--;\n [array[currentIndex], array[randomIndex]] = [\n array[randomIndex], array[currentIndex]];\n }\n return array;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3358,"value":"function spliced (len) { \n \n let cut = len *0.5;\n let arr = Array(len).keys()\n let A = [],B = [];\n \n for (const k of arr) {\n if(k %2) {\n B.push(k)\n } else { A.push(k) }\n }\n return A.concat(B)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4202,"value":"___\n\n### Threaded","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":3864,"value":"// adapted from: https://stackoverflow.com/a/8189268\nfunction chunked(a, n, { balanced = true, buffer = false } ={}) {\n \n if (n < 2) return [buffer ? a.slice(0).buffer : a.slice(0)];\n\n var len = a.length, \n out = [], i = 0,size;\n \n if (len % n === 0) {\n size = Math.floor(len / n);\n while (i < len) {\n out.push(buffer ? a.slice(i, (i += size)).buffer : a.slice(i, (i += size)));\n }\n } else if (balanced) {\n while (i < len) {\n size = Math.ceil((len - i) / n--);\n out.push(buffer ? a.slice(i, (i += size)).buffer : a.slice(i, (i += size)));\n }\n } else {\n n--;\n size = Math.floor(len / n);\n if (len % size === 0) size--;\n while (i < size * n) {\n out.push(buffer ? a.slice(i, (i += size)).buffer : a.slice(i, (i += size)));\n }\n out.push(buffer ? a.slice(size * n).buffer : a.slice(size * n));\n }\n return out;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5065,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":3683,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5096,"value":"inspectB = (inspect,worker(corpus[0],corpus[1]))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5142,"value":"parseFloat((inspect.time/inspectB.t).toPrecision(3))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2060,"value":"___\n\n### Stat ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1447,"value":"function logSum(array) {\n var sum = 0;\n for (var i = 0; i < array.length; i++) {\n sum += Math.log(array[i]);\n }\n return sum;\n }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":4607,"value":"function average(array,prop) {\n\n let size = array.length;\n let sum = 0;\n \n if(prop) {\n for (let i = 0; i < size; ++i) {\n sum += array[i][prop];\n }}\n else {\n for (let i = 0; i < size; ++i) {\n sum += array[i];\n }\n }\n return sum/size\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1450,"value":"function geometricMean(array) {\n return Math.exp(logSum(array) / array.length);\n }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1549,"value":"function harmonicMean(arr){\n\n let sum = 0;\n for (let i = 0; i < arr.length; i++)\n sum = sum + (1 / arr[i]);\n \n return arr.length/sum;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1891,"value":"function harmonicNumber (array) {\n\n let sum = 0;\n for (let i = 0; i < array.length; ++i) {\n sum += 1/array[i]\n }\n return sum\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":2779,"value":"// returns the value at the harmonic mean of the CDF\n// finds the value at the 'knee' of a distribution\n\nfunction integratedHarmean(array) {\n\n let vals = array.sort((a,b)=>b-a)\n let cumsum = vals.map((sum => value => sum += value)(0))\n let harmean = harmonicMean(cumsum);\n return vals[cumsum.findIndex(s=>s>harmean)];\n \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":20,"value":"___\n\n### Data","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":25,"value":"corpus = {\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,32).join(' ')),\n corpus.map((d,i)=>'['+i+']'+d[1].split(' ').slice(0,64).filter(()=>0.8>Math.random()).join(' ')).sort(() => .5 - Math.random() )\n ]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11083,"value":"flat = corpus[0].concat(corpus[0]).slice(12)//.concat(corpus[1]).concat(corpus[0]).concat(corpus[1])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":8031,"value":"Plot.plot({\n marks: [\n Plot.ruleY([0]),\n Plot.lineY(Object.values(atomic.segs).map(d=>d.size??d.length).sort((a,b)=>b-a), {y: d=>d, x: (d,i)=>i})\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9241,"value":"Object.entries(atomic.segs).sort((a,b)=>b[1].length-a[1].length)//.filter(d=>d[1].length==1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":8899,"value":"Object.entries(atomic.divs.million.flat().reduce((pool,item)=> (pool[item]? pool[item]++ : pool[item] = 1,pool),{})).sort((a,b)=>b[1]-a[1]).filter(d=>d[1]>0).map(d=>[corpus[0].concat(corpus[1])[d[0]],d[1]]).filter(d=>d[0]?.includes('million'))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7834,"value":"trig = Math.random()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9831,"value":"[...atomic.exit[0]].map((d,i)=>[corpus[0].concat(corpus[1])[i],d]).sort((a,b)=>b[1]-a[1])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11747,"value":"set = new QuickSet({span:2**14,slot:0,freq:1})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11731,"value":"temp = {\n let t1 = performance.now()\n\n\n let keys = Object.keys(atomic.divs)\n let divs = Object.values(atomic.divs)\n let span = divs.length\n let arr = {};\n let skip = new QuickSet({span:2**14})\n\n for (let i = 0; i < span; i = i + 1) {\n let data = divs[i]\n let size = data.length;\n if(!size) { continue }\n let len = Math.min(keys[i].length-1,16)\n set.clear(len)\n for (let j = 0; j < size; j = j + 1) {\n var val = data[j]\n if(val == i) continue\n set.sum(data[j])\n }\n for (let i = 0; i < len; ++i) {\n skip.put(set.rank[i])\n }\n arr[keys[i]] = set.stat[0]>0 ? Array.from(set.rank).map((idx,i)=>set.stat[i]>0 ? keys[idx] : null) : null \n }\n\n arr = Object.entries(arr).reverse().slice(4000)\n\n return {\n t:performance.now()-t1,\n r:arr,set,skip\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7957,"value":"$35","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":10808,"value":"{\n let MAX_BITS = 8;\n let mask = new Uint8Array(100);\n\n let hist = []\n let keys = []\n let stat = []//new Uint32Array(100);\n \n let uint = 3;\n let byte = 1 << (uint % MAX_BITS);\n let index = Math.trunc(uint / MAX_BITS)\n if((mask[index] & byte) == 0) { \n mask[index] |= byte;\n hist.push([index,byte,uint])\n keys[uint] = uint\n stat[uint] = 1\n } else {\n stat[uint]++\n }\n \n uint = 3;\n byte = 1 << (uint % MAX_BITS);\n index = Math.trunc(uint / MAX_BITS);\n if((mask[index] & byte) == 0) { \n mask[index] |= byte;\n hist.push([index,byte,uint])\n keys[uint] = uint\n stat[uint] = 1\n } else {\n stat[uint]++\n }\n\n //let res = [];\n //forEach(mask,item=>reif((mask[index] & byte) == 0) mask[index] |= bytes.push(item))\n return [hist,mask,keys,stat]\n\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":10902,"value":"function forEach(data, callback = item => item) {\n const MAX_BITS = 8;\n const len = data.length\n let cellIndex = -1\n let item = 0\n while (++cellIndex < len) {\n if (!data[cellIndex]) {\n item += MAX_BITS\n }\n else {\n let i = -1\n while (++i < MAX_BITS) {\n if (data[cellIndex] & (1 << i))\n callback(item)\n\n item++\n }\n }\n }\n }\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":10751,"value":"{\n let bitmask1 = 0b01000000_00000000_00000100_00001011; // [0, 1, 3, 10, 30]\n let bitmask2 = 0b00000000_00000000_10000000_11000001; // [0, 6, 7, 15]\n\n// Check for an item\n !!(bitmask1 & (1 << 10)); // has 10 item => true\n !!(bitmask1 & (1 << 9)); // has 9 item => false\n // As you can see, we don't need iterate every 32 item, to find one\n\n// Adding item\n bitmask1 |= 1 << 9; // add 9 item\n !!(bitmask1 & (1 << 9)); // has 9 item => true\n\n// Operating with items sets\n bitmask1 | bitmask2; // Unite all items\n !!((bitmask1 | bitmask2) & (1 << 15)); // Get intersection of sets\n // Here we put up to 1024 (it's 32*32) iterations into one bitwise operation\n return bitmask1\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6995,"value":"[ctph.digest(corpus[0][2]+corpus[0][1]+corpus[0][4]+corpus[0][3]),\n ctph.digest(corpus[0][1]+corpus[0][2]+corpus[0][3]+corpus[0][4])]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6699,"value":"import {Nilsimsa} from \"@dleeftink/nilsimsa-hashing\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":6934,"value":"{ \n let t1 = performance.now();\n let r = corpus[0].map(d=>new Nilsimsa(d))\n return {\n t:performance.now()-t1,\n r\n }\n }","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11922,"value":"{\n let base = 0\n let val = 256\n base <<= 1 << 9\n base <<= 128 << 6\n base <<= 64 << 3\n return [base,base.toString(2)]\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11870,"value":"{\n let t1 = performance.now();\n\n let init = corpus[0];\n let span = init.length;\n let list = [];\n\n let lower = 2;\n let upper = 3;\n let encoder = new TextEncoder();\n for (let i = 0; i < span; ++i) {\n for (var win = lower + 1; win < upper + 1; ++win) {\n let str = init[i];\n\n let prev;\n for (var j = 0; j < str.length - win; j++) {\n const hash = str.substring(j, j + win);\n const nums = new Uint16Array(win);\n for (let n = 0; n < win; ++n) {\n nums[n] = hash.charCodeAt(n);\n }\n list.push([hash, nums]);\n }\n }\n }\n\n return {\n t: performance.now() - t1,\n list,\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11876,"value":"QuickSet = (await import('https://unpkg.com/@suptxt/quickset/dist/index.js?module')).default","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11949,"value":"{\n let string = corpus[0][0]\n\n let char = [...string]\n let span = string.length\n\n let comb = 3\n \n return [1,2,3,4,5] => [ [1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5] ]\n\n\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":12001,"value":"combinations(5,3)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":11993,"value":"function combinations(n,r){\n let s = 1;\n let i = r;\n // n*(n-1)*....*(n-r+1)\n while(i 1) s *= r--;\n return s;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":12023,"value":"{\n let combs = Array.from({length:3},(_,i)=>Array.from({length:5},(_,j)=>[i,j]))\n return combs.flat()\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":12033,"value":"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 2e:"$2d:body"