cbloom rants 02-04-15 - LZSA - Part 1
cbloom rants 02-04-15 - LZSA - Part 2
cbloom rants 02-05-15 - LZSA - Part 3
cbloom rants 02-05-15 - LZSA - Part 4
cbloom rants 02-06-15 - LZSA - Part 5
cbloom rants 02-06-15 - LZSA - Part 6
cbloom rants 02-09-15 - LZSA - Some Results
And other suffix related posts :
cbloom rants 09-27-08 - 2 (On LZ and ACB)
cbloom rants 09-03-10 - LZ and Exclusions
cbloom rants 09-24-11 - Suffix Tries 1
cbloom rants 09-24-11 - Suffix Tries 2
09-26-11 - Tiny Suffix Note
cbloom rants 09-28-11 - String Matching with Suffix Arrays
cbloom rants 09-29-11 - Suffix Tries 3 - On Follows with Path Compression
cbloom rants 06-21-14 - Suffix Trie Note
cbloom rants 07-14-14 - Suffix-Trie Coded LZ
cbloom rants 08-27-14 - LZ Match Length Redundancy
cbloom rants 09-10-14 - Suffix Trie EOF handling
Did you ever implement any of this and see how it performs?
ReplyDeleteYeah, I implemented LZSA-Basic and LZSA-HC for packet compression and tested vs. the existing "Oodle Network" (LZP static dictionary variants).
ReplyDeleteI made a bunch of results, and now I can't find them. So maybe I'll try to re-run my tests or blah.
The thing that you could see in the results is that the Oodle Static-LZP doesn't scale that well with increased dictionary size. (with LZP you only match one string, so at some point you just have the best one string in there and adding more dictionary does nothing). Compression benefit slows down after a 16 MB dictionary or so. With LZSA, the compression on a 1 MB dictionary was about the same as Static-LZP, but it continues to improve steadily as you increase dictionary size.
It's not compelling for me in Oodle because game customers don't want to run big dictionaries for various legitimate reasons; 1 MB is common and 4 MB is probably the max. LZSA really shines (vs LZP) as you get to 32 or 64 MB or more.
Anyway, I'll do another dig around for those results...