3 ms·
LZ77 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). [
by faragon 9y ago
LZ77 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 9y agoSorry misread the paper and I meant linear space LZ77
- faragon 9y 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.