淺析Python實現(xiàn)DFA算法
一、概述
計算機操作系統(tǒng)中的進程狀態(tài)與切換可以作為 DFA 算法的一種近似理解。如下圖所示，其中橢圓表示狀態(tài)，狀態(tài)之間的連線表示事件，進程的狀態(tài)以及事件都是可確定的，且都可以窮舉。
DFA 算法具有多種應用，在此先介紹在匹配關鍵詞領域的應用。
二、匹配關鍵詞
我們可以將每個文本片段作為狀態(tài)，例如“匹配關鍵詞”可拆分為“匹”、“匹配”、“匹配關”、“匹配關鍵”和“匹配關鍵詞”五個文本片段。
【過程】：
- 初始狀態(tài)為空，當觸發(fā)事件“匹”時轉換到狀態(tài)“匹”；
- 觸發(fā)事件“配”，轉換到狀態(tài)“匹配”；
- 依次類推，直到轉換為最后一個狀態(tài)“匹配關鍵詞”。
再讓我們考慮多個關鍵詞的情況，例如“匹配算法”、“匹配關鍵詞”以及“信息抽取”。
可以看到上圖的狀態(tài)圖類似樹形結構，也正是因為這個結構，使得 DFA 算法在關鍵詞匹配方面要快于關鍵詞迭代方法（for 循環(huán)）。經(jīng)常刷 LeetCode 的讀者應該清楚樹形結構的時間復雜度要小于 for 循環(huán)的時間復雜度。
for 循環(huán)：
keyword_list = []
for keyword in ["匹配算法", "匹配關鍵詞", "信息抽取"]:
if keyword in "DFA 算法匹配關鍵詞":
keyword_list.append(keyword)
for 循環(huán)需要遍歷一遍關鍵詞表，隨著關鍵詞表的擴充，所需的時間也會越來越長。
DFA 算法：找到“匹”時，只會按照事件走向特定的序列，例如“匹配關鍵詞”，而不會走向“匹配算法”，因此遍歷的次數(shù)要小于 for 循環(huán)。具體的實現(xiàn)放在下文中。
【問】：那么如何構建狀態(tài)圖所示的結構呢？
【答】：在 Python 中我們可以使用 dict 數(shù)據(jù)結構。
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 字段來判斷狀態(tài)是否為最后一個狀態(tài)，如果是最后一個狀態(tài)，則停止狀態(tài)轉換，獲取匹配的關鍵詞。
【問】：如果關鍵詞存在包含關系，例如“匹配關鍵詞”和“匹配”，那么該如何處理呢？
【答】：我們仍然可以用 is_end 字段來表示關鍵詞的結尾，同時添加一個新的字段，例如 is_continue 來表明仍可繼續(xù)進行匹配。除此之外，也可以通過尋找除 is_end 字段外是否還有其他的字段來判斷是否繼續(xù)進行匹配。例如下面代碼中的“配”，除了 is_end 字段外還有“關”，因此還需要繼續(xù)進行匹配。
state_event_dict = {
"匹": {
"配": {
"關": {
"鍵": {
"詞": {
"is_end": True
},
"is_end": False
},
"is_end": False
},
"is_end": True
},
"is_end": False
}
}
接下來，我們來實現(xiàn)這個算法。
三、算法實現(xiàn)
使用 Python 3.6 版本實現(xiàn)，當然 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
關于上述代碼仍然有不少可迭代優(yōu)化的地方，例如先對關鍵詞列表按照字典序進行排序，這樣可以讓具有相同前綴的關鍵詞集中在一塊，從而在構建存儲結構時能夠減少遍歷的次數(shù)。
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]))
# 如果還能繼續(xù)，則繼續(xù)進行匹配
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() 函數(shù)。
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實現(xiàn)DFA算法的詳細內容，更多關于Python DFA算法的資料請關注腳本之家其它相關文章！
相關文章
最近在帶孩子學習數(shù)獨，職業(yè)使然，就上網(wǎng)搜了下相關程序的解法，這里分享給大家，希望對大家學習python有所幫助2017-04-04
這篇文章主要介紹了python中的np.argmax() 返回最大值索引號操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
這篇文章主要介紹了Python類方法 & 靜態(tài)方法的相關資料，幫助大家更好的理解和學習python，感興趣的朋友可以了解下2020-08-08
python 使用turtule繪制遞歸圖形（螺旋、二叉樹、謝爾賓斯基三角形）
這篇文章主要介紹了python 使用turtule繪制遞歸圖形（螺旋、二叉樹、謝爾賓斯基三角形） ,需要的朋友可以參考下2019-05-05
利用Numba與Cython結合提升python運行效率詳解
近些年來， Numba和Cython在數(shù)學科學界得到了廣泛的關注。它們都提供了一種加速CPU密集型任務的方法，但以不同的方式。本文描述了它們之間體系結構的差異2021-09-09
Python3控制路由器——使用requests重啟極路由.py
通過本文給大家介紹Python3控制路由器——使用requests重啟極路由.py的相關知識，代碼寫了相應的注釋，以后再寫成可以方便調用的模塊，感興趣的朋友一起學習吧2016-05-05
pyhton中__pycache__文件夾的產(chǎn)生與作用詳解
這篇文章主要介紹了pyhton中__pycache__文件夾的產(chǎn)生與作用詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-11-11
python使用openpyxl庫修改excel表格數(shù)據(jù)方法
今天小編就為大家分享一篇python使用openpyxl庫修改excel表格數(shù)據(jù)方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-05-05
今天小編就為大家分享一篇利用python實現(xiàn)逐步回歸，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-02-02
這篇文章主要介紹了python 獲取剪切板內容的兩種方法，幫助大家更好的理解和學習python，感興趣的朋友可以了解下2020-11-11