匹配符号流与动态模式

Question

您将如何实现以下问题的解决方案：
给定一串符号和模式，可随时添加，计算每个模式发生的频率。

例：
有传入的符号的连续流假设A B A C dé ... 用户可以在任何时间寄存器例如（B A C）一个新模式。如果模式在第二个时间步之前注册，则模式应计为一次。

在重叠模式仅所述第一图案的情况下，应该算作e.g （B A C）和（A C d）将导致仅（B A C）被计数。

解决办法：
琐碎的解决办法是只保留一个位置每格局，推动它时，模式匹配和重置所有位置一旦一个匹配。这将导致运行时O（n * m） 其中n是流的长度，并且m是最长模式的长度（例如，通过在所有模式中具有相同的长度m-1的前缀）。

另一种方法是构造一个有限自动机，并使用模式可以包含前缀的事实。

但是有几个问题与：

• 如何构建模式之间的边缘？ （例如乙dË从A B）

• 如何在运行时添加图案。例如。假设流是A B并且此刻仅注册了（A B C）的模式。现在用户注册（B A C）。如果流继续A C D E。由于在注册之前发生第一个符号，因此该模式不应匹配。

该想法可以链接到Aho Corasick algorithm。然而，该算法确实匹配所有出现的模式，而不仅仅是第一个。它不允许在运行时添加模式。

Answer 1

维护Aho-Corasick FSM的初始清空列表。每当一个新的模式被注册时，为这个模式创建一个新的FSM，将它追加到列表中，并检查列表末尾是否有2个单字符串FSM：如果是，删除它们，构建一个新的FSM用于两个字符串，并将此FSM替换为原来的2.现在检查是否有2个2字符串FSM，如果有，则将它们组合为单个4字符串FSM。重复这个将两个k-串FSM组合成单个（2k） - 串FSM的过程，直到所有的FSMs用于不同数目的串。 （请注意，对于相同数量的字符串，任何2个FSM必须位于列表中的相邻位置。）

假设n个注册总共发生。由于上述“压缩”过程，该列表将始终包含至多log2（n）+1 FSM，所以总体“成本因子”使用每个这些FSM来搜索输入流（vs 。包含所有字符串的单个FSM）是O（log n）。此外，特定字符串参与的FSM构建过程的数量限制在log2（n）+1，因为它参与构建的每个新FSM都必须是其参与构建的前一个FSM构建过程的两倍。因此，所有FSM（相对于构建包含所有字符串的单个FSM）的大厦的整体“成本因素”也是O（log n）。