tag:blogger.com,1999:blog-5246987755651065286.post427188576185585430..comments2024-02-22T16:15:42.388-08:00Comments on cbloom rants: 01-09-12 - LZ Optimal Parse with A Star Part 5cbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-5246987755651065286.post-22515566458405118822012-01-15T11:01:59.148-08:002012-01-15T11:01:59.148-08:00Though only something like 1-3%Though only something like 1-3%cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-59105707864862497082012-01-15T11:00:54.622-08:002012-01-15T11:00:54.622-08:00Yes!Yes!cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-8067549901272490302012-01-15T04:00:19.138-08:002012-01-15T04:00:19.138-08:00So it basically means that current LZMA could get ...So it basically means that current LZMA could get even better compression performance by using one of your methodologies ?Cyanhttps://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-42033923189979483262012-01-12T14:28:14.913-08:002012-01-12T14:28:14.913-08:00"What's the relative speed of the Chain* ..."What's the relative speed of the Chain* variants compared to A*"<br /><br />A* is a lot more variable. It can be as fast as Chain3 or so, but sometimes as bad as Chain6 or so.<br /><br />"and how much slower is ChainN compared to Chain1 (assuming a Suffix Tree or similarly fast match finder)? "<br /><br />First of all, something I maybe didn't point out is that both for ChainN and A* to be reasonably fast you have to pre-find all matches. So I decide in advance that I will consider at most 8 matches per position, and I go find all those matches and save them in an array. So you never redo match finding as you parse.<br /><br />If it's 8 matches, then Chain N+1 is 8X slower than Chain N.<br /><br />I should make clear that even if Chain was fast enough, it's not super awesome because it uses a pretty rough approximation for the cost to end after the N steps which doesn't include the current state at all. A* doesn't have this drawback.<br /><br />At the moment Chain is more usable in production because I haven't found a good way to control the occasional very long time that A* takes.cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-56743625256294529622012-01-11T20:20:41.629-08:002012-01-11T20:20:41.629-08:00What's the relative speed of the Chain* varian...What's the relative speed of the Chain* variants compared to A*, and how much slower is ChainN compared to Chain1 (assuming a Suffix Tree or similarly fast match finder)?ryghttps://www.blogger.com/profile/03031635656201499907noreply@blogger.com