2f:T42a,class TrieNode { constructor() { this.terminal = false; this.children = new Map(); this.value = null; this.size = 0; } add(text) { this.size += 1; if (text.length == 0) { this.terminal = true; return this; } const c = text[0]; if (!this.children.has(c)) { this.children.set(c, new TrieNode()); } return this.children.get(c).add(text.slice(1)); } set(text, value) { const prefix = this.search(text); if (prefix.i == text.length) { prefix.curr.value = value; return prefix.curr; } const curr = this.add(text); curr.value = value; return curr; } get(text) { const prefix = this.search(text); if (prefix.i == text.length) { return prefix.curr.value; } throw new Error(`${text} not found in trie.`); } search(text) { if (text.length == 0 || !this.children.has(text[0])) { return { i: 0, curr: this }; } const prefix = this.children.get(text[0]).search(text.slice(1)); prefix.i += 1; return prefix; } }30:T551,{ let prev_i = 0; let codes = []; for (let out of compress_generator(text)) { await Promises.delay(2000); const new_slice = text.slice(prev_i, out.i); let new_slice_code = 0; let prefix = new_slice.slice(0, new_slice.length - 1); try { // new_slice_code = trie.get(text.slice(prev_i, out.i - 1)); new_slice_code = out.trie.get(prefix); new_slice_code = new_slice_code === null ? new_slice[new_slice.length - 1] : `${new_slice_code}${new_slice[new_slice.length - 1]}`; } catch (error) { // yield htl.html`${error}`; new_slice_code = error; // await Promises.delay(2000); } codes.push(new_slice_code); yield htl.html`

${text.slice( 0, prev_i )}${text.slice( prev_i, out.i )}${text.slice(out.i)}

new_slice = ${new_slice} prefix=${prefix}
prev_i = ${prev_i}
out.i = ${out.i}
new_slice_code = ${new_slice_code}
codes = ${codes.join(", ")}
words = ${Array.from(words(out.trie)).join(", ")}

`; // if (new_slice_code === null) return; prev_i = out.i; } // new_slice_code = ${new_slice_code}-${text[out.i]} // // new_slice_code = ${trie.get(text.slice(prev_i, out.i))}${text[out.i]} }31:[] 2d:{"title":"LZ Compression","cells":[{"id":0,"value":"# LZ Compression\n\n* Algorithm from: https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch\n* Another demo: https://web.mit.edu/6.02/www/f2010/handouts/recitations/Recitation21VergheseFall2010.pdf\n* Wonderful demo: https://www.youtube.com/watch?v=RV5aUr8sZD0\n\n1. Initialize the dictionary to contain all strings of length one.\n1. Find the longest string W in the dictionary that matches the current input.\n1. Emit the dictionary index for W to output and remove W from the input.\n1. Add W followed by the next symbol in the input to the dictionary.\n1. Go to Step 2.","pinned":false,"hidden":false,"mode":"md"},{"id":14,"value":"char_codes = Array.from({ length: 256 }, (_, i) => i)","pinned":true,"hidden":false,"mode":"ojs"},{"id":5,"value":"char_map = new Map(char_codes.map((i) => [i, String.fromCharCode(i)]))","pinned":true,"hidden":false,"mode":"ojs"},{"id":193,"value":"viewof text = Inputs.text({ value: \"TOBEORNOTTOBEORTOBEORNOT#\" })","pinned":true,"hidden":false,"mode":"ojs"},{"id":26,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs"},{"id":79,"value":"function* words(curr) {\n // yield* [\"hello\"];\n // return;\n if (curr.terminal || curr.children.size == 0) {\n yield \"\";\n // return;\n }\n for (let [c, node] of curr.children.entries()) {\n for (let suffix of words(node)) {\n yield `${c}${suffix}`;\n }\n // yield* words(node).map((suffix) => `{c}{suffix}`);\n // .map((suffix) => `{c}{suffix}`)\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":30,"value":"trie = {\n const trie = new TrieNode();\n trie.add(\"TOBEORNOTTOBEORTOBEORNOT#\");\n trie.set(\"TOBO\", 22);\n return trie;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":149,"value":"trie.get(\"TOBO\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":98,"value":"trie.children.size","pinned":true,"hidden":false,"mode":"ojs"},{"id":106,"value":"Array.from(words(trie))","pinned":true,"hidden":false,"mode":"ojs"},{"id":81,"value":"{\n const trie = new TrieNode();\n // trie.add(\"h\");\n trie.add(\"hello\");\n trie.add(\"shello\");\n trie.add(\"hero\");\n trie.add(\"heroics\");\n trie.set(\"heron\", 22);\n return Array.from(words(trie));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":37,"value":"prefix = trie.search(text)","pinned":true,"hidden":false,"mode":"ojs"},{"id":39,"value":"new Object({\n ...prefix,\n prefix: text.slice(0, prefix.i),\n terminal: prefix.curr.terminal\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":22,"value":"function compress(text) {\n let result = null;\n for (let out of compress_generator(text)) {\n result = out;\n }\n return result;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":203,"value":"function* compress_generator(text) {\n const trie = new TrieNode();\n // trie.set(\"\\0\", trie.size);\n let new_text = [];\n const encoding_dict = new Map();\n const first_position = new Map();\n let i = 0;\n while (i < text.length) {\n let text_slice = text.slice(i, text.length);\n console.log(`i=${i}, size=${trie.size} and ${text_slice}`);\n const prefix = trie.search(text_slice);\n // break;\n // trie.add(text_slice);\n const prefix_slice = text.slice(i, i + prefix.i + 1);\n if (prefix.i < text_slice.length) {\n // Some new elements in prefix slice\n trie.set(prefix_slice, trie.size);\n first_position.set(trie.size, i);\n }\n encoding_dict.set(trie.get(prefix_slice), prefix_slice);\n new_text.push(trie.get(prefix_slice));\n console.log(prefix_slice, new_text, encoding_dict);\n i += prefix.i + 1; // Consumed i length, move to next\n yield { new_text, trie, encoding_dict, i, first_position };\n }\n\n // yield { new_text, trie, encoding_dict, i, first_position };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":195,"value":"htl.html`${viewof text}`","pinned":true,"hidden":false,"mode":"ojs"},{"id":206,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":200,"value":"text.length","pinned":true,"hidden":false,"mode":"ojs"},{"id":73,"value":"compressed_text = compress(text)\n// compressed_text = compress(\"TOBEORNOT\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":126,"value":"Array.from(words(compressed_text.trie))","pinned":true,"hidden":false,"mode":"ojs"},{"id":179,"value":"compressed_text.new_text\n .map((x) => compressed_text.encoding_dict.get(x))\n .join(\"\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}