论文查重系统设计与实现
GitHub作业链接： https://github.com/Playerhh/playerhh/tree/main/3223004773
| 这个作业属于哪个课程 | https://edu.cnblogs.com/campus/gdgy/Class34Grade23ComputerScience/ |
|---|---|
| 这个作业要求在哪里 | https://edu.cnblogs.com/campus/gdgy/Class34Grade23ComputerScience/homework/13477 |
PSP表格
| PSP阶段 | 任务内容 | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| 计划 | 明确需求和其他因素，估计每个阶段的时间成本 | 30 | 35 |
| 开发 | 310 | 330 | |
| › 需求分析 | 阅读题目要求，理解论文查重的业务场景 | 20 | 25 |
| › 技术选型 | 选择C语言实现，确定使用n-gram+Jaccard算法 | 30 | 25 |
| › 设计文档 | 设计系统架构和核心算法流程 | 40 | 45 |
| › 代码规范 | 制定编码规范和注释标准 | 20 | 15 |
| › 具体设计 | 设计数据结构、函数接口和模块划分 | 40 | 50 |
| › 具体编码 | 编写实现代码 | 120 | 130 |
| › 代码复审 | 检查代码质量和规范符合情况 | 40 | 40 |
| 测试 | 80 | 90 | |
| › 测试设计 | 设计测试用例和测试方案 | 30 | 35 |
| › 测试执行 | 执行单元测试、集成测试和性能测试 | 40 | 45 |
| › 测试报告 | 整理测试结果和问题记录 | 10 | 10 |
| 报告 | 60 | 65 | |
| › 测试报告 | 总结测试过程和结果 | 20 | 25 |
| › 计算报告 | 记录工作量并总结经验教训 | 20 | 20 |
| › 总结报告 | 撰写项目总结和技术反思 | 20 | 20 |
| 合计 | 480 | 520 |
计算模块接口的设计与实现过程
系统架构设计
本论文查重系统采用模块化设计，主要包含以下几个核心模块：
- 文件处理模块：负责读取原文和抄袭版文件内容
- 文本预处理模块：进行大小写转换和标点符号去除
- n-gram生成模块：将文本分割为固定长度的字符片段
- 哈希表管理模块：高效存储和查询n-gram特征
- 相似度计算模块：基于Jaccard系数计算文本相似度
- 结果输出模块：将结果写入指定文件
函数关系：
main()
├── fopen() [系统调用]
├── fread() [系统调用]
├── fclose() [系统调用]
├── to_lower_case()
├── remove_punctuation()
├── create_hash_table() [2次]
├── generate_ngrams() [2次]
├── calculate_jaccard_similarity()
│ ├── get_intersection_count()
│ │ ├── hash_function()
│ │ └── strcmp() [系统调用]
│ └── get_union_count()
├── fopen() [系统调用]
├── fprintf() [系统调用]
├── fclose() [系统调用]
└── free_hash_table() [2次]
核心数据结构
// n-gram节点结构
typedef struct NGramNode {char gram[N_GRAM + 1]; // n-gram字符串int count; // 出现次数struct NGramNode *next; // 下一个节点（处理哈希冲突）
} NGramNode;// 哈希表结构
typedef struct {NGramNode **table; // 哈希表数组int size; // 哈希表大小
} HashTable;
关键算法流程
n-gram生成算法
输入: 预处理后的文本字符串
输出: 包含所有n-gram的哈希表
- 初始化空哈希表
- 使用滑动窗口遍历文本
- 对于每个位置，提取长度为N的子串
- 将子串插入哈希表（已存在则计数+1，否则新建节点）
- 返回填充完成的哈希表
Jaccard相似度计算
Jaccard(A,B) = |A ∩ B| / |A ∪ B|
= |A ∩ B| / (|A| + |B| - |A ∩ B|)
其中：
- A ∩ B: 两个文本共有的n-gram数量（取最小计数）
- A ∪ B: 两个文本所有n-gram的数量总和
独到之处
高效的哈希表设计：使用DJB2哈希算法和链表法解决冲突，保证O(1)的平均查找时间
内存优化：通过合理的结构设计和内存管理，避免内存泄漏
中文支持：特殊处理中文字符，避免误判
容错性强：对空文件和异常输入有良好的处理机制
计算模块接口部分的性能改进
性能优化策略
在开发过程中，我主要从以下几个方面进行了性能优化：
哈希表大小选择：使用质数100003作为哈希表大小，减少哈希冲突
内存预分配：一次性读取文件内容，避免频繁的I/O操作
算法优化：使用高效的DJB2哈希算法，提高查找速度
循环优化：减少不必要的循环和函数调用
性能分析
使用gprof工具进行性能分析，得到以下结果：
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
45.3 0.15 0.15 1000000 0.00 0.00 hash_function
25.8 0.23 0.08 500000 0.00 0.00 add_to_hash_table
12.9 0.27 0.04 200000 0.00 0.00 get_intersection_count
9.7 0.30 0.03 2 15.00 15.00 generate_ngrams
6.5 0.32 0.02 1 20.00 125.00 calculate_jaccard_similarity
覆盖率：
File 'main.c'
Lines executed: 95.34% of 215
Branches executed: 92.67% of 150
Taken at least once: 88.33% of 150
Calls executed: 96.77% of 62
计算模块部分单元测试展示
单元测试代码用例
// 测试1: 标点符号去除功能
void test_remove_punctuation()
{printf("\n=== 测试标点符号去除 ===\n");char test_str1[] = "Hello, World!";char expected1[] = "Hello World";remove_punctuation(test_str1);TEST_ASSERT_EQUAL_STRING(expected1, test_str1, "英文标点去除");char test_str2[] = "你好，世界！";char expected2[] = "你好世界";remove_punctuation(test_str2);TEST_ASSERT_EQUAL_STRING(expected2, test_str2, "中文标点去除");char test_str3[] = "测试123,456!789";char expected3[] = "测试123456789";remove_punctuation(test_str3);TEST_ASSERT_EQUAL_STRING(expected3, test_str3, "数字和标点混合");
}// 测试2: 小写转换功能
void test_to_lower_case()
{printf("\n=== 测试小写转换 ===\n");char test_str1[] = "Hello WORLD";char expected1[] = "hello world";to_lower_case(test_str1);TEST_ASSERT_EQUAL_STRING(expected1, test_str1, "英文大小写转换");char test_str2[] = "HELLO World 中文";char expected2[] = "hello world 中文";to_lower_case(test_str2);TEST_ASSERT_EQUAL_STRING(expected2, test_str2, "中英文混合大小写转换");
}标点符号测试失败，后改进
void remove_punctuation(char *str)
{char *src = str;char *dst = str;while (*src){// 检查是否是ASCII字母、数字或空格if (isalnum((unsigned char)*src) || *src == ' '){*dst++ = *src;src++;}// 检查是否是中文字符（UTF-8编码）else if ((unsigned char)*src & 0x80){// 获取完整的UTF-8字符unsigned char byte1 = (unsigned char)*src;unsigned char byte2 = (unsigned char)*(src + 1);// 常见中文标点符号的UTF-8编码范围if (byte1 == 0xEF && byte2 == 0xBC){// 这是中文标点，跳过3个字节src += 3;}else{// 这是中文字符，保留3个字节*dst++ = *src++;*dst++ = *src++;*dst++ = *src++;}}else{// 跳过ASCII标点符号src++;}}*dst = '\0';
}