Make a ZeroTrie dense data optimization

[sffc]

ZeroTrie excels at storing sparse data and identical prefixes, but it is not as strong at dense data and identical suffixes.

For example, consider these strings (for simplicity, assume each string maps to a unique integer):

ar/FR
ar/IR
ar/SA
ar/UK
ar/US
en/AU
en/FR
en/UK
en/US
fr/FR
fr/SA
fr/UK
fr/US
it/IT

In a ZeroAsciiTrie, these strings take up 71 B. In a VarZeroVec (Index16), they use 98 B.

However, we can optimize the storage by observing that there is a dense matrix hiding inside these strings:

Lang \ Region	FR	SA	UK	US
ar	✔️	✔️	✔️	✔️
en	✔️	❌	✔️	✔️
fr	✔️	✔️	✔️	✔️

The ❌ is to illustrate that en-SA is not in the input data and the matrix need not be fully populated.

We can then store the dense matrix alongside a a trie with region names and a language trie with just these keys:

ar
ar/IR
en
en/AU
fr
it/IT

The sum of the size of the two tries and the dense matrix, assuming 1 B per cell in the matrix, is 55 B.

(For comparison, storing the key and row headers in their own tries with a fully dense matrix would be 56 B: not a significant difference in this toy example, but it starts to blow up when the dense matrix has a lot of sparsity.)

These numbers scale up to bigger datasets. For example, with this type of optimization, we could reduce the region display names lookup table from 272 kB to 137 kB.

See some early work in #6880

An open question is how we can detect the dense matrix inside of a zerotrie. An easy way to start would be to give a field separator hint like /, but it seems like we should be able to automatically extract the dense matrix from any arbitrary set of strings.

@Manishearth @echeran thoughts?

[Manishearth]

An open question is how we can detect the dense matrix inside of a zerotrie. An easy way to start would be to give a field separator hint like /, but it seems like we should be able to automatically extract the dense matrix from any arbitrary set of strings.

I kind of actually think that it would be a feature to be able to have a "dense delimited trie" where the trie struct contains a delimiter (chosen during datagen) and when that delim is encountered during string lookup it is treated as a level change.

But maybe automatic is better.

[sffc]

Related thought: we can optimize the storage of the dense matrix by having each row start with an initial value, and then each cell contains a u8 (maybe u12) difference from the initial value. If a cell in the matrix isn't in range (perhaps if it is pointing to a string belonging to a different language), we just put it in the trie. This could cut the size of the dense matrix by 50%.

Illustration of what I mean: suppose the values in the dense matrix are as follows

Lang \ Region	FR	SA	UK	US
ar	1	2	3	4
en	5	-	6	7
fr	8	9	6	10

Then we can add a column "initial value" and store just the offset, and any cells that aren't in range of the offset are removed from the dense matrix and fall back to the trie. Example:

Lang \ Region	Initial Value	FR	SA	UK	US
ar	1	0	1	2	3
en	5	0	-	1	2
fr	8	0	1	-	2

fr/UK, which in this example points to the same string as en/UK, would be added into the sparse structure.

[Manishearth]

I think that's a neat design!

[echeran]

All that sounds good to me. It's about figuring out the patterns (areas of low entropy) and designing around that, so a matrix data structure for subsets of data that form a dense matrix, etc. Sounds good. I like the initial value idea if that helps buy you savings as well. You can see what the resulting "delta" numbers look like, and how small they are. If they're extra small, you can do what @markusicu sometimes does and do bit packing into 4 bits or 12 bits or 18 bits, etc. as necessary.

Because the matrix of languages x regions for the locale data might have data present or not based on various factors, you might play around with multiple dense matrices, although one sparse matrix would be enough. Even if that would save space, that would have a tradeoff of space vs. time, as always (2 vs. 3 lookups).