起因: 从网页中爬去的页面，需要判断是否跟预设的关键词匹配(是否包含预设的关键词)，并返回所有匹配到的关键词 。
目前pypi 上两个实现
但是其实包都是基于DFA 实现的
这里提供源码如下:
#!/usr/bin/python2.6
# -*- coding: utf-8 -*-
import time
class Node(object):
def __init__(self):
self.children = None
# 标记匹配到了关键词
self.flag = False
# The encode of word is UTF-8
def add_word(root,word):
if len(word) = 0:
return
node = root
for i in range(len(word)):
if node.children == None:
node.children = {}
node.children[word[i]] = Node()
elif word[i] not in node.children:
node.children[word[i]] = Node()
node = node.children[word[i]]
node.flag = True
def init(word_list):
root = Node()
for line in word_list:
add_word(root,line)
return root
# The encode of word is UTF-8
# The encode of message is UTF-8
def key_contain(message, root):
res = set()
for i in range(len(message)):
p = root
j = i
while (jlen(message) and p.children!=None and message[j] in p.children):
if p.flag == True:
res.add(message[i:j])
p = p.children[message[j]]
j = j + 1
if p.children==None:
res.add(message[i:j])
#print '---word---',message[i:j]
return res
def dfa():
print '----------------dfa-----------'
word_list = ['hello', '民警', '朋友','女儿','派出所', '派出所民警']
root = init(word_list)
message = '四处乱咬乱吠，吓得家中11岁的女儿躲在屋里不敢出来，直到辖区派出所民警赶到后，才将孩子从屋中救出。最后在征得主人同意后，民警和村民合力将这只发疯的狗打死'
x = key_contain(message, root)
for item in x:
print item
if __name__ == '__main__':
dfa()
从正规式开始
通过下面的对应法则将正规式转换成NFA
例如：
运用子集法的3个概念：
(1 )状态集的ε-闭包: 状态集I中的任何状态s经任意条ε弧而能到达的所有状态的集合，定义为状态集I的ε -闭包，表示为ε -closure()。
(2)状态集的a弧转换: 状态集I中的任何状态s经过一条a弧而能到达的所有状态的集合，定义为状态集1的a弧转换，表示为move(l,a)。
(3)状态集的a弧转换的闭包a: lg= ε-closure(move(l,a))
上面的正规式转换成NFA：
先从初态0开始求：
【因为每个状态通过一条ε弧到达自己本身，所以求得ε的闭包包含自己】
（1）求0的ε的闭包：经过任意条ε所能到达的状态，集合为{0,1,3,4,5,6,7,9}
（2）求0的a弧转换：1经过a弧到达2，4经过a弧到达4，其余没有经过一条a弧到达某个状态，所以集合为{2,4}
（3）求a弧转换的闭包：{2,4}分别经过任意条ε所能到达的状态，集合为{2,4,6,7,9}
（4）求0的b弧转换：5经过b到5，7经过b到8，，其余没有经过一条b弧到达某个状态，所以集合为{5,8}
（5）求b弧转换的闭包：{5,8}分别经过任意条ε所能到达的状态，集合为{5,6,7,8,9}
0的ε-闭包：{0,1,3,4,5,6,7,9}
0的a弧转换：{2,4}
0的a弧转换的ε-闭包：{2,4,6,7,9}
0的b弧转换：{5,8}
0的b弧转换的ε-闭包：{5,6,7,8,9}
现在列一个表格：
（1）表格的列数为输入字符的个数+1，此题为a，b两个输入字符，所以为3列。
（2）第一列第一行填写初态的ε-闭包（此题0的ε-闭包），第二列第一行填写初态的a弧转换的ε-闭包（此题0的a弧转换的ε-闭包），第三列第一行填写初态的b弧转换的ε-闭包（此题0的b弧转换的ε-闭包）......以此类推。
（3）第一列的第二行以下填入上一行第二列以后的没有出现过的状态集。（此题第一行第二列第三列都没有出现在第一列中，将他们填入第一列）
下图为填好的表：
【新的终态的判断方法就是包含原来终态的集合就为终态，例如此题原来终态为9，所以包含9的集合就为终态，[双圈代表终态]；
新的初态就是包含原来初态的集合就为初态，例如此题原来初态为0，所以包含0的集合就为初态】
为表里的状态集重新标上号：
先了解几个概念：
1.多于状态：对于一个状态Si，若从开始状态出发，不可能到达改状态Si，则Si为多余（无用）状态。
2.死状态：对于一个状态Si，对于任意输入符号a，若转到它本身后，不可能从它到达终止状态，则称Si为死状态。
都称为无关状态
3.等价状态：若Si为自动机的一个状态，我们把从Si出发能导出的所有符号串的集合记为L（Si）。
设有两个状态Si和Sj，若有L（Si）=L（Sj），则称Si和Sj是等价状态。
4.可区别状态：自动机中两个状态Si和Sj，如果它们不等价，则称它们可区别。
5.两个状态(Si和Sj)等价的判断条件:
（1）状态Si和Sj必须同时为终止状态或同时为非终止状态。即终止状态和非终止状态是可区别的。
（2）状态Si和Sj对于任意输入符a∈Σ，必须转到等价的状态里，否则Si和Sj是可区别的。
DFA的化简算法：对于DFA M=(S,Σ,f,S0,Z)
(1)首先将DFA的状态集进行初始化，分成Π=(Z,S-Z);
(2) 用下面的过程对Π构造新的划分Π new
for (Π中每个组G) do //每个组都是一个状态集
begin
把G划分成小组，G中的任意两个状态Si和Sj在同一组中，当且仅当对于Σ中任意输入符号a ，Si和Sj的a转换是到同一组中，move(Si,a) ∈Gi ，move(Sj,a) ∈Gi。这样，只要Si和Sj的a转换是到不同的组中，则说明Si和Sj是可区别的，可进行划分。在Π new中用刚完成的对G的划分代替原来的G。
end ; Π := Π new；
(3)重复执行(2)，直到Π中每个状态集不能再划分(Π new= Π)为止;
(4)合并等价状态 ,在每个G中，取任意状态作为代表，删去其它状态;
(5)删去无关状态，从其它状态到无关状态的转换都成为无定义。
举例：
之前上面这个图画错了,现在图已经修改过了,谢谢提醒 :-D
这是DFA算法，自己设定好值，看下结果
import java.util.*;
import java.io.*;
class DFA
{
boolean recognizeString(int move[][], int accept_state[], String word)
{
int s=0;
for (int i = 0; i word.length(); i++)
{
char c = word.charAt(i);
s = move[s][c - 'a'];
}
for (int j = 0; j accept_state.length; j++)
if (s == accept_state[j]) return true;
return false;
}
public static void main(String args[]) throws IOException
{
int n, m;
BufferedReader in = new BufferedReader(new FileReader("DFA.in"));
StringTokenizer st = new StringTokenizer(in.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
while (n != 0)
{
int[][] move = new int[n][m];
for(int i=0; in; i++)
{
st = new StringTokenizer(in.readLine());
for (int j=0; jm; j++)
move[i][j] = Integer.parseInt(st.nextToken());
}
String[] temp = in.readLine().split("\\s");
int[] accept = new int[temp.length];
for (int i=0; iaccept.length; i++) accept[i] = Integer.parseInt(temp[i]);
String word = in.readLine();
while (word.compareTo("#") != 0)
{
DFA dfa = new DFA();
if (dfa.recognizeString(move, accept, word)) System.out.println("YES"); else System.out.println("NO");
word = in.readLine();
}
st = new StringTokenizer(in.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
}
}
}
首先划分终态集和非终态集，之后不断进行划分，直到不再发生变化。
每轮划分对所有子集进行。对一个子集的划分中，若每个输入符号都能把状态转换到等价的状态，则两个状态等价。
划分完成后，从每个子集选出一个代表，若DFA中存在两个子集内状态之间的转换，则MFA中两个子集的代表之间也存在对应的转换。简便方法：对每个子集删去除代表以外的状态，并把指向它们的箭弧改为指向代表。
MFA的初态是含有DFA初态的子集的代表。MFA的终态集是DFA终态集划分出来子集的代表。
最后，从MFA中删除从初态无法到达的状态和死状态（只有入射弧或指向自身的出射弧的非终止状态）。
去除不可达状态。建表，行列为不同状态，未标记的格子行列状态等价。首先标记行列一个非终止状态一个终止状态的格子。对未标记的格子(q,q')，若存在一个输入符号a，使q经a到达状态和q'经a到达状态不等价，则标记(q,q')。重复直到表格不再变化。
对于所有未标记的(q,q')，把与q'有关的转换都改到q上，删除q'。
本文转载自互联网，如有侵权，联系删除
