Are there LZW/LZ78/LZC etc. variants with efficient codeword encoding?

[Dresdenboy]

This is about encoding of the actual codeword range of this family of compressors. So far the number of used bits just gets increased after reaching the limit of the current codeword size (e.g. 9 -> 10 bits). But the new range only gets 50% used right after increasing by 1 bit, with slow filling of the range.
Is some existing algorithm adressing this? AC, RC, ANS come to my mind here. Anything else?

[Mauro Vezzosi]

​Just in these days I'm looking at lzw-ab, its "adjusted-binary" part does a good trick.
​https://github.com/dbry/lzw-ab

[Dresdenboy]

​Just in these days I'm looking at lzw-ab, its "adjusted-binary" part does a good trick.
​https://github.com/dbry/lzw-ab

Thanks, this variant looks interesting. I'll have a look at it.

[Dresdenboy]

A little update: LZW-AB is roughly 5-7% better than LZW. Some paper mentioned possible reductions of 8% vs standard LZW.

[Shelwien]

768,771 book1
567,221 1     // lzw-ab -1
484,819 2     // lzw-ab -2
436,111 3     // lzw-ab -3
402,414 4     // lzw-ab -4
354,568 2.zst // -22 --zstd=wlog=12 
299,755 1.gz  // 7z -tgzip -mx=9
264,731 1.zst // -22
214,938 1.glz // glza -x

[SolidComp]

Is that normal for GLZA? What's the story?

[Mauro Vezzosi]

768,771 book1
567,221 1.lzw-ab  // lzw-ab -1
484,819 2.lzw-ab  // lzw-ab -2
436,111 3.lzw-ab  // lzw-ab -3
402,414 4.lzw-ab  // lzw-ab -4
376,752 5.lzw-ab  // lzw-ab -5
355,634 6.lzw-ab  // lzw-ab -6
354,568 2.zst     // -22 --zstd=wlog=12 
338,861 7.lzw-ab  // lzw-ab -7
323,503 8.lzw-ab  // lzw-ab -8
312,855 9.lzw-ab  // lzw-ab -9
304,695 10.lzw-ab // lzw-ab -10
304,695 11.lzw-ab // lzw-ab -11
299,755 1.gz      // 7z -tgzip -mx=9
264,731 1.zst     // -22
214,938 1.glz     // glza -x

[Marco_B]

Any entropy stage stacked upon the LZW solves the issue, because not yet assigned dictionary entries have zero frequency. I pursued this approach with my compressor Bolt, where I used the Splay Tree (Douglas Jones) after the LZW. Please note that there is an improvement only with binary files while for text ones it goes to a degradation, but I think this is due to the profile of the Splay Tree; for other entropy encoders the result may vary, in this case you have to consider that LZW produces a huge alphabet and speed is a concern.
The command line options for Bolt are:

2 - LZW 12 bit
3 - LZW 14 bit
4 - LZW 12 bit + Splay Tree
5 - LZW 14 bit + Splay Tree

Another approach is starting to code the dictionary entries with maximum bit size and when the dictionary becomes full applying a strategy to recycle the least recently used entry, of course it is worth only for input stream large in respect to the dictionary size.

[Dresdenboy]

768,771 book1
[see Mauro Vezzosi's table]

(Where are these many blank lines in code blocks coming from?)
I already expected not too stellar performance with file sizes like this, as it still is LZW, creating dictionary entries, where many are never used. And more efficient encoding might just shave of fractions of a bit up to roughly one bit per symbol.

768,771 book1
567,221 1.lzw-ab  // lzw-ab -1
484,819 2.lzw-ab  // lzw-ab -2
436,111 3.lzw-ab  // lzw-ab -3
402,414 4.lzw-ab  // lzw-ab -4
376,752 5.lzw-ab  // lzw-ab -5
355,634 6.lzw-ab  // lzw-ab -6
354,568 2.zst     // -22 --zstd=wlog=12 
338,861 7.lzw-ab  // lzw-ab -7
323,503 8.lzw-ab  // lzw-ab -8
312,855 9.lzw-ab  // lzw-ab -9
304,695 10.lzw-ab // lzw-ab -10
304,695 11.lzw-ab // lzw-ab -11
299,755 1.gz      // 7z -tgzip -mx=9
264,731 1.zst     // -22
214,938 1.glz     // glza -x

Interesting! At those big dictionary sizes it even starts to look competitive.

Any entropy stage stacked upon the LZW solves the issue, because not yet assigned dictionary entries have zero frequency. I pursued this approach with my compressor Bolt, where I used the Splay Tree after the LZW. Please note that there is an improvement only with binary files while for text ones it goes to a degradation, but I think this is due to the profile of the Splay Tree; for other codecs the result may vary, in this case you have to consider that LZW produces a large alphabet and speed is a concern.
The command line options for Bolt are:

2 - LZW 12 bit
3 - LZW 14 bit
4 - LZW 12 bit + Splay Tree
5 - LZW 14 bit + Splay Tree

Another approach is starting to code the dictionary entries with maximum bit size and when the dictionary becomes full applying a strategy to recycle the least recently used entry, of course it is worth only for input stream large in respect to the dictionary size.

This also looks interesting. My Pascal days were roughly a quarter century ago. But as I'm testing compression of binary files, Bolt is on my list now.

[Mauro Vezzosi]

768,771 book1
[see Mauro Vezzosi's table]

(Where are these many blank lines in code blocks coming from?)

I don't understand what "many blank lines in code blocks" you're referring to.
​

At those big dictionary sizes

lzw-ab -11 requires ~5 MB.
-11 = 19 bits dictionary = 512 KiB.
512 KiB * (4 (first_references) + 4 (next_references) + 1 (terminators)) = ~4.5 MiB (the first 256 values are implicit and not allocated)

[Dresdenboy]

I don't understand what "many blank lines in code blocks" you're referring to.

Sorry, this was just a comment about the code box formatting to Shelwien as a forum admin.
​

lzw-ab -11 requires ~5 MB.
-11 = 19 bits dictionary = 512 KiB.
512 KiB * (4 (first_references) + 4 (next_references) + 1 (terminators)) = ~4.5 MiB (the first 256 values are implicit and not allocated)

Sounds plausible! I think the LZW part is pretty standard. Just the code-word/symbol encoding got more efficient. And since those symbols grow to 19 bits, the adjusted binary savings are going down to ~1/38 bits per encoded symbol, I think.

[Dresdenboy]

​Just in these days I'm looking at lzw-ab, its "adjusted-binary" part does a good trick.
​https://github.com/dbry/lzw-ab

There is the Horspool paper (Improving LZW), which describes it. I also checked his source. No additional information. But Charles Bloom did some interesting analysis of this encoding (calling it "flat codes" BTW):
http://cbloomrants.blogspot.com/2013...bits-flat.html

[Mauro Vezzosi]

​

Just in these days I'm looking at lzw-ab, its "adjusted-binary" part does a good trick.https://github.com/dbry/lzw-ab

There is the Horspool paper (Improving LZW), which describes it. I also checked his source. No additional information. But Charles Bloom did some interesting analysis of this encoding (calling it "flat codes" BTW):http://cbloomrants.blogspot.com/2013...bits-flat.html

Yes, after doing various Internet searches on LZW, I saw that this type of coding was known to others too.