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("文件不存在")
三、心得