marisa trie 后缀压缩？

Question

我正在使用 this marisa trie 库的自定义 Cython 包装器作为键值多图。

我的 trie 条目看起来像 key 0xff data1 0xff data2 将 key 映射到元组 (data1, data2)。 data1 是可变长度的字符串，但 data2 始终是 4 字节无符号整数。 0xff 是分隔符字节。

我知道从理论上讲，trie 并不是最佳的数据结构，但各种实际考虑使它成为最佳选择。

在这个用例中，我有大约 10-20 百万个密钥，每个密钥平均有 10 个数据点。 data2 对于许多条目来说是多余的（在某些情况下，data2 对于给定键的所有数据点总是相同的），所以我想到了采用最频繁的 data2 条目并为每个键添加一个 ("", base_data2) 数据点。

据我所知，由于 MARISA trie 没有后缀压缩，并且对于给定的键，每个 data1 都是唯一的，我假设这将为每个使用冗余键的数据元组节省 4 个字节（加上为每个键添加一个 4 字节 "value"）。重建 trie 后，我检查了冗余数据是否不再存储。我预计序列化和内存大小都会大幅减少，但实际上磁盘上的 trie 从 566MB 减少到 557MB（加载的 trie 的 RAM 使用量也有类似的减少）。

由此我得出结论，我对没有后缀压缩的说法一定是错误的。我现在将带有冗余 data2 编号的条目存储为 key 0xff data1 0xff，因此为了测试这个理论，我删除了尾随 0xff 并调整了使用 trie 来应对的代码。新的 trie 从 557MB 下降到 535MB。

因此，删除单个冗余尾随字节比删除相同数量 4 字节序列的改进大 2 倍，因此后缀压缩理论要么是完全错误的，要么是以某种非常复杂的方式实现。

我剩下的理论是，在 trie 的更高点添加 ("", base_data2) 条目会以某种可怕的方式抛出压缩，但当我已经添加时它应该再添加 4 个字节从 trie 中的较低位置移除了更多。

我对修复并不乐观，但我非常想知道为什么我会看到这种行为！感谢您的关注。

Answer 1

正如我所怀疑的那样，这是由填充引起的。

在lib/marisa/grimoire/vector/vector.h中有如下函数：

void write_(Writer &writer) const {
  writer.write((UInt64)total_size());
  writer.write(const_objs_, size_);
  writer.seek((8 - (total_size() % 8)) % 8);
}

重点是：writer.seek((8 - (total_size() % 8)) % 8);。写入每个块后，写入器填充到下一个 8 字节边界。

这解释了您所看到的行为，因为最初缩短密钥所删除的部分数据被替换为填充。

删除额外字节后，密钥大小将低于下一个边界限制，从而导致大小发生重大变化。

实际上，这意味着，由于填充代码位于库的序列化部分，您可能获得了预期的内存节省，但这并没有转化为磁盘节省。监控程序 RAM 使用情况应确认。

如果您担心磁盘大小，那么您也可以简单地压缩序列化数据，因为 MARISA 似乎不应用任何压缩。

marisa trie 后缀压缩？

marisa trie suffix compression?

c++

python

trie