algorithm - 连续序列数据中的模式

Question

假设我有一个事件列表。例如 A, D, T, H, U, A, B, F, H, ...。

我需要的是找到在完整序列中出现的频繁模式。在这个问题中，我们不能使用像先验或 fp 增长这样的传统算法，因为它们需要单独的项目集。而且，我不能将这个流分成更小的集合。

知道哪种算法适合我吗？

---

编辑

例如，对于序列 A, D, T, H, U, A, D, T, H, T, H, U, A, H, T, H 和 min_support = 2。

频繁模式将是

Of length 1 --> [A, D, T, H, U]
Of length 2 --> [AD, DT, TH, HU, UA, HT]
Of length 3 --> [ADT, DTH, THU, HUA]
Of length 4 --> [ADTH, THUA]
No sequences of length 5 and further

Answer 1

您可以尝试使用通配符和/或仅使用所有子字符串的 aho-corasick 算法。 Aho-corasick 基本上是一个有限状态机，它需要一个字典，然后它可以非常快速地在搜索字符串中找到多个模式。您可以使用 trie 和广度优先搜索构建有限状态机。这是一个很好的动画示例:http://blog.ivank.net/aho-corasick-algorithm-in-as3.html .所以您基本上需要 2 个步骤:构建有限状态机并搜索字符串。