当前位置: 首页 > news >正文

软工个人项目 - Helen

论文查重系统设计与实现

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

计算模块接口的设计与实现过程

系统架构设计

本论文查重系统采用模块化设计,主要包含以下几个核心模块:

  1. 文件处理模块:负责读取原文和抄袭版文件内容
  2. 文本预处理模块:进行大小写转换和标点符号去除
  3. n-gram生成模块:将文本分割为固定长度的字符片段
  4. 哈希表管理模块:高效存储和查询n-gram特征
  5. 相似度计算模块:基于Jaccard系数计算文本相似度
  6. 结果输出模块:将结果写入指定文件

函数关系:
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的哈希表

  1. 初始化空哈希表
  2. 使用滑动窗口遍历文本
  3. 对于每个位置,提取长度为N的子串
  4. 将子串插入哈希表(已存在则计数+1,否则新建节点)
  5. 返回填充完成的哈希表

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';
}
http://www.hskmm.com/?act=detail&tid=11152

相关文章:

  • 概率论第二章部分习题
  • 记录 | 心理行动机制模型
  • ENSP模拟搭建典型中小型企业网架构
  • 【Java】ArrayList讲解
  • 【Java】HashMap讲解
  • 图解15:DNS工作原理
  • 图解16:数据和信息流的9大架构模式
  • 图解12:软件开发8大模型
  • 图解13:软件版本是怎么命名的
  • 图解14:CDN(最近使用的都是阿里云的)
  • 2025年9月15灯塔arl安装部署教程_2025-09-20
  • WINUI/WPF——自定义ListView
  • 用 Rust 实现英文数字验证码识别
  • 图解9:IDEA30款好用的插件
  • 图解10:Redis优化18招
  • 图解11:API和SDK区别
  • Fedora42安装VMware+百度网盘
  • Fedora42安装配置idapro9.1
  • 利用个人账户密码复用获取域凭证:无需接入目标网络的攻击手法解析
  • Java 开发核心疑问解析:从 static 修饰到规范实践
  • 实用指南:坤驰科技诚邀您参加——第十三届中国光纤传大会
  • 2025.9.20
  • 图解8:kafka高效原理
  • Spring Boot 2.5.0 集成 Elasticsearch 7.12.0 实现 CRUD 完整指南(Windows 环境) - 教程
  • TypeScript - typeof 搭配 as const 技巧总结
  • 图解6:网站访问流程
  • 图解7:渲染原理和性能优化
  • [Linux/Docker] BusyBox : 开源、轻量级的Unix工具集
  • Part03 数据结构 - 教程
  • 图解3:幂等使用场景