data-structures - 大型数据集的广义后缀树 Java 实现

Question

我收集了大约 5000 万个字符串，每个字符串大约有 100 个字符。我正在寻找非常有效（运行时间和内存使用）的通用后缀树实现。

我已经尝试过https://github.com/npgall/concurrent-trees但即使运行时间很有效，它也会占用大量内存。有 250 万个长度为 100 的字符串。它已经占用了 50GB 的内存。

Answer 1

这不是一个理想的解决方案，但您可以使用enter link description here。它有一个 CritBit1D 版本，你可以存储任意长度的密钥。

缺点#1：您必须先将字符串转换为 long[] ，即。每长 4-8 个字符。

缺点 #2：如果您需要并发版本，则必须查看使用写时复制并发的 Critbit64COW。然而，这还没有为 Critbit1D 实现，所以你需要自己做，使用 Critbit64COW 作为模板。

但是，您可以只存储一个 64 位哈希码作为密钥，然后您可以使用 CritBit64（单线程）或 CritBit64COW（多线程）。顺便说一句，即使使用 CritBit64，同时读取也不是问题。

免责声明：我是 CritBit 的作者。