4 ms·
This looks really awesome. According to google scholar it went through peer review. Seeing that it would improve compression (linear time LZ77) would be cool bu
by zitterbewegung 10y ago
This 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 9y 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.