Hacker News Reader

Comment by wolf550e | Hacker News Reader

It will take me a while to read the paper. I saw there is no code inside. Do they have code that improves LZ parsing as used in all general purpose compressors? If they don't have code, can their algorithm be implemented to improve performance of zstd or lzma?

View on HN

In general the techniques in zstd/lzma are much faster than using compressed text indexes.

As a somewhat expert in the field I doubt that this paper has any practical implications.

May be it could be related to a output-code post-processor (e.g. instead of using generic entropy coding postprocessing, compress indexes with an new specific algorithm). If this allows good compression without an additional post-processing step (e.g. avoiding Huffman, arithmetic coding, etc.), it could be very interesting.

When theoreticians talk about LZ, they mean unlimited LZ, not LZ within a limited window. If you are only interested in data compression, the existing algorithms with limited window size should be much faster, use less memory, and achieve similar compression, except in some rare cases.

The primary motivation for unlimited LZ is text indexing. You can build text indexes based on LZ parsing and achieve ridiculous compression ratios with repetitive data (e.g. versioned documents). The query performance depends on the length of the dependency chains in the parsing, so you want to use as long windows as possible.

I skimmed the abstract and the paper and didn't see any, but that doesn't surprise me either. This is a theoretical computer science paper. It doesn't need code to show correctness, as long as they prove their claims. I'm curious why you're seeking such code?

edit: why the downvotes? Theoretical CS academics basically do math and very few write any actual code to supplement their papers.

I think you are downvoted because he asked a question and you didn't attempt to answer it. You're not wrong, just off topic for what was expected.

Fair enough. I answered the question implicitly but perhaps I should have been more explicit.

A combined compression and indexing scheme that actually has code is Succinct by Berkeley [0]. I remember being impressed by the tradeoffs you can dial in and its performance in a 2015 presentation [1].

[0] http://succinct.cs.berkeley.edu/wp/wordpress/ [1] https://www.youtube.com/watch?v=R_SHYey7eas (Video)

Thank you. Yes, I understand that theoretical computer science is math and the result is a proof. I'm more used to papers where the interesting part is a benchmark, with a "proof of correctness" part I can safely skip. And in order to produce the graphs of the benchmark results, they have to implement it.

Edit: Never mind, missed a word.

You can describe algorithms using normal English perfectly fine. You can then use normal English to prove the correctness of your claims. This is what almost all papers about algorithms from the theoretical CS community do.

Oh shoot, I missed the word "code", that's why it didn't make sense to me! Sorry, removing my comment...

Reply on news.ycombinator.com