知多一点有限状态自动机

不念不忘少年蓝@ 2022-01-19 05:29 213阅读 0赞

hello~亲爱的观众老爷们大家好~最近 LeetCode 上的算法已经刷得差不多了（剩下都是 hard，不看答案是不会做了），是时候小结一下在刷题过程中，学到的一些有意思的知识点。相信大家对 React 都有一点了解，可能也看过类似的说法：“React 把组件看成是一个状态机（State Machines）。通过与用户的交互，实现不同状态，然后渲染 UI，让用户界面和数据保持一致。”那状态机到底是什么呢？

本文将简单地介绍状态机的理念，并通过解答一道算法展示其具体的应用，希望能让你了解多一点状态机这个有趣的模型，在编程中处理复杂的状态时，有多一个新选择~以下是正文：

## 什么是状态机 ##

> **有限状态机**（英语：finite-state machine，缩写：**FSM**）又称**有限状态自动机**，简称**状态机**，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

以上摘自维基百科，看起来还是有点抽象~简单地说，就是有这么一个装置，用户不断把输入塞进去，装置告诉用户塞进去的输入是否合法。其实在编程过程中，或多或少都会接触到它，只是未察觉到而已。比如正则，就是状态机的典型应用。在看具体例子之前，还需要了解一下状态机的特征：

> 状态总数是有限的。

> 任一时刻，只处在一种状态之中。

> 某种条件触发后，会从一种状态转变到另一种状态。

好了~状态机的概念介绍完了，可以关掉本文啦！ 看起来比较枯燥是么，没关系，我们看图说话：

这是一张典型的状态机示意图，圆圈表示状态机中的状态，双圆圈也是状态，但它是特殊的，是最终状态，也就是接受状态。若根据输入，状态机最后的状态停留在最终状态，就意味着这个输入是可被接受的、合法的。箭头表示状态的转移，比如状态机处于 `S2` 状态时，往状态机输入 0，那么根据箭头，状态转移至 `S1`，输入 0 则“转移”到 `S2`， 也就是原地踏步，保持不变。注意，当输入 0 或 1 之外的字符时，状态机没有任何能适配该字符的转移，那么此时即可认为输入不合法了。

OK~至此，状态机基本的概念已经了解得差不多，下面将结合实例，看看它的实际用途。

## 状态机的应用 ##

上文说过，正则就是状态机的典型应用，那么我们不妨来实现一个简单的正则引擎，它能根据输入的字符串与正则表达式，返回该正则表达式是否匹配该字符串：

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
    
        '?' 可以匹配任何单个字符。
        '*' 可以匹配任意字符串（包括空字符串）。
        
    两个字符串完全匹配才算匹配成功。
    
    说明:
    
        s 可能为空，且只包含从 a-z 的小写字母。
        p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
    复制代码

这是 LeetCode 中的一道原题：[44. 通配符匹配][44.]，大家不妨先暂停阅读，试试解决这道题。解题思路其实挺多的，但既然是正则相关，那么状态机一定可以解决这个问题。那就先根据示例，画一下状态机的示意图找找感觉：

示例 1:
    
        输入:
        s = "aa"
        p = "a"
        输出: false
        解释: "a" 无法匹配 "aa" 整个字符串。
    复制代码

根据正则表达式 `p`，可以绘制出这个状态机：

如上图所示，一开始状态机的状态是 `S0`，当字符 `a` 输入后，状态机的状态从 `S0` 转移到 `S1`，接着再往状态机中输入字符 `a`，但在 `S1` 状态上，没有任何可以转移的路径，因而该输入不合法，返回 `false`。

下面我们多看一个有意思的示例：

示例 4:
    
        输入:
        s = "adceb"
        p = "*a*b"
        输出: true
        解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
    复制代码

根据示例，可以绘制出这个状态机：

这个状态机比较有趣，状态之间的转移，不再是只有一种可能，存在根据相同的输入转移到不同状态的可能。分析一下，状态机的起始状态是 `S0`,往状态机中输入字符 `a`，由于 `*` 可以匹配任意字符串，那么状态机既可以“原地踏步”，也可以转移到 `S1`。但状态机任一时刻，只处在一种状态之中，那该怎么办呢？其实可以假设手上有无数个待启动的状态机，碰到分支情况时，再启动若干个状态机，转移对应的状态。按照这个思路，此时我们需要启动两个状态机，其中一个状态的状态在 `S0`，另一个在 `S1`（从 `S0` 转移过去）。

之后无论是逐个输入 `dce` 三个字符，两台状态机均“原地踏步”，最后输入字符 `b`，根据转移条件，第一个状态机仍然只能原地踏步，但第二个状态机既能转移到 `S2`，也能原地踏步，因而再开一个状态机。第三台状态的状态是 `S3`。输入就此结束，检查已启动的状态机，发现有一个状态机的状态是最终状态，因而输入合法，返回 `true`。

由此可见，只要有一个状态机的状态是最终状态，那么输入就是合法的（也就是匹配成功）。现在思路有了，是时候用代码描述出来了，不妨先试试自己写对应的程序。以下是我的实现：

/**
     * @param {string} s
     * @param {string} p
     * @return {boolean}
     */
    var isMatch = function(s, p) {
      // 连续的*是没意义的，算是简单的优化
      p = p.replace(/\*+/g, '*');
      // 正则对应状态机的描述
      const map = {};
      // 初始状态
      let index = 0;
      for (const token of p) {
        map[index] = map[index] || {};
        map[index][token] = true;
        // 只要不是*，那只要匹配，一定能转移到下一个状态
        if (token !== '*') index++;
      }
      // 最大的index，就是状态机的最终状态
      const SUCCESS = index;
      // 已启动状态机的集合，值为该状态机所在的状态
      let set = new Set();
      set.add(0);
      for (let i = 0; i < s.length; i++) {
        const newSet = new Set();
        const token = s[i];
        for (const status of set) {
          // 如果状态机没有任何转移条件，那就没必要继续下面的判断，废弃这个状态机
          if (!map[status]) continue;
          // 原地踏步的情况
          if (map[status]['*']) newSet.add(status);
          // 匹配到对应字符，可以转移到下一个状态的情况
          if (map[status]['?'] || map[status][token]) newSet.add(status + 1);
        }
        if (!newSet.size) return false;
        // 用新的状态机集合取代旧的集合
        set = newSet;
      }
      return set.has(SUCCESS);
    };
    复制代码

代码我都加上注释，稍微过一下整体的流程~ `map` 就是整个状态机的描述。`map` 的键是对应的状态，值是一个对象，描述转移的路径（也就是那些箭头）。`set` 是已启动状态机的集合，由于每个状态机其实都一样，不同的是它们此刻的状态，因此集合的值是状态机的状态。之后就是遍历输入的字符串，往状态机中逐个输入字符，让状态机发生转移。最后判断启动的状态机中是否存在最终状态，返回结果即可~

LeetCode 中跑出来的结果如下：

## 小结 ##

上述算法，是存在优化空间的，比如已启动状态机的复用，但为了代码有更好的可读性，没有进行相关的优化。当然，根据跑出来的结果可以看出，算法的运行速度并不是十分理想，只优于 23% 的提交，为追求速度，用动态规划的思路解题会更合适。但使用状态机进行解答，思路是相当清晰的，也能加深对状态机的理解。日后碰到复杂状态的切换与维护，不妨考虑用状态机进行解决。

以上就是全文的内容啦！状态机其实相当有意思的模型，广泛应用于前端、后端乃至编译器之中。本文仅显浅地介绍了相关概念及其应用，详细的内容还需要翻阅对应的书籍资料~

感谢各位看官大人看到这里，知易行难，希望本文对你有所帮助~谢谢！

转载于:https://juejin.im/post/5c80b6ebf265da2d98092c07

[44.]: https://link.juejin.im?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fwildcard-matching%2F