软件工程-论文查重

seedwds / 2024-03-19 / 原文

第一次个人编程作业

这个作业属于哪个课程	<软件工程2024-双学位>
这个作业要求在哪里	<软件工程第一次个人编程作业>
这个作业的目标	完成编码任务

PSP表格

PSP2.1	Persenonal Software Process Stages	预计耗时（分钟）	实际耗时（分钟）
Planning	计划	30	30
Estimate	估计这个任务需要多少实践	10	10
Development	开发	120	70
- Analysis	需求分析（包括学习新技术）	30	20
- Design Spec	生成设计文档	20	10
- Design Review	设计复审	10	5
- Coding standard	代码规范（为目前的开发指定合适的规范）	15	10
- Design	具体设计	20	15
- Coding	具体编码	30	20
- Test	代码复审	15	10
- Reporting	测试（自我测试，修改代码，提交修改）	10	5
- Test Report	报告	10	5
- Size Measurement	计算工作量	10	5
- Postmortem & Process Improvement Plan	事后总结，并提出过程改进计划	20	15
	合计	300	195

2. 计算模块接口设计与实现

主要类设计

Document
- 表示一篇文档,包含文本内容
- 提供文本预处理功能,如移除标点、转小写等
- 实现将文档切分为词元序列的方法
SimilarityDetector
- 计算两篇文档相似度的核心类
- 使用最长公共子序列(LCS)算法计算相似度
- 包含基于动态规划和记忆化搜索的LCS计算方法
PlagiarismChecker
- 主程序入口
- 处理命令行参数
- 读取文件内容
- 使用SimilarityDetector计算相似度
- 输出结果到指定文件

算法关键点

文档预处理: 过滤掉标点符号、转为小写等,使文档标准化
词元序列化: 将文档切分为词元(token)序列,作为相似度计算的基础
LCS算法: 计算两文档词元序列的最长公共子序列长度
相似度计算:
相似度 = LCS长度 / max(原文词元数, 抄袭版词元数)

该算法的独到之处是使用LCS作为相似度计算的核心,能够规避"交换词序"这类改动的影响。

3. 性能改进

最初的LCS动态规划算法时间复杂度为O(mn),m和n分别为两文档词元序列长度,当文档较长时会导致性能低下。

为加速计算,我引入了以下优化策略:

哈希表存储词元
- 将较短文档的词元使用哈希表存储
- 查找是否属于LCS只需O(1)时间
记忆化搜索
- 避免重复计算相同的LCS子问题
- 使用记忆化数组存储子问题解,降低时间复杂度至O(mn)

经过上述优化,算法在长文档上的性能有了极大提升:

![算法性能分析][]

如图所示,消耗时间最长的函数已由LCS计算变为底层的文档预处理函数。

4. 单元测试

编写了以下单元测试用例:

import unittest
from plagiarism_checker import *

class TestSimilarityDetector(unittest.TestCase):

    def test_identical(self):
        doc1 = Document("The quick brown fox jumps over the lazy dog.")
        doc2 = Document("The quick brown fox jumps over the lazy dog.")
        result = SimilarityDetector.compute_similarity(doc1, doc2)
        self.assertAlmostEqual(result, 1.0)
    
    def test_different(self):
        doc1 = Document("I have a dream that one day...")
        doc2 = Document("In the beginning, God created the heavens and the earth...")
        result = SimilarityDetector.compute_similarity(doc1, doc2)
        self.assertAlmostEqual(result, 0.0)
        
    def test_reordered(self):
        doc1 = Document("The brown quick fox jumps lazy over the dog.")
        doc2 = Document("The quick brown fox jumps over the lazy dog.") 
        result = SimilarityDetector.compute_similarity(doc1, doc2)
        self.assertAlmostEqual(result, 1.0)

主要测试点包括:

完全相同的文档
完全不同的文档
存在词序改动的情况
删除/增加少量词语的情况

通过IDE的测试覆盖率分析工具,测试覆盖率达到了85%:

测试结果

5. 异常处理

针对以下几种可能的异常情况,做了处理:

1.文件不存在异常

目标: 提醒用户输入了无效的文件路径

测试用例:

def test_file_not_found(self):
    with self.assertRaises(FileNotFoundError):
        PlagiarismChecker.run("fakefile.txt", "orig.txt", "output.txt")

2.文件读取异常

目标: 捕获文件读取过程中的异常,如权限、磁盘空间等问题

测试用例:

def test_permission_denied(self):
# 创建一个临时只读文件

    file = open("temp.txt", "w")
    file.close()
    os.chmod("temp.txt", 0o400) # 设置为只读
    with self.assertRaises(PermissionError):
    doc = Document("temp.txt")
    
os.remove("temp.txt")

3.输入文件为空

目标: 确保输入文件有内容,防止除0错误

测试用例:

def test_empty_file(self):
    doc1 = Document("") 
    doc2 = Document("This is not empty.")
    with self.assertRaises(ValueError):
        SimilarityDetector.compute_similarity(doc1, doc2)