29:null 2a:["$","title",null,{"children":"Basic compression methods: reducing the alphabet | Job van der Zwan | Observable"}] 2f:T84f,And that confirms that our compression method is reversible. Of course, the way it is implemented is not practical for general usage in the slightest, as it requires a division of a gigantic number at each step. For large data input this number would quickly become prohibitively expensive in memory and computation overhead. But it is a basic conceptual building block - there are ways to avoid having to apply multiplication and division over the entire integer. Some are even fast enough to use in practical data compressors, like the methods based on Jarosław Duda's [asymmetric numeral systems](https://en.wikipedia.org/wiki/Asymmetric_numeral_systems). ## Encoding the string of unique characters One thing I skipped was that to decompress our compressed paragraph, the decompressor also needs to know which unique characters it contains. The most straightforward method would be to first encode a byte with the total number of characters, followed by the literal string, resulting in 1 + ${firstParagraphChars.length} extra bytes. But there is a slightly more clever way (which is the actual motivation for me to write this notebook actually, because I came up with it myself and wanted to share it). First, let's simplify things a bit and only look at the alphabet of unique bytes (so we forget about UTF-8 for a moment, other than that it will provide us with the stream of bytes). Now note that by definition each character in our alphabet string appears only once. So after our first character has been sent over, there are only 256 - 1 = 255 possible values left. After the second character there are only 254 possibilities left. Then 253, and so on. But that means that we should (in principle) be able to use less bits per character to encode IT, doesn't it? We just have to use our big integer trick again. Well... except now the base varies per character encoded. And the mapping has to be updated too. And we have to make sure that the whole process is reversible despite these two changes. But other than all of those overlapping constraints and the complications that follow from it, it's easy, I swear!30:T4c6,encodedUniqueChars = { // initiate a byte-mapping, starting out one-to-one const byteMap = [0]; for (let i = 1; i < 256; i++) byteMap[i] = i; // convert the characters of our first paragraph to UTF-8 encoded bytes const charBytes = (new TextEncoder()).encode(firstParagraphChars); // before we would shift the sum, then add the new char. In this case // we actually wish to shift the new character instead, because that // way we can decode our number later. let shiftPow = BigInt(256), shift = 1n, sum = 0n; for (let i = 0; i < charBytes.length; i++) { const char = charBytes[i]; const charIdx = byteMap.indexOf(char); sum = sum + shift * BigInt(charIdx); // update our byte map: replace the encoded byte // with the last byte in the map, then shrink it. byteMap[charIdx] = byteMap[byteMap.length - 1]; byteMap.pop(); // increase our shift value shift *= shiftPow; shiftPow--; } let encodedBits = []; const encoded = sum; while (sum > 0n) { encodedBits.push(Number(sum & 1n)); sum >>= 1n; } return {encoded, encodedBits, originalBits: charBytes.length * 8, ratio: (encodedBits.length * 100 / (charBytes.length * 8)).toFixed(2) + "%"}; }31:Tb46,fullExplanation = `# Basic compression methods: reducing the alphabet ${firstParagraph} ~~~ ${firstParagraphChars} ~~~ You can count to verify that there are ${firstParagraphChars.length} characters. Information theory tells us this should take around ${Math.log2(firstParagraphChars.length).toFixed(2)} bits per character, which is about ${100 - Math.log2(firstParagraphChars.length)*100/8|0}% fewer bits than a byte. So how would we achieve that? Well, one mathematical approach is to interpre each character in the input paragraph as a digit for a base-${firstParagraphChars.length} number. Then we take that (very large) number and convert it to a base-2 representation, which gives use the bits required. To decode, we reverse it: we take that large base-2 number, convert it back to base-${firstParagraphChars.length}, then convert the "digits" back to our string. If the idea of converting bases sounds scary, don't worry. It will be clear soon enough. First we have to create a reversible map our reduced alphabet to integers. That's pretty straightforward: we map each character to the position in which it appears in our alphabet (starting the count at zero). ~~~ ${(() => { const map = firstParagraphChars.split("").map((c, i) => ` ${c} ↔ ${i}`); map.splice(4, map.length - 8) map.splice(4, 0, " ..."); return map.join("\n") })()} ~~~ (Yes, this has the potentially confusing consequence of number digits mapping to different numbers than what they normally mean. Just keep in mind that characters are symbols, and we can assign any value to any symbol as long as we're consistent) Now we have a base-${firstParagraphChars.length} number! "But it is still just a string!" Yes, but we can already read that string as a number in base 43, each character represents an integer digit after all. You juse have to use the same algorithm for base-10 positional notation that you already know (but maybe have forgotten how to use consciously), but use base-${firstParagraphChars.length} instead. But that would be incredibly tedious and error prone, so let's make the computer do that for us instead. We wish to instruct it to convert the paragraph to an *actual* number representation. First we initiate a \`sum\` variable at zero, then use the positional notation algorithm to create our number. Going over each character ("digit") from left to right we: 1. multiply the existing sum by the total number of unique digits (${firstParagraphChars.length}) to "shift" the sum one digit to the left 2. map the character to its "digit" value and add it to this sum That's it. The only limitation is that this will quickly become a huge number, too large to fit in the 64 bit floats that JavaScript uses. Luckily, we can use the built-in [BigInt](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt) number type these days. `32:[] 2d:{"id":"471e388826885c8c","slug":null,"title":"Basic compression methods: reducing the alphabet","thumbnail":"4c8e582a8aeedda93a13e6a1955b09197e6cc8a40987d34da87accd2f3bd8eb1","access_level":"public","create_time":"$D2024-07-06T10:33:18.352Z","update_time":"$D2024-07-08T09:48:12.855Z","view_time":null,"first_public_time":"$D2024-07-07T13:21:56.752Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"3f83172cfde1e56a","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":"starter_2024"},"version":549,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null}],"members":[{"type":"team","id":"3f83172cfde1e56a","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":"starter_2024","role":"editor"},{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Basic compression methods: reducing the alphabet","cells":[{"id":6,"value":"md`${fullExplanation}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":151,"value":"bigIntFirstParagraph = {\n const totalChars = BigInt(firstParagraphChars.length);\n const charToBigInt = new Map(firstParagraphChars.split(\"\").map((c, i) => [c, BigInt(i)]))\n // initiate our compressed \"string\" as a `BigInt`.\n let sum = 0n, n = 0n, i = 0;\n // loop over each character in the paragraph, multiplying\n // the encoded string by the number of unique characters,\n // then adding the integer the character maps to.\n for (i = 0; i < firstParagraph.length; i++) {\n n = charToBigInt.get(firstParagraph[i]);\n sum = totalChars * sum + n;\n }\n return sum;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":234,"value":"Yep, that's a Big Integer I guess. Let's see how many bytes it converts to, and how it compares to the original one-byte-per-character version:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":204,"value":"compressedFirstParagraph = {\n let bigIntStr = bigIntFirstParagraph;\n const bytes = [];\n // repeatedly extract the lower eight bits\n // of the big int until it is zero\n while (bigIntStr) {\n const byte = Number(bigIntStr & 255n);\n bytes.push(byte);\n bigIntStr = bigIntStr >> 8n;\n }\n return bytes\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":217,"value":"// The number of characters of the regular string, which equals the number of bytes in utf-8\nfirstParagraph.length","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":211,"value":"// ratio of bytes\ncompressedFirstParagraph.length / firstParagraph.length ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":239,"value":"A 32% reduction in size! Nice! But can we actually decompress the result? If we did everything right, we should just reverse all the operations above to get back our original string. Let's see:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":241,"value":"function bytesToBigInt(bytes) {\n\n // conver the bytes back to a big integer\n let bigIntStr = 0n;\n for (let i = bytes.length - 1; i >= 0; i--) {\n bigIntStr = (bigIntStr << 8n) + BigInt(bytes[i]);\n }\n return bigIntStr\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":247,"value":"// Sanity check: is this the same number as our big integer?\nbytesToBigInt(compressedFirstParagraph) == bigIntFirstParagraph","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":136,"value":"bigIntToChar = new Map(firstParagraphChars.split(\"\").map((c, i) => [BigInt(i), c]))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":258,"value":"function decodeBytes(bytes) {\n let bigIntStr = bytesToBigInt(bytes);\n const uniqueChars = BigInt(firstParagraphChars.length);\n const chars = [];\n while (bigIntStr) {\n // Note: we are decoding the characters in reverse!\n const char = bigIntToChar.get(bigIntStr % uniqueChars);\n bigIntStr /= uniqueChars;\n chars.push(char);\n }\n \n return chars.reverse().join(\"\");\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":260,"value":"decompressedParagraph = decodeBytes(compressedFirstParagraph)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":267,"value":"// Is our decompressed string the same?\ndecompressedParagraph === firstParagraph","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":372,"value":"$2f","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":386,"value":"$30","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":446,"value":"decodedUniqueChars = {\n // reconstruct our big int number\n const {encodedBits} = encodedUniqueChars;\n let sum = 0n;\n for (let i = encodedBits.length - 1; i >= 0; i--) {\n sum = (sum << 1n) + BigInt(encodedBits[i]);\n }\n\n // re-create the byte-mapping\n const byteMap = [0];\n for (let i = 1; i < 256; i++) byteMap[i] = i;\n\n const bytes = [];\n let possibleCharacters = 256n;\n while (sum) {\n // mask out the current index\n const idx = Number(sum % possibleCharacters);\n bytes.push(byteMap[idx])\n\n // update the byte map\n byteMap[idx] = byteMap[byteMap.length - 1];\n byteMap.pop();\n\n // remove the decoded character from the sum\n // and reduce the total possible characters\n sum /= possibleCharacters;\n possibleCharacters--;\n }\n return (new TextDecoder()).decode(Uint8Array.from(bytes))\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":473,"value":"Woohoo! All that work for a grand total savings of... six bits. For small alphabets this doesn't make that big of a difference. But if we had a full alphabet (so all 256 bytes) then we would save a lot more:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":427,"value":"encodedFullAlphabet = {\n // initiate a byte-mapping, starting out one-to-one\n const byteMap = [0];\n for (let i = 1; i < 256; i++) byteMap[i] = i;\n\n const charBytes = Uint8Array.from({length: 256}, (v, i) => i);\n let shiftPow = BigInt(256), shift = 1n, sum = 0n;\n for (let i = 0; i < charBytes.length; i++) {\n const char = charBytes[i];\n const charIdx = byteMap.indexOf(char);\n sum = sum + shift * BigInt(charIdx);\n byteMap[charIdx] = byteMap[byteMap.length - 1];\n byteMap.pop();\n shift *= shiftPow;\n shiftPow--;\n }\n\n let encodedBits = [];\n const encoded = sum;\n while (sum > 0n) {\n encodedBits.push(Number(sum & 1n));\n sum >>= 1n;\n }\n\n return {encoded, encodedBits, originalBits: charBytes.length * 8, ratio: (encodedBits.length * 100 / (charBytes.length * 8)).toFixed(2) + \"%\"};\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":493,"value":"Instead of 256 × 8 = 2048 bits, we would need 1684 bits (210.5 bytes).\n\nYou might be wondering why we need to encode a literal string *at all* if we already know that we will use all 256 possible byte values. But there is a situation where this might still be useful: this form of encoding also lets use save the *order* in which these byte values first appear. So if that is something we want, and if we have a relatively short string with a high number of different byte values, then this approach can save us up to 45 bytes.\n\n---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":0,"value":"firstParagraph = `Most (lossless) algorithms for data compression try to compress data by making use of repeating patterns and statistics (e.g. \"these letters appear more often, use something like arithmetic coding to encode them with fewer bits\"), but one extremely simple one for text is using only as many bits as needed for the number of unique characters in the text. That is: even if we limit ourselves to the Latin alphabet, UTF-8 uses one byte per character. One byte can cover 256 possibilities. However, the Latin alphabet has 26 letters, and most of the time we use lower-case, with only a few upper-case characters, plus a few punctuation symbols (space included). For example, these are all the unique characters used in this paragraph, including an invisible space character:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":107,"value":"firstParagraphChars.length","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":22,"value":"firstParagraphChars = [...new Set(firstParagraph.split(\"\").sort())].join(\"\");","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":79,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}} 2e:"$2d:body"