DFA称为确定性有限自动机，即有限自动机。特征：有一组有限的状态和一些从一个状态通向另一个状态的边。每条边都标有一个符号，其中一个状态是初始状态，一些状态是最终状态。与不确定有限自动机不同，在DFA中，来自同一状态的两个边缘符号没有相同的符号。
一.概述二。匹配关键词三。算法实现3.1。建造仓库结构。匹配关键词3.3。完成代码四。其他用途4.1。添加通配符。
目录
计算机操作系统中的进程状态和切换可以看作是对DFA算法的一种近似理解。如下图所示，椭圆代表状态，状态之间的连接代表事件。过程的状态和事件是可确定的，并且可以是详尽的。
DFA算法有很多应用。在这里，我们将介绍它在关键字匹配中的应用。
一、概述
我们可以把每个文本片段看作一个状态。例如，匹配关键字可以分成五个文本段：Pi、匹配、匹配关闭、匹配关键字和匹配关键字。
[流程]:
初始状态为空，当事件“马”被触发时，会过渡到状态“马”；
触发事件“匹配”并转换到状态“匹配”；
以此类推，直到它改变到最后一个状态“匹配关键字”。
我们来考虑多个关键词的情况，比如“匹配算法”、“匹配关键词”、“信息抽取”。
可以看出，上图中的状态图类似于树形结构，也正是因为这种结构，DFA算法在关键字匹配上比关键字迭代法(for loop)更快。经常刷LeetCode的读者应该知道，树形结构的时间复杂度小于for循环。
For循环：
keyword_list=[]
对于['匹配算法'，'匹配关键字'，'信息提取']中的关键字：
如果“DFA算法”中的关键字与关键字匹配：
关键字_列表.追加(关键字)
for循环需要遍历关键字列表，随着关键字列表的扩展，需要的时间会越来越长。
DFA算法：在找“马”的时候，只会根据事件去特定的序列，比如“匹配关键词”，而不是“匹配算法”，所以遍历的次数比for loop少。下面给出了的具体实现。
[问]:那么如何构建状态图中所示的结构呢？
【答】:在Python中，我们可以使用dict数据结构。
state_event_dict={
马':
匹配':{
计算':{
法国':
' is_end': True
},
' is_end': False
},
关闭':{
键':{
单词':{
' is_end': True
},
' is_end': False
},
' is_end': False
},
' is_end': False
},
' is_end': False
},
字母':{
利息':{
烟雾':
拍':{
' is_end': True
},
' is_end': False
},
' is_end': False
},
' is_end': False
}
}
以嵌套字典为树结构，以键为事件，用is_end字段判断状态是否为最后一个状态。如果是最后一个状态，则停止状态转换，获取匹配的关键字。
【问】:如果关键词之间存在包含关系，比如“匹配关键词”和“匹配”，应该怎么做？
【答】:我们还是可以用is_end字段来表示关键字的结束，增加一个新的字段，比如is_continue，表示匹配还可以继续。此外，还可以通过查找is_end字段以外的其他字段来确定是否继续匹配。比如下面代码中的“match”除了is_end字段还有“off”，所以需要继续匹配。
state_event_dict={
马':
匹配':{
关闭':{
'键': {
'词': {
' is_end': True
},
' is_end': False
},
' is_end': False
},
' is_end': True
},
' is_end': False
}
}
接下来，我们来实现这个算法。
二、匹配关键词
使用Python 3.6版本实现，当然Python 3 .X都能运行。
三、算法实现
定义_生成_状态_事件_字典(关键字_列表：列表)-格言：
state_event_dict={}
# 遍历每一个关键词
对于关键字列表中的关键字：
当前事件=状态事件
长度=长度(关键字)
对于索引，枚举中的字符（关键字):
如果茶不在当前字典中：
next_dict={'is_end': False}
当前字典[char]=下一个字典
当前字典=下一个字典
否则：
下一个字典=当前字典[字符]
当前字典=下一个字典
如果索引==长度- 1:
current_dict['is_end']=True
返回状态_事件_字典
关于上述代码仍然有不少可迭代优化的地方，例如先对关键词列表按照字典序进行排序，这样可以让具有相同前缀的关键词集中在一块，从而在构建存储结构时能够减少遍历的次数。
3.1、构建存储结构
def match(state_event_dict: dict，content: str):
match_list=[]
state_list=[]
temp_match_list=[]
对于char_pos，char in enumerate(内容):
# 首先找到匹配项的起点
如果在状态事件字典中有字符：
状态列表附加（状态事件字典)
temp_match_list.append({
' start': char_pos，
匹配":"
})
# 可能会同时满足多个匹配项，因此遍历这些匹配项
对于索引，枚举中的状态(状态列表):
如果充电状态：
状态列表[索引]=状态[字符]
temp _ match _ list[index][' match ']=char
# 如果抵达匹配项的结尾，表明匹配关键词完成
if state[char]['is_end']:
match _ list。追加(复制。deepcopy(临时匹配列表[索引])
# 如果还能继续，则继续进行匹配
if len(state[char].keys())==1:
状态_列表. pop(索引)
临时_匹配_列表. pop(索引)
# 如果不满足匹配项的要求，则将其移除
否则：
状态_列表. pop(索引)
临时_匹配_列表. pop(索引)
返回匹配列表
3.2、匹配关键词
进口关于
导入副本
美术博士（Doctor of Fine Arts的缩写）级：
def __init__(self，keyword_list: list):
self.state_event_dict=self ._生成_状态_事件_字典(关键字_列表)
定义匹配（自身，内容：字符串):
match_list=[]
state_list=[]
temp_match_list=[]
对于char_pos，char in enumerate(内容):
如果茶在自我.状态_事件_字典中：
状态列表附加（自我状态事件字典)
temp_match_list.append({
' start': char_pos，
匹配":"
})
对于索引，枚举中的状态(状态列表):
如果充电状态：
状态列表[索引]=状态[字符]
temp _ match _ list[index][' match ']=char
if state[char]['is_end']:
match _ list。追加(复制。deepcopy(临时匹配列表[索引])
if len(state[char].keys())==1:
状态_列表. pop(索引)
临时_匹配_列表. pop(索引)
否则：
状态_列表. pop(索引)
临时_匹配_列表. pop(索引)
返回匹配列表
@静态方法
定义_生成_状态_事件_字典(关键字_列表：列表)-格言：
state_event_dict={}
对于关键字列表中的关键字：
当前事件=状态事件
长度=长度(关键字)
对于索引，枚举中的字符（关键字):
如果茶不在当前字典中：
next_dict={'is_end': False}
当前字典[char]=下一个字典
当前字典=下一个字典
否则：
下一个字典=当前字典[字符]
当前字典=下一个字典
如果索引==长度- 1:
current_dict['is_end']=True
返回状态_事件_字典
if __name__=='__main__ ':
dfa=DFA(['匹配关键词', '匹配算法', '信息抽取', '匹配'])
print(dfa.match('信息抽取之美术博士(美术博士的缩写)算法匹配关键词，匹配算法'))
输出：
[
{
'开始':0,
匹配":"信息抽取'
}, {
'开始':12,
匹配":"匹配'
}, {
'开始':12,
匹配":"匹配关键词'
}, {
'开始':18,
匹配":"匹配'
}, {
'开始':18,
匹配":"匹配算法'
}
]
3.3、完整代码
四、其他用法
在敏感词识别时往往会遇到同一种类型的句式，例如"你这个傻x”，其中X可以有很多，难道我们需要一个个添加到关键词表中吗？最好能够通过类似正则表达式的方法去进行识别。一个简单的做法就是"*",匹配任何内容。
添加通配符只需要对匹配关键词过程进行修改：
定义匹配（自身，内容：字符串):
match_list=[]
state_list=[]
temp_match_list=[]
对于char_pos，char in enumerate(内容):
如果茶在自我.状态_事件_字典中：
状态列表附加（自我状态事件字典)
temp_match_list.append({
' start': char_pos，
匹配":"
})
对于索引，枚举中的状态(状态列表):
is_find=False
state_char=无
# 如果是* 则匹配所有内容
如果' * '处于状态：
state_list[index]=state['*']
state_char=state['*']
is_find=True
如果充电状态：
状态列表[索引]=状态[字符]
state_char=状态[字符]
is_find=True
如果是_查找：
temp _ match _ list[index][' match ']=char
if state_char['is_end']:
match _ list。追加(复制。deepcopy(临时匹配列表[索引])
if len(state_char.keys())==1:
状态_列表. pop(索引)
临时_匹配_列表. pop(索引)
否则：
状态_列表. pop(索引)
临时_匹配_列表. pop(索引)
返回匹配列表
主()函数。
if __name__=='__main__ ':
dfa=DFA(['匹配关键词', '匹配算法', '信息*取', '匹配'])
print(dfa.match('信息抽取之美术博士(美术博士的缩写)算法匹配关键词，匹配算法，信息抓取'))
输出：
[
{
'开始':0,
匹配":"信息抽取'
}, {
'开始':12,
匹配":"匹配'
}, {
'开始':12,
匹配":"匹配关键词'
}, {
'开始':18,
匹配":"匹配'
}, {
'开始':18,
匹配":"匹配算法'
}, {
'开始':23,
匹配":"信息抓取'
}
]
以上就是浅析计算机编程语言实现美术博士(美术博士的缩写)算法的详细内容，更多关于Python DFA算法的资料请关注我们其它相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。