Post a Comment On: cbloom rants

I wrote an optimal parser for LZ4 to have as a reference point. It's a very easy format to optimal parse, because the state space is small enough that you can walk the entire dynamic programming table. That is, you just make a table which is : <------ all file positions ------> ^ XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX | XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX states XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX | XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX V XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX and then you just go fill all the slots. Like LZSS (Storer-Szymanski) it's simplest to walk backwards, that way any value in the table that you need from later positions is already computed. (* see addendum at end) For LZ4 the state is just the literal run len (there is no entropy coder; there is no "last offset"; and there are no carried bits between coding events - the way a match is coded is totally independent of what precedes it). I use 16 states. Whenever you code a literal, the state transition is just state++ , when you code a match the transition is always to state = 0. There is a small approximation in my optimal parse; I don't keep individual states for literal run lens > 15. That means I do measure the cost jump when you go from 14 to 15 literals (and have to output an extra byte), but I don't measure the cost jump when you go from 15+254 to 15+255. The optimal parse can be made very very slightly better by using 20 states or so (instead of 16). Then from state 15-20 you count the cost of sending a literal to be exactly 1 byte (no extra cost in control words or literal run len). At state 20 you count the cost to be 1 byte + (1/234) , that is you add in the amortized cost of the 1-1-1-1 code that will be used to send large literal run lengths. While this is better in theory, on my test set I don't get any win from going to more than 16 states. Without further ado, the numbers : raw greedy lazy optimal XXX lz4 -c0 lz4 -c1 lz4 -c2 lzt00 16914 6646 6529 6444 7557 6666 6489 lzt01 200000 198906 198901 198900 198922 198918 198916 lzt02 755121 412064 411107 410549 447200 412085 410705 lzt03 3471552 1827696 1821562 1815464 2024928 1827577 1820776 lzt04 48649 17521 16985 16461 21803 17540 16725 lzt05 927796 484749 462204 459700 518392 484764 460905 lzt06 563160 493815 493056 492938 508281 493838 493071 lzt07 500000 269945 266191 264112 300505 269945 265704 lzt08 355400 332459 332201 330793 335890 332476 331470 lzt09 786488 352802 346700 340317 416708 352821 344807 lzt10 154624 16517 15173 14845 21334 16537 15155 lzt11 58524 26719 26060 25749 30148 26737 25848 lzt12 164423 35168 33504 32485 60450 35187 33682 lzt13 1041576 1042758 1042750 1042749 1045665 1042774 1042765 lzt14 102400 57421 56834 56478 59832 57432 56541 lzt15 34664 14755 14055 13995 15702 14776 14078 lzt16 21504 12503 12396 12340 12908 12528 12365 lzt17 53161 24023 23450 23025 28657 24040 23157 lzt18 102400 86880 86109 85614 88745 86899 85675 lzt19 768771 381018 369110 359276 478748 381033 363233 lzt20 1179702 1051478 1047742 1043192 1073769 1051500 1045195 lzt21 679936 203405 196764 192411 244363 203410 194091 lzt22 400000 363832 362390 361524 371121 363845 361748 lzt23 1048576 1040762 1040758 1040623 1049408 1040778 1040717 lzt24 3471552 2391132 2372991 2369040 2426582 2391145 2369896 lzt25 1029744 328271 326682 324107 370278 328295 324206 lzt26 262144 246951 246876 246334 250159 246972 246481 lzt27 857241 478524 429287 425694 531932 478537 430366 lzt28 1591760 468568 455644 437666 580253 468589 445814 lzt29 3953035 2342525 2259916 2230095 2536827 2342537 2235202 lzt30 100000 100394 100394 100394 100410 100410 100410 total 24700817 15110207 14874321 14773314 16157477 15110591 14816193 raw greedy lazy optimal lz4 -c0 lz4 -c1 lz4 -c2 greedy, lazy, optimal are mine. They all use a suffix array for string searching, and thus always find the longest possible match. Greedy just takes the longest match. Lazy considers a match at the next position also and has a very simple heuristic for preferring it or not. Optimal is the big state table described above. Yann's lz4 -c2 is a lazy parse that seems to go 3 steps ahead with some funny heurstics that I can't quite follow; I see it definitely considers the transition threshold of matchlen from 18 to 19, and also some other stuff. It uses MMC for string matching. His heuristic parse is quite good; I actually suspect that most of the win of "optimal" over "lz4 -c2" is due to finding better matches, not from making better parse decisions. (Yann's lz4.exe seems to also add a 16 byte header to every file) See also previous posts on LZ and optimal parsing : cbloom rants 10-10-08 - 7 - On LZ Optimal Parsing
cbloom rants 10-24-11 - LZ Optimal Parse with A Star Part 1
cbloom rants 12-17-11 - LZ Optimal Parse with A Star Part 2
cbloom rants 12-17-11 - LZ Optimal Parse with A Star Part 3
cbloom rants 12-17-11 - LZ Optimal Parse with A Star Part 4
cbloom rants 01-09-12 - LZ Optimal Parse with A Star Part 5
cbloom rants 11-02-11 - StringMatchTest Release + String Match Post Index
cbloom rants 09-27-08 - 2 - LZ and ACB
cbloom rants 08-20-10 - Deobfuscating LZMA
cbloom rants 09-03-10 - LZ and Exclusions
cbloom rants 09-14-10 - A small note on structured data
cbloom rants 06-08-11 - Tech Todos
(*) ADDENDUM : It turns out you can optimal parse LZ4 without keeping all the states, that is with just a single LZSS style backwards walk and only a 1-wide dynamic programming table. There are several subtle things that make this possible. See the comments on this post : LZ-Bytewise conclusions