| 这个作业属于哪个课程 | 计科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 |
其结果截图如下：
