• 引言

    编译原理课程有介绍过NFA（非确定性状态机）到DFA（确定性状态机）的转换。直到最近才接触到相关的工程实践，还好编译原理的理论没丢光，思索片刻还能想起出处。这里简单记录下AC自动机里的转换过程，具体实现请查阅Github。

  • 简析

    ahocorasick是建立在trie上的多模式字符串匹配算法，其本质是在trie上构造一个DFA，对于每个字符输入都有两种确定的状态: 匹配成功、匹配失败。匹配过程即在这个DFA上不停的根据输入字符进行跳转，并记录途径节点的output匹配到的模式串，当消化掉所有输入字符后，根据output函数输出这些匹配到的模式串。

    下文提到的goto、fail、output与原论文语义一致，这里不再重复叙述算法流程和相关原理，可自行查阅维基百科以及相关课件。回到NFA转换DFA的问题，根据以下buildFails函数，算法可以构造出一个NFA。

      func (m *Matcher) buildFails() {
  	q := &list.List{}
  	da, ro := m.da, 0
  	m.fails[ro] = ro
  	chds := m.da.childs(ro)
  	for _, c := range chds {
  		m.fails[c.ID] = ro
  		q.PushBack(c)
  	}
  	var fid int
  	for q.Len() != 0 {
  		e := q.Front()
  		q.Remove(e)
  		nid := e.Value.(ndesc).ID
  		if da.isEnd(nid) {
  			vk, _ := da.vKeyOf(nid)
  			m.output[nid].vKey = vk
  		}
  		chds := da.childs(nid)
  		for _, c := range chds {
  			q.PushBack(c)
  			for fid = nid; fid != ro; fid = m.fails[fid] {
  				fs := m.fails[fid]
  				if da.hasLabel(fs, c.Label) {
  					fid, _ = da.child(fs, c.Label)
  					break
  				}
  			}
  			m.fails[c.ID] = fid
  		}
  	}
  }

    为了形象化这个NFA，我们假定现在输入Steel、tee、e作为模式串，The Man Of Steel: Superman作为待匹配的文本。那么通过以上的算法我们得到NFA：

    image

    当匹配Steel模式串时，有类似节点node258同时存在goto和fail跳转都能匹配成功的情况。如果选择goto到node259则会丢失tee和e的匹配串，如果选择fail到node261则会丢失Steel匹配串。

    因此需要在buildFails()后确定每一个fail跳转的可匹配输出，将同一输入字符产生的两种跳转情况合并为一种，保证选择goto跳转时不丢失fail跳转的匹配串。以下是Go的实现:

      func (m *Matcher) addOutput(nid, fid int) {
  	m.output[nid].Link = &m.output[fid]
  }

  func (m *Matcher) buildOutputs() {
  	da := m.da
  	for nid, fid := range m.fails {
  		if fid == -1 || !da.isEnd(fid) {
  			continue
  		}
  		da.toEnd(nid)
  		m.addOutput(nid, fid)
  	}
  }

  • 总结

    理论是指导实践的真知，而实践是验证理论的唯一标准。如果没有系统性的吸纳编译原理的理论知识，相信很多时候我们都会用一些比较繁琐的hard code去处理各种各样的corner case，不是说当我们在处理一些繁琐的事务就没有可以可提升自我的空间，而是缺少一些将繁琐变为简约优雅的理论，一些闪光点就消失在重复性的hard code里了。有时间再简要分析下cedar是怎样实现高效的double-array trie内存压缩。 ​