Modern LZ Compression (2019)

https://glinscott.github.io/lz/index.html

by imadr • 5 years ago

122 44 5 years ago

glinscott.github.io

dang• 5 years ago

Discussed at the time:

Modern LZ Compression - https://news.ycombinator.com/item?id=19064791 - Feb 2019 (4 comments)

user-the-name4• 5 years ago

"Modern", but uses Huffman coding? No LZ implementation aiming for high compression in the last decade has used Huffman.

chriswarbo• 5 years ago

For our goal of a high compression LZ variant, we will want to Huffman code our symbols (zstd actually uses FSE, a variant of arithmetic coding to do this, but we will cover that in a future post).

user-the-name4• 5 years ago

But why? Why spend that much effort introducing a method that is basically entirely outdated at this point, and is also fairly complicated?

hexxagone7• 5 years ago

You mean like zstd and brotli ? Is there any new LZ codec not using Huffman ?

retrac2• 5 years ago

It was my understanding Zstd used neither Huffman or AC but something else: https://en.wikipedia.org/wiki/Asymmetric_numeral_systems

Edit: It uses a variety of entropy encodings for different data structures, Huffman is one of them. My apologies for the confusing initial comment.

akkartik• 5 years ago

Does anyone have recommendations for learning the xz format? Particularly as used by the ZIM archival format: https://en.wikipedia.org/wiki/ZIM_(file_format)

adzm• 5 years ago

lzmautils / xz utils is probably your best bet. They have some documentation for sure but it's a complicated format so the source is invaluable.

meiji163• 5 years ago

I wonder if LZ would still be standard, if not for the inertia of gzip/zip? There are surely better and comparably fast algorithms (paq, ppm, etc.)

axiolite6• 5 years ago

zip/gzip are LZ algorithms, as mentioned near the top of the article. Based on LZ77 to be exact.

Did you perhaps mean LZW (gif & compress), which was based on LZ78?

zlib isn't really dominant, today. lzma seems to have overtaken it for anything destined for public distribution.

wolf550e3• 5 years ago

lzma is slow to decompress. Unless the bandwidth / storage costs are the primary concern, zstd has good enough compression ratio and the very fast decompression makes everything much nicer. Built-in threaded compression, long range compression, binary diff, dictionary compression, etc. are a bonus.

jltsiren• 5 years ago

LZ is popular because it's computationally efficient. When random memory access is slow but sequential access is fast, you want to encode substrings instead of individual symbols. Explicit higher-order probabilistic models require a lot of memory and generate too many cache misses. Implicit models based on the Burrows-Wheeler transform also have poor memory access patterns.

hexxagone7• 5 years ago

PAQ and PPM are not fast, certainly not in the same category as LZ codecs.

wolf550e3• 5 years ago

ppm and paq are a LOT slower than LZ77.

zinekeller• 5 years ago

if not for the inertia of gzip/zip

I think that's misidentifying where's credit is due: LZ might not be the most efficient compression format when it comes to size, but it's very efficient computation-wise when compressing and decompressing, and this still holds true today even when you consider newer algorthms like Zstandard (which uses a derivative of LZ). Sure, if you need to archive data into its compactest representation at any cost, LZ and derivatives won't deliver it, but unless there's a significant change to how computing works it's still in LZ's favour. At the time DEFLATE was designed, LZ just beat out every competition since realistically you can't run decompression at real-time using minimal memory.

hakmad• 5 years ago

This might not apply to all LZ based programs/algorithms but compress (an old Unix utility based on the Lempel-Ziv-Welch algorithm) fell out of favour after it ran afoul of patent issues (you can read more about it on the compress Wikipedia page [0] and a section of the GIF Wikipedia page [1] which covers more about the enforcement of the patent). From what I can gather though, it enjoyed considerable success and was pretty much the standard utility for compressing data on Unix. I think eventually though it would have been replaced because other algorithms (bzip2, gzip, etc.) have slightly better compression ratios (even if they are more computationally expensive).

[0] https://en.wikipedia.org/wiki/Compress [1] - https://en.wikipedia.org/wiki/GIF#Unisys_and_LZW_patent_enfo...

rurban• 5 years ago

I had to implement recently an oldstyle lz77 en/decoder to handle an old fileformat, and it was surprisingly simple. Even the encoder

retrac2• 5 years ago

There's quite a lot of retro modern LZ activity too! LZ turns out to be amazing on old machines, often only a couple times slower than a block copy. Optimal compressors and control over the algorithm have led to some very tight demos.

https://www.brutaldeluxe.fr/products/crossdevtools/lz4/index... LZ4 Data Compression - a rather long and in-depth article looking at LZ4 on the 65816 for the Apple IIgs with a decompressor that exploits that processor's block copy.

https://github.com/emmanuel-marty/lzsa - LZSA - a LZ4-like modern LZ that's more efficient both in speed and compression to LZ4 (at least on the 8 bitters it targets) - includes a neat chart of speed/compression trade-offs on a ZX Spectrum with a variety of algorithms

nathell• 5 years ago

"Managing Gigabytes" by Witten et al is _the_ book that got me into the field of compression back in the day. Granted, it’s a bit dated now as there’s been a lot of progress in the field, but I’d still heartily recommend it to newcomers.

nickdothutton• 5 years ago

Only partly related, since it deals with a specific type of data (English language Wikipedia), some of you might enjoy reading about the Hutter Prize: https://en.wikipedia.org/wiki/Hutter_Prize

nayuki• 5 years ago

First, we just shorten any symbols that are longer than our maximum code length — 11 — to that value. This means that our tree will no longer be a Huffman tree, so we need to do a fixup pass to redistribute the error we've introduced.

This can in fact be solved directly and optimally: https://en.wikipedia.org/wiki/Package-merge_algorithm ; https://en.wikipedia.org/wiki/Huffman_coding#Length-limited_...

pwrrr2• 5 years ago

I've spend hours trying to understand how you apply this theory. The internet is surprisingly absent of actual examples showing how it's done. The best I've found that explains the packag-merge is this page: https://create.stephan-brumme.com/length-limited-prefix-code...

pwrrr2• 5 years ago

I just made a huffman encoder on the c64, for fun. I need understand how you go from the variable length codes of huffman, to suddenly fixed lenght codes, because you don't want the codes to be above a certain length. hmm...

Modern LZ Compression (2019)

Related Stories