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