个人项目
| 项目 | 内容 |
|---|---|
| 这个作业属于哪个课程 | [软件工程](首页 - 计科23级12班 - 广东工业大学 - 班级博客 - 博客园) |
| 这个作业要求在哪里 | [作业要求](个人项目 - 作业 - 计科23级12班 - 班级博客 - 博客园) |
| 这个作业的目标 | 训练个人项目软件开发能力，学会使用性能测试工具和实现单元测试优化程勋 |
GitHub代码仓库 ：lei
PSP2表格
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 10 | 15 |
| Estimate | 估计这个任务需要多少时间 | 60 | 90 |
| Development | 开发 | 200 | 220 |
| Analysis | 需求分析 (包括学习新技术) | 30 | 40 |
| Design Spec | 生成技术文档 | 30 | 30 |
| Design Review | 设计复审 | 20 | 20 |
| Coding Standard | 代码规范 (为目前的开发制定合适的规范) | 10 | 10 |
| Design | 具体设计 | 30 | 40 |
| Coding | 具体编码 | 150 | 250 |
| Code Review | 代码复审 | 30 | 30 |
| Test | 测试（自我测试，修改代码，提交修改） | 20 | 30 |
| Reporting | 报告 | 60 | 100 |
| Test Repor | 测试报告 | 20 | 10 |
| Size Measurement | 计算工作量 | 60 | 45 |
| Postmortem & Process Improvement Plan | 事后总结，并提出过程改进计划 | 40 | 30 |
一、代码组织与模块设计
1. 模块划分与函数职责
代码采用 函数式模块化设计，主要功能由以下函数协同完成：
| 模块 | 函数/组件 | 职责 |
|---|---|---|
| 文件处理模块 | read_file |
读取文本文件内容，支持 UTF-8 中文 |
get_file_name |
从完整路径中提取文件名（便于结果输出） | |
| 核心算法模块 | lcs_similarity |
计算两个字符串的最长公共子序列（LCS）相似度 |
| 流程控制模块 | main |
解析命令行参数，协调文件读取、算法调用及结果输出 |
| 数据生成模块 | generate_dataset |
自动生成原文与抄袭版文件，用于测试和性能验证 |
2. 类与函数关系图
二、算法关键实现
1. LCS 动态规划算法
核心逻辑：状态转移方程
dp[i][j]={dp[i−1][j−1]+1if a[i−1]==b[j−1]max(dp[i−1][j],dp[i][j−1])otherwisedp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } a[i-1] == b[j-1] \ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases}
空间优化：采用 滚动数组，将空间复杂度从 O(n×m)O(n \times m) 降低到 O(min(n,m))O(\min(n,m))。
prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):for j in range(1, n + 1):if a[i - 1] == b[j - 1]:curr[j] = prev[j - 1] + 1else:curr[j] = max(prev[j], curr[j - 1])prev, curr = curr, [0] * (n + 1)
2. 中文字符处理
文件读取时强制指定 encoding="utf-8"，保证中文不乱码。
相似度计算基于字符级别（而非单词），因此天然支持中文。
三、设计独到之处
1. 内存效率优化
- 滚动数组 技术：仅保存两行 DP 数组，避免大规模内存开销。
- 文本直接处理：无需额外分词，保持输入数据简洁。
2. 鲁棒性设计
- 空文件处理：检测到空输入时直接返回
0.00%。 - 路径兼容性：
os.path.basename适配 Windows/Unix 风格路径。 - 异常处理：文件不存在或无法读取时，自动输出 0 相似度。
3. 输出友好性
- 历史保留：结果文件采用追加模式，支持多次运行累积记录。
- 格式化输出：结果以固定两位小数输出，便于人工查看或进一步分析。
四、计算模块接口部分的性能改进实践
1. 初始性能瓶颈分析
测试数据：两个 5000 字符的文本
原始性能：
- 时间：约 2.2 秒
- 内存：约 50 MB
2. 优化策略与实现
| 优化方向 | 具体措施 | 性能提升 |
|---|---|---|
| 算法优化 | 滚动数组替代完整 DP 表 | 内存降低 90%+ |
| 内存访问优化 | 按行连续访问数组，减少 Cache Miss | 时间缩短约 15% |
| 文件处理优化 | UTF-8 编码统一，避免重复解码 | 提升鲁棒性 |
3. 关键优化代码示例
prev, curr = curr, [0] * (n + 1) # 内存复用，减少开销
4. 最终性能对比
| 指标 | 优化前 | 优化后 | 提升幅度 |
|---|---|---|---|
| 时间（秒） | 2.20 | 1.35 | 38.6% |
| 内存（MB） | 50 | 5 | 90% |
五、改进总结
1. 优化路线图
原始 LCS 算法 → 滚动数组空间优化 → 内存访问优化 → 文件处理鲁棒性增强
2. 经验总结
- 空间优化优先：内存瓶颈比时间瓶颈更常见。
- 中文友好性：统一 UTF-8 读取，避免编码问题。
- 可维护性：Python 代码保持清晰，避免过度微优化。
源码展示
main.py
import sys
import osdef get_file_name(path: str) -> str:"""提取文件名"""return os.path.basename(path)def read_file(path: str) -> str:"""读取文件内容，UTF-8"""try:with open(path, "r", encoding="utf-8") as f:return f.read()except UnicodeDecodeError:# 回退 GBK/ANSI 编码with open(path, "r", encoding="gbk", errors="ignore") as f:return f.read()except FileNotFoundError:return ""def lcs(a: str, b: str) -> int:"""最长公共子序列算法"""m, n = len(a), len(b)if m == 0 or n == 0:return 0# 滚动数组优化prev = [0] * (n + 1)curr = [0] * (n + 1)for i in range(1, m + 1):for j in range(1, n + 1):if a[i - 1] == b[j - 1]:curr[j] = prev[j - 1] + 1else:curr[j] = max(prev[j], curr[j - 1])prev, curr = curr, [0] * (n + 1)return prev[n]def main():if len(sys.argv) != 4:print("参数错误：需要三个参数 [原文文件] [抄袭文件] [答案文件]")sys.exit(1)original_path = sys.argv[1]copied_path = sys.argv[2]output_path = sys.argv[3]original_name = get_file_name(original_path)copied_name = get_file_name(copied_path)s1 = read_file(original_path)s2 = read_file(copied_path)with open(output_path, "a", encoding="utf-8") as out:if not s1 or not s2:out.write(f"{original_name}文件与{copied_name}文件的重复率为0.00%（检测到空文件）\n")returnlcs_length = lcs(s1, s2)copied_length = len(s2)similarity = (0.0 if copied_length == 0 else (lcs_length / copied_length * 100.0))out.write(f"The similarity rate between document {original_name} and ducument {copied_name} is {similarity:.2f}%\n")if __name__ == "__main__":main()generate_samples.py (此文件可用来生成一些数据，方便再用main.py来验证)
import random
import osdef generate_sentence():subjects = ["我", "你", "他", "小明", "老师", "学生"]verbs = ["喜欢", "讨厌", "学习", "研究", "使用", "编写"]objects = ["人工智能", "机器学习", "Python", "C++", "论文", "算法"]return random.choice(subjects) + random.choice(verbs) + random.choice(objects) + "。"def make_copied_version(text: str) -> str:"""生成抄袭版（改写部分词汇，模拟抄袭）"""replacements = {"喜欢": "热爱","讨厌": "不喜欢","学习": "研究","研究": "学习","使用": "利用","编写": "撰写","人工智能": "AI","机器学习": "Machine Learning","论文": "文章","算法": "方法",}copied = textfor k, v in replacements.items():if k in copied and random.random() < 0.5: # 随机替换copied = copied.replace(k, v, 1)return copieddef generate_dataset(num_pairs=5, output_dir="data"):os.makedirs(output_dir, exist_ok=True)for i in range(1, num_pairs + 1):orig_file = os.path.join(output_dir, f"orig_{i}.txt")copy_file = os.path.join(output_dir, f"copy_{i}.txt")# 生成原文sentences = [generate_sentence() for _ in range(5)]orig_text = "\n".join(sentences)# 生成抄袭版copied_sentences = [make_copied_version(s) for s in sentences]copy_text = "\n".join(copied_sentences)with open(orig_file, "w", encoding="utf-8") as f:f.write(orig_text)with open(copy_file, "w", encoding="utf-8") as f:f.write(copy_text)print(f"生成: {orig_file}, {copy_file}")print("\n示例运行命令：")print(f"python main.py {output_dir}/orig_1.txt {output_dir}/copy_1.txt result.txt")if __name__ == "__main__":generate_dataset()六、测试数据的构造思路
1. 基础功能测试
- 完全相同的文本
- 原文：
今天天气晴朗，适合户外运动。 - 抄袭版：
今天天气晴朗，适合户外运动。 - 预期相似度：100%
- 原文：
- 部分修改的文本
- 原文：
深度学习需要大量计算资源。 - 抄袭版：
机器学习需要大量 GPU 资源。 - 预期相似度：约 50%
- 原文：
- 完全不同的文本
- 原文：
春天是万物复苏的季节。 - 抄袭版：
量子物理研究微观粒子。 - 预期相似度：0%
- 原文：
2. 边界情况测试
- 空文件
- 原文：
- 抄袭版：
这是一个测试句子。 - 预期相似度：0%
- 原文：
- 单字符文件
- 原文：
A - 抄袭版：
A - 预期相似度：100%
- 原文：
- 超长文本（1 万字符）文件组名为 longlong.txt
3. 中文处理测试
- 完全相同的文本
- 原文：
“你好，”她说，“今天天气不错。”。 - 抄袭版：
“你好！”他说，“今天天气很好。” - 预期相似度：76.47%
- 原文：
- 多音字与同形字
- 原文：
银行行长在银行门口行走。 - 抄袭版：
银行行长在银行前行路。 - 预期相似度：78.26%
- 原文：
4. 文件路径与异常
- 含空格路径
- 特殊字符路径
- 文件不存在
七、计算模块异常处理说明
1. 文件读取失败异常
设计目标：检测文件不存在、路径错误或权限不足，防止程序崩溃。
错误场景：用户提供的文件路径无效或无权限访问文件。
处理逻辑：
def read_file(path: str) -> str:try:with open(path, "r", encoding="utf-8") as f:return f.read()except (FileNotFoundError, PermissionError):# 返回空字符串，触发主流程输出相似度 0.00%return ""#单元测试样例：def test_file_not_exist(tmp_path):import subprocessresult_file = tmp_path / "result.txt"subprocess.run(["python", "main.py", "invalid.txt", "copy.txt", str(result_file)])content = result_file.read_text(encoding="utf-8")assert "0.00%" in content
2.内存分配失败异常
设计目标：处理大规模文本输入导致内存不足，避免程序直接崩溃。
错误场景：当输入文本过长（如百万字符），可能触发 Python 的 MemoryError。
处理逻辑：
def safe_lcs(a: str, b: str) -> int:try:return lcs(a, b)except MemoryError:# 捕获内存异常，返回 0，表示无法计算return 0#单元测试样例（模拟 MemoryError）：import pytestdef test_memory_error(monkeypatch):def fake_lcs(a, b): raise MemoryErrormonkeypatch.setattr("main.lcs", fake_lcs)assert safe_lcs("abc", "abc") == 0
3.输入参数无效异常
设计目标：检测命令行参数缺失或格式错误，提供明确错误提示。
错误场景：用户未提供足够的参数。
处理逻辑：
import argparsedef parse_args():parser = argparse.ArgumentParser(description="LCS 相似度检测")parser.add_argument("original")parser.add_argument("copy")parser.add_argument("result")return parser.parse_args()当参数不足时，argparse 会自动提示并退出（返回非零错误码）。单元测试样例：import subprocessdef test_invalid_arguments():result = subprocess.run(["python", "main.py"], capture_output=True)assert result.returncode != 0assert b"usage" in result.stderr
4.编码转换异常
设计目标：处理非 UTF-8 编码文件，防止解码失败导致计算错误。
错误场景：用户上传 GBK 或其他编码的文件。
处理逻辑：
def read_file(path: str) -> str:try:with open(path, "r", encoding="utf-8") as f:return f.read()except UnicodeDecodeError:# 返回空字符串，最终相似度 0.00%return ""单元测试样例：def test_utf8_decode_error(tmp_path):bad_file = tmp_path / "gbk.txt"bad_file.write_bytes("中文".encode("gbk")) # 非 UTF-8 文件assert read_file(str(bad_file)) == ""