0

我试图找出一种方法来检测数字流中某些模式的重复发生。问题是 - 模式元素不一定是相邻的。

例如，采用以下流（这里的每个字母表示一个唯一的数字）：

A  C  B  D  A  E  B  F  G  A  H  B  I  A  J  B ...

明显的模式是A _ B. 自然A，B它们本身也是模式，所以假设我们想要所有超过某个阈值长度的模式 - 在这种情况下为 2，或者所有不属于较长模式的模式 - 任何一个定义都对我有用。另请注意，它不会以任何固定速率重复出现（即 - 模式的 2 个实例可以通过任意数量的元素在它们之间间隔开）。您可能还会注意到 'B _ A' 和 'A _ B _ A _ B' 在这里也是重复出现的模式 - 这些也将作为输出受到欢迎。

顺便说一句，这正在简化事情，实际上我可以让 A 和 B 也出现在该模式之外，也许将来我想识别甚至A _ _ B（或在某个阈值内的距离），但现在我' d 解决上述更简单的问题。

还有一个限制 - 可能的值没有限制，对此感到抱歉。这确实削弱了我能想到的大多数解决方案。然而，从好的方面来说，我对复杂性有点松懈，我会满足于几乎没有攻击性指数的任何事情（尽管我糟糕的计算机将不得不提供一个有效的解决方案:)）

有两个想法来解决这个问题 -

  1. 保留值的“矩阵”，填充距离，识别重复出现的增量并标记它们。由于该区域是无界的，因此该矩阵必须是整个值空间的瓦片（从最低到最高可见值）。为了空间优化，我可能正在考虑多个矩阵，每个“组”值一个，并以另一种方式处理跨矩阵增量。

  2. 某种卷积/类似 FFT 的方法 - 将流的一部分与自身匹配并改变偏移量，看看一次有多少匹配。不过，我真的不明白我们怎么能适应这个。

如果有人有更好的方法来解决这个问题，知道现有的算法，怀疑问题无法解决，或者可以帮助我在建议的两个选项之间进行选择（或发现它们的问题），我将非常感激。如果对约束或示例不清楚 - 发表评论，我会添加它。

提前致谢！

编辑：添加基于后缀树的解决方案的选项。刚刚了解了 Ukkonen 的算法（Ukkonen's suffix tree algorithm in plain English?），试图确定它在这里是否有用......

4

1 回答 1

0

I think you can use Priority Queue-like structure. This is what I can think of:

While (your input stream has more elements)
    Check if it is 'A'

    if it is 'A':
        insert it in the queue

    // Now you have to look for 'B'
    if current element is NOT 'B'
        insert it in the queue

    // As soon as you get 'B'
    you can empty the queue and you have the pattern

    // If you find 'A' while looking for 'B'
    whatever you have in queue, just discard it, because in a pattern like A..A...B, A..A is not of your interst I believe

You can add additional constraints like minimum length. You can also use LinkedList for this.

于 2013-09-23T18:47:09.313 回答