第一次个人编程作业

PSP表格

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

主要类设计

1. Document

   • 表示一篇文档,包含文本内容
   • 提供文本预处理功能,如移除标点、转小写等
   • 实现将文档切分为词元序列的方法

2. SimilarityDetector

   • 计算两篇文档相似度的核心类
   • 使用最长公共子序列(LCS)算法计算相似度
   • 包含基于动态规划和记忆化搜索的LCS计算方法

3. PlagiarismChecker

   • 主程序入口
   • 处理命令行参数
   • 读取文件内容
   • 使用SimilarityDetector计算相似度
   • 输出结果到指定文件

算法关键点

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

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

3. 性能改进

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

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

1. 哈希表存储词元
   • 将较短文档的词元使用哈希表存储
   • 查找是否属于LCS只需O(1)时间
2. 记忆化搜索
   • 避免重复计算相同的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)