algorithm - 检测重复的线组

Question

我有几兆字节的数据，如下所示：

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

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

score 1 · Accepted Answer

zip 算法可以保持数据的可读性。他们只是创建重复元素的字典（例如，看看lempel - ziv）。我认为您描述的算法可能有问题。您的第二行与第一行不同，那么您怎么知道应该将它们视为一个群体？你什么时候限制组，开始一个新的？
你怎么能这么说

11 2 1
4 3 1

真的属于同一组吗？

我认为 lempel ziv 可以为您解决这个问题，它有一本字典，其中包括所有可能的子集及其出现次数。在您的字典中，您将有子集，例如

11 2 1
4 3 1
11 2 1

但是，如果您以某种方式知道重复行将成对或三胞胎出现，则可以限制算法中检查的子集，并将字典中的子集保持在您的预期长度。
这样，最终您的字典将如下所示：

key          : count
11 2 1       : 3
4  3 1       : 3
11 2 1, 4 3 1: 3
18 3 2       : 1

当然，它需要更多的调整，但我认为这个算法应该是大方向

score 1 · Accepted Answer

“复制前 n 行重复 m 次”是“从 j 行向后复制 k 行”的受限版本。第一个是第二个，k = n * m 和 j = n。更通用的 k,j 版本是 LZ77。（虽然通常它是字节而不是行。）

LZ77 算法可以很好地解决这个问题。gzip、zlib 等使用的哈希表方法快速且易于编码。首先，定义您认为值得的 k (mink) 的最小值，并定义您想要查找匹配项的距离，即 j (maxj) 的最大值。然后构造一个 maxj 行的滑动窗口进行搜索。

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

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

score 0 · Accepted Answer

如果您将文件视为长字符串，那么我认为您的问题在于找到最长的重复子字符串

3 回答 3