ZIP 等文件压缩的核心步骤之一是使用之前的解码文本作为引用源。例如，编码流可能会说“接下来的 219 个输出字符与 5161 字节前的解码流中的字符相同”。这使您可以仅用 3 个字节左右来表示 219 个字符。 (ZIP 的意义远不止于此，比如霍夫曼压缩，但我只是在谈论引用匹配。)
我的问题是字符串匹配算法的策略是什么。即使查看 zlib 等源代码似乎也无法很好地描述压缩匹配算法。
问题可能表述为:给定一个文本 block (比如 30K)和一个输入字符串，在 30K 文本中找到与输入的前面完全匹配的最长引用string."算法在迭代时必须高效，即 30K 文本 block 将通过从前面删除一些字节并在后面添加新字节并执行新匹配来更新。
我对执行此操作的算法的讨论更感兴趣，不是源代码或库。 (zlib 有很好的来源!)我怀疑可能有几种方法具有不同的权衡。
最佳答案
好吧，我注意到您详细介绍了问题，但没有提及 RFC 1951 的第 4 节中提供的信息(DEFLATE 压缩数据格式的规范，即 ZIP 中使用的格式)这让我相信您可能错过了这个资源。
他们的基本方法是使用三字节序列作为键的链式哈希表。只要链条不为空，就会扫描链条上的所有条目以 a) 消除错误碰撞，b) 消除太旧的匹配项，以及 c) 从剩余的匹配项中选择最长的匹配项。
(请注意，他们的推荐是由专利因素决定的；可能是他们知道一种更有效的技术，但不能确定它是否未被某人的专利所涵盖。就个人而言，我一直想知道为什么有人通过检查从传入数据的第二个字节、第三个字节等开始的三字节序列的匹配并剔除不匹配的匹配，无法找到最长的匹配。即，如果您的传入数据是“ABCDEFG ...”并且您在偏移量 100、302 和 416 处获得了“ABC”的哈希匹配，但是“BCD”的唯一哈希匹配位于偏移量 301 处，您知道，除非您有两个完全巧合的重叠哈希匹配——不太可能——然后 302 是你最长的匹配。)
另请注意他们对可选“惰性匹配”的建议(具有讽刺意味的是，它做了更多的工作):压缩器不会自动采用从传入数据的第一个字节开始的最长匹配，而是检查从第一个字节开始的更长的匹配下一个字节。如果您的传入数据是“ABCDE ...”并且您在滑动窗口中的唯一匹配项是“ABC”和“BCDE”，那么您最好将“A”编码为文字字节，将“BCDE”编码为一场比赛。
关于在滑动窗口中查找字符串匹配的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/642507/