algorithm - 检测重复的行组

Question

我有几兆字节的数据是这样的:

11  2  1
 4  3  1
11  2  1
 4  3  1
11  2  1
 4  3  1
18  3  2

我想通过添加“前 n 行重复 m 次”的行来压缩它。该算法应该读取行并延迟打印出来，直到找到最长的 m*n，但可以假设 n<=10。执行此操作的最佳方法是什么？

我正在考虑只保留 10 个数组，每个数组包含 1..10 行和重复计数器，在新行进入时旋转数组内容，并在新读取的行与任何行中最旧的条目不匹配时打印上述消息的数组，并且至少有一个数组充满了重复。

Answer 1

“复制前n行重复m次”是“从j行开始向后复制k行”的限制版本。第一个是第二个，k = n * m 且 j = n。更通用的 k,j 版本是 LZ77。 (尽管通常它是字节而不是行。)

LZ77 算法对此非常有效。 gzip、zlib 等使用的哈希表方法快速且易于编码。首先，定义您认为值得的 k (mink) 的最小值，并定义您要查找匹配项的时间，即 j (maxj) 的最大值。然后构建一个 maxj 行的滑动窗口进行搜索。

随着每一行的到来，更新一个仅依赖于最后的 mink 行的散列。在哈希表中查找与该哈希匹配的最后一行，然后将您的行直接与那里的滑动窗口中的内容进行比较，直到它们不匹配为止。然后如果得到的长度是 mink 或更多，你就有了一个匹配，它由一个长度和一个距离(k 和 j)组成。

使用惰性匹配，将匹配项的发出推迟到处理下一行时，这可能会产生更长的匹配项。