title: marisa trie suffix compression?
body: <p>I'm using a custom Cython wrapper of <a href="https://github.com/s-yata/marisa-trie" rel="noreferrer">this marisa trie</a> library as a key-value multimap.</p>
  
  <p>My trie entries look like <code>key 0xff data1 0xff data2</code> to map <code>key</code> to the tuple <code>(data1, data2)</code>. <code>data1</code> is a string of variable length but <code>data2</code> is always a 4-byte unsigned int. The <code>0xff</code> is a delimiter byte.</p>
  
  <p>I know a trie is not the most optimal data structure for this from a theoretical point of a view, but various practical considerations make it the best available choice.</p>
  
  <p>In this use case, I have about 10-20 million keys, each one has on average 10 data points. <code>data2</code> is redundant for many entries (in some cases, <code>data2</code> is always the same for all data points for a given key), so I had the idea of taking the most frequent <code>data2</code> entry and adding a <code>("", base_data2)</code> data point to each key. </p>
  
  <p>Since a MARISA trie, to my knowledge, does not have suffix compression and for a given key each <code>data1</code> is unique, I assumed that this would save 4 bytes per data tuple that uses a redundant key (plus adding in a single 4-byte "value" for each key). Having rebuilt the trie, I checked that the redundant data was no longer being stored. I expected a sizable decrease in both serialized and in-memory size, but in fact the on-disk trie went from 566MB to 557MB (and a similar reduction in RAM usage for a loaded trie). </p>
  
  <p>From this I concluded that I must be wrong about there being no suffix compression. I was now storing the entries with a redundant <code>data2</code> number as <code>key 0xff data1 0xff</code>, so to test this theory I removed the trailing <code>0xff</code> and adjusted the code that uses the trie to cope. The new trie went down from 557MB to 535MB.</p>
  
  <p>So removing a single redundant trailing byte made a 2x larger improvement than removing <em>the same number</em> of 4-byte sequences, so either the suffix compression theory is dead wrong, or it's implemented in some very convoluted way.</p>
  
  <p>My remaining theory is that adding in the <code>("", base_data2)</code> entry at a higher point in the trie somehow throws off the compression in some terrible way, but it should just be adding in 4 more bytes when I've removed many more than that from lower down in the trie.</p>
  
  <p>I'm not optimistic for a fix, but I'd dearly like to know why I'm seeing this behavior! Thank you for your attention.</p>