Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding

in random directions!? The most extreme and stereotypical version of this style are the billboards written by some homeless people. You can probably picture it already in your mind's eye: A wall of very dense text with little whitespace or structure, and a mix of fonts and colours seemingly at random. I had a brilliant mathematician friend who wrote like this. He would squeeze an entire semester's worth of study notes into a single sheet of paper, on one side. It was impenetrable gibberish to everyone else, but the colours and 2D positioning let him build a mental mind-map. For people like this, if you reformat their code even a tiny bit, their mental map is invalidated, and they lose track of it completely and become upset. I discovered this (the hard way) when applying automatic code formatting tools to the codebases I mentioned previously. Personally, I find this type of thing to be absolutely fascinating, because it's the intersection of many scientific fields but belongs in none, and hence is under-studied. There's elements of pedagogy, psychology, literacy, neuroscience, computer science, etc... It remains an open question how we can get large groups of neurodiverse humans to collaborate on a codebase when they don't even "read" or "think" in compatible ways! Enforcing a single style may work for most developers, but clearly not all. PS: Even on an anecdotal level, when I was a beginner programmer I could only read a single brace and indentation style. After two decades, I can now read almost any style, including inconsistent and outright crazy indentation without even noticing that something is amiss.

implementation [1] provides about 50% faster decoding than HC for 256 size alphabet, with compression rate similar to provided by AC. This advantage is due to being simpler than AC: using single natural number as the state, instead of two to represent a range. Beside simplifying renormalization, it allows to put the entire behavior for given probability distribution into a relatively small table: defining entropy coding automaton. The memory cost of such table for 256 size alphabet is a few kilobytes. There is a large freedom while choosing a specific table - using pseudorandom number generator initialized with cryptographic key for this purpose allows to simultaneously encrypt the data. This article also introduces and discusses many other variants of this new entropy coding approach, which can provide direct alternatives for standard AC, for large alphabet range coding, or for approximated quasi arithmetic coding. Check out his other papers / the github project (looked super interesting and similar).

than LZFSE, and in fact Apple does push for its use by offering it in its compression library. However, it tends not to compress as well as both LZFSE and Zstd. For 4G or WiFi (or even broadband), the time lost by transferring more data is not compensated by the time won by decompressing it faster, resulting in much slower downloads than even zlib. LZ4 is still relevant for higher speeds, such as those offered by magnetic hard drives. (Beyond a certain speed, such as for SSDs, compression no longer offers a benefit, but you might be ok with the slowdown given that you win drive space.) There is a separate discussion to be had about the fact that the open-sourced LZFSE reference implementation is not the one they use (which explains how little they touched it since), as it does not even have ARM-specific code. Also, LZFSE does not claim to be patent-unencumbered. LZ4 and Zstd do have optimized code for ARM. All in all, it is not a stretch to assume that Apple benefits from this FUD, which explains why there is no comparative benchmark anywhere to be found on their GitHub or in their documentation. It really looks like Zstd is better all around.