3 ms·
To clear this up: This is exactly how gzip actually works. I wrote a version of gunzip from scratch and just inserted some print statements in the middle to get
by jvns 13y ago
To clear this up: This is exactly how gzip actually works. I wrote a version of gunzip from scratch and just inserted some print statements in the middle to get this visualization.
- jvns 13y agoIf anyone is interested, the part of the source code that produces the visualization is here: https://github.com/jvns/gzip.jl/blob/visualization/gzip.jl#L360 https://github.com/jvns/gzip.jl/blob/visualization/gzip.jl#L...
- jcampbell1 13y agoYou are quite right, I am an idiot.
- cbhl 13y agoFrankly, learning about LZW[0][1] and the Burrows-Wheeler Transform[2] was probably one of the highlights of my first undergrad algorithms course. The latter certainly made me feel like an idiot, too. [0] http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welc... [1] For the record, LZW isn't used in gzip; it was the patent-encumbered compression format used in GIF. [2] http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transfo... (used in bzip2)
- jamesjporter 13y agoBWT is mindblowing. So many applications; e.g. it's used by pretty much all popular biological sequence alignment software to compress genomes so they fit in memory during the alignment :D