tag:blogger.com,1999:blog-834134852788085492.post5165911176443240925..comments2017-03-23T16:37:11.159+01:00Comments on RealTime Data Compression: Huffman revisited, Part 4 : Multi-bytes decodingCyanhttps://plus.google.com/117014154967737150730noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-834134852788085492.post-57824099354738619742015-10-16T14:41:05.481+02:002015-10-16T14:41:05.481+02:00If I only had time to work on everything I see val...If I only had time to work on everything I see valuable and interesting ...<br />Best,<br />JarekJarek Dudahttp://www.blogger.com/profile/11358050996148333936noreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-58079880372226437392015-10-16T13:42:42.921+02:002015-10-16T13:42:42.921+02:00I can only invite you to test these great ideas on...I can only invite you to test these great ideas on a custom FSE version. I can guess multiple issues that will have to be solved while making this direction viable, and maybe you could solve them all.<br />Yann Collethttp://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-66917656079701967782015-10-16T13:25:53.665+02:002015-10-16T13:25:53.665+02:00Sure, the objective is to speedup - by processing ...Sure, the objective is to speedup - by processing a few symbols at once.<br /><br />Initialization is first going once through all the positions (e.g. 4092) for your fast spread, then again to build the tables ( https://dl.dropboxusercontent.com/u/12405967/tANSalg.png ).<br />So increasing the alphabet doesn't cost time.<br />Its memory cost is mainly (+start+nb) a few more bits for the symbol in decodingTable, but it can be handled by a bit compression: 2 bytes are sufficient for "symbol + nbBits".<br /><br />Assume there is this various length grouping of symbols (e.g. B,C,D, ..., AA, AB, AC, AD ... ) - for example chosen from counts of the previously decoded data frame (e.g. 32kB).<br />Now, for the next data frame, the encoder counts occurrences of these grouped symbols (improving order of the method), the decoder decodes groups of symbols, exactly as in your post.<br /><br />The main cost is increased header: decoder needs to know frequencies on the extended alphabet (B,C ..., AA, AB ...) - for improving the order of the method (compression ratio).<br />It could be compensated by increasing data frame, and generally there should be stored differences of frequencies comparing to the previous frame...Jarek Dudahttp://www.blogger.com/profile/11358050996148333936noreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-19134413292053143662015-10-16T12:39:49.814+02:002015-10-16T12:39:49.814+02:00It sounds interesting, but we should keep in mind ...It sounds interesting, but we should keep in mind the objective.<br />The reason I've tested multi-bytes decoding for Huffman is speed. And within this speed budget, there is "table construction" phase.<br />It's just counter-productive to plan some gain on the decoding side if the table construction time now dominates the total operation.<br /><br />Also, note that FSEU16, the variant which can handle alphabet > 256, is slower than the regular FSE variant.Yann Collethttp://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-92171218423160189892015-10-16T12:33:19.643+02:002015-10-16T12:33:19.643+02:00As you guessed, the issue with FSE is that it woul...As you guessed, the issue with FSE is that it would only work for dominating symbols > 50%, and even then, it would only be worthwhile if one symbol is really frequent (such as P80).<br />So it's more of a corner case.Yann Collethttp://www.blogger.com/profile/02905407922640810117noreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-52776599784488494192015-10-16T08:29:32.528+02:002015-10-16T08:29:32.528+02:00A different view: what you are doing is grouping a...A different view: what you are doing is grouping a varying number of symbols, such that the probability of each group is above some threshold (e.g. 1/4096).<br />You could perform such groping separately (remembering about the prefix condition), additionally improving the order (compression ratio).<br /><br />So we need a prefix tree, but with symbols in branches instead of bits - degree of nodes is alphabet size instead of 2.<br />For example assuming dominating symbol A, such prefix-free grouping can be:<br />B,C,D, ..., AA, AB, AC, AD ... <br />doubling the size of alphabet, but also increasing speed and order of the method (compression ratio).<br />the next step would be tripling the alphabet:<br />B, C, D, ... AB, AC, AD, ... AAA, AAB, AAC, AAD ...<br /><br />An example of general expansion algorithm: <br />until exceeding some alphabet size, take the most probable leaf and expand it (in above examples, first A was expanded, then AA).<br /><br />Remember that tANS is not limited to 256 symbols. Using 4096 states, you could easily handle even >1000 size alphabet - it just approximates probabilities as q/4096 (a bit better with tuning).Jarek Dudahttp://www.blogger.com/profile/11358050996148333936noreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-1461108686062523542015-10-16T07:24:23.227+02:002015-10-16T07:24:23.227+02:00Hi Yann,
You can do something similar with FSE - w...Hi Yann,<br />You can do something similar with FSE - when the succeeding symbol(s) is uniquely determined by the current state only - what happens for high probability symbols (pr > 0.5).<br />It is always true when there are no bits read (just growing state).<br />When a single bit is read, the new state is x or x+1, if both have identical symbol (successive occurrences), you could read one more symbol and do the "+1" then.<br />But generally it sounds reasonable only while having a dominating symbol, like in your Proba80, where you could just group two symbols as the alphabet is small. <br /><br />Eventually, the number of bits for renormalization could be increased from the standard 1, making "no read bits" situation more frequent.<br />Best,<br />JarekJarek Dudahttp://www.blogger.com/profile/11358050996148333936noreply@blogger.comtag:blogger.com,1999:blog-834134852788085492.post-87412751065271057752015-10-14T13:49:04.394+02:002015-10-14T13:49:04.394+02:00Very interesting. In cached compression case (squa...Very interesting. In cached compression case (squashfs, ...) we don't care of the compression speed/time/memory. It's where quad symbol can be interesting mostly for the decompression speed.BRULE Hermanhttp://www.blogger.com/profile/17158368383622735314noreply@blogger.com