4 ms·
History of lossless data compression algorithms (2014)
- harveywi 4y agoGrammar-based compression algorithms are completely missing from this "history".
- lucb1e 4y agoHaven't heard of that before. Typing it into Wikipedia, I got https://en.wikipedia.org/wiki/Grammar-based_code https://en.wikipedia.org/wiki/Grammar-based_code which explains it in so much as "To compress a data sequence x=x[0..n], a grammar-based code transforms x into a context-free grammar G." (Very helpful, love it when they use pseudocode with single-letter recursive variable definitions which needs accompanying text for it to make sense... and the text isn't there.) There is an example given on the right in image form, which looks like recursive dictionary-based string substitution: "We hold these truths" compressed: we_holdQ5ths Q=Rse we_holdRse_5ths R=Se we_holdSese_5ths S=_th we_hold_these_5ths 5=tru we_hold_these_truths This method isn't described anywhere nor was the original included, but this seems to be the algorithm used.
- duskwuff 4y agoI'm not sure grammar-based compressors are a meaningful part of the history of lossless data compression. They're a topic in coding theory research, but, as far as I'm aware, they haven't had a significant impact in practical algorithms used in the field.
- bumper_crop 4y agoVery timely; I found out yesterday that the UPX program (EXE specific compressor from many years ago) was made by the same guys who made LZO. I had this realization that there is a progeny from people who write compression stuff. In a similar vein, The Rob Pike post from yesterday mentioned Ken Thompson had made a custom audio compression for the Plan 9 release. He also made the UTF-8 compressor too. I love seeing how these people keep refining the state of the art.
- Jerrrry 4y agoThe thoughts around information theory, entropy, compression, emergent behavior, and the intersectional limits of all of them are quite reminiscent and memetic to those who are interested. Complexity is fuckin cool.
- optimalsolver 4y agoData compression is apparently equivalent to general intelligence: http://mattmahoney.net/dc/rationale.html http://mattmahoney.net/dc/rationale.html ...which gives way to the theory of mind known as compressionism: http://ceur-ws.org/Vol-1419/paper0045.pdf http://ceur-ws.org/Vol-1419/paper0045.pdf
- Dylan16807 4y agoThat's a factor to some extent, but if you're sticking with lossless then the better your compression gets the more your remaining data is dominated by noise.
- gfody 4y agothat's why you need two brains, one to losslessly compress through symbolic expressiveness and another to lossily compress by generating noise like the incompressible noise
- anonGone73 4y agoThe Head and the Heart
- benj111 4y agoI thought men had their brains elsewhere?
- joe_the_user 4y agoPerfect compression is equivalent to finding the Kolmogorov complexity of a string. That's incomputable and so perfect compression is beyond any algorithm, even a "generally intelligent" algorithm. Generality in compression might increase an algorithms effectiveness but there's no proof this generality is equivalent to generality in dealing with the world humans deal with.
- pessimizer 4y ago
- ctur 4y agoThis seems pretty incomplete if it doesn't include anything about brotli, lz4, or zstd, or Finite State Entropy in general. It's basically missing the past decade or more. There's a lot of good history here, but just be aware it is missing the state of the art and thus shouldn't be used for deciding anything about algorithms or approaches to use today.
- lucb1e 4y agoDoes that mean this is also outdated? I'm not sure if zstd, brotli, etc. are PAQ-like > on the bleeding edge of archival software are the PAQ* formats For "a history of" I don't mind if they don't include the latest decade which is still subject to interpretation for how to structure the text and emphasize key moments/inventions and such, but if they make statements pertaining to the present that's a different story.
- felixhandte 4y agoNo widely deployed compressors are PAQ-like. The speed-up anticipated by the OP never materialized.
- _delirium 4y ago> It's basically missing the past decade or more. The page history [1] shows that the article was mostly written in December 2011, with only minor edits since then, so that sounds about right. [1] https://ethw.org/w/index.php?title=History_of_Lossless_Data_Compression_Algorithms&action=history https://ethw.org/w/index.php?title=History_of_Lossless_Data_...
- natly 4y agoNot mentioned here is Fabrice Bellards record breaking (at an enormous compute cost) compressor https://bellard.org/nncp/ https://bellard.org/nncp/.
- lucb1e 4y agoWhat does "ratio (bpb)" mean? I'd guess bytes-per-byte or something, like how many bytes of original you get for each byte of compression, but it doesn't work out: the original size is 1e9 bytes, compressed (rounded) 3.2e8, so that's a ratio of 3.1 (1e9/3.2e8=3.09989). The program size amounts to a rounding error on that figure. The bpb value given is 2.58, nowhere near 3.1. Edit: the paper defines it as "bits per input byte". What kinda measure is that, it's like "how well did it compress as compared to a factor 8", why 8?!
- isaacimagine 4y agoGiven 8 bits of input, how many bits does it take to reconstruct the original 8, on average? 8 / 2.58 = 3.1
- lucb1e 4y agoComparing bytes to bits is still apples to appleseeds rather than apples to apples, to my mind at least.
- dgacmu 4y agoIt's a common way to represent entropy (the information content). One could measure bits per x for any x, of course, but bits per character (nee byte) is quite common and goes back to Shannon.
- jltsiren 4y agoThe bit is the most fundamental unit of information. A base-e unit might be more elegant from a certain mathematical perspective, but the connections to formal logic and the ease of implementation make the base-2 bit the natural choice. At least when talking about things like information, entropy, and compression. Bytes, on the other hand, are entirely arbitrary. At some point, the industry converged to using groups of 8 bits as the primary semantically meaningful unit smaller than a word. Probably because people at that time thought that having 256 distinct characters would be more or less the right choice. And because groups of power-of-2 bits are convenient on hardware level. Entropy is usually expressed as bits per symbol (or bits per character), because that's what you get when you sum -P(c) log P(c) over all symbols c. People who are used to that convention often extend it to representing compression ratios. Using bits per byte is rare, because bytes are rarely semantically meaningful.
- lizardactivist 4y agoThis article is relevant and intersects with some of the algorithms in the topic link: https://oku.edu.mie-u.ac.jp/~okumura/compression/history.html https://oku.edu.mie-u.ac.jp/~okumura/compression/history.htm...
- dang 4y agoDiscussed at the time: History of Lossless Data Compression Algorithms - https://news.ycombinator.com/item?id=8088842 https://news.ycombinator.com/item?id=8088842 - July 2014 (44 comments)
- mtn_nerd 4y agoHow could they not include the middle-out algorithm?
- motohagiography 4y agoIs the theoretical limit to compression basically what Kolmolgorov complexity is, or is there another shannon/information theory theorem that defines the maximum possible lossless compression in terms of symbols over a channel, where the channel represents the algorithm? ("compression theorem" refers to something else more abstract I think.) Intuitively it seems like there would have to be one for lossless compression, and a proof that a theorem for the limits of lossy compression was either impossible or an open loop/Hard problem.
- joe_the_user 4y agoYes, the Kolmolgorov complexity of a string X is the minimum length of a program/string that when fed into an efficient universal computer will yield back the string X. The Kolmolgorov complexity of a string is also undecideable - it's essentially equivalent to the halting problem. "Best Lossy Compression" is ambiguous - how much loss is acceptable is isn't defined in the phrase.
- dhdc 4y agoThe theorem you are looking for is Shannon's Source Coding Theorem[1]. It basically states that no encoding scheme can losslessly compress data beyond the given data's Shannon entropy. [1]: https://en.m.wikipedia.org/wiki/Shannon's_source_coding_theorem https://en.m.wikipedia.org/wiki/Shannon's_source_coding_theo...
- motohagiography 4y agoAmazing, thank you, it had to be something like that. It makes much more sense as an encoding limitation than as something abstract as the "shortest possible program" via Kolmolgorov complexity. I was wondering whether KC may just be an inconsistently defined thought experiment compared to concrete ideas from information theory, and if it's not, how much in common it would necessarily have with the coding theorem, as how are they not talking about the same thing.
- dhdc 4y ago
- kloch 4y agoDoes anyone else remember a joke/malware DOS program that circulated on BBS's in the very early 1990's that promised 98% compression of any file? It just shortened the size in the FAT table (or similar gimmick that would result in data loss as you wrote new data to the disk)...
- pixelpoet 4y agoThe story of Phil Katz (the PK in PKZIP) is a fascinating and very sad one: https://web.archive.org/web/20000829071343/http://www2.jsonline.com/news/state/may00/katz21052000a.asp https://web.archive.org/web/20000829071343/http://www2.jsonl...
- asimpletune 4y agoPart of me wonders if there is some kind of connection between the theoretical minimum compression and radix economy. Like when you calculate the minimal amount of entropy required to encode some data, you end up in fractions of bits. Similarly, the theoretically most efficient radix is base e.
- peter_d_sherman 4y agoIn reading this article, my intuition says to me that the Burrows-Wheeler Transform (https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf...) and the Fourier Transform (https://en.wikipedia.org/wiki/Fourier_transform https://en.wikipedia.org/wiki/Fourier_transform) -- are related -- in some as-of-yet unknown to me, mathematical way... like maybe one is a specific, specialized sub-case of the other, or something like that... I don't have the mathematical ability to prove or disprove this conjecture -- but if some Mathematician in the future wanted to go down the path of either proving or disproving this, then I'd start with looking at the idea that both Transforms have reverse Transforms that preserve information, and that the Fourier Transform is basically its own reverse Transform... in other words, the Fourier Transform is sort of like an "identity" in the world of transforms... It seems that there would, or should be, in the world of Math, transform functions of "different orders", i.e., if Fourier is its own opposite, and if data compression comprises two transformation functions, one to compress data, another to decompress it -- then couldn't there also exist "Trinary Transforms" -- where you run transformation function A, get some data out of it, then run transformation function B on that resulting data, and get some different data out of it, then run transformation function C on that data -- and after running transformation function C -- you get your original data back. If those exist, then maybe N-ary Transformation Functions do too, where you run a set of data through N functions -- and you get your original data back after the Nth time... "transformation function families" -- for lack of better terminology! I don't know -- I don't have the Mathematical expertise to prove or disprove it! Disclaimer: All of the above is based on rampant speculation and conjecture -- and could be (and probably is!) absolutely and completely wrong on one or more levels -- so take with the proverbial "grain of salt"!