Do you have any idea what Ben Jos Walbeehm's DEFLOPT tool actually does?
Available here...
http://www.clrmame.com/download.htm
When I run it on zips created by KZIP, it often manages to shave off a few more bytes.
I'm guessing that it's either removing optional stuctures from the file format and/or re-arranging the file "chunks" within the file to pack them more efficiently somehow.
I'm just curious.
Awesoken at
I've been in contact with Ben Jos recently, so I know a little about it. DeflOpt optimizes the storage of the Huffman tables by running several trials. It tries various strategies, such as disabling the repeat code (16), or disabling the zero run-length codes (17 and/or 18). KZIP and PNGOUT do not perform these trials yet, although I do plan to implement them at some point. DeflOpt is not doing any pattern re-compression - that's why it is so fast. See RFC1951, section 3.2.7 (Compression with dynamic Huffman codes) for more information about these repeat codes.
krick at
Awesoken said
I've been in contact with Ben Jos recently, so I know a little about it.
Very cool. Great minds working together. Good things should happen.
I had another question or two regarding the deflate algorithm...
Is it possible to figure out the truly optimal deflate compession configuration for a file without actually brute forcing your way through every permutation of every variable?
i.e., is this a "traveling salesman" type problem or not. I'm suspecting it is.
Assuming it is, it would be cool to see someone use distributed computing ( http://en.wikipedia.org/wiki/List_of_distributed_computing_projects ) to create truly optimal zip files. I know that it would be a phenomenal waste of computer resources for the small gain but I'd like to see someone do it just to say that it has been done. In fact after compressing enough zip files to optimal compression, I wonder if the statistical data (see next question) would help for building better non-distributed compressors.
Would it be possible to scan a bunch of zipfiles containing similar types of files and use them to build some sort of statistical table that would aid in compressing files of similar type more optimally with less iterations?
To illustrate what I mean, I know from a "connect 4" game that I programmed in college that you can make the minimax algorithm much faster if you know what moves to try first. In the case of "connect 4", if you have the computer AI try the center column first, and then work outward from the center in both directions, it will reach winning end-game positions faster and in less moves.
I'm sure that there are certain combinations of factors in the deflate algorithm that more often lead to higher compression. These combinations should be tried first but knowing what the combinations are and which ones to try probably requires a lot of statistical analysis of optimally (or near optimally) compressed zip files.
And in a related question, is there a tool that can scan an existing zip file and output information about the way each internal file was compressed?
i.e. blocks/splits, run lenghts, huffman tables, etc...
Awesoken at
Is it possible to figure out the truly optimal deflate compession configuration
Deflate is combination of 2 algorithms: LZ77 sliding window compression and Huffman compression. Individually, they are both solvable in reasonable time. Taken together, it looks like a travelling salesman problem. The biggest problem is: how many blocks to use and more importantly, where to place the boundaries. Even if you could find the optimal block boundaries, there is still a problem. When you do the optimal pattern compression, it changes the Huffman table. When you re-optimize the Huffman table, it changes the optimal pattern compression. At best, you could run many passes and fall into a local minima. That's what KZIP does. If there's a way to optimize both Huffman tables and patterns simultaneously, I certainly haven't thought of it.
Would it be possible to scan a bunch of zipfiles containing similar types of files and use them to build some sort of statistical table that would aid in compressing files of similar type more optimally with less iterations?
I doubt that would accomplish much. Statistics only gives you a rough approximation - that's the easy part. It does nothing for the noise which makes up the last 1%.
is there a tool that can scan an existing zip file and output information about the way each internal file was compressed?
You should really get in contact with Ben Jos : ) He wrote this exact utility. I'm sure he would enjoy hearing from you.
Zardalu at
krick said
And in a related question, is there a tool that can scan an existing zip file and output information about the way each internal file was compressed?
i.e. blocks/splits, run lenghts, huffman tables, etc...
The utility Ken referred to is called FlateInfo. You can download it from http://www.walbeehm.com/download/.
And I'm working on a new version of DeflOpt. After a few years of not looking at it, I picked it up again recently. Originally, my idea was only to add PNG support, but while I was working on it, I thought of some more ways to shave off a few more bytes and it works quite nicely. Even better savings than before. Ironically, the current prototype does not do ZIP files, but it does PNG files and I also added support for GZ files. As soon as I have readded ZIP support, I'll make it available.
Ben Jos.
counting_pine at
DeflOpt is a good program. It's nice to hear it will be getting more features. Have you found more ways to shave bits of the headers, or are you trying things like block splitting/combining, or adjusting the positions of the split points?
If it's any use to anyone, I've written a tool that reads the Deflate stream in a PNG file and outputs information about it to a text file. The info it outputs is probably enough to reconstruct the deflate stream bit for bit. It might be a bit much to wade through, but I've found it useful from time to time.
It only really works on PNGs or separate IDAT chunks though, since I found the format easier to work with.
Zardalu at
counting_pine said
Have you found more ways to shave bits of the headers, or are you trying things like block splitting/combining, or adjusting the positions of the split points?
No, none of those things. And, no, I'm not throwing away any optional structures either as was asked earlier. After all, you can trust Ken not to leave any optional structures in there ;), so if DeflOpt did that, it would not be able to shave off a few bytes from KZIP-created files.
Actually, Ken pretty much explained already in an earlier reply what DeflOpt does. I called it "DeflOpt" because that's really all it does... it just optimises some things. It leaves all the hard work to other programs like KZIP, 7-zip, and (the long-retired) BJWFlate. It does not try to find better boundaries or better matches. It mostly just looks at the trees as they were created by the "zipper" and sees if it can use those trees more efficiently.
Let me give an example of one of the main things it does: The Huffman trees for deflating the actual data are themselves encoded and Huffman compressed. I mostly look at those trees, not the ones for the actual data. One of the encodings is the value 16, which means that the last byte that was encoded will be repeated a number of times. The number of times is encoded into 2 bits and the actual number is 3 more than the actual value of those 2 bits. Now, if the last byte was, say, 123 and if the Huffman code for 16 takes up 5 bits, then we could encode a sequence of 3 times 123 in 5+2=7 bits. But if 123 by itself can be encoded in 2 bits, then simply storing it 3 times in a row would take only 3*2=6 bits. After having saved some bits that way, it means that some codes may occur more often and others less often than before. Which means that maybe the code tree can be changed into something slightly more optimal too based on those new frequencies. Repeat this process until no more bits can be saved. There is more to it, but this is the main idea behind DeflOpt.
Ben Jos.
counting_pine at
Sorry, I was quite vague in my question. When I said headers, I meant the Huffman trees stored at the beginning of dynamic huffman blocks.
I've actually had a go myself at making a program to optimise the storage of the trees. The main thing I found difficult was coping with the various different ways of storing multiple zero code lengths. Especially if you allow code 16 to be used. I found a way to do it all optimally, but I'm not sure it was the best way.
And after all that it also suffers from the changing code tree problem. I don't know whether it's possible to find the overall minimum by feeding it a small set of different starting code trees, but you can probably get it quite close.
So, will the new DeflOpt feature a couple more tree storage optimisation strategies?
In any case, the PNG support alone already has me looking forward to it :)
Zardalu at
counting_pine said
Especially if you allow code 16 to be used. I found a way to do it all optimally, but I'm not sure it was the best way.
Optimally but not sure it was the best? That's a contradiction, isn't it? ;)
counting_pine said
So, will the new DeflOpt feature a couple more tree storage optimisation strategies?
Yes, it will. But also, it doesn't just use tree storage strategies anymore. It actually looks at relatively simple ways to change the trees used for actual data storage as well. I don't change trees in any major ways. I just create a few trees based on the old trees and based on frequencies I've generated. And I use those if they can gain more bits.
Ken told me he found a way to use a given tree optimally. And I believe him. I asked him enough questions about it to be sure that he does. But choosing the actual tree is not optimal. That's where I can still gain a few more bits.
Ben Jos.
Zardalu at
To be more specific, I am not sure I am optimal either. But at some point in my new DeflOpt prototype, I use a number of ways to get a "pretty good" tree. And then I choose the best based on L-codes, D-codes, AND the way to store those (C-codes). It's not optimal yet. I know that. Because I only use 4 different strategies per tree. I don't brute force it. That's my next "project".
Ben Jos.
Zardalu at
This is Ken's forum. And I definitely don't want to take it over or make it seem like it's something about DeflOpt. And I think Ken knows that because I've told him how I feel about forums. But I have made DeflOpt 1.19 available. The last one I wrote 2 years ago. I don't even know what I changed in that one. After those years, I just noticed that I had never made this one publicly available. Don't know if it does better than 1.18.
Ben Jos.
Zardalu at
Won't be. DeflOpt 2.00 doing PNG ZIP GZ... won't be.
counting_pine at
counting_pine said
I found a way to do it all optimally, but I'm not sure it was the best way.
I mean, the implementation of it was a bit ugly. But then, I'm often too harsh on my own code, so perhaps it's OK.
In any case, as long as there aren't any stupid mistakes, it gets the optimal tree storage, for any given set codes to construct it.
It's a lot simpler to do it for the Huffman trees than for the actual file content, because the trees are all stored with run length encoding, while there could be any number of length/distance codes for encoding a byte in the file.
So, for any given number of consecutive codelengths in a tree, there's an optimal way to encode it.
For a run of non-zero codelengths, you just have to know the best way of storing a run of up to 11 codes. (Any more than that, you just put in the optimal encoding for a run of 6, then subtract 6 from the total length)
For a run of zero-codes, I built up a table for the best way to encode each runlength. Higher run-lengths would be expressed as code 0, 16, 17 or 18, plus the optimal way to encode a shorter runlength. You can find out the best combination by brute force.
In my implementation it actually took two tables, where one of the tables wasn't allowed to use code 16, since it couldn't assume the previous code was an encoding of zero(s).
Sorry if all that leaves you confused. It all makes sense in my head, mostly :)
Zardalu said
... But I have made DeflOpt 1.19 available.
That's great. Do you have a link for it? I can only find 1.18 on clrmame.com
If I understand your last post, does that mean you only plan support for .zip in later releases?
Zardalu at
counting_pine said
It's a lot simpler to do it for the Huffman trees than for the actual file content, because the trees are all stored with run length encoding, while there could be any number of length/distance codes for encoding a byte in the file.
Right. That's why DeflOpt is so fast. Only a very limited number of possibilities to try. Then again, I thought of some "trick" recently that I want to implement soon. Brute-forcing some stuff. The main problem is that when you change the L-tree and/or the D-tree, you may be able to find a better C-tree as well. But changing the C-tree might suddenly make a different L-tree and/or D-tree better as well. If it were only a "single Huffman problem", it would be easy, but it's like a "stacked Huffman problem". The way everything is stored, if two codes have the same frequency, it may make a difference whether one of them is a bit longer than the other or the other way around. Because of the repeat codes. It happens "often enough" that one code with a certain frequency will turn out to be one bit longer than another code with that same frequency. And sometimes it's better to choose the first (because it falls into a nice repetition like "repeat the previous code N times") and sometimes the second...
counting_pine said
Sorry if all that leaves you confused. It all makes sense in my head, mostly :)
Makes sense to me. :)
counting_pine said
That's great. Do you have a link for it? I can only find 1.18 on clrmame.com
clrmame.com is not my site and I haven't been in contact with Roman for a long time and, anyway, it seems like he wouldn't even want to host it after some things I read on this site. http://www.walbeehm.com is my site. But I add and delete things on a whim. Either way, at this point, you can find it at http://www.walbeehm.com/download.
counting_pine said
If I understand your last post, does that mean you only plan support for .zip in later releases?
No, I actually wasn't paying attention. DeflOpt will have GZ, PNG, and ZIP support. What I meant to say was that I don't foresee myself working on BJWFlate anymore, at least not any time soon, and so no GZ or PNG support there either.
Ben Jos.
Zardalu at
I've been running DeflOpt against an enormous amount of GZIP, PNG, and ZIP files the past several days. So far so good. The only thing I am not entirely satisfied about is when running DeflOpt in verbose mode and it is parsing PNG files. It will display some information that is incorrect in case of more than one IDAT chunk. And in the extreme case of a large number of IDAT chunks all of length 1 (PNGSUITE contains a few of those) (or even 0), it would display some more incorrect information. But that's only what it displays in verbose mode. Those incorrect things don't affect non-verbose mode, and, most importantly, it will not affect the actual files DeflOpt creates.
I still have some more ideas to make DeflOpt even better, but 2.00 seems very stable now so I will probably release it this weekend. And then start a new development cycle for the next, even better version. Like I said, I have more ideas and from some preliminary testing, I already know that I can still gain even more bytes here and there. In addition to that, I have a PNG image that I use as one of my guidelines... an image I have not been able to gain any bits on so far... unionjack.png...
Ben Jos.
counting_pine at
I'll be looking forward to the next release :)
How big is your unionjack.png? I managed to get a 3012 byte version using PNGOUTWin.
Zardalu at
counting_pine said
I'll be looking forward to the next release :)
It is going to be a bit delayed. Hopefully some time this week. Wanted to write up a little bit of documentation, but that's a lot less interesting than programming. ;)
counting_pine said
How big is your unionjack.png? I managed to get a 3012 byte version using PNGOUTWin.
3,011 bytes, but that is one that Ken sent me. So far, I haven't managed to gain even one bit on that one.
Ben Jos.
Zardalu at
I have just released DeflOpt V2.00.
http://www.walbeehm.com/download/
This is Ken's forum, not mine, so anything related to DeflOpt should be sent to me directly, not posted publicly on this forum. Read DeflOpt.txt.
Ben Jos.
Awesoken at
I have no problem with people using my forum to comment on DeflOpt. I think a dedicated thread would be sensible. If you have technical questions, please make sure to direct them to Zardalu/Ben Jos, and not myself : )
BTW, I found a grammar problem in your included text file. Search for "will be ALWAYS be removed"
Edited at
Zardalu at
Awesoken said
I have no problem with people using my forum to comment on DeflOpt. I think a dedicated thread would be sensible. If you have technical questions, please make sure to direct them to Zardulu/Ben Jos, and not myself : )
Thanks, Ken. :)
Awesoken said
BTW, I found a grammar problem in your included text file. Search for "will be ALWAYS be removed"
Damn. I hate when I do that. It happened because I swapped some words around. Either way, I think I should add some more text to it regarding wildcards, so I will correct that stupid mistake then. Its wildcard handling works as I intended, but that does not mean that it works as someone else might expect. Thanks again, Ken.
Ben Jos.
Zardalu at
Awesoken said
Zardulu/Ben Jos
ZardAlu. :P
(It's the name of a race of aliens in several books by Charles Sheffield. The name is used as both singular and plural.)
Ben Jos.
ace_dent at
It would be cool if you could add a 'silent' switch to the program. I run various png optimization tools from a batch against 1,000s of icons, and want minimal output in my batch window.
The documentation could be improved by simply providing the help text from the program in the help text file you provide. Ideally this would go before "As the examples show, options..."
Cheers,
Andrew
Zardalu at
I see what you mean... like an "extra help" switch and a "silent" switch.
fred01 at
Would it be also possible to add a logging option so that the output is redirected to a file? This might be useful for analysing the impact of DeflOpt, like over several zipmax runs.
I also run into an
ace_dent at
Sorry, to just clarify...
- Silent switch: code feature to supress output text
- Documentation: I was referring to copying the help text out of the program into the text document 'DeflOpt.txt' (no code change). This will improve user 'out of box' experience,