31:T51e,# Building Intuition for Number Encodings using Trees *Disclaimer: in the notebook I'm going to assume that we are all reasonable comfortable with bits, bytes and counting in binary. Basically, a sentence like the following should make sense to you, ideally feel obvious even: "if we want to store an integer that can have any value between zero and fifteen (inclusive), then we need at least four bits". I* ***am*** *working on a notebook to explain binary numbers intuitively too, but it's not ready for publishing yet. I will update this notebook when it is.* When I wrote [my notebook on phase-in codes](https://observablehq.com/@jobleonard/phase-in-codes) a few years ago I was struggling to find a way to intuitively explain how they work. It felt like there was an elegant, obvious visual representation struggling to get out of the maths. Recently I was looking at [Huffman coding](https://en.wikipedia.org/wiki/Huffman_coding) again and it suddenly dawned on me that phase-in codes could also be represented as as binary trees, and probably even considered to be a special case of Huffman codes for uniform distribution. The main idea is that we start with our normal set of bit strings to encode numbers in the way that we are familiar with. Take that _"zero to fifteen"_ range I mentioned before:32:T511,As you can see by comparing the images this is really just a different way of interpreting our string of four bits, right? For example, six is `0110` in four-bit binary, but can also be interpreted as walking down a binary tree via nodes `0`, `1`, `1`, and `0`. The tree is sorted so that each tree walk results in the bit string we would get when converting a number to binary digits. However, **this does not have to be the case! We could have assigned any value to any of these bit strings.** (this is a key insight needed to make sense of the rest of the notebook so I'm bolding it) Now to give a quick refresher for phase-in codes. The tree above shows that given `n` bits, we can encode 2ⁿ values. However, what if our range of values is not a power of two? Suppose we know we only want to encode numbers from zero to sixteen, so seventeen values in total. The naive way to do so would be to encode each value using five bits. But that means we're "wasting" unused bit combinations from `10001` to `11111`. We could encode numbers seventeen to thirty-one (fifteen more values). We only need those five bits because the value of sixteen needs five bits to encode; all other used values would have "fit" in four bits. When displayed as a binary tree the waste becomes very visible:33:T51d,If we have a tree encoding a number of values, and wish to encode an extra value in our tree, then we can just: 1. take one of the leaves 2. attach two nodes to it 3. associate the original value of the former leaf with one of the new leaves 4. associate the new value with the other So for each value we wish to add we have to split one leaf into a node with two children. In this example we took the leaf for fifteen (`1111`), gave it two children (`11110` and `11111`), and assigned the values of fifteen and sixteen to those new leaves. This means we need five bits to encode the numbers fifteen and sixteen, but everything else can keep using four bits. If each number occurs equally often that means we'd use 4.12 bits on average. Not bad! The resulting bit strings for fifteen and sixteen no longer represent what we would get from a digit-to-binary conversion (`0b11110` is normally thirty, and `0b11111` is usually interpreted as thirty-one). Instead they purely represent the result of walking down this binary tree, and as mentioned we could assign any value to any leaf node. However, there is a pattern to how we pick our nodes to "split" and assign values to leaves that I will explain later. Here's another way of looking at the tree, where we flatten it to only show the bottom two layers:34:T64e,If you look closely you might already see a couple of patterns. First, for each value we wish to add we have to split one leaf into a node with two children (as explained before). If you think about that for a minute that probably becomes kind of obvious: we remove one value to add two, there's no way around that. With that in mind we can can come up with a formula for the number of "extra" nodes needed when the total values do not match an integer power of two. We start with a bitstring of a given length and how many different values it can encode (in our example, four bits can encode sixteen values). A bitstring with one more bit can encode twice as many (e.g. five bits can encode thirty-two values). For every extra value we wish to encode between those two ranges, we need to extend one of the bit strings of the lower range. In other words: the number of "split nodes" must be `total values - closest power of two equal or less than total values`. Let's work through an example. We want to encode zero to nineteen, so twenty values in total. The closest less or equal power of two is sixteen. Therefore, we need to extend four leaves, resulting in twelve bitstrings of length four, and eight bitstrings of length five. We could pick the leaves to split at random, at any level even. However, for phase-in codes we always pick the largest value of the second-lowest layer. As a consequence, for the "high" values we are always counting backwards from a bit string of all ones. You can check this in the examples above, but it's probably more easily visible when you can change the values yourself:35:T6f9,This ordering doesn't just look tidy, it has other benefits too. If we split leaves at random we cannot predict which bit-string has which value without first being told what the entire tree looks like, taking up extra bits. On top of that, to read out a number we would have to walk the tree one bit at a time, which is rather slow. However, with the above ordering all we need is to know is how many total values there are in total to determine which values need `n` bits, and which (if any) need `n+1`. It also lets us skip walking a tree one bit at a time, considerably speeding up the encoding/decoding of the bit strings (especially if we have many values). For example, say we know we encode values between zero and nineteen. We can start with reading out four bits at once and check if the resulting value less than `0b1100` (12). If so we're done reading out this number and can move on to the next. Otherwise we read one more bit and append it, resulting in a value between 24 and 31 (`0b11000` and `0b11111`). Then we just have to subtract twelve to get our final number. This is a lot faster than walking through four to five tree nodes while reading one bit at every step. Now we just need a quick way to determine the closest power of two equal or less than the total number of values. Together with those total values that lets us determine "threshold" value after which we change from using `n` to `n+1` bits. For that we need to use a logarithm, or more precisely a floored log2 function. We can actually efficiently approximate that with [`Math.clz32()`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/clz32), which is my candidate for "least used/known JavaScript function ever". (be honest, had you ever heard of it before?)36:T4bf,// Note: this function coverts the phase- // encoded bits to a string of 1 and 0 // characters, which works for demonstration // purposes but obviously is a very inefficient // way of actually storing data. // A real-world application of phase-in codes // would place actual bits into a stream of // bytes of some sort. function toBitString(value, totalValues) { // First we have to find the number of bits // required to fit totalValues. This tells // us the power of two bigger or equal to // totalValues. Also, I bet you've never seen // Math.clz32() in JavaScript before, have // you? It returns the number of leading zero // bits in the 32-bit binary representation // of a number. Yes, we could also use // Math.ceil(Math.log2(totalValues-1)), // but where's the fun in that?) let length = 32 - Math.clz32(totalValues - 1); const nextPow2 = (1 << length) >>> 0; // Once we have this power of two we can // determine the treshold value. Values // below it will require one bit less. const treshold = nextPow2 - totalValues; let returnString = ""; if (value < treshold) { length--; } else { value += treshold; } return value.toString(2).padStart(length, "0"); }37:T4aa,So there you have it, an intuitive explanation of phase-in codes! (at least I hope it feels somewhat intuitive now) The next question is: where would you use them? Well, where do you use bit-streams? In compression contexts! If you're trying to compress data but for some reason Huffman codes or other more sophisticated entropy codes are too much hassle, phase-in codes can be a relatively cheap way to squeeze out a few extra percentages of compression. Oh, and here's a bonus compression tip: if you know your data is biased to one side of the value range, make that side the one that uses the shortest bit-strings! So if your values are biased towards the high end, encode them "counting backwards". For example, LZ78-based compression schemes are biased to use newer dictionary entries over old ones, and newer dictionary entries have higher values. To get the most out of phase-in codes when encoding LZ78 dictionary tokens in a bit-stream, encode the newest dictionary value as zero, going up as you count backwards to the first dictionary entry. In my experiments this added a few extra percentages of compression on top of the extra percentages that phase-in codes themselves added.38:T568,

## Let's try to build intuition for other encodings using these trees! Now that we have this "binary tree walk" approach to interpreting bit strings, we can ask ourselves how that translates to other approaches to writing down numbers. I don't know yet if it helps build intuition or insight in how they work, but it doesn't hurt to try, right? ### Unary Coding Let's start with an easy encoding scheme: 1. start a count at zero 2. read a bit - if the bit is one, increase the count by one and repeat step 2. - if the bit is zero, stop. | bit string | alternative coding | value | | --- | --- | --- | | `0` | `1` | zero | | `10` | `01` | one | | `110` | `001` | two | | `1110` | `0001` | three | This is [unary coding](https://en.wikipedia.org/wiki/Unary_coding), one of the simplest variable length encodings one could imagine (arguably the simplest, since it is essentially the bit-version of the [unary numeral system](https://en.wikipedia.org/wiki/Unary_numeral_system)). Here "variable length" means "we don't know how high our numbers go, so that information has to be encoded in the bit string too." As you can see in the table, we can also flip the zero and one bit. Both work, as long as both reader and writer know which is the "count one more" bit and which is the "stop" bit. Lets look at a tree-representation of zero-terminated unary counting of ones:39:T4df,What the tree makes really obvious is that the number of bits grows linearly with the number written down. As an encoding scheme it is very inefficient, especially when compared to positional notation (the way we normally write down numbers). There the number of bits or digits grows logarithmically in response to the total values. ### LZ4-style variable integer encoding Let's try a different encoding scheme. The [LZ4 compression algorithm](https://lz4.github.io/lz4/) uses a simple method of storing variable-length numbers. For the sake of keeping our tree easy to interpret I will simplify it even more to the following: 1. start with a count of zero 2. read one byte and add its value (interpreted as unsigned 8-bit integer) to the count 3. while the byte value is 255, go to 2 *(LZ4 varint encoding starts with 4 bits (a nibble) instead of a byte, encoding a value between zero and fifteen, and only when that nibble is "saturated" (has the value fifteen) do we start looking at the following byte and use the procedure above)* When compared to unary coding we can see that we basically swapped out a byte for a bit. Instead of a binary tree it's a 256-way tree. Nodes 0-254 will all be leaves, node 255 moves one step down the tree:3a:T621,Apologies if the bit strings are getting difficult to read, but there is a reason I have chosen to stick to binary numbers: this way the number of characters directly represents the number of bits used. This hopefully gives more of an intuitive feeling how much space is used. On top of that comparisons between the various tree representations here would be more misleading if we switched to something compact, like hexadecimal numbers. So LZ4-style encoding is essentially the same as unary encoding, except that it uses a byte instead of a bit. Instead of base two, it is base 256 (I will refer to it as "radix 256" encoding or R256 from now on. I use "radix" instead of "base" to avoid confusion with binary-to-text encodings like [base 64](https://en.wikipedia.org/wiki/Base64)). R256 turns out to be easier to implement than unary encoding. Reading whole bytes is less work than reading out individual bits at varying offsets. Also, if you expect your values to be less than 255 most of the time (which is often true for the data LZ4 compresses) then you will not spend much time reading out bytes. For LZ4 this is a worthwhile trade-off, as is focused on being a really fast compression algorithm. Both unary and R256 grow linearly with the size of the quantity written down. This may not be immediately obvious with R256, but think about it: for every 256 values, it requires 8 extra bits. It would be nice if we didn't have to give up the logarithmic growth that we're used to with positional notations, so let's look at encodings that maintain that quality.3b:Tac4,### Elias Gamma Coding [Elias gamma coding](https://en.wikipedia.org/wiki/Elias_gamma_coding) is one of the simpler number encoding schemes invented by [Peter Elias](https://en.wikipedia.org/wiki/Peter_Elias). It solves the following problem: say we want to use variable length positional notation to write down numbers, but we do not know maximum size of our numbers. Therefore we cannot set a fixed number of bits beforehand. How to encode each individual number? Well, once we know the number we wish to write down, we *do* actually know how many bits it would take (e.g. five would be `0b101`, so three bits, thirty-seven would be `0b100101` so six bits). So what we can do is use the unary coding from above to first encode that number of bits (from now on: `nbits`), and then encode the actual number. That way the reader can always decipher how many bits to read. One clever trick Elias added was realizing that the first bit of a number is always one (you can verify this using the *"plain bit string"* column in the table below). At the same time, when using a one-terminated unary encoding to write down a number, that code¹ always *ends* with a one . So what we can do is "reuse" that bit and only write down the bits that come after the first "one". *¹ "code" here doesn't refer to computer code but to the number written down as a bit string, as in an "encoded value"* | Value

| As plain bit string

| Nr of bits

| Nr of bits,
unary encoded
(1-terminated) | Gamma coding
(space added
for readability)
| | --- | --- | --- | --- | --- | | one | `1` | one | `1` | `1` | | two | `10` | two | `01` | `0 1 0` | | three | `11` | two | `01` | `0 1 1` | | four | `100` | three | `001` | ` 00 1 00` | | five | `101` | three | `001` | ` 00 1 01` | | six | `110` | three | `001` | ` 00 1 10` | | seven | `111` | three | `001` | ` 00 1 11` | | eight | `1000` | four | `0001` | `000 1 000` | | nine | `1001` | four | `0001` | `000 1 001` | | … | … | … | … | … | | fifteen | `1111` | four | `0001` | `000 1 111` | | sixteen | `10000` | five | `00001` | `0000 1 0000` | What is really neat about this encoding is that the binary representation of a number reads just like it normally does, except with some padding of zero-bits in front of it. To decode a number we don't need any complicated calculations: just read one bit at a time, determining `nbits` by counting the number of zeroes before we hit a one, then read that number of bits and append them behind this one. To encode a number we just have to use our earlier log2 or `Math.clz32()` tricks to find `nbits`, subtract one, and padd the number with that many zeroes in front. So what does this look like in tree representation?3c:T98d,Compare this tree to the trees of unary and R256 coding, where the bit string length grows linearly. The bit string of gamma coding grows logarithmically, and we can see this in the tree: with every next layer of depth we double the number of leaf nodes, and the leaf nodes use one more bit to encode a value. The total number of bits used is twice the number of bits needed for normal binary notation, minus one (because of that overlapping one-bit trick mentioned earlier). ### Elias Delta Coding Gamma coding uses unary encoding for the `nbits` value, followed by positional notation for the actual number. You might be thinking: can't we find a way to write down `nbits` with positional notation too, so it also grows logarithmically instead of linearly? Well… sort of: the only way to write down `nbits` with positional notation requires encoding how many bits `nbits` needs. How else would the decoder know how many bits to read out? Assuming variable `nbits` size our only other method for that is unary notation again. Wait a minute… that's just using gamma coding for the `nbits` number! Congratulations, we have just (almost) rediscovered [Elias delta coding](https://en.wikipedia.org/wiki/Elias_delta_coding): | Value

| As plain bit string

| Nr of bits

| Nr of bits,
gamma encoded | Delta coding

| --- | --- | --- | --- | --- | | one | `1` | one | `1` | `1` | | two | `10` | two | `0 1 0` | `0 1 0 0` | | three | `11` | two | `0 1 0` | `0 1 0 1` | | four | `100` | three | ` 0 1 1` | `0 1 1 00` | | five | `101` | three | ` 0 1 1` | `0 1 1 01` | | six | `110` | three | ` 0 1 1` | `0 1 1 10` | | seven | `111` | three | ` 0 1 1` | `0 1 1 11` | | eight | `1000` | four | `00 1 00` | `00 1 00 000` | | nine | `1001` | four | `00 1 00` | `00 1 00 001` | | … | … | … | … | … | | fifteen | `1111` | four | `00 1 00` | `00 1 00 111` | | sixteen | `10000` | five | `00 1 01` | `00 1 01 0000` | Why almost? Because there is one extra trick: since we know how many numbers we are encoding we can drop the leading bit for the final number again. So e.g. nine, or `1001`, becomes "four bits in gamma coding", so `00100`, followed by the binary encoding for nine (`1001`) without the first bit, so `001`. resulting in `00100001` as the final bit string. Delta coding is a more complicated encoding than gamma coding, and it shows when trying to represent it as a tree:3d:T56d,Tree( {name: "", children: [ {name: "0", children: [ {name: "0", children: [ {name: "0", children: [{name: "…"}]}, {name: "1", children: [ {name: "00", children: [ {name: "000 (00100000, 8)"}, {name: "001 (00100001, 9)"}, {name: "…"}, {name: "111 (00100111, 15)"}, ]}, {name: "01", children: [ {name: "0000 (001010000, 16)"}, {name: "…"}, {name: "1111 (001011111, 31)"}, ]}, {name: "10", children: [ {name: "00000 (0011000000, 32)"}, {name: "…"}, {name: "11111 (0011011111, 63)"} ]}, {name: "11", children: [ {name: "000000 (00111000000, 64)"}, {name: "…"}, {name: "000000 (00111111111, 127)"} ]} ]} ]}, {name: "1", children: [ {name: "0", children: [ {name: "0 (0100, 2)"}, {name: "1 (0101, 3)"} ]}, {name: "1", children: [ {name: "00 (01100, 4)"}, {name: "01 (01101, 5)"}, {name: "10 (01110, 6)"}, {name: "11 (01111, 7)"}, ]} ]} ]}, {name: "1 (1, 1)"} ]}, { label: d => d.name, title: (d, n) => `${n.ancestors().reverse().map(d => d.data.name).join("")}`, // hover text } )3e:Tda6,I won't lie, I'm also struggling with deciphering the delta coding tree. It gets a bit easier if we compare it to the gamma coding one. We can see the leaves of that tree have been replaced with nodes, each of which have children that are now the actual leaves of the tree. Which makes sense: instead of two steps like gamma codes, delta codes use three steps. The part of the string that encodes `nbits` now grows logarithmically instead of linearly, so the length of the bitstring should grow more slowly again. Having said that, you might have noticed delta coding actually uses more bits than gamma coding for small numbers. That is because unary codes use fewer bits than gamma coding for small numbers, even though the latter grows logarithmically: | Value | Unary Coding (one-terminated) | Gamma Coding | | --- | --- | --- | | one | `1` | `1` | | two | `01` | `0 1 0` | | three | `001` | `0 1 1` | | four | `0001` | `00 1 00` | | five | `0000 1` | `00 1 01` | | six | `0000 01` | `00 1 10` | | seven | `0000 001` | `00 1 11` | | eight | `0000 0001` | `000 1 000` | For the numbers one, two and four unary encoding uses one bit less. For three and five it's a tie. From values of six or higher gamma coding is the winner. What that means for delta coding is that it ties with gamma coding for values of sixteen to sixty-three, and only requires fewer bits once it encodes values of sixty-four or higher.

Click here if you are curious how far this rabbit hole goes.

The next step would be to use delta coding to write down the number of bits required to write down a number, but as mentioned delta coding is more efficient only once the encoded value is sixty-four or more. So you can probably guess that the next "level" would require even bigger numbers before it becomes more efficient.

If unary codes are "level one", gamma coding is "level two" and delta coding "level three", then this (unnamed) "level four" code would only be more efficient than delta coding if the value of `nbits` is sixty-four or more. So this code would only be useful if we don't know ahead of times how big our integers will be, but they *probably* need more than sixty-four bits to write down.

"Level five" would only be more efficient if `nbits` is so large that we'd need sixty-four or more bits to write it down. This would imply we are dealing with a number of such mindbogglingly huge proportions that it needs more than sixteen exbibytes of storage just to write it down. What is an exbibyte? [See this wikipedia page](https://en.wikipedia.org/wiki/Byte#Multiple-byte_units). For context, as of writing we are in [the zettabyte era](https://en.wikipedia.org/wiki/Zettabyte_Era). Suffice to say that it is very unlikely anyone would ever have the need to write down an integer number that big with precision all the way to the last digit, let alone multiple variable integers, *let alone* integers expected to be around size while also having *unknown maximum* size. This is not a practical code under any realistic circumstance.

Having said that, Peter Elias did come up with a way to encode an *arbitrary* number of levels, which is known as [Elias omega encoding](https://en.wikipedia.org/wiki/Elias_omega_coding). I suppose it's theoretically more efficient than delta coding for ridiculously huge numbers, but at this point we are in the domain of mathematical curiosities than actually useful encoding schemes.

3f:T50a,function phaseInData(totalValues, collapse, start) { const root = { name: "", children: [] }; const maxBits = 32 - Math.clz32(totalValues + 1); const minBits = (Math.log2(totalValues + 1) | 0 ); const isPow2 = Math.log2(totalValues+1) === minBits; if (start > 0) root.children.push({ name: "…", children: [] }); for (let i = start; i <= totalValues; i++) { const bitString = toBitString(i, totalValues+1); // Yes this is disgusting, sorry. const labels = collapse ? bitString.length === maxBits ? [bitString.substring(0, bitString.length-1), bitString[bitString.length-1]] : [bitString] : bitString.split(""); let node = root; for (let j = 0; j < labels.length; j++) { const lbl = labels[j]; let _node; if (_node = node.children.find(({name}) => lbl === name)) { } else { let name = lbl; if (j === labels.length - 1) { name += " ("; if (!collapse || collapse && j === 1) name += bitString + " - "; name += i + ")"; } _node = { name, children: [] }; if (lbl === "0") node.children.unshift(_node); else node.children.push(_node); } node = _node; } } return root; }40:T4a2,function binaryData(totalValues, collapse, start) { const root = { name: "", children: [] }; const maxBits = 32 - Math.clz32(totalValues + 1); const minBits = (Math.log2(totalValues + 1) | 0 ); const isPow2 = Math.log2(totalValues+1) === minBits; if (start > 0) root.children.push({ name: "…", children: [] }); for (let i = start; i <= totalValues; i++) { const bitString = i.toString(2).padStart(maxBits, "0"); // Yes this is disgusting, sorry. const labels = collapse ? [bitString] : bitString.split(""); let node = root; for (let j = 0; j < labels.length; j++) { const lbl = labels[j]; let _node; if (_node = node.children.find(({name}) => lbl === name)) { } else { let name = lbl; if (j === labels.length - 1) { name += " ("; if (!collapse || collapse && j === 1) name += bitString + " - "; name += i + ")"; } _node = { name, children: [] }; if (lbl === "0") node.children.unshift(_node); else node.children.push(_node); } node = _node; } } return root; }41:T46d,function r256Chart (maxDepth) { const makeChildren = (depth = 0) => ([ {name: `${(0).toString(2).padStart(8, "0")} (${(0).toString(2).padStart(8, "0").padStart((depth+1)*8, "1")}, ${depth*256})`}, {name: `${(1).toString(2).padStart(8, "0")} (${(1).toString(2).padStart(8, "0").padStart((depth+1)*8, "1")}, ${depth*256 + 1})`}, {name: `${(2).toString(2).padStart(8, "0")} (${(2).toString(2).padStart(8, "0").padStart((depth+1)*8, "1")}, ${depth*256 + 2})`}, {name: "…"}, {name: `${(253).toString(2).padStart(8, "0")} (${(253).toString(2).padStart(8, "0").padStart((depth+1)*8, "1")}, ${depth*256 + 253})`}, {name: `${(254).toString(2).padStart(8, "0")} (${(254).toString(2).padStart(8, "0").padStart((depth+1)*8, "1")}, ${depth*256 + 254})`}, { name: `11111111`, children: depth === maxDepth ? [{name: "…"}] : makeChildren(depth+1) } ]); return Tree({ name: "", children: makeChildren(0) }, { label: d => d.name, title: (d, n) => `${n.ancestors().reverse().map(d => d.data.name).join("")}`, // hover text width: maxDepth * 800 }) }42:T1091,// import {Tree} from "@d3/tree" // Had to copy the code because I needed the labels to always be on the right. // It's just a minimal change but oh well. // Copyright 2021 Observable, Inc. // Released under the ISC license. // https://observablehq.com/@d3/tree function Tree(data, { // data is either tabular (array of objects) or hierarchy (nested objects) path, // as an alternative to id and parentId, returns an array identifier, imputing internal nodes id = Array.isArray(data) ? d => d.id : null, // if tabular data, given a d in data, returns a unique identifier (string) parentId = Array.isArray(data) ? d => d.parentId : null, // if tabular data, given a node d, returns its parent’s identifier children, // if hierarchical data, given a d in data, returns its children tree = d3.tree, // layout algorithm (typically d3.tree or d3.cluster) sort, // how to sort nodes prior to layout (e.g., (a, b) => d3.descending(a.height, b.height)) label, // given a node d, returns the display name title, // given a node d, returns its hover text link, // given a node d, its link (if any) linkTarget = "_blank", // the target attribute for links (if any) width = 640, // outer width, in pixels height, // outer height, in pixels r = 3, // radius of nodes padding = 1, // horizontal padding for first and last column fill = "#999", // fill for nodes fillOpacity, // fill opacity for nodes stroke = "#555", // stroke for links strokeWidth = 1.5, // stroke width for links strokeOpacity = 0.4, // stroke opacity for links strokeLinejoin, // stroke line join for links strokeLinecap, // stroke line cap for links halo = "#fff", // color of label halo haloWidth = 3, // padding around the labels dx = 16 } = {}) { // If id and parentId options are specified, or the path option, use d3.stratify // to convert tabular data to a hierarchy; otherwise we assume that the data is // specified as an object {children} with nested objects (a.k.a. the “flare.json” // format), and use d3.hierarchy. const root = path != null ? d3.stratify().path(path)(data) : id != null || parentId != null ? d3.stratify().id(id).parentId(parentId)(data) : d3.hierarchy(data, children); // Sort the nodes. if (sort != null) root.sort(sort); // Compute labels and titles. const descendants = root.descendants(); const L = label == null ? null : descendants.map(d => label(d.data, d)); // Compute the layout. const dy = width * 0.8 / (root.height + padding) | 0; tree().nodeSize([dx, dy])(root); // Center the tree. let x0 = Infinity; let x1 = -x0; root.each(d => { if (d.x > x1) x1 = d.x; if (d.x < x0) x0 = d.x; }); // Compute the default height. if (height === undefined) height = x1 - x0 + dx * 2; const svg = d3.create("svg") .attr("viewBox", [-dy * padding / 2, x0 - dx, width, height]) .attr("width", width) .attr("height", height) .attr("style", "max-width: 100%; height: auto; height: intrinsic;") .attr("font-family", "sans-serif") .attr("font-size", 10); svg.append("g") .attr("fill", "none") .attr("stroke", stroke) .attr("stroke-opacity", strokeOpacity) .attr("stroke-linecap", strokeLinecap) .attr("stroke-linejoin", strokeLinejoin) .attr("stroke-width", strokeWidth) .selectAll("path") .data(root.links()) .join("path") .attr("d", d3.linkHorizontal() .x(d => d.y) .y(d => d.x)); const node = svg.append("g") .selectAll("a") .data(root.descendants()) .join("a") .attr("xlink:href", link == null ? null : d => link(d.data, d)) .attr("target", link == null ? null : linkTarget) .attr("transform", d => `translate(${d.y},${d.x})`); node.append("circle") .attr("fill", d => d.children ? stroke : fill) .attr("r", r); if (title != null) node.append("title") .text(d => title(d.data, d)); if (L) node.append("text") .attr("dy", "0.32em") .attr("x", 6) .attr("text-anchor", "start") .attr("paint-order", "stroke") .attr("stroke", halo) .attr("stroke-width", haloWidth) .text((d, i) => L[i]); return svg.node(); }43:[] 2f:{"title":"Building Intuition for Number Encodings using Trees","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":212,"value":"binaryPhaseInChart(15, true)","pinned":false,"hidden":false,"mode":"ojs"},{"id":217,"value":"What we do now is split each bit of the bit string into a separate node and create a binary tree to walk down:","pinned":false,"hidden":false,"mode":"md"},{"id":224,"value":"binaryPhaseInChart(15, false)","pinned":false,"hidden":false,"mode":"ojs"},{"id":227,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":1125,"value":"binaryChart(16)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1130,"value":"It would be nice if we could somehow only use as many bits as strictly necessary. At first glance that appears impossible from the perspective of *reading* from the bit-stream: if the next five bits are `10000`, how would we distinguish a sixteen (`10000`) from an eight followed by a number that starts with a zero-bit? (`1000`, `0`)\n\nHowever, if we look at bit strings in terms of walking down a tree, again **giving ourselves the freedom to assign any value to a resulting bit string**, then we can see that there is a trick we could use:","pinned":false,"hidden":false,"mode":"md"},{"id":235,"value":"binaryPhaseInChart(16, false)","pinned":false,"hidden":false,"mode":"ojs"},{"id":248,"value":"$33","pinned":false,"hidden":false,"mode":"md"},{"id":245,"value":"binaryPhaseInChart(16, true)","pinned":false,"hidden":false,"mode":"ojs"},{"id":254,"value":"Now let's move on to the splitting strategy. I will show the result first for the trees for zero to seventeen, eighteen and nineteen respectively to get an intuitive feeling for the final behavior:","pinned":false,"hidden":false,"mode":"md"},{"id":256,"value":"binaryPhaseInChart(17, true, 11)","pinned":false,"hidden":false,"mode":"ojs"},{"id":259,"value":"binaryPhaseInChart(18, true, 11)","pinned":false,"hidden":false,"mode":"ojs"},{"id":274,"value":"binaryPhaseInChart(19, true, 11)","pinned":false,"hidden":false,"mode":"ojs"},{"id":271,"value":"$34","pinned":false,"hidden":false,"mode":"md"},{"id":11,"value":"viewof totalValues = Inputs.range([1, 63], {value: 19, step: 1, label: \"Encode integers from zero to… (inclusive)\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":126,"value":"viewof collapse = Inputs.toggle({value: true, label: \"Flatten tree\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":206,"value":"binaryPhaseInChart(totalValues, collapse)","pinned":false,"hidden":false,"mode":"ojs"},{"id":311,"value":"$35","pinned":false,"hidden":false,"mode":"md"},{"id":322,"value":"$36","pinned":true,"hidden":false,"mode":"ojs"},{"id":320,"value":"function fromBitString(str, totalValues) {\n // I'm slightly abusing binary literal\n // type coercion here, but this is\n // not production code anyway.\n const value = +(\"0b\"+str);\n const length = 32 - Math.clz32(totalValues-1);\n const nextPow2 = (1<>> 0;\n\n const treshold = nextPow2 - totalValues;\n return value < treshold ? value : (value - treshold) >>> 0;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":958,"value":"$37","pinned":false,"hidden":false,"mode":"md"},{"id":408,"value":"$38","pinned":false,"hidden":false,"mode":"md"},{"id":431,"value":"unaryChart(10)","pinned":false,"hidden":false,"mode":"ojs"},{"id":466,"value":"$39","pinned":false,"hidden":false,"mode":"md"},{"id":481,"value":"r256Chart(1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":549,"value":"$3a","pinned":false,"hidden":false,"mode":"md"},{"id":554,"value":"$3b","pinned":false,"hidden":false,"mode":"md"},{"id":630,"value":"Tree(\n {name: \"\", children: [\n {name: \"0\", children: [\n {name: \"0\", children: [\n {name: \"0\", children: [\n {name: \"0\", children: [{name: \"…\"}]},\n {name: \"1\", children: [\n {name: \"000 (0001000, 8)\"},\n {name: \"001 (0001001, 9)\"},\n {name: \"010 (0001010, 10)\"},\n {name: \"011 (0001011, 11)\"},\n {name: \"100 (0001100, 12)\"},\n {name: \"101 (0001101, 13)\"},\n {name: \"110 (0001110, 14)\"},\n {name: \"111 (0001111, 15)\"}\n ]}\n ]},\n {name: \"1\", children: [\n {name: \"00 (00100, 4)\"},\n {name: \"01 (00101, 5)\"},\n {name: \"10 (00110, 6)\"},\n {name: \"11 (00111, 7)\"} \n ]}\n ]},\n {name: \"1\", children: [\n {name: \"0 (010, 2)\"},\n {name: \"1 (011, 3)\"}\n ]}\n ]},\n {name: \"1 (1, 1)\"}\n ]},\n {\n label: d => d.name,\n title: (d, n) => `${n.ancestors().reverse().map(d => d.data.name).join(\"\")}`, // hover text\n }\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":705,"value":"$3c","pinned":false,"hidden":false,"mode":"md"},{"id":847,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs"},{"id":838,"value":"$3e","pinned":false,"hidden":false,"mode":"md"},{"id":740,"value":"**`TODO: LEB128 as well as prefix-based varint and zigzag encoding`**","pinned":false,"hidden":false,"mode":"md"},{"id":926,"value":"### LEB128\n\nLEB128 (see also the [wikipedia](https://en.wikipedia.org/wiki/LEB128))","pinned":false,"hidden":false,"mode":"md"},{"id":326,"value":"

\n\n## Other Code","pinned":false,"hidden":false,"mode":"md"},{"id":427,"value":"function unaryChart (totalValues) {\n const makeChildren = (depth = 0) => [\n {name: `0 (${\"\".padEnd(depth, \"1\")}0, ${depth})`, children: []},\n depth < totalValues ? {\n name: \"1\",\n children: makeChildren(depth+1)\n } : {\n name: \"…\",\n children: []\n }\n ];\n\n const tvlog2 = (Math.log2(totalValues)+1);\n return Tree({\n name: \"\",\n children: makeChildren(0, totalValues)\n }, {\n label: d => d.name,\n title: (d, n) => `${n.ancestors().reverse().map(d => d.data.name).join(\"\")}`, // hover text\n dx: 40\n })\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":84,"value":"function binaryPhaseInChart(totalValues, collapse, start = 0) {\n return Tree(phaseInData(totalValues, collapse, start), {\n label: d => d.name,\n title: (d, n) => `${n.ancestors().reverse().map(d => d.data.name).join(\"\")}`, // hover text\n dx: 14\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":25,"value":"$3f","pinned":true,"hidden":false,"mode":"ojs"},{"id":1121,"value":"function binaryChart(totalValues, collapse, start = 0) {\n \n return Tree(binaryData(totalValues, collapse, start), {\n label: d => d.name,\n title: (d, n) => `${n.ancestors().reverse().map(d => d.data.name).join(\"\")}`, // hover text\n dx: 14\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1115,"value":"$40","pinned":true,"hidden":false,"mode":"ojs"},{"id":474,"value":"$41","pinned":true,"hidden":false,"mode":"ojs"},{"id":7,"value":"$42","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W43","stdlib":"1","titling":"auto"}