Reduced dictionary feature for web content compression

As a part of my summer internship at Cloudflare, I worked on improving brotli dictionary compression for web data. Our changes implement a more thorough search of the dictionary for compression levels 5-9 with performance optimizations, resulting in a significant improvement in file size, particularly on small files, and a limited performance impact.
Measured at level 5 on a data set of HTML files smaller than 250kb, we achieve an average file size improvement of 6.8% (2.1% when weighted by file size). For CSS, the average file size is 2.8% lower (1% when weighted). The file improvement for other use cases or for larger files will be smaller. While the compression improvement comes with a 2% increase in CPU time, it is possible to get the performance of the current brotli code and thus improve compression without additional performance cost by using more aggressive heuristics while still retaining most of the compression improvement.

To achieve this, we use a different subset of the dictionary each for HTML, CSS and JS files and find matches using a combination of a bloom filter, a hash table and a radix trie, among other heuristics. Due to the nature of the dictionary and LZ compression, this will be primarily useful on small to medium-sized text files. While our work was focused on web content, extending it to plain text or for example XML data by generating a dictionary for these data types is also possible.

The code is available [here](https://github.com/fhanau/brotli/tree/cloudflare-reduced_dict). We think that the brotli project could also benefit from this, but there are some issues that should be considered before this can be integrated:

- The code includes functions to create and load custom dictionaries, which is very useful for extending this work to new kinds of text data, but not needed for most users.
- For performance reasons, a radix trie must be used. The current implementation uses a third-party radix trie [library](https://github.com/antirez/rax), which might not be an option for the brotli project.
- Since initializing the radix trie takes some time, a dictionary object is created once and then used with one or several BrotliEncoderState objects, which is primarily useful when the dictionary is used with several files at once. This requires adding functions to the API and makes using the dictionary more complex.