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

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 compression algorithm。它建立在检测字符串重复并将其用于压缩的基础上。我相信你可以使用一个Trie 它。

Answer 2

如果你可以先进行排序，然后很容易经历更多的时间来寻找重复操作。当然，像SQL查询这样的自由格式排序听起来有点可怕。

Answer 3

我在这一领域的专家，但你可能想看看一些压缩算法，在我看来，这是相当正是他们做什么。

Answer 4

如果字符串足够大，一个有趣的方法是在其上运行压缩工具（如gzip，bzip或7zip）。这些工具通过定位重复（各级），并通过指针取代他们的文字（或字典）的初审工作。你实现的压缩是重复的度量。转储文件（你将不得不编写代码来做到这一点）会给你重复的内容。