字符串匹配之有限自动机

字符串匹配的基本解决方案,是在长串中从头至尾遍历匹配模式串,直到找到完全匹配的位置,这样做一个最大的问题就是每次都重头开始匹配,完全没有用到已经匹配过的结果,非常的浪费,于是自动有限机和KMP就是基于这种利用已经匹配到的结果,在不匹配的位置出现时,立即查找下一个有效位置的算法。

在列出有限自动机的定义之前,想先讲讲这个算法的思想。所谓有限自动机机,我理解就是一张状态转移表,表头包括有限的模式串字符集与可能产生的状态。模式串字符集很好理解,例如要查找的模式串为aaba,那字符集就是{a, b};可能产生的状态也很好理解,也用aaba举例,可能产生的匹配结果无非是,a, ab, aab, aaba, 那状态也就是0,1,2,3,4,表示的是当前匹配成功多少位了,只有当状态达到4的时候,才表示完全匹配到了。

字符串匹配的有限自动机的关键,就在于构建这个状态转移表。

下面给出《算法导论》里自动有限机的定义:

一个有限自动机M是一个5元组(Q, q0, A, ∑, δ)

  • Q是状态的有限集合
  • q0∈Q 是Q的初始状态
  • A 是Q的子集,是一个特殊的接受状态集合
  • ∑ 是有限输入字母表
  • δ是一个从Q×∑到Q的函数,成为M的转移函数

有点抽象,但是对应到字符串匹配的问题里看看,就一目了然了,下面将用于匹配的模式串用P表示。
Q:就是此前提到的字符串可能匹配到的数目,从0到P.length;q0肯定是0呀;A很显然在完全匹配的情况下只能是P.length;∑ 就是前文所说的P的字符集,而重中之重的转移函数δ,就是接下来要详细解析一下的东西了。

状态转移函数其实也很好理解,以aaba为例。假设当前aaba与被匹配的字符串已经匹配到了aa两个字符,那么当前的状态就是2,在状态2的前提下,去查看下一个字符,如果下一个字符是b那么状态很自然就转移成了2+b= 2+1=3,如果下一个字符是a,a和b不相等了,那此时的状态是几呢?是0吗?需要重新开始匹配吗?显然不是呀,因为aaa 和 aaba明显 还是可以成功匹配aa的呀,所以状态2+a的结果仍旧是2,这个值的求解过程简单说来就是每当遇到一个不匹配的位置时,查看此前已经匹配成功的结果后缀与P的前缀最长的公共部分,例如aab的前缀与aaa的后缀能匹配到的最大长度就是2(这一部分算法导论里给了非常详细的证明,因为公式实在不好敲,加上论证也比较绕口,就不贴了哈,这个思想其实就是KMP算法的基础,下一篇文章会再分析)。这就是状态转移表的一行,现在我试着把整个状态转移表画出来。

| 状态 | a | b|
| -- |:-----:|
| 0 | 1 | 0|
| 1 | 2 | 1|
| 2 | 2 | 3|
|3| 4| 0|
|4| 2| 1|

要求出状态4与字符集的转移关系其实是为了查找下一个匹配位置的。而状态值,我啰嗦一下,就是表示当前能够匹配成功字符串长度,例如状态3+b=0,表示aabb的后缀( abb ,bb, b ) 都没有办法和aab进行匹配,我们就可以跳过abb和P的比较,直接进行到b之后的下一个字符了,这就是算法利用已知结果免去重复计算的方法。我们通过在状态表中根据当前状态+下一个字符输入查询得到新的状态,然后比较新的状态是否就是可接受状态P.length 来判断是否匹配成功,从而最终完成字符串的匹配。这就是自动有限机用在字符串匹配里的计算过程。

下面我贴一下求解状态转移表的伪代码

compute-transition-function(P, ∑)
      m = P.length
      for q = 0 to m
          for each character a in ∑
                k = min(m+1, q+2)
                repeat
                    k = k -1
                until P[0..k] == P[q-k..q]a
                δ(q, a) = k
      return δ
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,482评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,377评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,762评论 0 342
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,273评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,289评论 5 373
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,046评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,351评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,988评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,476评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,948评论 2 324
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,064评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,712评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,261评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,264评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,486评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,511评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,802评论 2 345

推荐阅读更多精彩内容

  • 引言 字符串匹配一直是计算机科学领域研究和应用的热门领域,算法的改进研究一直是一个十分困难的课题。作为字符串匹配中...
    潮汐行者阅读 1,624评论 2 6
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 134,599评论 18 139
  • 第5章 引用类型(返回首页) 本章内容 使用对象 创建并操作数组 理解基本的JavaScript类型 使用基本类型...
    大学一百阅读 3,212评论 0 4
  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 171,510评论 25 707
  • 销售是一种很神奇的职业,它得让不想买,不愿买,不能买,甚至买不起的人统统都变成我要买,乍听起来像是变魔术。 然而文...
    虫鸣吹晚风阅读 356评论 0 1