这个作业属于哪个课程 | 计科21级12班 |
---|---|
这个作业要求在哪里 | 个人项目 |
这个作业的目标 | 熟悉个人软件开发流程 |
Github地址:zhaowendao123456/3121005137 (github.com)
一、PSP表格
*PSP2.1* | *Personal Software Process Stages* | *预估耗时(分钟)* | *实际耗时(分钟)* |
---|---|---|---|
Planning | 计划 | 20 | 15 |
· Estimate | · 估计这个任务需要多少时间 | 20 | 15 |
Development | 开发 | 600 | 800 |
· Analysis | · 需求分析 (包括学习新技术) | 120 | 60 |
· Design Spec | · 生成设计文档 | 30 | 120 |
· Design Review | · 设计复审 | 10 | 20 |
· Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 20 | 30 |
· Design | · 具体设计 | 60 | 30 |
· Coding | · 具体编码 | 360 | 480 |
· Code Review | · 代码复审 | 60 | 30 |
· Test | · 测试(自我测试,修改代码,提交修改) | 60 | 30 |
Reporting | 报告 | 100 | 150 |
· Test Report | · 测试报告 | 40 | 60 |
· Size Measurement | · 计算工作量 | 20 | 30 |
· Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 40 | 60 |
· 合计 | 720 | 965 |
二、需求分析
设计一个查重算法,用于计算两篇文档的重复率。
三、设计文档
3.1查重算法实现原理
3.1.1TF-IDF权重计算
TF即词频,用于描述词汇在文档中的权重,通过该词汇在文档中出现的次数来计算。
IDF即逆文档频率,由于在文档中“停用词”出现频率最高,而该类词汇对语义影响较小,而部分词汇在文档集合中占比较小而在待测试文档中词频较高,可以认为该类词汇对语义影响较大。因此引入逆文档频率计算权重。计算公式如下:
$$
idf=log(\frac{N}{df})
$$
使得低频词汇IDF较高,高频词汇IDF较低。
使用Wi表示每个词汇权重,公式如下:
$$
Wi=df\times idf
$$
3.1.2余弦相似性算法计算文本相似度
通过TF-IDF算法将待测文章向量化后,通过余弦定理计算两向量D1,D2的余弦值,当cos(D1,D2)趋近于1,文章相似度高,反之相似度低,高维向量余弦定理公式如下:
$$
cos\Theta=\frac{\sum w_k(D_1)\times w_k(D_2)}{\sqrt(\sum w_k^2(D_1)\times w_k^2(D2))}
$$
3.2实现思路
原理解释清楚后,代码实现思路就非常清晰了。首先从本地读取两篇待测文档,将文本进行分词并统计各个词汇数量,分别通过TF-IDF算法计算每个词汇权重,将两篇文本向量化。将向量带入余弦定理公式计算相似度。各个模块也是沿着这个思路逐一实现。
3.3模块接口及功能说明
模块 | 说明 |
---|---|
Count | 将文本分成词汇,通过jieba库实现 |
MergeWord | 合并两篇文档的关键词 |
Vector | 得出文档向量,通过TF算法实现 |
CosCount | 余弦相似度计算 |
四、测试报告
4.1性能测试
该性能测试使用Pycharm测试工具。test函数调用所有函数,因此不考虑其运行时间,从表中可知,Vector计算文档向量函数占用时间较长。
4.2结果测试
首先测试两个测试文本,其文本内容如下:
通过计算,得到文本相似度为0.535,因此,可以认为该项目精确度尚可。
通过该项目计算课堂提供测试样例的结果如下表:
与原文orig.txt对比的文件 | 相似度 |
---|---|
orig_0.8_del.txt | 0.576 |
orig_0.8_del_add.txt | 0.998 |
orig_0.8_dis_1.txt | 0.578 |
orig_0.8_dis_10.txt | 0.578 |
orig_0.8_dis_15.txt | 0.578 |
其结果截图如下: