101–110 of 181 posts
I've studied the Burrows-Wheeler Transform, I understand the transformation, I've re-implemented it countless times for kicks, I see how it improves compressability, but for the life of me the intuition of _why_ it works has never really clicked. It's a fantastic bit of algorithmic magic that will always impress me to see it.
Earlier quoted context omitted.
The bash 4 thing is due to the GPL 3, not some inherent slowness in updating software. It has nothing to do with zstd, which is permissively licensed.
It doesn't matter why. All that matters is that "current" is not a valid word. Old things exist in "current" systems. And current systems may also be old systems.
Earlier quoted context omitted.
zstd is faster and provides better compression than gzip at every point on the curve. There is no reason to use gzip these days other than backwards compatibility.
zstd is a great setup, for sure, but the build system they use is patently awful. Can someone make an autoconf or hell, even CMake build system for them pleasee???
I've studied the Burrows-Wheeler Transform, I understand the transformation, I've re-implemented it countless times for kicks, I see how it improves compressability, but for the life of me the intuition of _why_ it works has never really clicked. It's a fantastic bit of algorithmic magic that will always impress me to see it.
Yeah. BWT and zero knowledge proofs are my goto examples of CS things that seem like pure magic.
I remember seeing someone (probably Avi Wigderson) demonstrating a zero-knowledge proof for graph coloring on an overhead projector when I was starting my second year studying CS. He had a slide with a graph, multiple slides with different permutations of the same valid coloring of the vertices, and a piece of paper with "doors" over the vertices to cover everything. The audience could ask him to open the doors over the vertices connected by any edge, and he would show that the coloring is valid, as far as those two vertices are concerned. And then he would replace the coloring with another permutation for the next iteration. The idea felt clever but kind of obvious in retrospect.
I poke around in this space periodically, but I've never found a compelling reason to move away from gzip.
I am a huge proponent of zstd after I learned about it on HN. I've recently had to compress a 12 Gb csv file. zstd took ~3 sec for compression and ~11 sec for decompression and got the file to ~1.1 Gb. Xz took ~3.5 min for compression(!) and the resulting file was ~740 Mb(I didn't measure the decompression time). I just realized that in most cases it's more efficient to use zstd, especially for file transfer. The maj…
Earlier quoted context omitted.
I always understood it as working because of the predictability of a symbol/letter/token given the previous one. Sorting all the shifts of a string puts all the characters in order, then looking at the last column shows you all the _preceding_ characters. If there's any predictability there (which there often is), it's now easier to compress. It's sorta like an entropy coder in that way. I've never thought of it as b…
Understanding why increasing predictability helps with compression is not the hard part though. What's hard to grasp is why the transform is reversible.
I've studied the Burrows-Wheeler Transform, I understand the transformation, I've re-implemented it countless times for kicks, I see how it improves compressability, but for the life of me the intuition of _why_ it works has never really clicked. It's a fantastic bit of algorithmic magic that will always impress me to see it.
In terms of why it aids compression, or why it's reversible?
As far as the first goes: it transforms n-grams into repeated characters.
Earlier quoted context omitted.
Understanding why increasing predictability helps with compression is not the hard part though. What's hard to grasp is why the transform is reversible.
a word can be factored into the set and frequency of letters + the specific permutation. compressable patterns in either channel seem likely when the underlying words are language like.
Describing a multiset takes as much information as the multiset contained to begin with, on average. BWT somehow works better on things of use.
Earlier quoted context omitted.
I am a huge proponent of zstd after I learned about it on HN. I've recently had to compress a 12 Gb csv file. zstd took ~3 sec for compression and ~11 sec for decompression and got the file to ~1.1 Gb. Xz took ~3.5 min for compression(!) and the resulting file was ~740 Mb(I didn't measure the decompression time). I just realized that in most cases it's more efficient to use zstd, especially for file transfer. The maj…
Did you confuse gzip and xz? You mention numbers from xz and then suddenly talk about gzip? These two are not related…