好的，tries数据结构已经存在了一段时间。一个典型的实现应该可以独立于数据集大小n，给出O(m)的查找、插入和删除操作，其中m是消息长度。然而，在最坏的情况下，相同的实现需要占用256个字节的输入字节。
其他数据结构，特别是哈希表，可以给你期望的O(m)查找、插入和删除操作，有些实现甚至提供常数时间的查找。然而，在最坏的情况下，这些例程要么不停止，要么花费O(nm)的时间。
问题是，是否存在一种数据结构，可以在保持与哈希表或搜索树相当的内存占用的同时，提供O(m)的查找、插入和删除时间？
可能适合说的是，我只关心最坏情况下的行为，无论是时间方面还是空间方面。
您尝试过使用Patricia（别名critbit或Radix）树吗？我认为它们可以解决最坏情况下的空间问题。
有一个被称为后缀数组的数据结构。我记不得这个领域的研究了，但我认为他们用这个数据结构已经非常接近O(m)的查找时间了，并且它比你通常使用的基于树的索引方法要紧凑得多。
Dan Gusfield的书是字符串算法的圣经。
我认为有两个原因不必担心最坏情况：
如果您需要压缩，并且您几乎没有共同的子序列，那么您需要设计一种基于数据特定形状而不是基于字符串通用假设的压缩算法。例如，在完全/高度填充的助记符数据集的情况下，跟踪数据中的“空洞”而不是填充数据的数据结构可能更有效。
话虽如此，如果您有适度的扇出，避免使用固定的trie节点大小可能会更好。您可以将trie的每个节点设置为哈希表。从小尺寸开始，随着元素的插入而增加。当每个哈希表由于增加而必须重新组织时，最坏情况的插入将是c * m，其中c是可能字符/唯一原子元素的数量。
您可以在这里看到基准测试。它们与哈希表一样快，但内存需求更低，最坏情况下性能更好。
