2b:null 2c:["$","title",null,{"children":"QuickFuzz Demo | dleeftink | Observable"}] 31:T938,ents = { let t1 = performance.now(); let data = corpusEN[0]; let span = data.length; let bits = 4, divs = 1 / bits; let calc = (span) => bits * Math.ceil(span * divs); let refs = {}; let dict = {}; let init = Array.from({ length: span }, () => []); // create basic word dictionary for (let i = 0; i < span; ++i) { let line = data[i].split(" "); let size = line.length; for (let j = 0; j < size; ++j) { let word = line[j]; if (word.length < 2) continue; let list = refs[word]; list ? list.push(i) : (refs[word] = list = [i]); init[i].push(list) } } // prepare dictionary for numeric encoding let flat = Array.from({ length: span }, () => ""); let keys = Object.keys(refs); //.sort((a,b)=> Math.abs(6-a.length) - Math.abs(6-b.length)) //.sort((a,b)=>a.length - b.length || a.localeCompare(b)) span = keys.length; for (let i = 0; i < span; ++i) { let line = keys[i]; // transliterate non-ascii chars line = transliterable(line) ? encodeURIComponent(line) : line; // playing with below parameters seem to improve/decrease fuzzy cluster quality // TO DO better padding rules // line = line.padEnd(calc(line.length),' ') let copy = line; for (let j = 0; j < bits; ++j) { line += " ".repeat(j + 1) + copy; } line = line.padEnd(calc(line.length), " "); flat[i] = line; } // concatenate keys for one-shot encoding // might not be te best strategy for isolated terms let pads = bits * 0; let mark = String.fromCodePoint(0).repeat(pads); let rope = flat.join(mark) + mark; let size = rope.length; let [view, exit] = byteLense(size, bits); let utf8 = new TextEncoder(); utf8.encodeInto(rope, exit); let freq = new Map(); let from, till = 0, ceil = Math.ceil; // build word-to-word index for (let i = 0; i < span; ++i) { let word = keys[i]; dict[word] = []; from = till; till += ceil((flat[i].length + pads) * divs); for (let n = from; n < till; ++n) { let hash = view[n]; let data = freq.get(hash); data ? data.at(-1) == i ? null : data.push(i) : freq.set(hash, (data = [i])); dict[word].push(data); } } return { t: performance.now() - t1, dict, refs, init, }; } 32:[] 2f:{"id":"2664ca1608d43e6d","slug":"quickfuzz-demo","title":"QuickFuzz Demo","thumbnail":"ff5436cb457e279da3af739b283dd848f28ac98a9f4f1ef45fab741b8b301a07","access_level":"public","create_time":"$D2023-09-23T07:13:10.993Z","update_time":"$D2023-10-07T13:37:40.678Z","view_time":null,"first_public_time":"$D2023-09-23T07:13:10.993Z","fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"10e70264ea4e147e","login":"dleeftink","name":"","avatar_url":"https://avatars-next.observableusercontent.com/3700a558b99f2f54fb2542d09667aadabaae51f24e04e47e420c844503696b0e","tier":"starter_2024"},"version":206,"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":1,"collection":null,"type":"notebook","body":{"title":"QuickFuzz Demo","cells":[{"id":0,"value":"# QuickFuzz Demo\n## Fuzzy matching using byte words","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":110,"value":"___","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":36,"value":"quickFuzz = {\n\n let t1 = performance.now()\n let keys = Object.keys(ents.dict);\n let vals = Object.values(ents.dict);\n\n let clip = 32;\n let span = keys.length;\n let dict = {};\n \n let freq = new QuickSet({span,slot:8,freq:1,fifo:false})\n\n for (let i = 0; i < span; ++i) {\n \n let data = vals[i];\n let size = data.length\n \n for (let j = 0; j < size; ++j) {\n let nums = data[j]\n let iter = nums.length\n // if (iter > clip) continue\n for (let n = 0; n < iter; ++n) {\n freq.minsum(nums[n])\n }\n }\n \n let word = keys[i]\n dict[word] = freq.top().filter(d=>d[0]!== i && d[1]>0).map(d=>keys[d[0]])\n freq.clear(true)\n\n }\n\n return {\n t: performance.now()-t1 + ents.t,\n dict\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":20,"value":"___\n\n### Static","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":27,"value":"function byteLense(span = 512, bits = 1) {\n \n let buff, exit, calc;\n switch (true) {\n case bits <= 1:\n calc = (span) => span;\n buff = new ArrayBuffer(span);\n return [exit = new Uint8Array(buff), exit,calc];\n\n case bits <= 2:\n calc = (span) => 2 * Math.ceil(span * 0.5);\n buff = new ArrayBuffer(calc(span))\n return [new Uint16Array(buff), new Uint8Array(buff),calc ];\n\n case bits <= 4:\n calc = (span) => 4 * Math.ceil(span * 0.25)\n buff = new ArrayBuffer(calc(span));\n return [new Uint32Array(buff), new Uint8Array(buff),calc];\n\n case bits <= 8:\n calc = (span) => 8 * Math.ceil(span * 0.125)\n buff = new ArrayBuffer(calc(span));\n return [new Float64Array(buff), new Uint8Array(buff),calc];\n\n default: throw new Error('Maximum bits is 8')\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":24,"value":"function transliterable(string) { \n return (/\\P{ASCII}/gu).test(string)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":16,"value":"___\n\n### Imports","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":38,"value":"QuickSet = (await import('https://unpkg.com/@suptxt/quickset/dist/index.js?module')).default","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":12,"value":"import {newsweb} from \"@dleeftink/datasets\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":14,"value":"corpusEN = newsweb","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}} 30:"$2f:body"