有限自动机的字符串匹配

自动机虽然是通过很多数学知识来论证其正确性,但是其原理确很简单。这里通过加回忆之前的学习,简单介绍下自动机的字符串匹配原理。自动机的字符在完成前期的工作后,其字符串的匹配时间复杂度为O(n),其中n为目标串的字符数,即自动机的匹配搜索不需要回溯,其如何完成避免回溯工作的呢?

很简单,假设目标串为abdabdabcefged.... 匹配串为abdabc,
那么在第一次匹配时,进行到最后一个c时,发现出错了。会有两种处理方法:
1、匹配串右移一个单位,重新开始匹配
2、尽量利用前面已经匹配的5个字符的信息,尽量让匹配串向右移动,以略过不必要的匹配动作。
以下面为例,
                 abdabdabcefged....
                 abdabc
                       abdabc

当目标串中的d与匹配串的c进行判断,失败。我们发现如果将匹配串右移3个位置(实际上就是失败后,直接转移到匹配串的第二个a与目标串进行比较,这不就是没有回溯了吗),如上图所示,不就利用了前面已经完成的匹配部分的信息,什么信息呢?
(目标串用蓝色,匹配串用红色)
abdab作为已经匹配完成的部分,如果我们知道其后缀是匹配串的前缀,不就可以利用这个信息,而不用再进行比较判断了吗!
仔细观察确实如此,我们观察匹配串abdabc发现,其自身存在相同部分,前面的ab与后面的ab。正如上面演示的那样,如果某个目标串与匹配串比较到第6个时失败,且当前失败字符为d,那么目标串在进行到此时其内容应该是******abdabd。由于我们事先已经分析过匹配串,得知其自身相同部分,因此在c处匹配失败,且失败字符为d.那么不就相同于已经完成匹配串到abd的匹配工作,下面应该是目标串的下一个字符与匹配串的a(第二个)。

看到了吧,自动机的思想就是如此。即分析匹配串的自身的性质,充分利用已有的匹配部分的内容,从而实现无回溯搜索匹配。
实现难点就在分析匹配串的自身的性质,并形成可供搜索匹配动作使用的结构化信息。
自动机的形象化表示:
finit state machine
代码如下:
  1 #!/urs/bin/env python
  2 # -*- coding=utf-8 -*-
  3
  4 """
  5     Author:Yangxiaowei
  6     Function:Search string-pattern with NFA(NOT Finite Automata Machine)
  7 """
  8
  9 class NFA:
 10
 11     def __init__(self,pattern):
 12         self.pattern = pattern
 13         if not self.pattern:return
 14         self.search_prepare()
 15
 16     def search_prepare(self):
 17         l = len(self.pattern)
 18
 19         #init
 20         self.nfa = []
 21         self._cur = 0
 22         self._end = l
 23         self._chars = set()
 24         for c in self.pattern:self._chars.add(c)
 25         for i in range(l+1):
 26             ls = {}
 27             for c in self._chars:ls[c]=0
 28             self.nfa.append(ls)
 29         self.nfa[0][self.pattern[0]] = 1
 30
 31         #analyze pattern and write info to nfa
 32         for i in range(1,self._end+1):
 33             s = self.pattern[0:i]
 34             for c in self._chars:
 35                 sc = s+c
 36                 for j in range(len(sc)):
 37                     if self.pattern.startswith(sc[j:]):
 38                         self.nfa[i][c] = i-j+1
 39                         break
 40
 41     def nfa_next(self,char):
 42         if char not in self._chars:self._cur = 0
 43         else:self._cur = self.nfa[self._cur][char]
 44         return self._cur
 45
 46     def search(self,content):
 47         result = []
 48         l = len(content)
 49         if not l:return result
 50         j = 0
 51         while j!=l:
 52             k = self.nfa_next(content[j])
 53             if k==self._end:result.append(l-j-1)
 54             j += 1
 55         return result
 56
 57
 58     def print_search(self,result,content):
 59         for i in result:
 60             print content[:i],
 61             print self.pattern,
 62             print content[i+self._end:]
 63
 64
 65
 66 if __name__ == "__main__":
 67     content = "abababcabaabccaba"
 68     nfa = NFA("abc")
 69     r = nfa.search(content)
 70     nfa.print_search(r,content)

发表评论