Improved matchfinder for high quality compression #36

New Issue

claunia · 2026-01-29T20:29:31Z

claunia commented

2026-01-29 20:29:31 +00:00

Originally created by @ebiggers on GitHub (Sep 27, 2015).

Brotli currently always finds matches using "cache tables": each 4-byte (or 5-byte for lower quality compression) sequence is hashed and placed in a limited-size array of sequences which share the same hash code. This works great in many cases but is not really well suited for large windows, especially in high compression modes.

An alternative which is used in LZMA and some other compressors is to have each hash bucket store a binary tree of sequences which share that hash code. The tree is sorted in two ways: by sequences in lexicographic order, and as a minheap for distance (the shortest distances are at the top). Matches can be found by searching for the current sequence in the tree, while re-rooting the tree.

There are normally two binary tree nodes allocated for each position in the sliding window, so this does require additional memory (8 times the sliding window size in bytes).

I implemented this as a proof of concept to see what would happen.

It does indeed seem to be better; here are some example results with an uncompressed archive of the silesia corpus (211,941,764 bytes) at quality 11:

Current version: compressed to 51,973,280 bytes in 10 mins 10 secs
With binary tree matchfinder: compressed to 51,609,618 bytes in 7 mins 34 secs

The code can be found at: repository https://github.com/ebiggers/brotli, branch "bt_matchfinder". Please feel free to do whatever you want with the code. I've left several TODOS in it.

Originally created by @ebiggers on GitHub (Sep 27, 2015). Brotli currently always finds matches using "cache tables": each 4-byte (or 5-byte for lower quality compression) sequence is hashed and placed in a limited-size array of sequences which share the same hash code. This works great in many cases but is not really well suited for large windows, especially in high compression modes. An alternative which is used in LZMA and some other compressors is to have each hash bucket store a binary tree of sequences which share that hash code. The tree is sorted in two ways: by sequences in lexicographic order, and as a minheap for distance (the shortest distances are at the top). Matches can be found by searching for the current sequence in the tree, while re-rooting the tree. There are normally two binary tree nodes allocated for each position in the sliding window, so this does require additional memory (8 times the sliding window size in bytes). I implemented this as a proof of concept to see what would happen. It does indeed seem to be better; here are some example results with an uncompressed archive of the silesia corpus (211,941,764 bytes) at quality 11: ``` Current version: compressed to 51,973,280 bytes in 10 mins 10 secs With binary tree matchfinder: compressed to 51,609,618 bytes in 7 mins 34 secs ``` The code can be found at: repository https://github.com/ebiggers/brotli, branch "bt_matchfinder". Please feel free to do whatever you want with the code. I've left several TODOS in it.

claunia closed this issue

2026-01-29 20:29:31 +00:00

claunia commented

2026-01-29 20:29:32 +00:00

@ebiggers commented on GitHub (Sep 27, 2015):

Tried the same data with a 16 MiB window:

Current version: compressed to 51,587,583 bytes in 12 mins 29 secs
With binary tree matchfinder: compressed to 50,960,226 bytes in 8 mins 8 secs

@ebiggers commented on GitHub (Sep 27, 2015): Tried the same data with a 16 MiB window: Current version: compressed to 51,587,583 bytes in 12 mins 29 secs With binary tree matchfinder: compressed to 50,960,226 bytes in 8 mins 8 secs

claunia commented

2026-01-29 20:29:32 +00:00

@eustas commented on GitHub (Oct 5, 2015):

Hello.

Thank you for your fantastic research!
Changes that improve both speed and compression ratio are very valuable for any compressor.

We are going to explore this solution and try to implement it in brotli.

PS: sorry for the late response.

@eustas commented on GitHub (Oct 5, 2015): Hello. Thank you for your fantastic research! Changes that improve both speed and compression ratio are very valuable for any compressor. We are going to explore this solution and try to implement it in brotli. PS: sorry for the late response.

claunia commented

2026-01-29 20:29:32 +00:00

@eustas commented on GitHub (Nov 17, 2015):

Hello again.

We have been busy last month, and have had no time to integrate your improvement to brotli encoder. Sorry.

But don't worry - this awesome change is still on our radars, and we are enthusiastic about integrating it.

Thank you for your patience.

Best regards,
Eugene.

@eustas commented on GitHub (Nov 17, 2015): Hello again. We have been busy last month, and have had no time to integrate your improvement to brotli encoder. Sorry. But don't worry - this awesome change is still on our radars, and we are enthusiastic about integrating it. Thank you for your patience. Best regards, Eugene.

claunia commented

2026-01-29 20:29:32 +00:00

@szabadka commented on GitHub (Jan 27, 2016):

Thanks for the suggestion, this was implemented in #306, mostly along the lines of your proof-of-concept.

@szabadka commented on GitHub (Jan 27, 2016): Thanks for the suggestion, this was implemented in #306, mostly along the lines of your proof-of-concept.

claunia referenced this issue

2026-01-29 20:46:27 +00:00

[PR #36] [MERGED] [python] Use BrotliDecompress() #617

claunia referenced this issue

2026-01-29 20:46:27 +00:00

[PR #38] [MERGED] add Python port of bro utility and scripts to test Brotli extension #619

claunia referenced this issue

2026-01-29 20:46:27 +00:00

[PR #36] [python] Use BrotliDecompress() #621

claunia referenced this issue

2026-01-29 20:46:27 +00:00

[PR #38] add Python port of bro utility and scripts to test Brotli extension #622