tag:blogger.com,1999:blog-834134852788085492.post2198797850829117155..comments2024-03-02T07:59:30.808+01:00Comments on RealTime Data Compression: Progressive Hash Series : a new method to find repetitionsCyanhttp://www.blogger.com/profile/02905407922640810117noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-834134852788085492.post-25924061881191773012011-11-14T19:37:57.272+01:002011-11-14T19:37:57.272+01:00That's great news ! I'm glad it helped.
N...That's great news ! I'm glad it helped. <br />Nice reading your blog entryCyanhttps://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-84257340869408339522011-11-13T00:44:53.135+01:002011-11-13T00:44:53.135+01:00Merci beaucoup pour cet article!
I just finished ...Merci beaucoup pour cet article!<br /><br />I just finished a writing a PNG encoder for Flash (http://moodycamel.com/blog/2011/a-better-png-encoder-for-flash), for which I re-implemented DEFLATE in haXe. I used your method to make the GOOD compression level fast enough to be competitive with the C zlib library :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-59968565540645572642011-10-25T12:11:49.097+02:002011-10-25T12:11:49.097+02:00Yep, that's exactly that.Yep, that's exactly that.Cyanhttps://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-65028766951054305812011-10-25T00:22:24.968+02:002011-10-25T00:22:24.968+02:00"We need to know if the moved position is MML..."We need to know if the moved position is MML-3, or MML-4, "<br /><br />What does this mean? You store in the slot the mml of the entry there?<br /><br />If I understand this correctly, something like this will happen :<br /><br />Say I have in the hash :<br /><br />supx... (mml 3)<br />supbx.. (mml 4)<br />supbdx... (mml 5)<br /><br />then I add "word" which hashes to the same slot as "sup" (mml 3). I will replace it and push all the sups deeper down their list.<br /><br />Now any attempt to match "supy" will fail to find an mml 3 slot. You could still try the mml 4 slot but "supy" doesn't match at mml 4.<br /><br />But then I will add "sup" to the tree at mml 3 and that will fix the chain.<br /><br />So basically the chain can get screwed up due to hash collisions, but it will get fixed in the next update. That's cool.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-83415702415239481062011-10-22T10:14:11.672+02:002011-10-22T10:14:11.672+02:00Hi Charles
The proposed scheme is to insert alway...Hi Charles<br /><br />The proposed scheme is to insert always at MML=MinMatch slot. If the slot is already filled, then the current occupier has to move on (because it is necessarily older).<br /><br />After that, it becomes more complex, but that's also where many improvements can be made.<br /> <br />We need to know if the moved position is MML-3, or MML-4, since we will move it to MML-N+1.<br />At the new position, a collision might occur again, so we have to solve it again. Either one of the 2 positions is eliminated, and the swapping ends there, or the youngest one occupy the slot.<br />Therefore, in the second case, the older position has to move again.<br />And so on.<br /><br />This might seem worrying, since it means that we could be swapping many slots for a single position update. But in fact, we've got ample room to control that : elimination rule will ensure that, at some point, the update process stops.<br /><br />For the example provided in this article, the only elimination rule was : if a position is stored at its MML=Minmatch+Maxattempts slot, it's eliminated. Obviously, more aggressive elimination rule can ensure the update stop sooner (for example, adding a max_distance).Cyanhttps://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-53122371769648774692011-10-22T05:53:04.540+02:002011-10-22T05:53:04.540+02:00LZO (among others) use the idea of storing multipl...LZO (among others) use the idea of storing multiple hashes in the same hash table. My current fast LZH stores a min-matchlen-3 and mml-5 hash in the same table.<br /><br />It sounds like your update scheme may be better, but I don't understand it completely.<br /><br />If you look for a MML of 3 and don't find a match, do you stop searching? Or go ahead and search the MML-4 slot? (you could fail to find an MML-3 but find an MML-4 due to collisions)<br /><br />When you add to the hash, you start at MML 3, if you find a hit already there, you move it to the MML 4 slot, does that then move to the MML 5 slot?cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.com