31:T448,md`I wanted to know how many leaves the average prefix trie had after its creation the compression stage of [LZString](http://pieroxy.net/blog/pages/lz-string/index.html). The result was this notebook. Turns out that for most intents and purposes, we can assume that at least 50% of all nodes will be leaves, and in the few constructions where this is not true the majority will have only one child (like the perfectly compressible string). That is quite useful information when trying to optimize your data structure for memory and performance. Anyway, maybe someone else is interested in playing with this. Try copy-pasting a [random English Wikipedia page](https://en.wikipedia.org/wiki/Special:Random), or if you want to test it with a bigger character set, a [random Japanese Wiki page](https://ja.wikipedia.org/wiki/%E7%89%B9%E5%88%A5:%E3%81%8A%E3%81%BE%E3%81%8B%E3%81%9B%E8%A1%A8%E7%A4%BA). [Project Gutenberg](https://www.gutenberg.org/browse/scores/top) has a lot of large, free texts as well (turn off the circlepack and tree renders first though, or you risk freezing your browser).`32:T63c,circlePackedChart = { if(renderCirclePackedAndCollapsibleTree){ const root = pack(data); const svg = d3.select(DOM.svg(width, height)) .style("font", "10px sans-serif") .style("width", "100%") .style("height", "auto") .attr("text-anchor", "middle"); const shadow = DOM.uid("shadow"); svg.append("filter") .attr("id", shadow.id) .append("feDropShadow") .attr("flood-opacity", 0.3) .attr("dx", 0) .attr("dy", 1); const node = svg.selectAll("g") .data(d3.nest().key(d => d.height).entries(root.descendants())) .join("g") .attr("filter", shadow) .selectAll("g") .data(d => d.values) .join("g") .attr("transform", d => `translate(${d.x + 1},${d.y + 1})`); node.append("circle") .attr("r", d => d.r) .attr("fill", d => color(d.height)); const leaf = node.filter(d => !d.children); leaf.select("circle") .attr("id", d => (d.leafUid = DOM.uid("leaf")).id); leaf.append("clipPath") .attr("id", d => (d.clipUid = DOM.uid("clip")).id) .append("use") .attr("xlink:href", d => d.leafUid.href); leaf.append("text") .attr("clip-path", d => d.clipUid) .selectAll("tspan") .data(d => d.data.name.split(/(?=[A-Z][^A-Z])/g)) .join("tspan") .attr("x", 0) .attr("y", (d, i, nodes) => `${i - nodes.length / 2 + 0.8}em`) .text(d => d); node.append("title") .text(d => `${d.ancestors().map(d => d.data.name).reverse().join("/")}\n${format(d.value)}`); return svg.node(); } else return html`
`; }33:Tef4,collapsibleChart = { if (renderCirclePackedAndCollapsibleTree){ const root = d3.hierarchy(data); root.x0 = dy / 2; root.y0 = 0; root.descendants().forEach((d, i) => { d.id = i; d._children = d.children; if (d.depth && d.data.name.length !== 7) d.children = null; }); const svg = d3.create("svg") .attr("width", width) .attr("height", dx) .attr("viewBox", [-margin.left, -margin.top, width, dx]) .style("font", "10px sans-serif") .style("user-select", "none"); const gLink = svg.append("g") .attr("fill", "none") .attr("stroke", "#555") .attr("stroke-opacity", 0.4) .attr("stroke-width", 1.5); const gNode = svg.append("g") .attr("cursor", "pointer"); function update(source) { const duration = d3.event && d3.event.altKey ? 2500 : 250; const nodes = root.descendants().reverse(); const links = root.links(); // Compute the new tree layout. tree(root); let left = root; let right = root; root.eachBefore(node => { if (node.x < left.x) left = node; if (node.x > right.x) right = node; }); const height = right.x - left.x + margin.top + margin.bottom; const transition = svg.transition() .duration(duration) .attr("height", height) .attr("viewBox", [-margin.left, left.x - margin.top, width, height]) .tween("resize", window.ResizeObserver ? null : () => () => svg.dispatch("toggle")); // Update the nodes… const node = gNode.selectAll("g") .data(nodes, d => d.id); // Enter any new nodes at the parent's previous position. const nodeEnter = node.enter().append("g") .attr("transform", d => `translate(${source.y0},${source.x0})`) .attr("fill-opacity", 0) .attr("stroke-opacity", 0) .on("click", d => { d.children = d.children ? null : d._children; update(d); }); nodeEnter.append("circle") .attr("r", 2.5) .attr("fill", d => d._children ? "#555" : "#999"); nodeEnter.append("text") .attr("dy", "0.31em") .attr("x", d => d._children ? -6 : 6) .attr("text-anchor", d => d._children ? "end" : "start") .text(d => d.data.name) .clone(true).lower() .attr("stroke-linejoin", "round") .attr("stroke-width", 3) .attr("stroke", "white"); // Transition nodes to their new position. const nodeUpdate = node.merge(nodeEnter).transition(transition) .attr("transform", d => `translate(${d.y},${d.x})`) .attr("fill-opacity", 1) .attr("stroke-opacity", 1); // Transition exiting nodes to the parent's new position. const nodeExit = node.exit().transition(transition).remove() .attr("transform", d => `translate(${source.y},${source.x})`) .attr("fill-opacity", 0) .attr("stroke-opacity", 0); // Update the links… const link = gLink.selectAll("path") .data(links, d => d.target.id); // Enter any new links at the parent's previous position. const linkEnter = link.enter().append("path") .attr("d", d => { const o = {x: source.x0, y: source.y0}; return diagonal({source: o, target: o}); }); // Transition links to their new position. link.merge(linkEnter).transition(transition) .attr("d", diagonal); // Transition exiting nodes to the parent's new position. link.exit().transition(transition).remove() .attr("d", d => { const o = {x: source.x, y: source.y}; return diagonal({source: o, target: o}); }); // Stash the old positions for transition. root.eachBefore(d => { d.x0 = d.x; d.y0 = d.y; }); } update(root); return svg.node(); } else return html`
`; }34:T6af,sortableBarChart = { const margin = { top: 20, right: 0, bottom: 30, left: 40 }; const height = 500; const y = d3 .scaleLinear() .domain([0, d3.max(barChartData, (d) => d.value)]) .nice() .range([height - margin.bottom, margin.top]); const xAxis = (g) => g .attr("transform", `translate(0,${height - margin.bottom})`) .call(d3.axisBottom(sortableBarChart_x).tickSizeOuter(0)); const yAxis = (g) => g .attr("transform", `translate(${margin.left},0)`) .call(d3.axisLeft(y)) .call((g) => g.select(".domain").remove()) .call((g) => g .select(".tick:last-of-type text") .clone() .attr("x", 3) .attr("text-anchor", "start") .attr("font-weight", "bold") .text("total nodes with a given nr of children") ); const svg = d3.select(DOM.svg(width, height)); const bar = svg .append("g") .attr("fill", "steelblue") .selectAll("rect") .data(barChartData) .join("rect") .style("mix-blend-mode", "multiply") .attr("x", (d) => sortableBarChart_x(d.name)) .attr("y", (d) => y(d.value)) .attr("height", (d) => y(0) - y(d.value)) .attr("width", sortableBarChart_x.bandwidth()); const gx = svg.append("g").call(xAxis); const gy = svg.append("g").call(yAxis); svg.node().update = () => { const t = svg.transition().duration(750); bar .data(barChartData, (d) => d.name) .order() .transition(t) .delay((d, i) => i * 20) .attr("x", (d) => sortableBarChart_x(d.name)); gx.transition(t) .call(xAxis) .selectAll(".tick") .delay((d, i) => i * 20); }; return svg.node(); }35:T6d3,sortableBarChartPercent = { const margin = { top: 20, right: 0, bottom: 30, left: 40 }; const height = 500; const y = d3 .scaleLinear() .domain([0, d3.max(percentBarChartData, (d) => d.value)]) .nice() .range([height - margin.bottom, margin.top]); const xAxis = (g) => g .attr("transform", `translate(0,${height - margin.bottom})`) .call(d3.axisBottom(sortableBarChart_x).tickSizeOuter(0)); const yAxis = (g) => g .attr("transform", `translate(${margin.left},0)`) .call(d3.axisLeft(y)) .call((g) => g.select(".domain").remove()) .call((g) => g .select(".tick:last-of-type text") .clone() .attr("x", 3) .attr("text-anchor", "start") .attr("font-weight", "bold") .text("percentage of nodes with a given nr of children") ); const svg = d3.select(DOM.svg(width, height)); const bar = svg .append("g") .attr("fill", "steelblue") .selectAll("rect") .data(percentBarChartData) .join("rect") .style("mix-blend-mode", "multiply") .attr("x", (d) => sortableBarChart_x(d.name)) .attr("y", (d) => y(d.value)) .attr("height", (d) => y(0) - y(d.value)) .attr("width", sortableBarChart_x.bandwidth()); const gx = svg.append("g").call(xAxis); const gy = svg.append("g").call(yAxis); svg.node().update = () => { const t = svg.transition().duration(750); bar .data(percentBarChartData, (d) => d.name) .order() .transition(t) .delay((d, i) => i * 20) .attr("x", (d) => sortableBarChart_x(d.name)); gx.transition(t) .call(xAxis) .selectAll(".tick") .delay((d, i) => i * 20); }; return svg.node(); }36:T6cf,sortableBarChartRootChars = { const margin = ({top: 20, right: 0, bottom: 30, left: 40}); const height = 500; const y = d3.scaleLinear() .domain([0, d3.max(rootCharsBarChartData, d => d.value)]).nice() .range([height - margin.bottom, margin.top]); const xAxis = g => g .attr("transform", `translate(0,${height - margin.bottom})`) .call(d3.axisBottom(sortableBarChartRootChars_x).tickSizeOuter(0)); const yAxis = g => g .attr("transform", `translate(${margin.left},0)`) .call(d3.axisLeft(y)) .call(g => g.select(".domain").remove()) .call(g => g.select(".tick:last-of-type text").clone() .attr("x", 3) .attr("text-anchor", "start") .attr("font-weight", "bold") .text("total child nodes for a given root char code")); const svg = d3.select(DOM.svg(width, height)); const bar = svg.append("g") .attr("fill", "steelblue") .selectAll("rect") .data(rootCharsBarChartData) .join("rect") .style("mix-blend-mode", "multiply") .attr("x", d => sortableBarChartRootChars_x(d.name)) .attr("y", d => y(d.value)) .attr("height", d => y(0) - y(d.value)) .attr("width", sortableBarChartRootChars_x.bandwidth()); const gx = svg.append("g") .call(xAxis); const gy = svg.append("g") .call(yAxis); svg.node().update = () => { const t = svg.transition() .duration(750); bar.data(rootCharsBarChartData, d => d.name) .order() .transition(t) .delay((d, i) => i * 20) .attr("x", d => sortableBarChartRootChars_x(d.name)); gx.transition(t) .call(xAxis) .selectAll(".tick") .delay((d, i) => i * 20); }; return svg.node(); }37:T146b,LZScript = { const blob = new Blob([` "use strict"; let i = 0, getCharFromInt = String.fromCharCode, streamData, streamDataVal, streamDataPosition, streamGetCharFromInt; function _node(val) { return { v: val, d: {} }; } function streamBits(value, numBitsMask) { for (let i = 0; numBitsMask >>= 1; i++) { // shifting has precedence over bitmasking streamDataVal = value >> i & 1 | streamDataVal << 1; if (++streamDataPosition === 16) { streamDataPosition = 0; streamData.push(streamGetCharFromInt(streamDataVal)); streamDataVal = 0; } } } function compress(uncompressed) { // data - empty stream streamData = []; if (uncompressed != null) { // davaVal streamDataVal = 0; // dataPosition streamDataPosition = 0; streamGetCharFromInt = getCharFromInt; var j = 0, value = 0, dictionary = {}, freshNode = true, c = 0, node = _node(3), // first node will always be initialised like this. nextNode, dictSize = 3, numBitsMask = 0b100; if (uncompressed.length) { // If there is a string, the first charCode is guaranteed to // be new, so we write it to output stream, and add it to the // dictionary. For the same reason we can initialize freshNode // as true, and new_node, node and dictSize as if // it was already added to the dictionary (see above). c = uncompressed.charCodeAt(0); // == Write first charCode token to output == // 8 or 16 bit? value = c < 256 ? 0 : 1 // insert "new 8/16 bit charCode" token // into bitstream (value 1) streamBits(value, numBitsMask); streamBits(c, value ? 0b10000000000000000 : 0b100000000); // Add charCode to the dictionary. dictionary[c] = node; for (j = 1; j < uncompressed.length; j++) { c = uncompressed.charCodeAt(j); // does the new charCode match an existing prefix? nextNode = node.d[c]; if (nextNode) { // continue with next prefix node = nextNode; } else { // Prefix+charCode does not exist in trie yet. // We write the prefix to the bitstream, and add // the new charCode to the dictionary if it's new // Then we set node to the root node matching // the charCode. if (freshNode) { // Prefix is a freshly added character token, // which was already written to the bitstream freshNode = false; } else { // write out the current prefix token value = node.d[0x10000]; streamBits(value, numBitsMask); } // Is the new charCode a new character // that needs to be stored at the root? if (dictionary[c] == undefined) { // increase token bitlength if necessary if (++dictSize >= numBitsMask) { numBitsMask <<= 1; } // insert "new 8/16 bit charCode" token, // see comments above for explanation value = c < 256 ? 0 : 1 streamBits(value, numBitsMask); streamBits(c, value ? 0b10000000000000000 : 0b100000000); dictionary[c] = _node(dictSize) // Note of that we already wrote // the charCode token to the bitstream freshNode = true; } // add node representing prefix + new charCode to trie node.d[c] = _node(++dictSize) // increase token bitlength if necessary if (dictSize >= numBitsMask) { numBitsMask <<= 1; } // set node to first charCode of new prefix node = dictionary[c]; } } // === Write last prefix to output === if (freshNode) { // character token already written to output freshNode = false; } else { // write out the prefix token streamBits(node.v, numBitsMask); } // Is c a new character? if (dictionary[c] == undefined) { // increase token bitlength if necessary if (++dictSize >= numBitsMask) { numBitsMask <<= 1; } // insert "new 8/16 bit charCode" token, // see comments above for explanation value = c < 256 ? 0 : 1 streamBits(value, numBitsMask); streamBits(c, 0b100000000 << value); } // increase token bitlength if necessary if (++dictSize >= numBitsMask) { numBitsMask <<= 1; } } // Mark the end of the stream streamBits(2, numBitsMask); // Flush the last char streamDataVal <<= 16 - streamDataPosition; streamData.push(streamGetCharFromInt(streamDataVal)); } return {compressed: streamData.join(''), trie: dictionary}; } /** * The message should be the raw string to compress. * The returned message is the compressed string, * plus the trie that was constructed. * @param {MessageEvent} e */ onmessage = function (e) { const result = compress(e.data); // {compressed, trie} postMessage(result); } `], {type: "text/javascript"}); return URL.createObjectURL(blob); }38:T520,trieToChartData = { let maxDepth = 0, totalLeaves = 0, totalNodes = 0, maxChildren = 0, totalChildren = []; function _trieToChartData(name, trie, depth) { totalNodes++; if (depth > maxDepth) { maxDepth = depth; totalChildren[depth] = []; } let node = {name, children: []}; let children = []; let keys = Object.keys(trie.d); for(let i = 0; i < keys.length; i++){ const key = keys[i]; const char = String.fromCharCode(key); children.push(_trieToChartData(char, trie.d[key], depth+1)); } if (children.length) { node.children = children; } else { node.value = 1; totalLeaves++; } totalChildren[children.length] = (totalChildren[children.length]|0) + 1; return node; } return function(trie) { maxDepth = 0; totalLeaves = 0; totalNodes = 0; totalChildren = []; maxChildren = 0; const data = _trieToChartData("root", {d: trie}, 0); for(let i = 0; i < totalChildren.length; i++) totalChildren[i] = totalChildren[i] | 0; // remove root (it has all chars so the most children) totalChildren[totalChildren.length-1]--; while(totalChildren[totalChildren.length-1] <= 0) totalChildren.pop(); return {maxDepth, totalNodes, totalLeaves, totalChildren, data}; } }39:T3ecd,predeftxt = { return { lzwiki: `Lempel–Ziv–Welch (LZW) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch. It was published by Welch in 1984 as an improved implementation of the LZ78 algorithm published by Lempel and Ziv in 1978. The algorithm is simple to implement and has the potential for very high throughput in hardware implementations.[1] It is the algorithm of the widely used Unix file compression utility compress and is used in the GIF image format. The scenario described by Welch's 1984 paper[1] encodes sequences of 8-bit data as fixed-length 12-bit codes. The codes from 0 to 255 represent 1-character sequences consisting of the corresponding 8-bit character, and the codes 256 through 4095 are created in a dictionary for sequences encountered in the data as it is encoded. At each stage in compression, input bytes are gathered into a sequence until the next character would make a sequence with no code yet in the dictionary. The code for the sequence (without that character) is added to the output, and a new code (for the sequence with that character) is added to the dictionary. The idea was quickly adapted to other situations. In an image based on a color table, for example, the natural character alphabet is the set of color table indexes, and in the 1980s, many images had small color tables (on the order of 16 colors). For such a reduced alphabet, the full 12-bit codes yielded poor compression unless the image was large, so the idea of a variable-width code was introduced: codes typically start one bit wider than the symbols being encoded, and as each code size is used up, the code width increases by 1 bit, up to some prescribed maximum (typically 12 bits). When the maximum code value is reached, encoding proceeds using the existing table, but new codes are not generated for addition to the table. Further refinements include reserving a code to indicate that the code table should be cleared and restored to its initial state (a "clear code", typically the first value immediately after the values for the individual alphabet characters), and a code to indicate the end of data (a "stop code", typically one greater than the clear code). The clear code lets the table be reinitialized after it fills up, which lets the encoding adapt to changing patterns in the input data. Smart encoders can monitor the compression efficiency and clear the table whenever the existing table no longer matches the input well. Since codes are added in a manner determined by the data, the decoder mimics building the table as it sees the resulting codes. It is critical that the encoder and decoder agree on the variety of LZW used: the size of the alphabet, the maximum table size (and code width), whether variable-width encoding is used, initial code size, and whether to use the clear and stop codes (and what values they have). Most formats that employ LZW build this information into the format specification or provide explicit fields for them in a compression header for the data. Encoding A high level view of the encoding algorithm is shown here: Initialize the dictionary to contain all strings of length one. Find the longest string W in the dictionary that matches the current input. Emit the dictionary index for W to output and remove W from the input. Add W followed by the next symbol in the input to the dictionary. Go to Step 2. A dictionary is initialized to contain the single-character strings corresponding to all the possible input characters (and nothing else except the clear and stop codes if they're being used). The algorithm works by scanning through the input string for successively longer substrings until it finds one that is not in the dictionary. When such a string is found, the index for the string without the last character (i.e., the longest substring that is in the dictionary) is retrieved from the dictionary and sent to output, and the new string (including the last character) is added to the dictionary with the next available code. The last input character is then used as the next starting point to scan for substrings. In this way, successively longer strings are registered in the dictionary and available for subsequent encoding as single output values. The algorithm works best on data with repeated patterns, so the initial parts of a message see little compression. As the message grows, however, the compression ratio tends asymptotically to the maximum (i.e., the compression factor or ratio improves on an increasing curve, and not linearly, approaching a theoretical maximum inside a limited time period rather than over infinite time).[2] Decoding The decoding algorithm works by reading a value from the encoded input and outputting the corresponding string from the initialized dictionary. To rebuild the dictionary in the same way as it was built during encoding, it also obtains the next value from the input and adds to the dictionary the concatenation of the current string and the first character of the string obtained by decoding the next input value, or the first character of the string just output if the next value can not be decoded (If the next value is unknown to the decoder, then it must be the value added to the dictionary this iteration, and so its first character must be the same as the first character of the current string being sent to decoded output). The decoder then proceeds to the next input value (which was already read in as the "next value" in the previous pass) and repeats the process until there is no more input, at which point the final input value is decoded without any more additions to the dictionary. In this way, the decoder builds a dictionary that is identical to that used by the encoder, and uses it to decode subsequent input values. Thus, the full dictionary does not need to be sent with the encoded data. Just the initial dictionary that contains the single-character strings is sufficient (and is typically defined beforehand within the encoder and decoder rather than explicitly sent with the encoded data.) Variable-width codes If variable-width codes are being used, the encoder and decoder must be careful to change the width at the same points in the encoded data so they don't disagree on boundaries between individual codes in the stream. In the standard version, the encoder increases the width from p to p + 1 when a sequence ω + s is encountered that is not in the table (so that a code must be added for it) but the next available code in the table is 2p (the first code requiring p + 1 bits). The encoder emits the code for ω at width p (since that code does not require p + 1 bits), and then increases the code width so that the next code emitted is p + 1 bits wide. The decoder is always one code behind the encoder in building the table, so when it sees the code for ω, it generates an entry for code 2p − 1. Since this is the point where the encoder increases the code width, the decoder must increase the width here as well—at the point where it generates the largest code that fits in p bits. Unfortunately, some early implementations of the encoding algorithm increase the code width and then emit ω at the new width instead of the old width, so that to the decoder it looks like the width changes one code too early. This is called "early change"; it caused so much confusion that Adobe now allows both versions in PDF files, but includes an explicit flag in the header of each LZW-compressed stream to indicate whether early change is being used. Out of graphics file formats capable of using LZW compression, TIFF uses early change, while GIF and most others don't. When the table is cleared in response to a clear code, both encoder and decoder change the code width after the clear code back to the initial code width, starting with the code immediately following the clear code. Packing order Since the codes emitted typically do not fall on byte boundaries, the encoder and decoder must agree on how codes are packed into bytes. The two common methods are LSB-first ("least significant bit first") and MSB-first ("most significant bit first"). In LSB-first packing, the first code is aligned so that the least significant bit of the code falls in the least significant bit of the first stream byte, and if the code has more than 8 bits, the high-order bits left over are aligned with the least significant bits of the next byte; further codes are packed with LSB going into the least significant bit not yet used in the current stream byte, proceeding into further bytes as necessary. MSB-first packing aligns the first code so that its most significant bit falls in the MSB of the first stream byte, with overflow aligned with the MSB of the next byte; further codes are written with MSB going into the most significant bit not yet used in the current stream byte. GIF files use LSB-first packing order. TIFF files and PDF files use MSB-first packing order. `, aaaaaa: `AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA`, abacadae: `ABACADAEAFAGAHAIAJAKALAMANAOAPAQARASATAUAVAWAXAYAZBCBDBEBFBGBHBIBJBKBLBMBNBOBPBQBRBSBTBUBVBWBXBYBZCDCECFCGCHCICJCKCLCMCNCOCPCQCRCSCTCUCVCWCXCYCZDEDFDGDHDIDJDKDLDMDNDODPDQDRDSDTDUDVDWDXDYDZEFEGEHEIEJEKELEMENEOEPEQERESETEUEVEWEXEYEZFGFHFIFJFKFLFMFNFOFPFQFRFSFTFUFVFWFXFYFZGHGIGJGKGLGMGNGOGPGQGRGSGTGUGVGWGXGYGZHIHJHKHLHMHNHOHPHQHRHSHTHUHVHWHXHYHZIJIKILIMINIOIPIQIRISITIUIVIWIXIYIZJKJLJMJNJOJPJQJRJSJTJUJVJWJXJYJZKLKMKNKOKPKQKRKSKTKUKVKWKXKYKZLMLNLOLPLQLRLSLTLULVLWLXLYLZMNMOMPMQMRMSMTMUMVMWMXMYMZNONPNQNRNSNTNUNVNWNXNYNZOPOQOROSOTOUOVOWOXOYOZPQPRPSPTPUPVPWPXPYPZQRQSQTQUQVQWQXQYQZRSRTRURVRWRXRYRZSTSUSVSWSXSYSZTUTVTWTXTYTZUVUWUXUYUZVWVXVYVZWXWYWZXYXZYZ0102030405060708090a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0A0B0C0D0E0F0G0H0I0J0K0L0M0N0O0P0Q0R0S0T0U0V0W0X0Y0Z12131415161718191a1b1c1d1e1f1g1h1i1j1k1l1m1n1o1p1q1r1s1t1u1v1w1x1y1z1A1B1C1D1E1F1G1H1I1J1K1L1M1N1O1P1Q1R1S1T1U1V1W1X1Y1Z232425262728292a2b2c2d2e2f2g2h2i2j2k2l2m2n2o2p2q2r2s2t2u2v2w2x2y2z2A2B2C2D2E2F2G2H2I2J2K2L2M2N2O2P2Q2R2S2T2U2V2W2X2Y2Z3435363738393a3b3c3d3e3f3g3h3i3j3k3l3m3n3o3p3q3r3s3t3u3v3w3x3y3z3A3B3C3D3E3F3G3H3I3J3K3L3M3N3O3P3Q3R3S3T3U3V3W3X3Y3Z45464748494a4b4c4d4e4f4g4h4i4j4k4l4m4n4o4p4q4r4s4t4u4v4w4x4y4z4A4B4C4D4E4F4G4H4I4J4K4L4M4N4O4P4Q4R4S4T4U4V4W4X4Y4Z565758595a5b5c5d5e5f5g5h5i5j5k5l5m5n5o5p5q5r5s5t5u5v5w5x5y5z5A5B5C5D5E5F5G5H5I5J5K5L5M5N5O5P5Q5R5S5T5U5V5W5X5Y5Z6768696a6b6c6d6e6f6g6h6i6j6k6l6m6n6o6p6q6r6s6t6u6v6w6x6y6z6A6B6C6D6E6F6G6H6I6J6K6L6M6N6O6P6Q6R6S6T6U6V6W6X6Y6Z78797a7b7c7d7e7f7g7h7i7j7k7l7m7n7o7p7q7r7s7t7u7v7w7x7y7z7A7B7C7D7E7F7G7H7I7J7K7L7M7N7O7P7Q7R7S7T7U7V7W7X7Y7Z898a8b8c8d8e8f8g8h8i8j8k8l8m8n8o8p8q8r8s8t8u8v8w8x8y8z8A8B8C8D8E8F8G8H8I8J8K8L8M8N8O8P8Q8R8S8T8U8V8W8X8Y8Z9a9b9c9d9e9f9g9h9i9j9k9l9m9n9o9p9q9r9s9t9u9v9w9x9y9z9A9B9C9D9E9F9G9H9I9J9K9L9M9N9O9P9Q9R9S9T9U9V9W9X9Y9ZabacadaeafagahaiajakalamanaoapaqarasatauavawaxayazaAaBaCaDaEaFaGaHaIaJaKaLaMaNaOaPaQaRaSaTaUaVaWaXaYaZbcbdbebfbgbhbibjbkblbmbnbobpbqbrbsbtbubvbwbxbybzbAbBbCbDbEbFbGbHbIbJbKbLbMbNbObPbQbRbSbTbUbVbWbXbYbZcdcecfcgchcicjckclcmcncocpcqcrcsctcucvcwcxcyczcAcBcCcDcEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUcVcWcXcYcZdedfdgdhdidjdkdldmdndodpdqdrdsdtdudvdwdxdydzdAdBdCdDdEdFdGdHdIdJdKdLdMdNdOdPdQdRdSdTdUdVdWdXdYdZefegeheiejekelemeneoepeqereseteuevewexeyezeAeBeCeDeEeFeGeHeIeJeKeLeMeNeOePeQeReSeTeUeVeWeXeYeZfgfhfifjfkflfmfnfofpfqfrfsftfufvfwfxfyfzfAfBfCfDfEfFfGfHfIfJfKfLfMfNfOfPfQfRfSfTfUfVfWfXfYfZghgigjgkglgmgngogpgqgrgsgtgugvgwgxgygzgAgBgCgDgEgFgGgHgIgJgKgLgMgNgOgPgQgRgSgTgUgVgWgXgYgZhihjhkhlhmhnhohphqhrhshthuhvhwhxhyhzhAhBhChDhEhFhGhHhIhJhKhLhMhNhOhPhQhRhShThUhVhWhXhYhZijikiliminioipiqirisitiuiviwixiyiziAiBiCiDiEiFiGiHiIiJiKiLiMiNiOiPiQiRiSiTiUiViWiXiYiZjkjljmjnjojpjqjrjsjtjujvjwjxjyjzjAjBjCjDjEjFjGjHjIjJjKjLjMjNjOjPjQjRjSjTjUjVjWjXjYjZklkmknkokpkqkrksktkukvkwkxkykzkAkBkCkDkEkFkGkHkIkJkKkLkMkNkOkPkQkRkSkTkUkVkWkXkYkZlmlnlolplqlrlsltlulvlwlxlylzlAlBlClDlElFlGlHlIlJlKlLlMlNlOlPlQlRlSlTlUlVlWlXlYlZmnmompmqmrmsmtmumvmwmxmymzmAmBmCmDmEmFmGmHmImJmKmLmMmNmOmPmQmRmSmTmUmVmWmXmYmZnonpnqnrnsntnunvnwnxnynznAnBnCnDnEnFnGnHnInJnKnLnMnNnOnPnQnRnSnTnUnVnWnXnYnZopoqorosotouovowoxoyozoAoBoCoDoEoFoGoHoIoJoKoLoMoNoOoPoQoRoSoToUoVoWoXoYoZpqprpsptpupvpwpxpypzpApBpCpDpEpFpGpHpIpJpKpLpMpNpOpPpQpRpSpTpUpVpWpXpYpZqrqsqtquqvqwqxqyqzqAqBqCqDqEqFqGqHqIqJqKqLqMqNqOqPqQqRqSqTqUqVqWqXqYqZrsrtrurvrwrxryrzrArBrCrDrErFrGrHrIrJrKrLrMrNrOrPrQrRrSrTrUrVrWrXrYrZstsusvswsxsyszsAsBsCsDsEsFsGsHsIsJsKsLsMsNsOsPsQsRsSsTsUsVsWsXsYsZtutvtwtxtytztAtBtCtDtEtFtGtHtItJtKtLtMtNtOtPtQtRtStTtUtVtWtXtYtZuvuwuxuyuzuAuBuCuDuEuFuGuHuIuJuKuLuMuNuOuPuQuRuSuTuUuVuWuXuYuZvwvxvyvzvAvBvCvDvEvFvGvHvIvJvKvLvMvNvOvPvQvRvSvTvUvVvWvXvYvZwxwywzwAwBwCwDwEwFwGwHwIwJwKwLwMwNwOwPwQwRwSwTwUwVwWwXwYwZxyxzxAxBxCxDxExFxGxHxIxJxKxLxMxNxOxPxQxRxSxTxUxVxWxXxYxZyzyAyByCyDyEyFyGyHyIyJyKyLyMyNyOyPyQyRySyTyUyVyWyXyYyZzAzBzCzDzEzFzGzHzIzJzKzLzMzNzOzPzQzRzSzTzUzVzWzXzYzZABACADAEAFAGAHAIAJAKALAMANAOAPAQARASATAUAVAWAXAYAZBCBDBEBFBGBHBIBJBKBLBMBNBOBPBQBRBSBTBUBVBWBXBYBZCDCECFCGCHCICJCKCLCMCNCOCPCQCRCSCTCUCVCWCXCYCZDEDFDGDHDIDJDKDLDMDNDODPDQDRDSDTDUDVDWDXDYDZEFEGEHEIEJEKELEMENEOEPEQERESETEUEVEWEXEYEZFGFHFIFJFKFLFMFNFOFPFQFRFSFTFUFVFWFXFYFZGHGIGJGKGLGMGNGOGPGQGRGSGTGUGVGWGXGYGZHIHJHKHLHMHNHOHPHQHRHSHTHUHVHWHXHYHZIJIKILIMINIOIPIQIRISITIUIVIWIXIYIZJKJLJMJNJOJPJQJRJSJTJUJVJWJXJYJZKLKMKNKOKPKQKRKSKTKUKVKWKXKYKZLMLNLOLPLQLRLSLTLULVLWLXLYLZMNMOMPMQMRMSMTMUMVMWMXMYMZNONPNQNRNSNTNUNVNWNXNYNZOPOQOROSOTOUOVOWOXOYOZPQPRPSPTPUPVPWPXPYPZQRQSQTQUQVQWQXQYQZRSRTRURVRWRXRYRZSTSUSVSWSXSYSZTUTVTWTXTYTZUVUWUXUYUZVWVXVYVZWXWYWZXYXZYZ`, }; }3a:[] 2f:{"title":"Average LZString Compression Dictionary Shape","cells":[{"id":0,"value":"md`# Average LZString Compression Dictionary Shape`","pinned":false,"hidden":false,"mode":"ojs"},{"id":484,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":317,"value":"viewof renderCirclePackedAndCollapsibleTree = checkbox({\n options: [\n { value: \"toggle\", label: \"Render circle packed and collapsible tree\" }\n ],\n value: \"\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":120,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":77,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":22,"value":"viewof input = textarea({\n title: \"You can insert your own text to compress below, or alternatively select a pre-defined text\",\n placeholder: \"Lorem ipsum...\", \n value: predeftxt[predefStrings],\n spellcheck: false,\n width: \"100%\",\n rows: 10,\n submit: \"Send to worker!\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":537,"value":"viewof predefStrings = {\n return html` `\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":334,"value":"viewof barChartOrder = {\n return html``\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":339,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":610,"value":"$35","pinned":true,"hidden":false,"mode":"ojs"},{"id":501,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":401,"value":"md`\nNodes that have no child nodes: ${((trieData.totalChildren[0]/trieData.totalNodes)*10000|0)/100}%\n\nNodes that have one child: ${((trieData.totalChildren[1]/trieData.totalNodes)*10000|0)/100}%\n\nNodes that have two children: ${((trieData.totalChildren[2]/trieData.totalNodes)*10000|0)/100}%\n\nNodes that have three children: ${((trieData.totalChildren[3]/trieData.totalNodes)*10000|0)/100}%\n\nNodes that have four children: ${((trieData.totalChildren[4]/trieData.totalNodes)*10000|0)/100}%\n\nNodes with five or more children: ${(((trieData.totalNodes - trieData.totalChildren[0] - trieData.totalChildren[1] - trieData.totalChildren[2] - trieData.totalChildren[3] - trieData.totalChildren[4])/trieData.totalNodes)*10000|0)/100}%\n\nCompression size of original: ${compressed_output.compressed.length} / ${input.length} or ${(compressed_output.compressed.length/input.length * 10000 | 0)/100}%`","pinned":false,"hidden":false,"mode":"ojs"},{"id":41,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":16,"value":"compressionWorker = {\n const worker = new Worker(LZScript); \n worker.onmessage = function(ev) {\n mutable compressed_output = ev.data;\n }\n\n return worker;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"mutable compressed_output = null;","pinned":false,"hidden":false,"mode":"ojs"},{"id":24,"value":"postMessageToWorker = {\n compressionWorker.postMessage(input);\n return html`/* A new message will be posted to the worker whenever input changes */`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":26,"value":"$38","pinned":false,"hidden":false,"mode":"ojs"},{"id":59,"value":"trieData = trieToChartData(compressed_output.trie)","pinned":false,"hidden":false,"mode":"ojs"},{"id":130,"value":"trieDepth = trieData.maxDepth","pinned":false,"hidden":false,"mode":"ojs"},{"id":217,"value":"data = trieData.data","pinned":false,"hidden":false,"mode":"ojs"},{"id":352,"value":"barChartData = {\n const labelWidth = (trieData.totalChildren.length + \"\").length\n return trieData.totalChildren.map((value, name) => {\n name = name + \"\";\n while(name.length < labelWidth) name = \"0\" + name;\n return {name, value};\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":607,"value":"percentBarChartData = {\n let total = 0;\n for (const { value } of barChartData) {\n total += value;\n }\n return barChartData.map(({ name, value }) => ({\n name,\n value: value / total\n }));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":491,"value":"rootCharsBarChartData = {\n return trieData.data.children.map(node => {\n let {name} = node;\n if (name === '\\n') name = '\\\\n';\n return {name, value: node.children.length};\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":544,"value":"$39","pinned":false,"hidden":false,"mode":"ojs"},{"id":171,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":331,"value":"SortableBarChart = html`

Sortable Bar Chart

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":345,"value":"{\n switch (barChartOrder) {\n case \"name-ascending\": \n barChartData.sort((a, b) => a.name.localeCompare(b.name));\n rootCharsBarChartData.sort((a, b) => a.name.localeCompare(b.name));\n break;\n case \"value-ascending\": \n barChartData.sort((a, b) => a.value - b.value);\n rootCharsBarChartData.sort((a, b) => a.value - b.value);\n break;\n case \"value-descending\": \n barChartData.sort((a, b) => b.value - a.value);\n rootCharsBarChartData.sort((a, b) => b.value - a.value);\n break;\n }\n sortableBarChart_x.domain(barChartData.map(d => d.name));\n sortableBarChart.update();\n sortableBarChartRootChars_x.domain(rootCharsBarChartData.map(d => d.name));\n sortableBarChartRootChars.update();\n return barChartOrder;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":340,"value":"sortableBarChart_x = d3.scaleBand()\n .domain(barChartData.map(d => d.name))\n .range([margin.left, width - margin.right])\n .padding(0.1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":507,"value":"sortableBarChartRootChars_x = d3.scaleBand()\n .domain(rootCharsBarChartData.map(d => d.name))\n .range([margin.left, width - margin.right])\n .padding(0.1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":98,"value":"CirclePacking = html`

Circle Packing

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":117,"value":"height = width","pinned":false,"hidden":false,"mode":"ojs"},{"id":115,"value":"pack = data => d3.pack()\n .size([width - 2, height - 2])\n .padding(3)\n (d3.hierarchy(data)\n .sum(d => d.value)\n .sort((a, b) => b.value - a.value))","pinned":false,"hidden":false,"mode":"ojs"},{"id":100,"value":"format = d3.format(\",d\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":102,"value":"color = d3.scaleSequential([trieDepth*2, 0], d3.interpolateMagma)\n//color = d3.scaleSequential([trieDepth*2, 0], d3.interpolateInferno)","pinned":false,"hidden":false,"mode":"ojs"},{"id":39,"value":"html`

Collapsible Tree

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":252,"value":"diagonal = d3.linkHorizontal().x(d => d.y).y(d => d.x)","pinned":false,"hidden":false,"mode":"ojs"},{"id":57,"value":"tree = d3.tree().nodeSize([dx, dy])","pinned":false,"hidden":false,"mode":"ojs"},{"id":257,"value":"dx = 10","pinned":false,"hidden":false,"mode":"ojs"},{"id":259,"value":"dy = width / trieDepth","pinned":false,"hidden":false,"mode":"ojs"},{"id":262,"value":"margin = ({top: 10, right: 120, bottom: 10, left: 40})","pinned":false,"hidden":false,"mode":"ojs"},{"id":166,"value":"html`

Other libraries

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"import {textarea, checkbox} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":49,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W3a","stdlib":"1","titling":"auto"}