0

我有一个很大的数字向量，比如 500 个数字。我想要一个程序来根据以下规则检测此类向量中的模式（在这种情况下再次出现）：

一个数字序列是一个模式，如果：

  • 序列的大小在 3 到 20 个数字之间。

  • 序列中数字的相对位置在向量中至少重复一次。所以假设我有一个序列 (1,4,3)，然后 (3,6,5) 在向量中的其他位置，那么 (1,4,3) 是一个模式。（以及（2,5,4），（3,6,5）等）

  • 序列不能相交。因此，向量 (1,2,3,4,5) 不包含模式 (1,2,3) 和 (3,4,5)（我们不能对两个序列使用相同的数字）。但是， (1,2,3,3,4,5) 确实包含模式 (1,2,3) （或 (3,4,5)）

  • 仅当 A 出现在 B 之外的其他位置时，模式 B 的子集 A 才是模式。因此，向量 (1,2,3,4,7,8,9,2,3,4,5) 将包含模式 ( 1,2,3,4) 和 (1,2,3)，因为 (1,2,3,4) 重复（以 (2,3,4,5) 的形式）和 (1,2, 3) 重复（以 (7,8,9) 的形式）。但是，如果向量是 (1,2,3,4,2,3,4,5)，则唯一的模式将是 (1,2,3,4)，因为 (1,2,3) 仅出现在上下文中(1,2,3,4)。

我想知道几件事：

首先，我希望规则不会相互冲突。我自己做的，所以可能会在我没有注意到的地方发生冲突，如果你注意到了，请告诉我。

其次，如何以最有效的方式实施这样的系统？也许有人可以指出一些关于这个主题的特定文献？我可以从搜索所有 3 的子集的序列重复开始，然后是 4,5，直到 20。但这似乎不是很有效。非常欢迎指导。

先感谢您！

4

1 回答 1

2

只是几个观察：

如果您对相对值感兴趣，那么您的第一步应该是计算向量的相邻元素之间的差异，例如：

Original numbers:
1   4   3   2   5   1   1   3   6   5   6   2   5   4   4   4   1   4   3   2
*********                   *********       *********           *********
Difference values:
  3   -1  -1  3   -4  0   2   3   -1  1   4   3   -1  -3  0   -3  3   -1  -1
  ******                      ******          ******              ******

完成此操作后，您可以使用自相关方法来查找数据中的重复模式。这可以在O ( n log n ) 时间内计算出来，如果您只关心完全匹配，可能会更快。

于 2013-11-05T01:19:10.767 回答