Github連結
一、PSP表格
| PSP2.1 | Personal Software Process Stages | 預估耗時（分鐘） | 實際耗時（分鐘） |
|---|---|---|---|
| Planning | 計劃 | 30 | 60 |
| · Estimate | · 估計這個任務需要多少時間 | 120 | 900 |
| Development | 開發 | 150 | |
| · Analysis | · 需求分析 (包括學習新技術) | 90 | |
| · Design Spec | · 生成設計文檔 | ||
| · Design Review | · 設計複審 | 75 | |
| · Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | 20 | 10 |
| · Design | · 具體設計 | 100 | |
| · Coding | · 具體編碼 | ||
| · Code Review | · 代碼複審 | ||
| · Test | · 測試（自我測試，修改代碼，送出修改） | ||
| Reporting | 報告 | ||
| · Test Repor | · 測試報告 | 15 | |
| · Size Measurement | · 計算工作量 | 5 | |
| · Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | ||
| · 合計 | 940 | 1775 |
二、計算子產品接口
(2.1)計算子產品接口的設計與實作過程
2.1.1思路來源
拿到題目原先是打算直接用正規表達式處理，敏感詞篩選嘛簡單，看到題目後續輸出要求以及處理要求後徹底傻眼了，看來隻能面向百度(Google)程式設計了，後來想着這玩意涉及到的用途可多去了，再加上這些敏感詞絕大部分試圖通過讀音或者字形相近來進行僞裝以逃避檢測系統，現有的比對算法可以檢測出讀音完全一樣的詞語，但不能準确識别讀音相近和字形相近的異體字，簡單來說就是中文處理敏感詞非常棘手，那麼對應的相關領域的論文總該被知網收錄吧，于是(感謝福大賬号讓我能白嫖論文)，看了看論文的關鍵字音形碼(雖然我最後沒有用到但是我實作了)、字典樹、模糊比對，于是思路便有了，但是其實後面這些算法确實是實作了，唯一能用的上還是隻有AC自動機，這篇論文直接為我提供了參考的大方向，節約了不少"摸着石頭過河"的時間。
2.1.2項目設計
如果僅僅談到最終代碼所要用到的類，函數的數量，那麼可以很快就說完，最終實作的類有結點類和AC樹類，它們直接的關系好比你中有我，我中有你，脫離了AC樹類，結點類的存在毫無意義，脫離了結點類，AC樹類的實作難度較大。
對于結點類中實作了資料的封裝，非葉子節點條件下将包含目前節點的孩子節點的字典、目前節點的對應的字詞資訊、失敗指針指派，對于葉子節點額外将源敏感詞，和目前組合的敏感詞的長度指派，對于AC樹類中實作了封裝根節點、用于處理漢字拼音的Pinyin對象、存放轉換敏感詞後獲得的矩陣、以及敏感詞組合混搭形成的詞組序列和比對成功的組合内容。
在AC樹類中添加了協調處理函數prepareWork這是用于協調處理我的敏感詞轉換群組合以及插入的必要函數，通過終端輸入相應指令後通過讀取檔案中的所有敏感詞彙聚形成的清單傳入prepareWokr函數中，該函數調用str2matrix函數(這個2我覺得命名方式非常诙諧，最初接觸的時候是在matlab上看到的，原先猜不出這個2的具體含義直到我念了念它的對應的英文，two(to)????)将每個敏感詞轉換成對應的組合矩陣，在str2matrix函數中調用insertKey函數和recursionInsert函數實作敏感詞組合形成的組合矩陣，然後将調用build_tree函數将對應的獲得敏感詞組合成的所有新詞彙插入到字典樹中，進而調用make_fail函數為字典樹的每個結點建立失敗指針，可以說prepareWork在初步形成敏感詞字典樹中起到了總指揮的作用，其餘函數在引導下分工合作。上圖：
AC樹類中的搜尋函數之間的關系是，如圖：
2.1.3關鍵算法
有好幾個需要分别介紹：
敏感詞矩陣轉換：将敏感詞轉換成對應的組合矩陣，中文敏感詞和英文處理方法是一緻的都是利用AC樹類的Pinyin對象提取敏感詞的拼音和對應的拼音首字母去，利用正規表達式去除多餘的"-"，然後利用遞歸的方式将每個獨立的闆塊互相連接配接，上圖:
區分完整的拼音和拼接的拼音原因是，處理諧音字和繁體字時是通過擷取整個字的拼音，然後直接判斷有無對應的word(即目前節點資訊)是該拼音，而對應有些敏感詞試圖通過拼音僞裝的方式，則通過拼接的拼音即将一個拼音拆成多個字母，每個節點僅包含該拼音的一個字母。以"漢字"為例子，樹的一部分長這樣：
AC自動機：建立字典樹->建構fail指針->查找比對
1.建構字典樹：根據輸入的敏感詞，建構字典樹。在建構字典樹的過程中，如果從根結點到某個節點的路徑完全比對上某個敏感詞，則将這個敏感詞的長度加入節點的存儲資訊中（用于後續搜尋比對時能還原出比對到的敏感詞）。
2.建構fail指針：由于fail指針的加入，在節點比對失敗時，不用重新從根結點出發進行查找，可以直接跳到失敗指針指向的節點進行下一步查找，進而減少搜尋路徑，大大提高搜尋效率
3.查找比對：搜尋過程，先按字典樹的查找過程進行比對，如果在某個節點比對失敗，則運用失敗指針跳轉到下一個節點繼續進行比對。當搜尋到某個結點時，如果該節點存儲了模式串的資訊（模式串的長度），對進行處理（輸出），否則不額外處理。當然會出現關鍵字可能處理的時候發生重疊例如當拼音首字母和拼音出現的時候，需要向前回溯，利用目前結點保留的長度資訊結合向前回溯來判斷是否為同一種敏感詞隻是因為處理不夠合理所造成的。
2.1.4獨到之處
應該就是将敏感詞拆分後組合成不同的比對詞彙，然後将組合成的比對詞彙插入到字典樹中，主要是用到遞歸，遞歸這個寫的真讓人痛不欲生，但又不得不稱贊遞歸寫得好代碼就相對簡潔。這部分展現在str2matrix,insertKey和recursionInsert函數的配合以及prepareWork的協調，如果不是有prepareWork函數的協調那可能得把所有功能塞一個函數裡，搞得又臭又長。
(2.2)計算子產品接口部分的性能改進
從上圖可知，代碼中程式消耗最大的函數來源于xpinyin庫，漢字轉換成對應的拼音需要消耗大量時間，對于這部分性能的改進我無能為力，對應search函數的性能基于AC自動機的搜尋，時間複雜度為O(N+M)，就目前來看采用的算法也是我無法改進的，效率的拖慢估計是因為我内置了幾個用于判斷字元和比對處理的函數，這部分函數是必要的且經過實踐邏輯無誤，幾個函數之間密切相關試圖優化一個(雖然我也沒有法子)就有可能導緻其餘的處理不如預期，但是，其實我是有優化過的從最初的DFA字典樹的方式聽說AC自動機可以建構fail指針當比對出錯時進行回溯節省大量時間，是以是有個優化的過程是将整體的代碼進行重構，由最初的DFA算法改進到實作fail指針的AC自動機，但是對應其餘部分例如建構敏感詞矩陣，目前來看遞歸是最好的實作方式也是不可改進的方式，如果需要展示自己編寫的消耗時間最大的函數那應該是如下：
def search(self, sentence, line):
# index_store用于存儲相應的比對開始的下标，主要用于避免關鍵詞重疊
# 用于篩選關鍵字避免出現添加關鍵字的子集情況
# start用于輔助糾正關鍵字重疊的情況
index_store = []
tmp = self.root
for index, letter in enumerate(sentence):
if self.illegalWord(letter):
# 說明比對已經開始，非法字元可以通過，中文中插入數字字元則不能通過
continue
letter = self.p_worker.get_pinyin(letter).replace('-', '')
while tmp.children.get(str.lower(letter)) is None and tmp.fail is not None:
tmp = tmp.fail
# 比對開始
if tmp.children.get(str.lower(letter)) is not None:
tmp = tmp.children.get(str.lower(letter))
# 如果temp的fail為空，代表temp為root節點，
# 沒有在樹中找到符合的敏感字，故跳出循環，檢索下個字元
else:
continue
# 如果檢索到目前節點的長度資訊存在，則代表搜尋到了敏感詞，列印輸出即可
if tmp.length:
# af_start用于判别上一原文敏感詞是否屬于目前原文敏感詞内容
af_start = self.matched(node=tmp, sentence=sentence, cur_pos=index, line=line)
if len(index_store):
if af_start == index_store[len(index_store) - 1]:
# 說明上個原文敏感詞還真是目前敏感詞的子集
self.combination.pop(len(self.combination) - 2)
index_store.append(af_start)
對于這個search函數改進我隻能說祖宗之法不可變啊????，大部分基于最初的AC自動機更改目前來看尚無更好方式。
(2.3)計算子產品部分單元測試展示
大概就對代碼中的search函數進行測試，由于存在誤差就是對應的偏旁部首查詢實在無能為力，(時間來不及，前面編碼算法啥的占用時間過長關鍵又沒用到)就直接針對不同的樣例進行測試，目前來看夠構造有:1.無修改内容；2.中文中插入空格，字母，數字和非法字元等；3.中文采用諧音，拼音，首字母甚至繁體以及偏旁部首；4.英文中插入字元；5.英文大小寫變化；覆寫率以及情況如下:
from ACTrie.actrie import Trie
AcTrie = Trie()
# 測試無修改
word_store = ["中文"]
AcTrie.prepareWork(word_store)
AcTrie.search("中文", line=1)
assert AcTrie.combination[0] == "Line1: <中文> 中文"
# 中文中插入非法字元
AcTrie.search("中*文", line=1)
assert AcTrie.combination[1] == "Line1: <中文> 中*文"
# 中文插入字母，數字
AcTrie.search("中a文 中1文", line=1)
assert len(AcTrie.combination) == 2
# 中文采用諧音，拼音以及首字母
AcTrie.search("種文", line=1)
assert AcTrie.combination[2] == "Line1: <中文> 種文"
AcTrie.search("中wen", line=1)
assert AcTrie.combination[3] == "Line1: <中文> 中wen"
AcTrie.search("中w", line=1)
assert AcTrie.combination[4] == "Line1: <中文> 中w"
# 英文插入字元
word_store.clear()
word_store = ["ch"]
AcTrie.prepareWork(word_store)
AcTrie.search("c**h", line=1)
assert AcTrie.combination[5] == "Line1: <ch> c**h"
# 英文插入數字
AcTrie.search("c23h", line=1)
assert AcTrie.combination[6] == "Line1: <ch> c23h"
# 英文大小寫變化
AcTrie.search("CH", line=1)
assert AcTrie.combination[7] == "Line1: <ch> CH"
(2.4)計算子產品部分異常處理說明
對于目前項目代碼可能出現的異常有指令行參數錯誤，以及檔案讀寫錯誤，具體展現在檔案讀取時檔案不存在這個錯誤，對于這些錯誤進行處理，建構測試樣例大緻可以分為，指令行參數錯誤輸入的指令行參數數目過少或者過多，對于指令行參數過少或者過多，采用的方式是直接退出程式，避免輸出奇奇怪怪的結果，而對于檔案讀寫錯誤，目前來看涉及的是檔案不存在，對于檔案不存在是指words.txt和org.txt檔案不存在，對于檔案不存在的讀功能出錯采用try+except方式捕獲并提示，具體在main.py入口中。
指令行參數錯誤：對于指令行參數錯誤僅僅進行簡單的處理，即判斷指令行參數數目是否正确，以及判斷對應位置的對應參數是否正确，樣例建構以及對應場景聲明：
1.指令行參數缺失或備援，輸入過多或者過少例如python main.py words.txt org.txt:
2.指令行參數錯誤，例如對應位置參數不合理，像python main.py word.txt org.txt ans.txt：
這部分處理代碼如下，對于指令行參數先判斷數量，數量過多或者過少直接提示使用者後退出程式，對于數量合格的指令行參數，檢驗對應位置的對應參數的是否合理，不合理可能導緻讀取内容不符合要求，例如本來應該先讀敏感詞檔案結果讀成了待檢測檔案這是不允許的，對于這樣的錯誤提示使用者後直接退出程式即可：
args = sys.argv
# 參數錯誤
if len(args) != 4:
print("參數數目備援或者缺失")
exit(-1)
if args[1] != "words.txt":
print("敏感詞檔案參數錯誤")
exit(-1)
if args[2] != "org.txt":
print("待檢測檔案參數錯誤")
exit(-1)
if args[3] != "ans.txt":
print("答案寫入檔案參數錯誤")
exit(-1)
try:
f = open(args[1], encoding="utf-8")
# 讀取敏感詞檔案一次性讀取所有行數
word_store = f.readlines()
f.close()
# 開始插入敏感詞到樹中
AcTrie.prepareWork(word_store)
# 讀入待檢測檔案
f = open(args[2], encoding="utf-8")
contents = f.readlines()
f.close()
# 開始比對對應的字段
for line, content in enumerate(contents):
AcTrie.search(content, line + 1)
# 寫入到檔案中
AcTrie.writeFile(args[3])
except FileNotFoundError:
print("檔案不存在")
三、心得