一、算法概述本篇博客为模式串匹配算法课的实践作业(任意实现一个匹配算法并测试性能),我选择了一个比较简单也比较古老的算法
Aho-Corasick算法用来定位文本字符串中有限数量的任意关键字的所有出现。该算法利用关键字构造一个有限状态模式匹配机,然后利用模式匹配机对文本字符串进行单次处理。构建模式匹配机所花费的时间与关键字长度的总和成正比。模式匹配机在处理文本字符串时进行的状态转换的次数与关键字的数量无关。
1.模式匹配机- keywords: K = { y 1 , y 2 , … , y k } K=left{y_{1}, y_{2}, ldots, y_{k}right} K={y1,y2,…,yk},有限字符串集合。
- K的模式匹配机:输入:text string x,输出:x中K的关键字作为子字符串出现的位置。
- 模式匹配机由一组状态组成,每个状态用一个数字表示。通过连续读取x中的符号,进行状态转换和输出。模式匹配机的行为由三个函数决定:goto函数g、failure函数f和输出函数output。
- 以关键词{he , she , his , hers } 为例:
状态0通常被指定为启动状态。在上图中,一共有0、1、…9共10个状态,abc图分别表示goto,failure,output三个函数。
- goto函数g:将 状态和符号对 映射到一个状态,或者映射为失败。上图中的有向图表示goto函数。例如,标记h为0到1的边表示g (0, h) = 1(没有箭头表示失败)。
- failure函数f:将一个状态映射到另一个状态。当goto函数报告失败时,将咨询failure函数。
- output函数:某些状态被指定为输出状态,表明找到了一组关键字。输出函数通过将一组关键字(可能为空)与每个状态相关联来形式化这个概念。
模式匹配机的运行周期定义如下:设s是机器的当前状态,a是输入字符串x的当前符号。
- 如果g(s, a) = s’,则机器进行goto函数转换。它进入状态s’, x的下一个符号成为当前的输入符号。如果,输出output(s’) 不等于空,机器输出的s’以及当前输入符号的位置。操作周期完成。
- 如果g(s, a) = fail,则机器查找failure函数f,进行故障转换。如果f(s) = s’,则机器以s’为当前状态,a为当前输入符号重复循环。
初始时,机器的当前状态是启动状态,文本字符串的第一个符号是当前输入符号。然后,机器通过对文本字符串的每个符号进行一个操作循环来处理文本字符串。例如,以上图中的机器来处理输入文本串“usher”。
- 处于状态4且当前输入符号为e时:g(4, e)= 5, 机器进入状态5,前进到下一个输入符号并发出output(5),表明它在文本字符串中位置4的末尾找到了关键字“she”和“he”。
- 处于状态5且当前输入符号为r时:g(5, r) =fail,机器进入状态2 = f(5)。又由于g(2, r)= 8,M进入状态8并前进到下一个输入符号。在这个运行周期中没有产生任何输出。
这一小节将展示如何从一组关键字构造有效的goto、failure和output函数。该结构分为两部分。在第一部分,确定状态和goto函数。在第二部分,计算failure函数。output函数的计算从构造的第一部分开始,在第二部分完成。
Goto 函数- 为了构造goto函数,需要构造一个goto graph。从一个代表状态0的顶点开始,然后,通过向图中添加从状态0开始的有向路径,将每个关键字y输入到图中。新的顶点和边被添加到图中,这样,从0状态开始,图中就会有一条指明关键字y的路径。关键字y被添加到该路径终止状态的输出函数中。
-
failure函数由goto函数构造。定义goto图中状态s的深度为从起始状态到s的最短路径的长度。因此上图 (a)中,启动状态为深度0,状态1和3为深度1,状态2、状态4和状态6为深度2。先计算深度为1的所有状态的失效函数,然后计算深度2的所有状态的失效函数,以此类推,直到计算出所有状态的失效函数(除了没有定义失效函数的状态0)。计算某一状态下失效函数f的算法在概念上很简单。令所有深度为1的状态有f(s)=0,现在假设所有深度小于d的状态都计算了f。failure函数深度d的状态由深度小于d的状态的失效函数计算。深度d的状态可以由深度d-1状态的goto函数的非失效值确定。
-
具体来说,为了计算深度d状态的失效函数,我们考虑深度d-1的每个状态r,并执行以下操作: 1. 如果对于所有的a,g(r, a) =fail,什么也不做。2. 否则,对于每个符号a,g (r, a) = s,做如下操作:第一步:设置 state = f( r )。第二步:执行 state⬅f(state)语句零次或多次,直到state的值达到g (state, a)≠fail。第三步:设f( s ) = g (state, a)。
-
例如,根据上图的 (a)计算failure函数,我们首先设置f(1) = f(3) = 0 (因为状态1和状态3是深度为1的状态)。然后我们计算3失效函数为2、6、4,状态深度为2。为了计算f(2),我们设state = f(1) = 0;由于g (0, e)=0,我们得到f(2)=0。为了计算f(6),我们设state = f(1) = 0;由于g (0, i) = 0,我们得到f(6)=0。为了计算f(4),我们设state =f (3) = 0;由于g(0, h) = 1,我们发现f(4) = 1。继续这种方式,我们得到了上图(b)所示的failure函数。
-
在计算failure函数的过程中,也更新了output函数。当我们确定f(s) = s’ 时,将状态s的输出与状态s’的输出合并。
def patternMatchingMachine(text, keywords): # 算法1
symbols = set(list(''.join(keywords)))
goto, output = gotoFunction(keywords, symbols)
failure, output = failureFunction(keywords, symbols, goto, output)
state = 0
for i in range(len(text)):
if text[i] in symbols:
# we look for another path or 0
while (state, text[i]) not in goto.keys() and state != 0:
state = failure[state]
# we progress in new path or start again at start state
state = goto[(state, text[i])]
if state in output.keys():
print("主串:",text,"中存在模式串:", output[state],"位置:", i + 1)
算法二:Goto 函数的构建
def gotoFunction(keywords, symbols): # algorithm 2
goto = {}
output = {}
newstate = 0 # start state
for i in range(len(keywords)):
state = 0
j = 0
# we follow the path if the keyword overlaps with one already in it
while (state, keywords[i][j]) in goto.keys():
state = goto[(state, keywords[i][j])]
j += 1
# we add a path in the graph until the keyword is completely added
for p in range(j, len(keywords[i])):
newstate += 1 # not yet used state
goto[(state, keywords[i][p])] = newstate
state = newstate
# the last state corresponds to the end of the keyword
output[state] = [keywords[i]]
# all symbols found in keywords but not in first position point to start state
for a in symbols:
if (0, a) not in goto.keys():
goto[(0, a)] = 0
return goto, output
算法三:Failure函数的构建
def failureFunction(keywords, symbols, goto, output): # algorithm 3
failure = {}
queue = []
# we compute depth = 1
for a in symbols:
if goto[(0, a)] != 0:
s = goto[(0, a)]
queue.append(s)
failure[s] = 0 # depth -1 = 0
# we compute depth > 1
while queue != []:
r = queue[0] # first-in
del queue[0] # first-out
for a in symbols:
if (r, a) in goto.keys():
s = goto[(r, a)]
queue.append(s)
state = failure[r] # state of depth -1
# since (0, any a) is in the grap, a state will always be found
while (state, a) not in goto.keys():
state = failure[state]
# depth -1 = previous state with same symbol or 0
failure[s] = goto[(state, a)]
# failure[s] is in output if a keyword ends at this state
if failure[s] in output.keys():
output[s].extend(output[failure[s]])
return failure, output
三、算法测试
测试思路:
- 读入两个txt文件分别作为主串和关键词,当主串中存在与某个关键词相同的子串时,输出主串,命中的关键词,以及关键词在主串中的位置,同时输出时间消耗,该时间包含构造goto,failure,output 以及搜索的时间。
测试实施:
- url_2w.txt 中有2万条url,每一条url作为一条关键词,将所以的关键词输入到匹配机中构建一棵trie树。
- url_data.txt中有100w条url,每一条url作为一条待搜索的主串,在构造好关键词tire树后,遍历每一条主串进行搜索。
- 测试时将一些用户友好性的输出注释后,速度大幅度提升。
- 关键词:2w条,主串:100w条
- 总耗时:30.72195601s,平均每条主串耗时:0.0000307s
参考:
- Efficient string matching: an aid to bibliographic search https://dl.acm.org/doi/abs/10.1145/360825.360855
- https://github.com/helene-peree/String-matching



