像ZIP这样的文件压缩的核心步骤之一是使用先前解码的文本作为参考源。例如，编码的流可以说“接下来的219个输出字符与5161字节前的解码流中的字符相同。”这样可以用3个字节左右来表示219个字符。 （ZIP还有更多内容，例如霍夫曼压缩，但我只谈到了参考匹配。）
我的问题是字符串匹配算法的策略是什么。即使查看zlib等源代码，似乎也无法得到压缩匹配算法的良好描述。
问题可以陈述为：给定一个文本块，比如30K的文本块，和一个输入字符串，找到30K文本块中与输入字符串前面完全匹配的最长参考。当进行迭代时，算法必须高效，即文本块将通过从前面删除一些字节并向后添加新的字节来进行更新，并执行新的匹配。
我对讨论如何实现算法更感兴趣，而不是源代码或库。（zlib的源代码非常好！）我怀疑可能有几种不同的方法，存在不同的权衡取舍。
嗯，我注意到您对问题进行了详细说明，但是没有提到RFC 1951第4部分提供的信息（DEFLATE压缩数据格式的规范，也就是ZIP中使用的格式），这让我相信您可能错过了这个资源。
它们的基本方法是使用三字节序列作为键的链式哈希表。只要链不为空，就会扫描沿着它的所有条目来a)消除错误的碰撞，b)消除太旧的匹配，以及c)从剩余的匹配中选择最长的匹配。
请注意，他们的建议是受到专利因素的影响;可能他们知道更有效的技术，但不能确定它是否被某个人的专利覆盖。个人而言，我一直想知道为什么不能通过检查从传入数据的第二个字节开始的三字节序列的匹配项，第三个字节等，来找到最长的匹配项，并筛选不匹配的匹配项。即，如果你的传入数据是“ABCDEFG...”，你有“ABC”在偏移100、302和416处的哈希匹配项，但你只有“BCD”在偏移301处的哈希匹配项，你知道，除非你有两个完全巧合的重叠哈希匹配项，否则302就是你最长的匹配项。
还要注意他们建议的可选的“懒匹配”（尽管它会更努力）：压缩器不会自动选择从传入数据的第一个字节开始的最长匹配，而是检查下一个字节开始的更长匹配。如果您的传入数据是“ABCDE...”，并且滑动窗口中您唯一的匹配是“ABC”和“BCDE”，那么最好将“A”编码为一个字节，将“BCDE”作为匹配。
我认为您在描述修改过的最长公共子串问题版本。
