具有O(1)插入时间和O(log m)查找的数据结构？

Question

背景故事(跳到数据结构部分第二到最后一段):我的工作(的LZ77品种)的压缩算法.该算法归结为找到给定字符串与已经看到的所有字符串之间的最长匹配.

要快速做到这一点,我使用的哈希表(与单独的链)作为DEFLATE规范建议:我插入迄今所看到每一个串在一个时间(每个输入字节一个)与米槽在链中的每个散列码.插入的速度快(恒定时间,没有条件逻辑),但搜索是缓慢的,因为我要看看O(米)的字符串,找到最长的匹配.因为我做几十万的查找数千插入和数以万计的一个典型的例子,我需要一个高效的数据结构,如果我想我的算法快速运行(目前它是太慢米 > 4,我想一个米接近128).

我已经实现了一个特殊情况,其中m是1,运行速度非常快但是只提供一般的压缩.现在我正在为那些喜欢提高速度压缩比的人开发一种算法,其中m越大,压缩效果越好(显然是一点).不幸的是,到目前为止,我的尝试对于压缩比的适度增加来说太慢了,因为m增加了.

所以,我正在寻找一种允许非常快速插入的数据结构(因为我做了比搜索更多的插入),但仍然相当快的搜索(优于O(m)).是否存在O(1)插入和O(log m)搜索数据结构？如果不这样做,最好的数据结构是什么？我愿意牺牲记忆力来提高速度.我应该在我的目标平台上添加它,跳转(ifs,循环和函数调用)非常慢,堆分配也是如此(我必须使用原始字节数组来实现所有内容以获得可接受的性能).

到目前为止,我已经考虑过按顺序存储m个字符串,这将允许使用二进制搜索进行O(log m)搜索,但插入也会变为O(log m).

谢谢!

Answer 1

您可能对这个匹配查找结构感兴趣：

http://encode.ru/threads/1393-A-propose-new-fast-match-searching-struct

插入时间为 O(1)，查找时间为 O(m)。但对于等效的匹配查找结果，(m) 比标准哈希表低很多倍。例如，当 m=4 时，该结构获得与 80 探针哈希表相同的结果。