4 ms·

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?

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?

vecter 9y ago
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.
- rckclmbr 9y ago
  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.
  - vecter 9y ago
    Fair enough. I answered the question implicitly but perhaps I should have been more explicit.
- wfunction 9y ago
  Edit: Never mind, missed a word.
  - adrianN 9y ago
    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.
    - wfunction 9y ago
      Oh shoot, I missed the word "code", that's why it didn't make sense to me! Sorry, removing my comment...
- alex_hirner 9y ago
  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/ http://succinct.cs.berkeley.edu/wp/wordpress/ [1] https://www.youtube.com/watch?v=R_SHYey7eas https://www.youtube.com/watch?v=R_SHYey7eas (Video)
- wolf550e 9y ago
  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.
matt4711 9y ago
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.
- faragon 9y ago
  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.
jltsiren 9y ago
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.

vecter 9y ago

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.

rckclmbr 9y ago
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.
- vecter 9y ago
  Fair enough. I answered the question implicitly but perhaps I should have been more explicit.
wfunction 9y ago
Edit: Never mind, missed a word.
- adrianN 9y ago
  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.
  - wfunction 9y ago
    Oh shoot, I missed the word "code", that's why it didn't make sense to me! Sorry, removing my comment...
alex_hirner 9y ago
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/ http://succinct.cs.berkeley.edu/wp/wordpress/ [1] https://www.youtube.com/watch?v=R_SHYey7eas https://www.youtube.com/watch?v=R_SHYey7eas (Video)
wolf550e 9y ago
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.

matt4711 9y ago

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.

faragon 9y ago
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.

jltsiren 9y ago

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.