使用有限状态机进行序列检测

引言

该算法及其基础库是由卑微的作者作为随机 马尔可夫链式引擎的一部分创建的，该引擎用于为一家大型企业 Web 平台生成听起来自然的字母数字标识符，用于“固定”密码。它还可以用于代码转换，或作为处理序列的数据挖掘算法的回溯工具。我还计划使用它来生成遵循严格对位法规则的旋律性人声线条，这是我众多个人项目之一。

假设我们有一个有限的符号字母表，例如 { A, B, C }，虽然有限但足以演示该方法。我们还有一个输入的字符流，一次出现一个，例如

(1) A, A, B, A, C, A, C, C, ...

现在，如果我们的序列识别器设置为识别序列

0: [], 1: [A], 2: [B], 3: [C]

序列 0 是初始状态，当第一个符号尚未从输入流中到来时。其他符号仅对应于特定符号的出现，我们将称它们为平凡的，因为它们的长度小于 2。对于上述符号输入流内容，其识别的序列索引（SI）将是

0, 1, 1, 2, 1, 3, 1, 3, 3, ...

此时，这看起来更像一个基本的 有限状态转换器。我们可以观察到，为了在具有 N 个字符的字母表上建立序列识别器，我们需要 N+1 个平凡状态，以便它至少能识别该字母表中的每个单独符号。然而，让我们让事情变得更有趣。我们将一些非平凡序列添加到上述识别器中（注意：它们没有特定的顺序。）

4: [AA], 5: [BA], 6: [AC], 7: [ACC]

现在，对于相同的输入流 (1)，我们应该按如下方式识别 SI

0, 1, 4, 2, 5, 6, 1, 3, 7, ...

一个序列可以是任何非完整长度的子字符串，适用于任何其他序列，例如 [AAB], [BAAB], [AABCCC] 等。序列的唯一规则是它们都必须不同。

实现

我的第一个想法是使用长度为 K 的循环缓冲区，其中 K 是要检测的最长序列的长度。这样，我就可以跟踪最后 K 个符号，并将它们与预定义的序列进行匹配。这种暴力方法要求我们以迭代方式将缓冲区中的符号与每个序列的符号进行匹配，然后最长的匹配获胜。此方法对于每个新符号的复杂度为 O(SUM(sequenceLength))，而理论上一步的理想复杂度应为 O(1)，因为毕竟我们每一步只添加一个符号。这可以通过实现一个算法来构建有限状态机（FSM）的状态图来实现，该状态图能够一个接一个地“接受”符号。每个新符号将 FSM 移到一个新状态（可能回到同一个状态）。移到一个新状态只是沿着当前状态节点的相应出边进行移动，这是一种纯粹的 O(1) 操作。但是，为了能够做到这一点，我们需要一些东西来建立 米利状态机声明。

NEXT_STATE = SOME_FUNCTION(NEXT_SYMBOL, CURRENT_STATE)

这可以通过构建此类 FSM 的状态图来完成。状态图将有一个初始状态，如上所述，但没有最终状态，因为我们的识别器以 在线 方式运行。在本例中，我们将符号用它们的零基索引加上撇号表示。现在，假设我们有一个 4 符号字母表，序列如下

0: [], 1: [0'], 2: [1'], 3: [2'], 4: [3'], 5: [1'3'], 6: [2'2'2'], 7: [2'2'1'1'], 8: [2'2'2'2'], 9: [2'2'2'3']

状态图的构建可以分阶段进行，如下所示。

1. 向树中添加平凡序列

注意：对于所有后续图片，边都标有相应的字符索引；节点标有 <SI>s<MachineStateIndex>n; 机器状态索引作为节点的唯一标识符，并在节点创建时按顺序分配。 最初，我们为所有平凡状态添加节点，现在的树看起来像这样

正如我们所见，该树现在包含所有从初始状态可达的平凡状态。很好，但离让我们的卑微 FSM 正常运行还远远不够。这一阶段可以安全地与下一阶段合并，只是为了概念上的清晰性而分开。

2. 向树中添加非平凡序列

现在，我们将迭代所有非平凡序列，将我们的平凡树构建成一个前缀树，或 字典树。对于每个序列，我们从初始节点开始扫描其符号，添加缺失的边和节点到字典树。不过，所有原子字符都应由前一阶段覆盖。此时，一些非叶节点将没有关联的 SI，并用下划线标记。这是因为这些节点不代表任何完整的序列，只是中间状态；在下一阶段将解决这个 SI 缺失的问题。如果特定序列的最后一个节点已分配其 SI，则我们遇到了预定义序列集中不唯一的项，应报错。

3. 写入缺失的 SI

在此阶段，我们需要为所有节点写入缺失的 SI。有一个子程序

public static Node FindNode(this StateGraph graph, IList<int> sequenceReversed)

在当前和下一阶段发挥关键作用。它通过字典树筛选给定序列（可能不完整），并找到对应的序列索引节点，从而找到当前序列的最长完整前缀序列。让我们举一个节点 6 和 8 的操作示例。对于节点 6，序列是 2'2'，因此函数首先尝试查找具有 SI 的节点。它失败了，所以它从序列的第一个符号开始截取，得到 2'，然后尝试查找并找到带有 SI 3 的节点 3，所以它将 SI 3 写入节点 6。在下面的图片中，搜索迭代以 糟糕的 不同颜色绘制，并带有对应的黑色步骤。

对于节点 8，它遵循相同的方法，将 2'2'1 截断为 2'1，然后截断为 1'，从而将 SI 2 写入节点 8。

现在，我们字典树中的每个节点都有其 SI（注意：SI 不是唯一的）。唯一的问题是 - 并非所有转换边都已到位。每个节点都应该为字母表中的每个符号设置好这些边。这些边将把它连接到其他非初始节点。因此，我们需要再进行一个阶段。

4. 添加缺失的转换

我们将使用相同的 FindNode 函数来填补转换边中的空白。过程看起来与前一阶段非常相似。我们迭代节点的边，如果转换缺失，我们将在节点序列（不要与节点 SI 混淆）中添加相应的符号，然后搜索可以由其自身组成的相应节点，将转换添加到其中。例如，对于节点 10，转换 2' 将指向自身以及其他几个节点。这是最终的图。

它也可以表示为一个大小为 N 列 x M 行的矩阵，其中 N 是字母表中的符号数，M 是节点/状态数。

     0'    1'     2'     3'
0    1     2      3      4    
1    1     2      3      4    
2    1     2      3      5    
3    1     2      6      4    
4    1     2      3      4    
5    1     2      3      4    
6    1     8      7      4    
7    1     8     10     11    
8    1     9      3      5
9    1     2      3      5    
10   1     8     10     11    
11   1     2      3      4    

现在，字典树已经成为一个可以被状态机使用的完整转换图。现在，让我们快速看一下与我们所经历的所有概念相关的代码。

Using the Code

StateGraph 及其嵌套类 StateGraph.Node 以及扩展方法代表了与状态图创建相关的所有逻辑。为了方便调试和单元测试，上述状态图创建阶段被实现为单独的函数，因此可以按原样调用它们。主要的“生产”构造函数将它们组合在一起。

public StateGraph(int alphabetSize, int[][] sequences)
    : this(alphabetSize)
{
    this.BuildTrie(sequences); // stages 1, 2
    this.WriteInMissingSequenceIndices(); // stage 3
    this.WriteInMissingTransitions(); // stage 4
}

完成图的构建后，StateMachine 成为主要执行者。此类非常直观，以至于可以列出其全部代码。

public class StateMachine
{
    public StateMachine(StateGraph stateGraph)
    {
        Graph = stateGraph
            ?? throw new ArgumentNullException(nameof(stateGraph));

        _currentNode = stateGraph.Root;

        Symbol = StateGraph.DefaultSymbol;
    }

    public readonly StateGraph Graph;
    private StateGraph.Node _currentNode;

    public int Symbol { get; private set; }

    public int State => _currentNode.NodeIndex;

    public void AcceptSymbol(int symbol)
    {
        try
        {
            _currentNode = _currentNode.Transitions[symbol];
        }
        catch (IndexOutOfRangeException e)
        {
            throw new ArgumentException("symbol is out of state range", e);
        }

        Symbol = symbol;
    }

    public int AcceptSymbolAndGetSequenceIndex(int state)
    {
        AcceptSymbol(state);

        return _currentNode.SequenceIndex;
    }

    public void Reset()
    {
        _currentNode = Graph.Root;
        Symbol = StateGraph.DefaultSymbol;
    }

    public int Sequence => _currentNode.SequenceIndex;
} 

该代码不明确保证线程安全，但一旦完全构建好，状态图就被视为只读数据结构，因此任何数量的状态机都可以从多个线程/任务的上下文中同时使用它。这就是我在 Kestrel 驱动的 Web 服务器场中运行的实际 Web 应用程序中如何使用它的。状态机是按每个请求实例化的，而状态图（实际上，应用程序中有几个）则保留为 单例 共享。只要每个状态机都在其自己的线程/任务的上下文中调用，它就没问题。否则，同步必须由调用代码负责。总之，以下是一个非常简单的应用程序的完整代码，我曾用它来剖析库的性能。

class Program
{
    static void Main()
    {
        const int alphabetSize = 4;

        var sequences = new[]
        {
            new[] { 1, 3 },
            new[] { 2, 2, 2 },
            new[] { 2, 2, 1, 1 },
            new[] { 2, 2, 2, 2 },
            new[] { 2, 2, 2, 3 }
        };

        for (int i = 0; i < 100000; ++i)
        {
            var g = new StateGraph(alphabetSize, sequences);

            var sm = new StateMachine(g);

            for (int k = 0; k < alphabetSize; ++k)
            {
                for (int j = 0; j < 1000 * k; ++j)
                {
                    sm.AcceptSymbol(k);

                    var sequence = sm.Sequence;
                }
            }
        }
    }
}

亲爱的读者，请随时分享对该库的任何使用和/或改进想法。是的，该库的完整源代码以及所有应有的单元测试都在这里

• https://github.com/DNemtsov/SequenceRecognizer