6 ms·
Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
- wolf550e 10y agoIt 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 10y agoI 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 10y agoI 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 10y agoFair enough. I answered the question implicitly but perhaps I should have been more explicit.
- wfunction 10y agoEdit: Never mind, missed a word.
- adrianN 10y agoYou 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 10y agoOh shoot, I missed the word "code", that's why it didn't make sense to me! Sorry, removing my comment...
- alex_hirner 10y agoA 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 10y agoThank 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 10y agoIn 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 10y agoMay 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 10y agoWhen 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.
- zitterbewegung 10y agoThis looks really awesome. According to google scholar it went through peer review. Seeing that it would improve compression (linear time LZ77) would be cool but not only does it do that but also compute search index data structures. https://scholar.google.com/scholar?hl=en&q=Space-Efficient+Construction+of+Compressed+Indexes+in+Deterministic+Linear+Time&btnG=&as_sdt=1%2C14&as_sdtp= https://scholar.google.com/scholar?hl=en&q=Space-Efficient+C...
- faragon 10y agoLZ77 was already linear time using hash tables for the search (e.g. lzop [1], LZ4 [2], LZF [3], and other similar LZ77 compressors using the same technique). [1] https://www.lzop.org/ https://www.lzop.org/ [2] https://github.com/lz4/lz4 https://github.com/lz4/lz4 [3] http://oldhome.schmorp.de/marc/liblzf.html http://oldhome.schmorp.de/marc/liblzf.html
- zitterbewegung 10y agoSorry misread the paper and I meant linear space LZ77
- faragon 10y agoThose fast LZ77 I pointed before use linear time (O(n)) and constant space size (fixed-size hash tables) -which is O(1) space, even better than O(n) -linear- space complexity-.
- wolf550e 10y agoTo get perfect parsing LZ, you need a lot of space to store backreferences. When you increase the window size, the space grows a lot. I don't know what zstd does, but I would love to see it improved by algo magic.
- visarga 10y agoI used to play with suffix arrays a long time ago. I wanted to accelerate grep on a gigabyte text file. The tool was called "sary" (short for suffix array) and still exists on a forgotten SourceForce page. Good tool, it was able to find any substring in a huge file instantly.
- tmzt 10y agoHow might your method compare to the tech in ripgrep or The Silver Searcher? Are there cases where it might be faster?
- projectorlochsa 10y agomost speed gain tricks in ripgrep have nothing to do with string algorithms. you can save a lot of time by parallelizing your filesystem walks or by using some system call tricks for reading files as quickly as possible.
- burntsushi 10y ago> most speed gain tricks in ripgrep have nothing to do with string algorithms There are actually several tricks at the "string algorithm" level. I didn't invent any of them, but no other search tool combines all of them AFAIK. They are: * Heuristic for choosing the skip character in boyer moore. (Pick rare bytes.) * Roll UTF-8 decoding into the regex automaton. * Use SIMD for multiple string literal search. (This is an unpublished algorithm from Intel's Hyperscan project.) There was also significant work required for scaling glob matching. Some popular repositories have gitignore files with over 3000 rules. These are important because ripgrep isn't just for searching code repositories. It should be able to do most things that grep can do, but faster. (The smarter UTF-8 handling is particularly beneficial when searching non-ASCII text.) Within the context of this thread though, and as someone who has written a linear time suffix array algorithm, the suffix array isn't particularly well suited to the problem of code search. Its constant factors are just too high. Generating an index would take a long time. (Although I haven't read the OP yet.) > some system call tricks for reading files as quickly as possible. ripgrep does two different types of searches. One uses memory maps. The other uses standard `read` calls. The latter is actually faster on Linux when searching code repositories. So no real tricks there. :-)
- wfunction 10y agoAnybody going to implement this and share it open-source? :)
- lifepillar 10y agoYou may ask this guy: https://github.com/nicolaprezza https://github.com/nicolaprezza He already has some interesting code :)
- jankotek 10y agoI read paper with that intend. But it is pretty hard to digest. It is mostly just proof of computational complexity.
- eggie 10y agoIt is very likely that this will eventually end up in sdsl-lite and/or other compressed data structures libraries https://github.com/simongog/sdsl-lite https://github.com/simongog/sdsl-lite
- pzh 10y agoCan somebody who read the paper in depth comment on whether the result is practical or not? Since it's a TCS paper, it's hard to gauge whether the constant factors are palatable or not, and there are many theoretical CS papers that give asymptotically optimal or significantly improved algorithms that have astronomical constant factors (e.g. matrix multiplication, etc.)
- JPLeRouzic 10y agoAs long as you can express some information as lists of symbols, you need to search patterns in it and to store in a compressed form, particularely for biological molecules which are incredibly long (your DNA is nanometers large and meters long!) There are already bioinformatics tools such as BowTie that use the Burrows-Wheeler transform. https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf... I think the important thing here is that the running time is deterministic, which is important if your query usually runs for days or even weeks! (edited)
- eggie 10y agoThe compressed suffix tree (CST) supports a number of search algorithms that run in the order of the query length irrespective of the size of the corpus which is being searched. That the suffix tree is compressed allows it use space that is often not much larger than the input sequence, and this effect is improved in the case of inputs with internal repetitions, which seems to be the norm in the case of naturally-arising data (i.e. almost anywhere that Zipf's law holds). As the authors point out, existing algorithms for the construction of the compressed suffix tree require space that is proportional to the alphabet size. When we work with limited alphabets, like DNA, this factor is small and we tend to not worry about it. Many real-world data sets do have larger alphabet sizes, and so there is a need to efficiently generate the CST for them. Removing the alphabet-size bound on the space required for construction is a big deal. Existing methods require huge amounts of space to construct the CST or CSA (compressed suffix array) for large alphabets, and are barely practical to use. In practice results of this kind have proceeded implementations that are usable by a year or more. Libraries like sdsl-lite have accelerated the rate at which implementations get into the hands of compressed data structure researchers in much the same way that R did for statistical models, so hopefully we can see benefits of this result sooner. Unfortunately, it will take a deeper reading of the paper by someone who is more intimately involved in this research to be able to describe exactly why this result may not be practical. A quick read does not suggest any obvious problems, the authors have a good track record and are very positive about many follow-on results (see conclusions).
- burntrelish1273 10y agoDoes this imply zlib and gzip may be able to be patched to reduce memory usage and runtime?
- faragon 10y agoRegarding reducing run time, zlib/gzip already use a O(n) algorithm (Rabin-Karp rolling hash search), despite being "slow" in comparison with other "pure-hashing" LZ77 implementations (e.g. LZO, LZ4, LZF). I don't have access to that paper, but "compressing indexes" is likely to be slow, no matter how is implemented: fastest LZ77 using hashing relies on doing few operations per input byte. So no matter if the hash table space could be reduced or not, the speed would not be likely to be faster (anyway, you can trade hash table size vs compression ratio, even without that new technique).
- wolf550e 10y agoIf you can, you should upgrade from DEFLATE (the compression format in zlib, gzip, zip files, png, office docs, etc) to something more modern like zstd. If you must preserve ability to decompress by zlib, there are different implementations of a DEFLATE compressor that are better than zlib (either faster or better compression ratio). A DEFLATE compressor needs to keep a data structure that is able to answer the query "where in the last 32,768 bytes of input there are occurrences of the exact 3 bytes I'm looking at? If possible, check whether the 4th byte matches too and find the longest match. Among matches equally long, prefer those which are closer". For a 32KB window, a data structure that always finds the best match is not large, unless you're on a microcontroller. The size of the data structure becomes a problem when the window is large.
- gnavarro69 10y agoHi, a note from one of the coauthors of the paper ;-) Yes, it is a theoretical paper and then the presentation focuses on what is needed in such a paper: to establish that the big-Oh complexity can be reached. Some theoretical papers will never become practical, but we believe this one can. However, this will require a fair amount of algorithm engineering, to take the important theoretical ideas and implement them with common sense, changing theoretically appealing but practically useless modules by others that work better, even if they do not reach the desired worst-case complexity. A promising aspect of this algorithm is that it is easily parallelizable (the batched queries). A postdoc of mine that has experience in multithreading and compact data structures is already working on this. I won't dare to say how competitive will be the resulting LZ-parsing algorithm, though. We have had some experiences with good theoretical results whose implementation looks unsurmountable but that turned out to work very well after some algorithm engineering. An example is our work on top-k document retrieval: http://epubs.siam.org/doi/abs/10.1137/140998949 http://epubs.siam.org/doi/abs/10.1137/140998949 http://dl.acm.org/citation.cfm?id=3043958 http://dl.acm.org/citation.cfm?id=3043958 Another well-known case is the first paper on the FM-index, with constants like sigma^sigma multiplying the space, and its current realizations, e.g. Burrows-Wheeler Aligner. In this case, I think it will not be that hard, but still it will not be a matter of just translating the algorithm into code. Best, Gonzalo