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