浅析Python实现DFA算法
一、概述
计算机操作系统中的进程状态与切换可以作为 DFA 算法的一种近似理解。如下图所示,其中椭圆表示状态,状态之间的连线表示事件,进程的状态以及事件都是可确定的,且都可以穷举。
DFA 算法具有多种应用,在此先介绍在匹配关键词领域的应用。
二、匹配关键词
我们可以将每个文本片段作为状态,例如“匹配关键词”可拆分为“匹”、“匹配”、“匹配关”、“匹配关键”和“匹配关键词”五个文本片段。
【过程】:
- 初始状态为空,当触发事件“匹”时转换到状态“匹”;
- 触发事件“配”,转换到状态“匹配”;
- 依次类推,直到转换为最后一个状态“匹配关键词”。
再让我们考虑多个关键词的情况,例如“匹配算法”、“匹配关键词”以及“信息抽取”。
可以看到上图的状态图类似树形结构,也正是因为这个结构,使得 DFA 算法在关键词匹配方面要快于关键词迭代方法(for 循环)。经常刷 LeetCode 的读者应该清楚树形结构的时间复杂度要小于 for 循环的时间复杂度。
for 循环:
keyword_list = [] for keyword in ["匹配算法", "匹配关键词", "信息抽取"]: if keyword in "DFA 算法匹配关键词": keyword_list.append(keyword)
for 循环需要遍历一遍关键词表,随着关键词表的扩充,所需的时间也会越来越长。
DFA 算法:找到“匹”时,只会按照事件走向特定的序列,例如“匹配关键词”,而不会走向“匹配算法”,因此遍历的次数要小于 for 循环。具体的实现放在下文中。
【问】:那么如何构建状态图所示的结构呢?
【答】:在 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 } }
用嵌套字典来作为树形结构,key 作为事件,通过 is_end
字段来判断状态是否为最后一个状态,如果是最后一个状态,则停止状态转换,获取匹配的关键词。
【问】:如果关键词存在包含关系,例如“匹配关键词”和“匹配”,那么该如何处理呢?
【答】:我们仍然可以用 is_end
字段来表示关键词的结尾,同时添加一个新的字段,例如 is_continue
来表明仍可继续进行匹配。除此之外,也可以通过寻找除 is_end
字段外是否还有其他的字段来判断是否继续进行匹配。例如下面代码中的“配”,除了 is_end
字段外还有“关”,因此还需要继续进行匹配。
state_event_dict = { "匹": { "配": { "关": { "键": { "词": { "is_end": True }, "is_end": False }, "is_end": False }, "is_end": True }, "is_end": False } }
接下来,我们来实现这个算法。
三、算法实现
使用 Python 3.6 版本实现,当然 Python 3.X 都能运行。
3.1、构建存储结构
def _generate_state_event_dict(keyword_list: list) -> dict: state_event_dict = {} # 遍历每一个关键词 for keyword in keyword_list: current_dict = state_event_dict length = len(keyword) for index, char in enumerate(keyword): if char not in current_dict: next_dict = {"is_end": False} current_dict[char] = next_dict current_dict = next_dict else: next_dict = current_dict[char] current_dict = next_dict if index == length - 1: current_dict["is_end"] = True return state_event_dict
关于上述代码仍然有不少可迭代优化的地方,例如先对关键词列表按照字典序进行排序,这样可以让具有相同前缀的关键词集中在一块,从而在构建存储结构时能够减少遍历的次数。
3.2、匹配关键词
def match(state_event_dict: dict, content: str): match_list = [] state_list = [] temp_match_list = [] for char_pos, char in enumerate(content): # 首先找到匹配项的起点 if char in state_event_dict: state_list.append(state_event_dict) temp_match_list.append({ "start": char_pos, "match": "" }) # 可能会同时满足多个匹配项,因此遍历这些匹配项 for index, state in enumerate(state_list): if char in state: state_list[index] = state[char] temp_match_list[index]["match"] += char # 如果抵达匹配项的结尾,表明匹配关键词完成 if state[char]["is_end"]: match_list.append(copy.deepcopy(temp_match_list[index])) # 如果还能继续,则继续进行匹配 if len(state[char].keys()) == 1: state_list.pop(index) temp_match_list.pop(index) # 如果不满足匹配项的要求,则将其移除 else: state_list.pop(index) temp_match_list.pop(index) return match_list
3.3、完整代码
import re import copy class DFA: def __init__(self, keyword_list: list): self.state_event_dict = self._generate_state_event_dict(keyword_list) def match(self, content: str): match_list = [] state_list = [] temp_match_list = [] for char_pos, char in enumerate(content): if char in self.state_event_dict: state_list.append(self.state_event_dict) temp_match_list.append({ "start": char_pos, "match": "" }) for index, state in enumerate(state_list): if char in state: state_list[index] = state[char] temp_match_list[index]["match"] += char if state[char]["is_end"]: match_list.append(copy.deepcopy(temp_match_list[index])) if len(state[char].keys()) == 1: state_list.pop(index) temp_match_list.pop(index) else: state_list.pop(index) temp_match_list.pop(index) return match_list @staticmethod def _generate_state_event_dict(keyword_list: list) -> dict: state_event_dict = {} for keyword in keyword_list: current_dict = state_event_dict length = len(keyword) for index, char in enumerate(keyword): if char not in current_dict: next_dict = {"is_end": False} current_dict[char] = next_dict current_dict = next_dict else: next_dict = current_dict[char] current_dict = next_dict if index == length - 1: current_dict["is_end"] = True return state_event_dict if __name__ == "__main__": dfa = DFA(["匹配关键词", "匹配算法", "信息抽取", "匹配"]) print(dfa.match("信息抽取之 DFA 算法匹配关键词,匹配算法"))
输出:
[
{
'start': 0,
'match': '信息抽取'
}, {
'start': 12,
'match': '匹配'
}, {
'start': 12,
'match': '匹配关键词'
}, {
'start': 18,
'match': '匹配'
}, {
'start': 18,
'match': '匹配算法'
}
]
四、其他用法
4.1、添加通配符
在敏感词识别时往往会遇到同一种类型的句式,例如“你这个傻X”,其中 X 可以有很多,难道我们需要一个个添加到关键词表中吗?最好能够通过类似正则表达式的方法去进行识别。一个简单的做法就是“*”,匹配任何内容。
添加通配符只需要对匹配关键词过程进行修改:
def match(self, content: str): match_list = [] state_list = [] temp_match_list = [] for char_pos, char in enumerate(content): if char in self.state_event_dict: state_list.append(self.state_event_dict) temp_match_list.append({ "start": char_pos, "match": "" }) for index, state in enumerate(state_list): is_find = False state_char = None # 如果是 * 则匹配所有内容 if "*" in state: state_list[index] = state["*"] state_char = state["*"] is_find = True if char in state: state_list[index] = state[char] state_char = state[char] is_find = True if is_find: temp_match_list[index]["match"] += char if state_char["is_end"]: match_list.append(copy.deepcopy(temp_match_list[index])) if len(state_char.keys()) == 1: state_list.pop(index) temp_match_list.pop(index) else: state_list.pop(index) temp_match_list.pop(index) return match_list
main() 函数。
if __name__ == "__main__": dfa = DFA(["匹配关键词", "匹配算法", "信息*取", "匹配"]) print(dfa.match("信息抽取之 DFA 算法匹配关键词,匹配算法,信息抓取"))
输出:
[
{
'start': 0,
'match': '信息抽取'
}, {
'start': 12,
'match': '匹配'
}, {
'start': 12,
'match': '匹配关键词'
}, {
'start': 18,
'match': '匹配'
}, {
'start': 18,
'match': '匹配算法'
}, {
'start': 23,
'match': '信息抓取'
}
]
以上就是浅析Python实现DFA算法的详细内容,更多关于Python DFA算法的资料请关注猪先飞其它相关文章!
相关文章
- 这篇文章主要介绍了python-opencv-画外接矩形框的实例代码,代码简单易懂,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-04
Python astype(np.float)函数使用方法解析
这篇文章主要介绍了Python astype(np.float)函数使用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-06-08- 2022虎年新年即将来临,小编为大家带来了一个利用Python编写的虎年烟花特效,堪称全网最绚烂,文中的示例代码简洁易懂,感兴趣的同学可以动手试一试...2022-02-14
- 在本篇文章里小编给大家分享的是一篇关于python中numpy.empty()函数实例讲解内容,对此有兴趣的朋友们可以学习下。...2021-02-06
python-for x in range的用法(注意要点、细节)
这篇文章主要介绍了python-for x in range的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-10- 这篇文章主要介绍了Python 图片转数组,二进制互转操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要介绍了Python中的imread()函数用法说明,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-16
- 这篇文章主要介绍了python如何实现b站直播自动发送弹幕,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-02-20
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
python Matplotlib基础--如何添加文本和标注
这篇文章主要介绍了python Matplotlib基础--如何添加文本和标注,帮助大家更好的利用Matplotlib绘制图表,感兴趣的朋友可以了解下...2021-01-26- 这篇文章主要介绍了解决python 使用openpyxl读写大文件的坑,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-13
- 今天小编就为大家分享一篇python 计算方位角实例(根据两点的坐标计算),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
- 这篇文章主要为大家详细介绍了python实现双色球随机选号,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-05-02
- 在本篇文章里小编给大家整理的是一篇关于python中使用np.delete()的实例方法,对此有兴趣的朋友们可以学习参考下。...2021-02-01
- 这篇文章主要介绍了使用Python的pencolor函数实现渐变色功能,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-09
- 这篇文章主要介绍了python自动化办公操作PPT的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-05
Python getsizeof()和getsize()区分详解
这篇文章主要介绍了Python getsizeof()和getsize()区分详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-20- 这篇文章主要介绍了解决python 两个时间戳相减出现结果错误的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-12
- 这篇文章主要为大家详细介绍了python实现学生通讯录管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-25