|
<< ctxmodel.net
2008-07-02 07:33:44 Shelwien >
As to CM compressor, there's that for now - http://compression.ru/sh/ash04.rar As to fpaq0pv4b - that's surely not anything final. Many ideas left, but I need some feedback to work on it.
2008-07-02 08:59:32 Shelwien >
I agree about that. Anyway ash is too old, and was targeted at stationary data (mostly text), and was never optimized for speed. But now I don't have any use for a higher order CM compressor, except for maybe Hutter Challenge but that requires a completely different approach, certainly not universal. However its still possible that I'd write something like that, if there'd be some interesting discussion of the topic. And to try and start such a discussion I was talking too much on encode.ru forums and even started this site. So eventually I may write a said CCM/LPAQ competitor, but can't say how soon that'd happen. Especially considering that it requires like a day of coding to make a alpha version ;)
2008-07-02 12:57:08 inikep >
I'm sure that there will be some interesting discussion when you'll create a CCM/LPAQ competitor. The main goal for this should be creating a fast open-source CM library (it can be commercial, but free for non-commercial use) that will replace Shkarin's PPMd. When do you have a free day? (as I'm waiting for an alpha version :)
2008-07-03 01:12:26 Shelwien >
> I'm sure that there will be some interesting discussion when > you'll create a CCM/LPAQ competitor. But I need a discussion _before_. Eg. If I was asked to do it as a job, I'd consider: 1) Optimizing LPAQ or 2) PAQ9a 3) Optimizing PPMd or 4) PPmonstr (I have a decompiled source) 5) Decompiling CCMx and optimizing (though a single day certainly won't be enough to get an improvement) And my own coders are out of the question here (though I surely would try to replace things, like mixers, with my own), because I don't like implementing the inferior techniques, and messing with experimental ones would take a lot of time. > The main goal for this should be creating a fast open-source > CM library (it can be commercial, but free for > non-commercial use) that will replace Shkarin's PPMd. I'm all for open source and won't even bother with GPL probably. But anything replacing PPMd is kinda unbelievable, because eg. rar still uses PPMd vH (instead of significantly better vJ), and most people don't even know rar and use only zip. > When do you have a free day? (as I'm waiting for an alpha > version :) Well, there's already 5 choices listed, and I cannot choose myself, because I don't like doing any just for fun. And going my own way, I still need to settle with: 1) Alphabet - plain bytewise (a fast implementation is possible with vectors), bitwise, unary. composite unary/binary. Also there's a sense to support a larger alphabet, like 16bit for unicode (and utf8) encoding. 2) Statistic storage - hash, suffix tree, dynamic calculation caching, and many intermediates. 3) Coder type - choosing a multiplication-free coder affects statistics' storage and processing. Also less precise coders are faster, but restrict the statistics precision. 4) Parsing style - full CM is slow, plain PPM is too redundant, a PPM-like with optimal parsing would be highly asymmetric and considerably complex, etc. 5) Redundancy analysis - are segmentation and simple fallback algorithms necessary, or they can be left out? 6) Preprocessing - do we need a multiple stream support (used by eg. advanced executable filters)? also there's a dependence on alphabet size in dictionary filters. 7) Multithreading - how many cores to support? Care to answer? :)
2008-07-03 12:12:27 Anonymous >
>1) Alphabet - plain bytewise (a fast implementation is possible with vectors), bitwise, unary. composite unary/binary. Bytewise is risky. AFAIK nobody has created a fast and effective byte-wise CM compressor. >Also there's a sense to support a larger alphabet, like >16bit for unicode (and utf8) encoding. I think that there is no sense as Unicode files can be easily converted to UTF8 (e.g. in preprocessing). >2) Statistic storage - hash, suffix tree, dynamic calculation >caching, and many intermediates. The fastest one :) >3) Coder type - choosing a multiplication-free coder affects >statistics' storage and processing. Also less precise coders >are faster, but restrict the statistics precision. Results from http://www.maximumcompression.com/data/summary_mf.php : PAQ8O8 64042114 bytes in 43660 s LPAQ8 78704186 bytes in 1312 s CCM 1.30c 78598980 bytes in 277 s PPMonstr J 78086417 bytes in 1628 s PPMd.J1 96737515 bytes in 172 s For me it's obvious that PPMonstr/LPAQ won't replace PPMd.J1. But a CM compressor that has similar/the same speed and better compression have a great chance. So the goal is to achieve 70-86 MB (10-27% better than PPMd.J1) at similar/the same speed (172-277s). CCM did it, but won't be popular as it's not open-source. 4) Parsing style - full CM is slow, plain PPM is too redundant, a PPM-like with optimal parsing would be highly asymmetric and considerably complex, etc. If I were you I'd start using a good tested recepit: Christian wrote (encode.ru forum): If I recall correct ccm mixes orders 1-6. It does nibble based hashing with simple collision handling. Additionally, it has a match model which is quite similar to that of lpaq1. Besides, it does have some sparse models and models some other stuff implicitly. Further on, you can implement a mechanism to turn models on/off on the fly to improve speed. You should definitely add some probability mapping and dynamic model mixing since plain "naked" models and fixed weights gently tend to leave a lot of bits behind. Some simple data filters can help, too. As a note, if you want to go for speed you'll have to decide against compression ratio almost always.
2008-07-03 13:39:17 Shelwien >
> > 1) Optimizing LPAQ or 2) PAQ9a > Do you think that it's possible to improve its speed about 3x? 2x for sure, dunno about 3x. Replacing the counters and mixers would certainly make it faster, and then its written in not IntelC-friendly way. > Christian (CCM author) wrote: > PAQ is really great, but you should not use it as a template > in order to write a fast context mixer. Sure, and I'm usually saying the same about Matt's works. But still the easiest way to beat LPAQ is to optimize LPAQ Actually that's the point of what I'm talking about - there're formal but boring ways to reach the goal, and then there might be a "right" way, but who knows where it is. > > 3) Optimizing PPMd or 4) PPmonstr (I have a decompiled source) > I think that PPMd/PPmonstr is not a good base for CM compressor. > The main problems: > a) it's a PPM compressor (a byte-wise alphabet, many changes > in source are needed if you want to use a bit-wise alphabet) PPM is necessary if you want speed. Also bitwise coding is wrong, though simple in some cases. Its wrong because there're no bitwise-generated files, and its really hard and impractical to try it with almost any design except for direct coding and simple mixing. I'd even bet that these fast bitwise CM coders are CM only because PPM masking would be too slow and complex with bitwise scheme. > b) unreadable sources (I've spent many days on this code and > for me it's still hard to read) Dunno. In the case of PPMd there's not much of code, and anyway I'm usually reformatting all the code I'm working with so that I can easily read and edit it. > > 5) Decompiling CCMx and optimizing > 1. It's not legal (It won't be possible to create a public CM library) I don't care. I'm only talking about that because I'm not interested in actually doing it, but you can compare the original fpaq0p and fpaq0pv4B source - I think its impossible to prove that v4B is evolution of v1. And of course with reverse-engineered source that would be even more applicable, and it won't even have the same performance as original because I'd modify it. > 2. You'll get ASM code, which is still not good to create > a public CM library I said "decompiling", not "disassembling". Check out http://www.hex-rays.com/decompiler.shtml or something. > > And my own coders are out of the question here > > Why? I believe that the easist thing for you is to create a > CM compressor on the basis of your order-1/order-2 CM. > Only orders 3-6 and match model are missing. As I said, I don't like some things and a hash for statistics is one of them, so it'd be easier for me to hack out all the internals from LPAQ except for hash, than forcing myself to add it into my own program. Also I don't like preprocessing hacks either, and LPAQ is full of that. So with my own source, I'd try to design a good data structure for statistics and some proper filters (like a disassembler for executables instead of E8), and it'd take forever :) Though well, guess I can patch together an order6 coder if you want it that much. But even before doing it I know that both its speed and quality would be nothing special. Btw, you can write to shelwien@gmail.com instead.
2008-07-03 14:34:49 Shelwien >
> Bytewise is risky. AFAIK nobody has created a fast and > effective byte-wise CM compressor. I think that nobody tried. The previous generation of compressor developers (which I am part of) got busy... or lazy, and the "new wave" is heavily affected by paq series. And anyway this topic is far from being popular - there're too few people who do anything at all. > > Also there's a sense to support a larger alphabet, like > > 16bit for unicode (and utf8) encoding. > I think that there is no sense as Unicode files can be > easily converted to UTF8 (e.g. in preprocessing). Well, and I think that compression can be improved by converting utf8 back to unicode. We won't know for sure until someone tries, right? ;) > > 2) Statistic storage - hash, suffix tree, dynamic > > calculation caching, and many intermediates. > The fastest one :) And this isn't the answer either, because making a good implementation of each structure for fair comparison would take a considerable time. >>3) Coder type - choosing a multiplication-free coder affects >>statistics' storage and processing. Also less precise coders >>are faster, but restrict the statistics precision. Still, do we need a multiplication-free coder or not? > CCM did it, but won't be popular as it's not open-source. Well, I tested it a little and I surely don't like how it handles texts... while PPMd is advertised as a "text compression method" in archivers. But its compression of binaries is certainly good. > it does have some sparse models and models some other stuff > Some simple data filters can help, too. These things are what's important here, and they're not explained.
2008-07-03 17:09:43 inikep >
> PPM is necessary if you want speed. CCM doesn't use PPM. > Its wrong because there're no bitwise-generated files But order-1 PPM gives worse compression than order-1 CM. > I said "decompiling", not "disassembling". > Check out http://www.hex-rays.com/decompiler.shtml > or something. Interesting. Some time ago I've tried http://boomerang.sourceforge.net/ , but results were poor. > In the case of PPMd there's not much of code, > and anyway I'm usually reformatting all the code I'm working > with so that I can easily read and edit it. It's not so easy with PPMd/PPMonstr as Dmitry has problems with finding the bugs. http://www.winturtle.netsons.org/MOC/MOC.htm : FAILS ON MOC - PPMD rev. J (guru meditation) > it'd be easier for me to hack out all > the internals from LPAQ except for hash If you'll do it by yourself it can be much faster. > So with my own source, I'd try to design a good data structure > for statistics and some proper filters I'm talking only about pure compressor without any filters. Filters can be added later, filters can be external. > Btw, you can write to shelwien@gmail.com instead. You can write to inikep@gmail.com. > Well, and I think that compression can be improved by > converting utf8 back to unicode. > We won't know for sure until someone tries, right? ;) Yes. For English, French, German it almost doesn't matter as most letters come from Latin alphabet (1 byte in UTF8). It should be bigger difference for Russian, Chinese,... > 2) Statistic storage - hash, suffix tree, dynamic calculation > caching, and many intermediates. > Still, do we need a multiplication-free coder or not? I can answer take hash, take multiplication-free coder, and so on. But you have more experience and knowledge to choose by yourself. Concluding, in my opinion with you skills you can try to create a fast CM compressor instead of e.g. improving order1/2 coders. It'd be a success if it'd achieve 70-86 MB (10-27% better than PPMd.J1) at similar/the same speed (172-277s). In this case it'd have a chance to take place of PPMd and I'll help to promote it.
2008-07-03 18:40:20 Anonymous >
-Bitwise coding = Permits using parts of current byte as context. Bytewise,Nibble? -Statistic storage: hashing always faster than other data-structures (even cache concscious/oblivious DS). -what's about preprocessing? Dictionary, lzp,... -can the compression/speed in PPMD be improved on modern processors by replacing the bytewise ari-coder with your bitwise-coder ?
2008-07-04 00:46:11 Shelwien >
> > PPM is necessary if you want speed. > > CCM doesn't use PPM. I know, but it only means that something faster is possible. In fact, its natural to use a single context, because that's how most of data is generated. But as I said, it might get really complex if we try to make a PPM with optimal parsing. > > Its wrong because there're no bitwise-generated files > > But order-1 PPM gives worse compression than order-1 CM. You are talking about specific implementations, not methods. And PPMd is a wrong example for comparison - its too old, and was a speed trade-off even in that time (btw, it would be probably _much_ faster on old or embedded platforms than the new compressors with their hashes). Also if order-1 PPM would cause significant redundancy, it could be easily switched to order-1 mixing. But the point of PPM is that only a single counter is updated per byte, most of the time. > - PPMD rev. J (guru meditation) I think its more like he has problems with finding the motivation to fix the bugs. > > it'd be easier for me to hack out all > > the internals from LPAQ except for hash > > If you'll do it by yourself it can be much faster. Well, I tend to get really slow when given too much choice. > I'm talking only about pure compressor without any filters. > Filters can be added later, filters can be external. Right, but that would be a completely different compressor. At least, all the parameters have to be retuned for use with filters. > > Well, and I think that compression can be improved by > > converting utf8 back to unicode. > > We won't know for sure until someone tries, right? ;) > > Yes. For English, French, German it almost doesn't matter Well, I was talking about enwik8. > > 2) Statistic storage - hash, suffix tree, dynamic calculation > > caching, and many intermediates. > > > Still, do we need a multiplication-free coder or not? > > I can answer take hash, take multiplication-free coder, and > so on. But you have more experience and knowledge to choose > by yourself. Maybe, but I can't choose, that's why I'm asking. Any technique has its disadvantages, and there's no single best choice. A hash... well, ok, but I don't have a good multiplication-free coder - they generally cause like 10% redundancy. Would you wait until I invent something reasonable? ;) Or can you suggest something? :) > Concluding, in my opinion with you skills you can try to > create a fast CM compressor instead of e.g. improving > order1/2 coders. It'd be a success if it'd achieve 70-86 MB > (10-27% better than PPMd.J1) at similar/the same speed > (172-277s). In this case it'd have a chance to take place of > PPMd and I'll help to promote it. I already agreed to try and make an order6 coder based on o1rc. But still I believe that much more research is needed to really create a new "standard". > > -Bitwise coding = Permits using parts > > of current byte as context. > Bytewise, Nibble? Now, just where the prefix of current byte can be a good context? With some analog data? But that requires a special model anyway. And nibble is out of the question, because it combines all the flaws of both bitwise and bytewise schemes. Imho the best is to use unary coding for a few most probable symbols, and then switch to binary. But how to implement the counters for such a design (changes in symbol ranking would require recomputing the probabilities) and what kind of storage to use with these counters (access to statistics of the whole alphabet is necessary, and there basically should be a single node per symbol, but for the binary part the cumulative probabilities should be used) - that still has to be investigated. > -Statistic storage: hashing always faster than other > data-structures (even cache concscious/oblivious DS). Imho PPMd demonstrates that they're not faster. Maybe a single hash is ok, but using multiple hashes at once (at least one per each order) is surely slow. Also other structures allow to take care of more correlations in the data, and better peak compression would open more possibilities for speed trade-offs - like skipping updates or something. > -what's about preprocessing? Dictionary, lzp,... And who just said "Filters can be added later, filters can be external."? ;) > -can the compression/speed in PPMD be improved on modern > processors by replacing the bytewise ari-coder with your > bitwise-coder ? Ppmonstr uses a bitwise coder btw. But yes, probably. Anyway, it has to be fully redesigned for speed optimization - eg. there're too much branches which are very unhealthy for modern architectures. Basically, a random branch might be worse than a division.
2008-07-04 06:31:24 inikep >
>But the point of PPM is that only a single counter is >updated per byte, most of the time PPMd is more complicated. In his paper Dmitry calls it PPMII (PPM with Information Inheritance). >I was talking about enwik8 AFAIR, on enwik8 adding UTF-8 encoded words to a static/semi-dynamic dictionary gives almost nothing in compression ratio. >they generally cause like 10% redundancy >Would you wait until I invent something reasonable? ;) >Or can you suggest something? :) Yes, take what do you have and do create a preliminary version of a CM compressor :) I'll see speed, ratio, and places for improvements. Then you can decide if it's worth to continue or to abandon. >I already agreed to try and make an order6 coder based on o1rc. Great. I'm trying to give you some motivation. I believe in your skills, but if you don't have time or you are not convinced (quoting "I know that both its speed and quality would be nothing special") we can forget about it. >And who just said "Filters can be added later, >filters can be external."? ;) Somebody else :) The second post is not mine.
2008-07-04 06:41:14 inikep >
>And who just said "Filters can be added later, >filters can be external."? ;) I said it, but the second post is not mine. Somebody else said: "what's about preprocessing? Dictionary, lzp,... "
2008-07-04 07:47:56 Shelwien >
> > But the point of PPM is that only a single counter is > > updated per byte, most of the time > PPMd is more complicated. In his paper Dmitry calls it > PPMII (PPM with Information Inheritance). I know, but the inheritance part doesn't affect the speed much, because its just a method of counter initialization. As to partial updates, I'm not sure whether it got used in PPMd (I mean, not ppmonstr), and anyway its not that necessary if we're optimizing for speed. > > I was talking about enwik8 > AFAIR, on enwik8 adding UTF-8 encoded words to a > static/semi-dynamic dictionary gives almost nothing in > compression ratio. Well, these dictionary filters are redundant (as there're multiple encodings of the same byte string), and also paq8, being a bitwise coder, doesn't benefit much from reduced alphabet size. Btw, considering bitwise coding, there's a good demonstration of its main flaw: breaking the archive of some text and checking for how long the random data would be decoded as text (its a CM-driven text generation, in fact). I mean, paq8 compresses texts better than bytewise compressors (well, they're old), but the data generated by it becomes a total garbage much faster than if we try it with ppmonstr or ash. > Yes, take what do you have and do create a preliminary > version of a CM compressor :) I'll see speed, ratio, and > places for improvements. Then you can decide if it's worth > to continue or to abandon. I'm at order3 for now, but its already hashed, so I expect reaching the order6 later today. > Great. I'm trying to give you some motivation. Yeah, and it works. You see, I just can't knowingly make something imperfect, unless I have an application for it, or somebody asks me to. > I believe in your skills, but if you don't have time or you > are not convinced (quoting "I know that both its speed and > quality would be nothing special") we can forget about it. I'm not particularly busy now, so we'll have a result soon. Btw, my current tuning target is book1 wcc386 (concatenated), and the current result (at order3) is 501877.
2008-07-04 11:10:15 inikep >
>I expect reaching the order6 later today Great >I just can't knowingly make something imperfect, unless I have an application for it So you are a perfectionist. I believe that there is always a place for improvement, no matter on efforts.
2008-07-04 13:49:32 Anonymous >
I've made some experiments with your test file (1305395 bytes?) with lpaq1. I've disabled different models to observe decrease in compression ratio and speed up. The result are in the following format: compressed size, time, options (1-6=order, w=word, m=match, a=APM) 459393, 4.970, lpaq1_12346wma 465501, 4.240, lpaq1_12346wm 467635, 4.000, lpaq1_12346w 476578, 4.027, lpaq1_126wm 478806, 4.093, lpaq1_1234m 487625, 3.692, lpaq1_1234 511813, 4.212, lpaq1_346wm 517927, 4.188, lpaq1_12m 565988, 2.796, lpaq1_12 575895, 3.571, lpaq1_6wm 586437, 3.495, lpaq1_34 609838, 3.330, lpaq1_6w 726609, 2.299, lpaq1_m
2008-07-04 14:07:14 Anonymous >
464842, 3.234, ccm 6 464867, 2.653, ccm 5 466970, 0.783, ccm 0
2008-07-04 14:48:14 Shelwien >
Thanks for testing, here's what I currently have: 1305395 // book1 wcc386 822161 // o1plain (straight o1 w/o mixing) 659612 // toffer's m01 (o1) 640942 // o1rc9j (o1 with 3 mixers) 569607 // o2mm (o2 with 2 mixers) 566845 // toffer's m012a (o2) 550491 // (tmp) o1rc9j4 hashed o2 result 543881 // (tmp) o1rc9j2 straight o2 501705 // (tmp) o1rcj5 (o3) 481925 // (tmp) o1rcj6 (o4) 476667 // (tmp) o1rcj7 (o5) // E8 added 531182 // (tmp) o2mix 485524 // (tmp) o3mix 468279 // (tmp) o4mix 463373 // (tmp) o5mix 462253 // (tmp) o6mix
2008-07-04 16:57:05 i > Result are good! Good job! What about speed?
2008-07-04 17:51:13 Shelwien >
Slow enough, but speed can be improved if compression quality allows that. I intend to run a proper benchmark with ccm and maybe lpaq, but I have to stop optimization for that. Well, you can test this yourself for now http://ctxmodel.net/files/o6mix.exe
2008-07-05 03:05:32 Shelwien >
The merged results: a10 acrord32 english flashmx fp.log ccm5 832483 1191245 499597 3670609 440405 PPMd -o8 833778 1544682 1095161 3717851 609367 lpaq8 7 823026 1139912 412535 3629400 359231 o6mix 841823 1337534 623998 3771525 653217 mso97 ohs.doc rafale vcfiu world95 ccm5 1613968 762710 774758 537789 497682 PPMd -o8 1867250 831662 789486 651130 462663 lpaq8 7 1547386 734189 721553 488446 427349 o6mix 1748500 879422 771885 683528 568787 ccm5 10821246 42.924s PPMd -o8 12403030 14.538s lpaq8 7 10283027 116.590s o6mix 11880219 156.838s And these are results for my optimization target: [source] [ppmd] [lpaq] [ccm5] [o6mix] book1 768771 210264 202579 225706 215138 wcc386 536624 279766 232014 239110 243578 book1_wcc386 1305395 489965 453176 464867 460361 I think the distribution is similar, so its not a matter of wrong target choice.
2008-07-05 08:11:38 inikep >
>speed can be improved if compression quality allows that. There results (o6mix) are without a match model?
2008-07-05 12:15:15 Anonymous >
Your results seem to be quiet good, regarding the fact that you don't use "per model context merging", which is implicitly done using FSM. For a future project i plan to use delayed counters and a secondary model (per primary model), which estimates probabilities based on a quantisation of a primary model's counter sate. A final estimate is a static mix of both probabilities. This should allow to be more than competative to the FSM approach at higher orders. For CMM4 i also tried to use simulate a linear counter in the logistic domain. The results are ok, but there was no speed increase, since this approach doesn't require "stretch"-transformation prior to mixing.
2008-07-05 12:15:43 toffer >
Whoops, forgot to include my name in the above post...
2012-08-29 19:41:29 Anonymous > But ZCM compressor is not considered ?
2012-12-04 01:24:21 Shelwien > its too new for this discussion :)
2013-08-01 17:10:59 >
2014-11-27 03:44:18 >
2014-12-11 06:36:48 buy+viagra+on...>
Thank you for sharing your info. I really appreciate your efforts and I am waiting for your next post thank you once again
2015-01-12 04:05:52 >
|