Paper Content Similarity Detection
PSP表格
PSP2.1 | Personal Software Process Stages | 预估耗时(分钟) | 实际耗时(分钟) |
---|---|---|---|
Planning | 计划 | 20 | 20 |
· Estimate | · 估计这个任务需要多少时间 | 20 | 20 |
Development | 开发 | 320 | 360 |
· Analysis | · 需求分析 (包括学习新技术) | 60 | 60 |
· Design Spec | · 生成设计文档 | 10 | 0 |
· Design Review | · 设计复审 | 10 | 0 |
· Coding Standard | · 代码规范 (为目前的开发制定合适的规范) | 10 | 0 |
· Design | · 具体设计 | 20 | 60 |
· Coding | · 具体编码 | 180 | 210 |
· Code Review | · 代码复审 | 10 | 10 |
· Test | · 测试(自我测试,修改代码,提交修改) | 20 | 20 |
Reporting | 报告 | 60 | 60 |
· Test Report | · 测试报告 | 20 | 20 |
· Size Measurement | · 计算工作量 | 10 | 10 |
· Postmortem & Process Improvement Plan | · 事后总结, 并提出过程改进计划 | 30 | 30 |
合计 | 400 | 440 | |
碎碎念
还以为要阅读 python-difflib或者 git-diff源码然后再手搓一个字符串相似度算法出来呢,吓死宝宝了
从 LCS
说起
查了一下用于检验的文本来源,是这个项目。里面提到了 LCS算法。顺便引用一下 Wikipedia对 LCS的定义。[1]
A longest common subsequence (LCS) is the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The problem of computing longest common subsequences is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.
一个标准的 LCS算法如下:[2]
def longestCommonSubsequence1(s1: str, s2: str) -> int:
# 获取两个字符串的长度
n, m = len(s1), len(s2)
# 在字符串前面加上空格,这样索引就从1开始,方便处理边界情况
s1, s2 = " " + s1, " " + s2
# 创建一个二维数组,用于存储最长公共子序列的长度
f = [[0] * (m + 1) for _ in range(n + 1)]
# 初始化边界条件,当一个字符串为空时,最长公共子序列的长度为0
for i in range(n + 1):
f[i][0] = 0
for j in range(m + 1):
f[0][j] = 0
# 动态规划求解最长公共子序列的长度
for i in range(1, n + 1):
for j in range(1, m + 1):
if s1[i] == s2[j]:
# 如果当前字符相同,则最长公共子序列的长度在前一状态的基础上加1
f[i][j] = f[i - 1][j - 1] + 1
else:
# 如果当前字符不同,则最长公共子序列的长度取前一状态两种选择的最大值
f[i][j] = max(f[i - 1][j], f[i][j - 1])
# 最终返回最长公共子序列的长度
return f[n][m]
LCS的中心思想就是造一个二维大数组 f
储存两个字符串 s1
, s2
所有从左数起的子字符串的最长公共子序列 LCS的长度,然后动态规划,求得最终的两个字符串 s1
, s2
的最长公共子序列 LCS的长度。更详细的解释可以看这一篇文章。
易见 LCS套了两层 for循环,故时间复杂度为 $O(nm)$。
再说说 python
的 difflib
库
python
的 difflib
库的用法参看此文档。其中。一个使用 difflib
计算文本相似度的例子如下。
import difflib
def calculate_similarity(original_text, plagiarized_text):
differ = difflib.SequenceMatcher(None, original_text, plagiarized_text)
return differ.ratio() * 100
original_text = "今天是星期天,天气晴,今天晚上我要去看电影。"
plagiarized_text = "今天是周天,天气晴朗,我晚上要去看电影。"
similarity_percentage = calculate_similarity(original_text, plagiarized_text)
print("重复率:{:.2f}%".format(similarity_percentage))
我们来稍微解释一下这个算法的原理。
class difflib.SequenceMatcher(isjunk=None, a='', b='', autojunk=True)
对象 difflib.SequenceMatcher
在示例代码被传入三个参数 isjunk
, a
, b
。isjunk
检查是否有可以忽略的垃圾元素,这个可以不用管,直接传入 None
。a
, b
是传入的将要被比较的字符串。autojunk
是可选参数,可以忽略。
SequenceMatcher.ratio()
该方法返回一个[0, 1]之间的浮点数,就是文本重复率的度量值。我们看看他的源码是如何实现它的。
class SequenceMatcher:
# ...
def ratio(self):
matches = sum(triple[-1] for triple in self.get_matching_blocks())
return _calculate_ratio(matches, len(self.a) + len(self.b))
# ...
我们发现它又涉及到 SequenceMatcher.get_matching_blocks()
和 _calculate_ratio(matches, length)
两个函数,以及 matches
这个属性。
我们先来看 _calculate_ratio(matches, length)
。
_calculate_ratio(matches, length)
def _calculate_ratio(matches, length):
if length:
return 2.0 * matches / length
return 1.0
很简单,几乎不用解释。考虑到 len(self.a) + len(self.b)
不可能为0,_calculate_ratio(matches, length)
就是匹配字符数 matches
乘以2再除以两个字符串的总长度 length
。作为重复率的度量非常正常。
我们再来看看 SequenceMatcher.get_matching_blocks()
做了什么。
SequenceMatcher.get_matching_blocks()
源码很复杂,我们直接看描述吧。[3]
返回描述非重叠匹配子序列的三元组列表。 每个三元组的形式为 (i, j, n),其含义为 a[i:i+n] == b[j:j+n]。 这些三元组按 i 和 j 单调递增排列。
最后一个三元组用于占位,其值为 (len(a), len(b), 0)。 它是唯一 n == 0 的三元组。 如果 (i, j, n) 和 (i', j', n') 是在列表中相邻的三元组,且后者不是列表中的最后一个三元组,则 i+n < i' 或 j+n < j';换句话说,相邻的三元组总是描述非相邻的相等块。
有点难以理解是吧。举个例子。
>>> s = SequenceMatcher(None, "abxcd", "abcd")
>>> s.get_matching_blocks()
[Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
容易看出"abxcd"和"abcd"两个字符串的公共部分有两块,为"ab"和"cd",对应于三元组(a=0, b=0, size=2), (a=3, b=2, size=2)。
三元组的第一个参数 a为公共部分的第一个元素在第一个字符串的索引,三元组的第二个参数 b为公共部分的第一个元素在第二个字符串的索引,最后一个参数 size是这个公共部分的长度。
第三个三元组 (a=5, b=4, size=0)只是为了补位。
这样就可以看明白 matches = sum(triple[-1] for triple in self.get_matching_blocks())
的意思了。所有 get_matching_blocks()
得到的三元组的 size元素的和,就是最大公共字符串的长度,也就是 matches
的值。
显然,这是一个 LCS算法的变种。但是它的时间复杂度并非为 $O(nm)$。这又涉及到 find_longest_match()
这个方法。很遗憾,我现在还看不懂,只能照着描述粗略看看了。
SequenceMatcher.find_longest_match()
描述。[3:1]
找出
a[alo:ahi]
和b[blo:bhi]
中的最长匹配块。
如果
isjunk
被省略或为None
,find_longest_match()
将返回(i, j, k)
使得a[i:i+k]
等于b[j:j+k]
,其中alo <= i <= i+k <= ahi
并且blo <= j <= j+k <= bhi
。 对于所有满足这些条件的(i', j', k')
,如果i == i'
,j <= j'
也被满足,则附加条件k >= k'
,i <= i'
。 换句话说,对于所有最长匹配块,返回在 a 当中最先出现的一个,而对于在 a 当中最先出现的所有最长匹配块,则返回在 b 当中最先出现的一个。
一如既往抽象的描述,直接看例子吧。
>>> s = SequenceMatcher(None, " abcd", "abcd abcd")
>>> s.find_longest_match(0, 5, 0, 9)
Match(a=0, b=4, size=5)
同上,忽略 isjunk
参数。find_longest_match()
方法将要输入四个参数 alo
, ahi
blo
, bhi
,其中 alo
, blo
为子字符串的范围的开头,ahi
, bhi
为子字符串的范围的结尾。find_longest_match()
方法将要求出最长匹配块,它由一个三元组描述。如" abcd"和"abcd abcd"的最大匹配块为" abcd",在第一个字符串中从索引0开始,在第二个字符串中从4开始,这个子字符串长度为5,刚好就是输出三元组的三个元素的值。
我们算是 RTFSC之中的重要部分一遍了,接下来实际应用一下吧。
使用 difflib
进行示例的比较
理论部分说完了。现在看看实际效果。
首先按照要求写一份 main.py
的代码,读取原文文件和抄袭版论文的文件,进行文本相似度计算,并且写入答案文件。其中 main.py
在于项目文件夹下面,而测试文件都在于项目文件夹的 ./test文件夹里面。
main.py
的实现十分简单,简单到了 main()
函数只有接受命令行参数 argv[]
,打开文件 open()
,读取文件 read()
,计算相似度 calculate_similarity()
,写入答案文件 write()
几个模块,其中 calculate_similarity()
只是调用了 difflib
的 SequenceMatcher.ratio()
一个方法(SequenceMatcher.ratio()
的内部细节前文已经论述),做到了简洁易读,便于维护。以至于流程图都没有必要画了。
# 这是要在终端执行的指令
python ./main.py ./test/orig.txt ./test/orig_0.8_add.txt ./test/answer.txt
# 这是 main.py的内容
import difflib
import sys
def calculate_similarity(original_text, plagiarized_text):
differ = difflib.SequenceMatcher(None, original_text, plagiarized_text)
return differ.ratio() * 100
def main():
# 检查命令行参数,一共四个,多了少了都不行。
if len(sys.argv) != 4:
print("Usage: python main.py <original_file> <plagiarized_file> <answer_file>")
return
# 读取原文文件和抄袭版论文文件
with open(sys.argv[1], 'r', encoding='utf-8') as original_file:
original_text = original_file.read()
with open(sys.argv[2], 'r', encoding='utf-8') as plagiarized_file:
plagiarized_text = plagiarized_file.read()
# 计算相似度
similarity_percentage = calculate_similarity(original_text, plagiarized_text)
# 写入答案文件
with open(sys.argv[3], 'w', encoding='utf-8') as answer_file:
answer_file.write("重复率:{:.2f}%".format(similarity_percentage))
if __name__ == "__main__":
main()
得到结果写在 ./test/answer.txt当中。
# 这是 ./test/answer.txt的内容
重复率:91.42%
程序运行成功了。
性能分析
开始之前
首先写一个 system.py来获取系统信息。
import platform
import sys
import cpuinfo
import psutil
def get_system_environment():
# 获取操作系统信息
os_name = platform.system()
os_version = platform.release()
# 获取Python版本信息
python_version = sys.version
# 获取CPU信息
cpu_info = cpuinfo.get_cpu_info()
cpu_architecture = cpu_info.get('arch')
# 获取内存信息
total_memory = psutil.virtual_memory().total
# 打印系统环境信息
print("操作系统:", os_name)
print("操作系统版本:", os_version)
print("Python版本:", python_version)
print("CPU架构:", cpu_architecture)
print("内存总量:", total_memory, "bytes")
if __name__ == "__main__":
get_system_environment()
测试结果会输出在终端。
我现在拿手头上的笔记本电脑做测试。
[arch@archlinux Project1]$ python -u "/home/arch/Code/Project/Project1/system.py"
操作系统: Linux
操作系统版本: 6.7.9-zen1-1-zen
Python版本: 3.11.8 (main, Feb 12 2024, 14:50:05) [GCC 13.2.1 20230801]
CPU架构: X86_64
内存总量: 16543997952 bytes
cProfile
我们使用 cProfile
工具进行性能分析。首先修改一下 main.py
文件。
# 这是 main.py的内容
import difflib
import sys
import cProfile
import io
import pstats
def calculate_similarity(original_text, plagiarized_text):
differ = difflib.SequenceMatcher(None, original_text, plagiarized_text)
return differ.ratio() * 100
def main():
# 检查命令行参数,一共四个,多了少了都不行。
if len(sys.argv) != 4:
print("Usage: python main.py <original_file> <plagiarized_file> <answer_file>")
return
# 读取原文文件和抄袭版论文文件
with open(sys.argv[1], 'r', encoding='utf-8') as original_file:
original_text = original_file.read()
with open(sys.argv[2], 'r', encoding='utf-8') as plagiarized_file:
plagiarized_text = plagiarized_file.read()
# 开始性能分析
pr = cProfile.Profile()
pr.enable()
# 计算相似度
similarity_percentage = calculate_similarity(original_text, plagiarized_text)
# 结束性能分析
pr.disable()
# 将性能分析结果写入文件
with open('cprofile_output.profile', 'w', encoding='utf-8') as profile_file:
s = io.StringIO()
sortby = 'cumulative'
ps = pstats.Stats(pr, stream=s).sort_stats(sortby)
ps.print_stats()
profile_file.write(s.getvalue())
# 写入答案文件
with open(sys.argv[3], 'w', encoding='utf-8') as answer_file:
answer_file.write("重复率:{:.2f}%".format(similarity_percentage))
if __name__ == "__main__":
main()
运行 python ./main.py ./test/orig.txt ./test/orig_0.8_add.txt ./test/answer.txt
结果如下。
# 这是 ./cprofile_output.profile的内容
912591 function calls in 0.258 seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.258 0.258 /home/arch/Code/Project/Project1/./main.py:7(calculate_similarity)
1 0.000 0.000 0.251 0.251 /usr/lib/python3.11/difflib.py:597(ratio)
1 0.002 0.002 0.251 0.251 /usr/lib/python3.11/difflib.py:421(get_matching_blocks)
1763 0.202 0.000 0.248 0.000 /usr/lib/python3.11/difflib.py:305(find_longest_match)
858057 0.045 0.000 0.045 0.000 {method 'get' of 'dict' objects}
1 0.000 0.000 0.007 0.007 /usr/lib/python3.11/difflib.py:120(__init__)
1 0.000 0.000 0.007 0.007 /usr/lib/python3.11/difflib.py:184(set_seqs)
1 0.000 0.000 0.007 0.007 /usr/lib/python3.11/difflib.py:222(set_seq2)
1 0.005 0.005 0.007 0.007 /usr/lib/python3.11/difflib.py:266(__chain_b)
12274 0.001 0.000 0.001 0.000 {method 'setdefault' of 'dict' objects}
17437 0.001 0.000 0.001 0.000 {method 'append' of 'list' objects}
1701 0.000 0.000 0.001 0.000 /usr/lib/python3.11/collections/__init__.py:442(_make)
1763 0.000 0.000 0.001 0.000 <string>:1(<lambda>)
8758 0.000 0.000 0.000 0.000 {method '__contains__' of 'set' objects}
3464 0.000 0.000 0.000 0.000 {built-in method __new__ of type object at 0x7efa7dcdb0a0}
1 0.000 0.000 0.000 0.000 {built-in method builtins.sum}
1 0.000 0.000 0.000 0.000 {method 'sort' of 'list' objects}
3887 0.000 0.000 0.000 0.000 {built-in method builtins.len}
1702 0.000 0.000 0.000 0.000 /usr/lib/python3.11/difflib.py:619(<genexpr>)
1763 0.000 0.000 0.000 0.000 {method 'pop' of 'list' objects}
1 0.000 0.000 0.000 0.000 /usr/lib/python3.11/difflib.py:39(_calculate_ratio)
9 0.000 0.000 0.000 0.000 {method 'add' of 'set' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.000 0.000 {method 'items' of 'dict' objects}
1 0.000 0.000 0.000 0.000 /usr/lib/python3.11/difflib.py:196(set_seq1)
可见运行中消耗时间的模块主要是 ratio()
, get_matching_blocks()
, find_longest_match()
这三个方法。
换位思考
其实细心的读者早就发现了。我们在 main.py
里面的 calculate_similarity()
函数完全可以使用一般的 LCS
算法写一遍。
# main.py
# 替换为一般的 LCS算法
...
def longestCommonSubsequence(s1, s2):
# 获取两个字符串的长度
n, m = len(s1), len(s2)
# 在字符串前面加上空格,这样索引就从1开始,方便处理边界情况
s1, s2 = " " + s1, " " + s2
# 创建一个二维数组,用于存储最长公共子序列的长度
f = [[0] * (m + 1) for _ in range(n + 1)]
# 初始化边界条件,当一个字符串为空时,最长公共子序列的长度为0
for i in range(n + 1):
f[i][0] = 0
for j in range(m + 1):
f[0][j] = 0
# 动态规划求解最长公共子序列的长度
for i in range(1, n + 1):
for j in range(1, m + 1):
if s1[i] == s2[j]:
# 如果当前字符相同,则最长公共子序列的长度在前一状态的基础上加1
f[i][j] = f[i - 1][j - 1] + 1
else:
# 如果当前字符不同,则最长公共子序列的长度取前一状态两种选择的最大值
f[i][j] = max(f[i - 1][j], f[i][j - 1])
# 最终返回最长公共子序列的长度
return f[n][m]
def calculate_similarity(original_text, plagiarized_text):
matches = longestCommonSubsequence(original_text, plagiarized_text)
ratio = matches * 2 / (len(original_text) + len(plagiarized_text))
return ratio * 100
...
我们试着用它替换原来的 calculate_similarity
()函数做一个测试。
# 这是 cprofile_output.profile的内容
127501428 function calls in 45.909 seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.210 0.210 45.909 45.909 /home/arch/Code/Project/Project1/./main.py:40(calculate_similarity)
1 33.761 33.761 45.699 45.699 /home/arch/Code/Project/Project1/./main.py:11(longestCommonSubsequence)
127501420 11.250 0.000 11.250 0.000 {built-in method builtins.max}
1 0.688 0.688 0.688 0.688 /home/arch/Code/Project/Project1/./main.py:19(<listcomp>)
4 0.000 0.000 0.000 0.000 {built-in method builtins.len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
可见运行时间是45秒以上,是使用 diiflib
库的方法的175倍。可见算法优化的重要性了。
异常处理
俗话说得好,“测试工程师走进一家酒吧,进行了各种测试,结果都非常完美。然后,顾客点了一份炒饭,酒吧炸了”[4]。作为工程师,你永远无法预料到用户的异常行为所造成的严重后果,因此要在设计程序时考虑各种意外情况。
用户在使用 main.py
程序时,唯一的输入接口是文件名和文件路径。因此只需要规范它们即可。
我们单独写一个函数进行异常处理。
# main.py
def check_file_paths(original_file_path, plagiarized_file_path):
try:
# 检查文件路径格式是否符合要求
orig_pattern = re.compile(r'^\.\/test\/orig\.txt$')
plagiarized_pattern = re.compile(r'^\.\/test\/orig_0\.8_.+\.txt$')
if not orig_pattern.match(original_file_path):
raise ValueError("Invalid original file path.")
if not plagiarized_pattern.match(plagiarized_file_path):
raise ValueError("Invalid plagiarized file path.")
except ValueError as ve:
print("Invalid file path:", str(ve))
return False
return True
然后在主函数调用它。
不要忘记检查参数数量也是异常处理。
# main.py
def main():
# 检查命令行参数,一共四个,多了少了都不行。
if len(sys.argv) != 4:
print("Usage: python main.py <original_file> <plagiarized_file> <answer_file>")
return
我们最终得到的 main.py
如下。
# main.py
import difflib
import sys
import os
import re
import cProfile
import io
import pstats
def calculate_similarity(original_text, plagiarized_text):
differ = difflib.SequenceMatcher(None, original_text, plagiarized_text)
return differ.ratio() * 100
def check_file_paths(original_file_path, plagiarized_file_path):
try:
# 检查文件路径格式是否符合要求
orig_pattern = re.compile(r'^\.\/test\/orig\.txt$')
plagiarized_pattern = re.compile(r'^\.\/test\/orig_0\.8_.+\.txt$')
if not orig_pattern.match(original_file_path):
raise ValueError("Invalid original file path.")
if not plagiarized_pattern.match(plagiarized_file_path):
raise ValueError("Invalid plagiarized file path.")
except ValueError as ve:
print("Invalid file path:", str(ve))
return False
return True
def main():
# 检查命令行参数,一共四个,多了少了都不行。
if len(sys.argv) != 4:
print("Usage: python main.py <original_file> <plagiarized_file> <answer_file>")
return
original_file_path = sys.argv[1]
plagiarized_file_path = sys.argv[2]
answer_file_path = sys.argv[3]
# 检查文件路径是否有效
if not check_file_paths(original_file_path, plagiarized_file_path):
return
# 处理文件
with open(original_file_path, 'r', encoding='utf-8') as original_file:
original_text = original_file.read()
with open(plagiarized_file_path, 'r', encoding='utf-8') as plagiarized_file:
plagiarized_text = plagiarized_file.read()
# 开始性能分析
pr = cProfile.Profile()
pr.enable()
# 计算相似度
similarity_percentage = calculate_similarity(original_text, plagiarized_text)
# 结束性能分析
pr.disable()
# 将性能分析结果写入文件
with open('cprofile_output.profile', 'w', encoding='utf-8') as profile_file:
s = io.StringIO()
sortby = 'cumulative'
ps = pstats.Stats(pr, stream=s).sort_stats(sortby)
ps.print_stats()
profile_file.write(s.getvalue())
# 写入答案文件
with open(answer_file_path, 'w', encoding='utf-8') as answer_file:
answer_file.write("重复率:{:.2f}%".format(similarity_percentage))
if __name__ == "__main__":
main()
我们来试试几种引发异常的情况。
original_file_path
异常
[arch@archlinux Project1]$ python ./main.py ./orig.txt ./test/orig_0.8_add.txt ./test/answer.txt
Invalid file path: Invalid original file path.
plagiarized_file_path
异常
[arch@archlinux Project1]$ python ./main.py ./test/orig.txt ./test/orig_0.8.txt ./test/answer.txt
Invalid file path: Invalid plagiarized file path.
- 传入参数数量异常
[arch@archlinux Project1]$ python ./main.py ./test/orig.txt ./test/orig_0.8_add.txt
Usage: python main.py <original_file> <plagiarized_file> <answer_file>