在一串数字的末尾找到重复序列

Question

在一串数字的末尾找到重复序列

arraysalgorithmlanguage-agnosticsequencerepeat

7

我的问题是：我有一个大的数字序列。我知道，在某个点之后，它变得周期性 - 也就是说，序列开头有k个数字，然后有m个数字重复出现在序列的其余部分。为了更清楚地说明这一点，例如，序列可能看起来像这样：[1, 2, 5, 3, 4, 2, 1, 1, 3, 2, 1, 1, 3, 2, 1, 1, 3, ...]，其中k是5，m是4，那么重复块就是[2, 1, 1, 3]。从这个例子中可以看出，我可以在较大的块内有重复的位，因此仅查找重复的第一个实例并不会有所帮助。

但是，我不知道k或m是多少 - 我的目标是将序列[a_1，a_2，...，a_n]作为输入，并输出序列[a_1，...，a_k，[a_(k+1)，...，a_(k+m)]] - 基本上通过将大部分序列列为重复块来截断较长的序列。

有没有高效的方法来解决这个问题？而且，更理想的是计算方面更难但更好 - 是否可能在生成所需序列时进行操作，以便我只需要生成最小量？我已经查看了这个站点上的其他类似问题，但它们似乎都处理没有起始非重复位的序列，并且通常不必担心内部重复。

如果有帮助/有用的话，我也可以说明为什么我在研究这个问题以及我将用它做什么。

谢谢！

编辑：首先，我应该提到我不知道输入序列是否恰好在重复块的末尾结束。

我试图解决的实际问题是写出二次无理数（实际上是负的）连分数展开的一个漂亮的封闭式表达式。对于这些CFE的部分商*，很容易产生任何精度的结果 - 然而，在某个点上，二次无理数的CFE的尾部会成为一个重复块。我需要处理这个重复块中的部分商。

我的当前想法是：也许我可以调整一些建议从右边开始工作的算法，使其适用于这些序列之一。或者，也许在二次无理数为周期性的证明中有一些东西可以帮助我看到为什么它们开始重复，这将帮助我想出一些简单的检查标准。 *如果我将一个连分数扩展写成[a_0，a_1，...]，我将a_i称为部分商。

对于那些感兴趣的人，可以在这里找到一些背景信息：http://en.wikipedia.org/wiki/Periodic_continued_fraction

- Istarion

如果你的序列是无限的，一般情况下这个问题是无法解决的：你永远不知道自己是否处于一个“内部重复”段落中，这个段落在以后某个时候会停止。你对k/m有任何限制吗？还是你只想要一个“最佳猜测”算法来逐步操作（针对“随着生成”的部分）？ - Danica

在给定的输入[a_1...a_n]末尾，您是否保证至少有2个重复的最终周期子序列？ - Alexey Frunze

@Dougal 我对m有一些上限，尽管它们不是特别好的估计值 - 这个序列在技术上是无限的，但我正在考虑输入其中一个有多个重复部分的有限部分。这也回答了Alex的问题 - 是的，我保证至少有两次重复。 - Istarion

5个回答

2

那么，ninjagecko给出了一个很好的解答我的问题。非常感谢！但是，我最终找到了一种更高效、基于数学的方法来处理我所关注的特定案例——也就是，写出一个二次无理数连分数展开的闭式表达式。显然，这个解决方案只适用于这个特定的情况，而不是我所询问的一般情况，但我认为将其放在这里可能有助于其他人解决类似的问题。

基本上，我记得一个二次无理数仅当它的连分数展开是纯周期性的时候才能被化简——也就是说，从一开始就重复，没有任何前导项。

当你计算一个数 x 的连分数展开时，你基本上将 x_0 设置为 x，然后通过定义 a_n = floor(x_n) 和 x_(n+1)=1/(x_n-a_n) 形成一个序列 [a_0; a_1, a_2, a_3, ... ]。通常情况下，你只需一直进行下去，直到达到所需的精度。然而，对于我们的目的而言，我们只需要运行此方法，直到 x_k 是一个化简后的二次无理数（如果它大于 1，且其共轭数在 -1 和 0 之间）。一旦这种情况发生，我们知道 a_k 是我们重复块的第一个项。然后，在找到 x_(k+m+1) 等于 x_k 时，我们知道 a_(k+m) 是我们重复块的最后一项。

- Istarion

1

从右侧搜索：

a_n == a_n-1 吗
(a_n,a_n-1) == (a_n-2,a_n-3) 吗
...

这显然是O(m^2)。唯一可用的限制似乎是m<n/2，因此它是O(n^2)

这对您的应用程序是否可接受？（我们是在帮您做作业，还是有一个实际的现实问题？）

- Roland Turner

很遗憾，我不能保证我们的输入结束于重复序列的末尾，但也许我们仍然可以从右边开始进行工作。我正在处理一个涉及连分数展开（特别是负连分数展开）的现实世界问题。二次方数在其连分数展开中是周期性的（但不一定纯周期性，因此序列的开头部分），我希望能够编写一个漂亮的、闭合的列表，代表给定二次方数的整个负连分数展开。 - Istarion

1

这个页面列出了几种好的循环检测算法，并提供了一个用C语言实现的算法。

- Apocalisp

这些算法（例如 Floyd 算法和列出的算法）不适用，因为它们只能在具有指针的图形或仅依赖于前一个数字的列表上工作。 - ninjagecko

1

一个应用“开箱即用”的循环检测算法会出现大量误报。然而，如果你通过将每个k位数字块或每个k位滑动窗口视为单个数字来增加字母表大小，这对于某些序列可能是实用的，并且速度可能相当快。 - mcdowella

1

考虑一旦序列重复多次后会怎样。例如，它将以...12341234123412341234结束。如果您取字符串的重复部分，直到最后一个重复周期之前，然后将其沿着该周期的长度滑动，您将发现在序列末尾的子字符串和向左滑动的相同子字符串之间存在长匹配，而这个距离与其长度相比很小。

反过来，如果您有一个字符串，其中对于大量的x，a[x] = a[x + k]，那么您也有a[x] = a[x + k] = a[x + 2k] = a[x + 3k]...因此，当向左滑动与其长度相比较短的距离时，能够匹配自身的字符串必须包含重复。

如果你查看http://en.wikipedia.org/wiki/Suffix_array，你会发现你可以在线性时间内构建一个按顺序排列的字符串所有后缀列表，以及一个告诉你每个后缀与前一个后缀在排序顺序中有多少个字符相同的数组。如果你寻找具有最大值的条目，这将是我候选的字符串，如..1234123412341234，并且两个后缀起始点之间的距离将告诉您序列重复的长度（但在实践中，像http://en.wikipedia.org/wiki/Rabin-Karp这样的滚动哈希搜索可能更快更容易，尽管存在可编码的线性时间后缀数组算法，例如Karkkainen和Sanders的“简单线性工作后缀数组构建”）。

假设当可用字符数为8、16、32、64、……2^n时，您应用此算法，并最终在2^p处找到重复。您在早期阶段浪费了多少时间？2^(p-1) + 2^(p-2) + ……，这相当于2^p的总和，因此重复搜索只是一个恒定的开销。

- mcdowella

又一个有用的答案，谢谢！正如我上面提到的，如果序列在重复块中途结束，似乎仍然会遇到问题，但这可能是一个更容易解决的问题。 - Istarion

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ninjagecko · Accepted Answer

你可以使用滚动哈希来实现线性时间复杂度和O(1)空间复杂度（我认为这是可能的，因为我不相信你可以有两个频率不是彼此的倍数的无限重复序列）。

算法：你只需要保持两个滚动哈希，像这样扩展：

                       _______  _______  _______
                      /       \/       \/       \
...2038975623895769874883301010883301010883301010
                      .        .        .      ||
                      .        .        .    [][]
                      .        .        .  [ ][ ]
                      .        .        .[  ][  ]
                      .        .       [.  ][   ]
                      .        .     [  . ][    ]
                      .        .   [    .][     ]
                      .        . [      ][      ]
                      .        [       ][       ]

继续对整个序列执行此操作。第一次遍历仅检测重复出现2 * n次的周期，其中n是某个值。但这不是我们的目标：我们的第一次遍历的目标是检测所有可能的周期，这正是它所做的。在执行此过程时，我们还要跟踪所有相对质数周期，以便稍后进行检查。

periods = Set(int)
periodsToFurthestReach = Map(int -> int)

for hash1,hash2 in expandedPairOfRollingHashes(sequence):
    L = hash.length
    if hash1==hash2:
        if L is not a multiple of any period:
            periods.add(L)
            periodsToFurthestReach[L] = 2*L
        else L is a multiple of some periods:
            for all periods P for which L is a multiple:
                periodsToFurthestReach[P] = 2*L

在这个过程中，我们得到了一个所有时期及其达到程度的列表。我们的答案可能是达到最远的那个，但我们会检查所有其他时期是否重复（因为我们知道要检查哪些时期，所以速度很快）。如果这个计算难度较大，我们可以通过在遍历列表时修剪掉不再重复的时期（就像埃拉托斯特尼筛法一样），来进行优化，方法是保持下一个重复周期的优先级队列。

最后，我们会再次检查结果，以确保没有哈希冲突（即使有，也会将其列入黑名单并重复操作）。

在这里，我假设你的目标是最小化非重复长度，而不是提供一个可以进一步分解的重复元素；如果存在其他压缩方式，您可以修改此算法以找到它们。