6

我的问题是：我有一大串数字。我知道，在某个时间点之后，它会变成周期性的——也就是说，在序列的开头有 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) 编写一个很好的封闭式表达式。为这些 CFE 生成任何精确度的部分商* 非常简单 - 但是，在某些时候，二次无理数的 CFE 尾部变成了重复块。我需要处理这个重复块中的部分商。

我目前的想法是：也许我可以调整一些建议的算法来使用这些序列之一。或者，也许证明二次无理数是周期性的，这将帮助我了解它们为什么开始重复，这将帮助我提出一些简单的标准来检查。

*如果我将连分数展开式写为 [a_0, a_1, ...]，我将 a_i 称为部分商。

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

4

5 回答 5

7

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

算法：您只需保留两个滚动散列，其扩展如下：

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

在整个序列中继续这样做。第一遍将仅检测对于某个 n 值重复 2*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

在这个过程之后，我们有一个所有时期的列表以及它们已经达到了多远。我们的答案可能是范围最广的答案，但我们会检查所有其他时期的重复（很快，因为我们知道要检查的时期）。如果这在计算上很困难，我们可以通过在遍历列表时修剪掉周期（停止重复）来进行优化，就像 Eratosthenes 的筛子一样，通过保留我们下一个期望周期重复的优先级队列。

最后，我们再次检查结果以确保没有哈希冲突（即使有，也不太可能，黑名单并重复）。

在这里，我假设您的目标是最小化非重复长度，而不是给出可以进一步分解的重复元素；您可以修改此算法以查找所有其他压缩（如果存在）。

于 2012-05-04T04:11:02.293 回答
2

因此，ninjagecko 为我提出的问题提供了一个很好的工作答案。非常感谢！然而，我最终找到了一种更有效、基于数学的方法来处理我正在研究的特定情况——也就是说，为二次无理数的连分数展开写出一个封闭形式的表达式。显然，该解决方案仅适用于这种特定情况，而不是我询问的一般情况，但我认为将其放在这里可能会很有用，以防其他人有类似的问题。

基本上，我记得当且仅当它的连续分数展开是纯周期性的时，二次无理数会被约简——例如，它从一开始就重复，没有任何前导项。

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

于 2012-05-04T22:39:11.340 回答
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)

这对您的应用程序是否可接受？（我们是在为您做功课，还是这里存在实际的现实问题？）

于 2012-05-04T02:06:22.830 回答
1

本页列出了几种良好的循环检测算法，并给出了 C 中算法的实现。

于 2012-05-04T02:46:50.763 回答
1

考虑重复多次后的序列。它将结束，例如 ...12341234123412341234。如果您将字符串的重复部分直到最后一个重复循环之前，然后将其滑动该循环的长度，您会发现序列末尾的子字符串和同一个子串向左滑动了一段与其长度相比很小的距离。

相反，如果你有一个字符串，其中 a[x] = a[x + k] 表示大量 x，那么你也有 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，因此重复搜索只是一个恒定的开销。

于 2012-05-04T05:09:25.887 回答