algorithm - 你如何检测字符串列表中的重复？

Question

我有一系列 SQL 调用，我想用它来检测循环（以及因此不必要的重复 sql 调用），但它让我想到了这个更普遍的问题。

给定一个列表，说 [a,b,c,b,c,a,b,c,b,c,a,b,b]

有什么办法可以把它变成 a,[[b,c]*2,a]*2,b*2

或者，[a,[b,c]*2]*2,a,b*2

也就是说，检测重复（可能是嵌套的）。

Answer 1

查看Lempel-Ziv-Welsh 压缩算法。它建立在检测字符串中的重复并利用它们进行压缩的基础上。我相信你可以使用Trie 。

Answer 2

如果您可以先对其进行排序，那么很容易再经过一次查找重复运行。当然，对像 SQL 查询这样的自由格式进行排序听起来有点吓人。

Answer 3

我不是该领域的专家，但您可能想查看一些压缩算法，在我看来，这正是他们所做的。

Answer 4

如果字符串足够大，一个有趣的方法是在其上运行压缩工具（如 gzip、bzip 或 7zip）。这些工具的工作原理是定位重复（在不同级别），并用指向文本第一个实例（或字典）的指针替换它们。您实现的压缩是重复的量度。转储文件（您必须编写代码来执行此操作）将为您提供重复的内容。