前言
项目中有一个查重的需求，就类似论文查重这种的需求，我的组长已经写好了这个 Demo 了，我也挺感兴趣的，所以也看了看是如何实现的，看完后，感慨一声，噢！原来是这样实现的啊！现在呢，就记录下我从中学到的知识！
需求
输入：需要查重的内容，通常是非常长的文本，对于论文来说，可能上万字。
输出：显示重复的句子，将重复句子标红，以及整体内容的重复率。
标红是次要矛盾，查重是主要矛盾，需要先解决。
发挥想象
我们想象一下，纯人工查重的办法。工作人员拿到一篇论文，阅读这篇论文（假设该工作人员的大脑是超强大脑，工作人员对论文库中的论文非常熟悉，基本能倒背如流的程度），每阅读一句就与大脑中的论文进行对比，如果发现重复的内容太多了（即重复的句子很多），那么计算下重复的内容大概占全文的多少，进而得出整篇论文的重复率。
很明显，人工查重，效率肯定是不高的。
如何通过代码实现？
已有资源：
- 一篇待查重的论文，假设论文内容两万字。
- 论文数据库中大量的论文数据，假设数据库中的每篇论文的内容也两万字左右。
思路：将输入的论文内容与论文数据库中存在的论文内容进行一一对比。
思考：
- 如何对比？是一句一句进行对比，还是一段一段的进行对比？
- 对比的时候，如何才能说明对比的内容是重复的？也就是说判断重复的标准是什么？
接触新领域：
自然语言处理（NLP），自然语言处理任务中，我们经常需要判断两篇文档是否相似、计算两篇文档的相似程度。
文本相似度算法
对于如何说明对比的内容是重复的，那么这里就涉及到文本相似度算法了。通过查找资料，我了解到文本相似度算法有挺多的。
下面我列举了几种：
- Jaccard 相似度算法
- Sorensen Dice 相似度系数
- Levenshtein
- 汉明距离（海明距离）（Hamming Distance）
- 余弦相似性
对于这些文本相似度的算法，主要就是对文本进行分词，然后再对分好的词进行相关的计算，得出两个文本的相似度。
所以，对于两个文本，计算相似度的思路是：分词->通过某种算法计算得到相似度
断句
当然，这些算法，都是两个文本进行的，这两个文本可以是句子，也可以是段落，还可以是超长文本。假设我们直接是超长文本，直接使用相似度算法去匹配相似度，那么可能会误判，毕竟超长文本，分词出来的词语，相同的数量肯定是很多的，所以重复性也就会越高。
所以，首先要解决的问题就是，对于超长的文本，我们该如何进行中文断句？
经过了解，得知 BreakIterator 这个类可以完成这件事。
BreakIterator：https://docs.oracle.com/javase/7/docs/api/java/text/BreakIterator.html
分词
分词，将一个句子中的词语进行划分，分出有意义的词语。这里主要使用 IK 分词器。
实现
准备工作
Maven依赖
<!-- IK分词器 --> <dependency> <groupId>com.janeluo</groupId> <artifactId>ikanalyzer</artifactId> <version>2012_u6</version> </dependency> <!-- 汉语言处理包 Han Natural Language Processing --> <dependency> <groupId>com.hankcs</groupId> <artifactId>hanlp</artifactId> <version>portable-1.5.4</version> </dependency> <!-- 阿帕奇 集合工具 --> <dependency> <groupId>org.apache.commons</groupId> <artifactId>commons-collections4</artifactId> <version>4.4</version> </dependency> <!-- 糊涂工具包 --> <dependency> <groupId>cn.hutool</groupId> <artifactId>hutool-all</artifactId> <version>5.7.10</version> </dependency> <dependency> <groupId>org.projectlombok</groupId> <artifactId>lombok</artifactId> <version>1.18.16</version> </dependency> <dependency> <groupId>org.apache.commons</groupId> <artifactId>commons-lang3</artifactId> <version>3.8.1</version> </dependency> Sentence 类
把句子抽象出来，写成一个 Sentence 类去代表句子。
@Data public class Sentence { /** * 文本 */ private String text; /** * 相似度 */ private Double similar; /** * 是否重复，0否，1是，默认0，重复标准就是，当相似度大于60%时，就认为该句子是重复的 */ private Integer duplicatesState = 0; /** * 与该句子最相似的句子 */ private Sentence maxSimilarSentence; /** * 重复句子下标，可能存在多个重复句子，所以使用集合记录 */ private List<Integer> duplicatesIndex = new ArrayList<>(); } 策略模式
由于这里有多种算法，考虑可以使用策略模式，来选择不同的算法实现。
public interface SimDegreeAlgorithm { /** * 计算两个句子的相似度 * @param a * @param b * @return double **/ double getSimDegree(String a, String b); } /** * @author god23bin * @description Jaccard 相似度算法，集合的交集与集合的并集的比例. */ public class Jaccard implements SimDegreeAlgorithm { @Override public double getSimDegree(String a, String b) { } } /** * @author god23bin * @description 余弦相似性算法 * 怎么用它来计算两个字符串之间的相似度呢？ * 首先我们将字符串向量化（向量就是并集中的每个字符在各自中出现的频率），之后就可以在一个平面空间中，求出他们向量之间夹角的余弦值即可。 */ public class CosSim implements SimDegreeAlgorithm { @Override public double getSimDegree(String a, String b) { } } /** * @author god23bin * @description 相似度算法的策略 */ public class SimDegreeStrategy { private SimDegreeAlgorithm simDegreeAlgorithm; public SimDegreeStrategy(SimDegreeAlgorithm simDegreeAlgorithm) { this.simDegreeAlgorithm = simDegreeAlgorithm; } public double getSimDegree(String a, String b) { return simDegreeAlgorithm.getSimDegree(a, b); } } 本简单实现中，将选择使用余弦相似性算法来作为文本相似度算法的实现。
断句
写一个工具类来实现断句。简单说明一下，如何通过 BreakIterator 这个类实现断句。
- 调用
getSentenceInstance()就可以获取能判断句子边界的实例对象。 - 通过实例对象调用
setText()方法设置需要判断的句子字符串。 - 通过实例对象调用
first()和next()方法判断边界点。 - 根据边界点进行分割字符串。
public class SentenceUtil { /** * 将长文本进行断句 * @param content 长文本 * @return */ public static List<Sentence> breakSentence(String content) { // 获取实例对象 BreakIterator iterator = BreakIterator.getSentenceInstance(Locale.CHINA); // 设置文本，待断句的长文本 iterator.setText(content); // 存储断好的句子 List<Sentence> list = new ArrayList<>(); // 断句的边界 int firstIndex; int lastIndex = iterator.first(); // lastIndex 不等于 -1 （BreakIterator.DONE的值为 -1），说明还没断完，还没结束 while (lastIndex != BreakIterator.DONE) { firstIndex = lastIndex; lastIndex = iterator.next(); if (lastIndex != BreakIterator.DONE) { Sentence sentence = new Sentence(); sentence.setText(content.substring(firstIndex, lastIndex)); list.add(sentence); } } return list; } } 分词
写一个工具类来实现分词，使用 IK 分词器对文本进行分词。
public class IKUtil { /** * 以List的形式返回经过IK分词器处理的文本分词的结果 * @param text 需要分词的文本 * @return */ public static List<String> divideText(String text) { if (null == text || "".equals(text.trim())) { return null; } // 分词结果集 List<String> resultList = new ArrayList<>(); // 文本串 Reader StringReader re = new StringReader(text); // 智能分词： 合并数词和量词，对分词结果进行歧义判断 IKSegmenter ik = new IKSegmenter(re, true); // Lexeme 词元对象 Lexeme lex = null; try { // 分词，获取下一个词元 while ((lex = ik.next()) != null) { // 获取词元的文本内容，存入结果集中 resultList.add(lex.getLexemeText()); } } catch (IOException e) { System.out.println("分词IO异常：" + e.getMessage()); } return resultList; } } 余弦相似性算法
逻辑
整个算法的逻辑是这样的，那么我们一一实现。
@Override public double getSimDegree(String a, String b) { if (StringUtils.isBlank(a) || StringUtils.isBlank(b)) { return 0f; } // 将句子进行分词 // 计算句子中词的词频 // 向量化 // a、b 一维向量 // 分别计算三个参数，再结合公式计算 } 统计词频
分词上面已经实现，那现在是需要对句子中分好的词进行词频的统计，分词工具返回的是一个 List<String> 集合，我们可以通过哈希表对集合中的词语的出现次数进行统计，就是我们要的词频了。
public static Map<String, Integer> getWordsFrequency(List<String> words) { Map<String, Integer> wordFrequency = new HashMap<>(16); // 统计词的出现次数，即词频 for (String word : words) { wordFrequency.put(word, wordFrequency.getOrDefault(word, 0) + 1); } return wordFrequency; } 向量化
向量化，我们看看 @呼延十 大佬是如何说的：
字符串向量化怎么做呢？我举一个简单的例子：
A: 呼延十二 B: 呼延二十三 他们的并集 [呼，延，二，十，三] 向量就是并集中的每个字符在各自中出现的频率。 A 的向量：[1,1,1,1,0] B 的向量：[1,1,1,1,1]
所以
两个句子是这样的： 句子1：你笑起来真好看，像春天的花一样！ 句子2：你赞起来真好看，像夏天的阳光！ 进行分词，分词结果及频率： [你, 笑起来, 真, 好看, 像, 春天, 的, 花, 一样]，出现频率都是1 [你, 赞, 起来, 真, 好看, 像, 夏天, 的, 阳光]，出现频率都是1 它们的并集： [你，笑起来，赞，起来，真，好看，像，春天，夏天，的，花，一样，阳光] 它们的向量： [你，笑起来，赞，起来，真，好看，像，春天，夏天，的，花，一样，阳光] 句子1向量：[1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0 ] 句子2向量：[1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1 ] 代码表示：
// 向量化，先并集，然后遍历在并集中对应词语，在自己的分词集合中对应词语出现次数，组成的数就是向量 Set<String> union = new HashSet<>(); union.addAll(aWords); union.addAll(bWords); // a、b 一维向量 int[] aVector = new int[union.size()]; int[] bVector = new int[union.size()]; List<String> collect = new ArrayList<>(union); for (int i = 0; i < collect.size(); ++i) { aVector[i] = aWordsFrequency.getOrDefault(collect.get(i), 0); bVector[i] = bWordsFrequency.getOrDefault(collect.get(i), 0); } 计算余弦相似度
最后，计算余弦相似度，结合公式计算。
/** * 分别计算三个参数 * @param aVec a 一维向量 * @param bVec b 一维向量 */ public static double similarity(int[] aVec, int[] bVec) { int n = aVec.length; double p1 = 0; double p2 = 0f; double p3 = 0f; for (int i = 0; i < n; i++) { p1 += (aVec[i] * bVec[i]); p2 += (aVec[i] * aVec[i]); p3 += (bVec[i] * bVec[i]); } p2 = Math.sqrt(p2); p3 = Math.sqrt(p3); // 结合公式计算 return (p1) / (p2 * p3); } 代码
CosSim
public class CosSim implements SimDegreeAlgorithm { /** * 计算两个句子的相似度：余弦相似度算法 * @param a 句子1 * @param b 句子2 **/ @Override public double getSimDegree(String a, String b) { if (StringUtils.isBlank(a) || StringUtils.isBlank(b)) { return 0f; } // 将句子进行分词 List<String> aWords = IKUtil.divideText(a); List<String> bWords = IKUtil.divideText(b); // 计算句子中词的词频 Map<String, Integer> aWordsFrequency = getWordsFrequency(aWords); Map<String, Integer> bWordsFrequency = getWordsFrequency(bWords); // 向量化，先并集，然后遍历在并集中对应词语，在自己的分词集合中对应词语出现次数，组成的数就是向量 Set<String> union = new HashSet<>(); union.addAll(aWords); union.addAll(bWords); // a、b 一维向量 int[] aVector = new int[union.size()]; int[] bVector = new int[union.size()]; List<String> collect = new ArrayList<>(union); for (int i = 0; i < collect.size(); ++i) { aVector[i] = aWordsFrequency.getOrDefault(collect.get(i), 0); bVector[i] = bWordsFrequency.getOrDefault(collect.get(i), 0); } // 分别计算三个参数，再结合公式计算 return similarity(aVector, bVector); } public static Map<String, Integer> getWordsFrequency(List<String> words) { Map<String, Integer> wordFrequency = new HashMap<>(16); // 统计词的出现次数，即词频 for (String word : words) { wordFrequency.put(word, wordFrequency.getOrDefault(word, 0) + 1); } return wordFrequency; } /** * 分别计算三个参数 * @param aVec a 一维向量 * @param bVec b 一维向量 **/ public static double similarity(int[] aVec, int[] bVec) { int n = aVec.length; double p1 = 0; double p2 = 0f; double p3 = 0f; for (int i = 0; i < n; i++) { p1 += (aVec[i] * bVec[i]); p2 += (aVec[i] * aVec[i]); p3 += (bVec[i] * bVec[i]); } p2 = Math.sqrt(p2); p3 = Math.sqrt(p3); // 结合公式计算 return (p1) / (p2 * p3); } } 回顾思考
思考：
- 如何对比？是一句一句进行对比，还是一段一段的进行对比？
- 对比的时候，如何才能说明对比的内容是重复的？也就是说判断重复的标准是什么？
通过文本相似度算法，我们可以得到两个句子的相似度。那么相似度多少，我们才能认为它重复了呢？这个就由我们来决定了，在这里，当相似度达到60%以上，那么就认为当前句子是重复的。
现在，整体的查重逻辑应该是比较明了了：
我们可以拿到长文本，对长文本进行断句，得到句子集合，将这个句子集合与数据库中的数据（也进行断句，得到句子集合）进行相似度计算，记录相似度大于标准的句子，即记录重复句子及重复句子的数量，这样我们就能够判断，这长文本里面到底有多少个句子是重复的，进而得出重复率。
分析文本工具类
我们可以再封装一下，写一个分析文本工具类 AnalysisUtil
public class AnalysisUtil { public static BigDecimal getAnalysisResult(List<Sentence> sentencesA, List<Sentence> sentencesB, SimDegreeAlgorithm algorithm) { int simSentenceCnt = getSimSentenceCnt(sentencesA, sentencesB, algorithm); BigDecimal analysisResult = null; if (CollectionUtil.isNotEmpty(sentencesA)) { analysisResult = BigDecimal.valueOf((double) simSentenceCnt / sentencesA.size()).setScale(4, BigDecimal.ROUND_HALF_UP); } else { analysisResult = new BigDecimal(0); } return analysisResult; } /** * 返回 A 在 B 中的相似句子数量，同时记录相似句子的相似度及其所在位置（在进行处理的过程中，通过对 A 中数据进行相关操作实现）。 * @param sentencesA 原始文本集合，即断好的句子集合 * @param sentencesB 模式文本集合，即断好的句子集合 * @param algorithm 相似度算法 **/ public static int getSimSentenceCnt(List<Sentence> sentencesA, List<Sentence> sentencesB, SimDegreeAlgorithm algorithm) { return null; } } 计算相似的句子数量
/** * 返回 A 在 B 中的相似句子数量，同时记录相似句子的相似度及其所在位置（在进行处理的过程中，通过对 A 中数据进行相关操作实现）。 * @param sentencesA 原始文本集合，即断好的句子集合 * @param sentencesB 模式文本集合，即断好的句子集合 * @param algorithm 相似度算法 **/ public static int getSimSentenceCnt(List<Sentence> sentencesA, List<Sentence> sentencesB, SimDegreeAlgorithm algorithm) { // 当前句子相似度 double simDegree = 0f; // 相似的句子数量 int simSentenceCnt = 0; // 计算相似度的策略 SimDegreeStrategy simDegreeStrategy = new SimDegreeStrategy(algorithm); for (Sentence sentence1 : sentencesA) { // 当前句子匹配到的最大的相似度 double maxSimDegree = 0f; // 记录 B 里的，与 A 中最大相似度的那个句子 Sentence temp = null; for (Sentence sentence2 : sentencesB) { // 计算相似度 simDegree = simDegreeStrategy.getSimDegree(sentence1.getText(), sentence2.getText()); // 打印信息 printSim(sentence1, sentence2, simDegree, algorithm); // 相似度大于60，认为文本重复 if (simDegree * 100 > 60) { sentence1.setDuplicatesState(1); // 记录该句子在 B 中的位置 sentence1.getDuplicatesIndex().add(sentencesB.indexOf(sentence2)); } // 记录最大的相似度 if (simDegree * 100 > maxSimDegree) { maxSimDegree = simDegree * 100; temp = sentence2; } } // 如果当前句子匹配到的最大相似度是大于60%的，那么说明该句子在 B 中至少有一个句子是相似的，即该句子是重复的 if (maxSimDegree > 60) { ++simSentenceCnt; } sentence1.setSimilar(maxSimDegree); sentence1.setMaxSimilarSentence(temp); } return simSentenceCnt; } 完整代码
public class AnalysisUtil { /** * 计算出与项目库内容重复的句子在当前内容下所占的比例 * @param sentencesA 待查重的句子集合 * @param sentencesB 项目库中的项目内容句子集合 * @param algorithm 相似度算法 * @return java.math.BigDecimal **/ public static BigDecimal getAnalysisResult(List<Sentence> sentencesA, List<Sentence> sentencesB, SimDegreeAlgorithm algorithm) { int simSentenceCnt = getSimSentenceCnt(sentencesA, sentencesB, algorithm); BigDecimal analysisResult = null; if (CollectionUtil.isNotEmpty(sentencesA)) { analysisResult = BigDecimal.valueOf((double) simSentenceCnt / sentencesA.size()).setScale(4, BigDecimal.ROUND_HALF_UP); } else { analysisResult = new BigDecimal(0); } return analysisResult; } /** * 根据相似度算法，分析句子集合，返回 A 在 B 中的相似句子数量，同时记录相似句子的相似度及其所在位置（在进行处理的过程中，通过对 A 中数据进行相关操作实现）。 * @param sentencesA 原始文本集合，即断好的句子集合 * @param sentencesB 模式文本集合，即断好的句子集合 * @param algorithm 相似度算法 * @return int **/ public static int getSimSentenceCnt(List<Sentence> sentencesA, List<Sentence> sentencesB, SimDegreeAlgorithm algorithm) { // 当前句子相似度 double simDegree = 0f; // 相似的句子数量 int simSentenceCnt = 0; // 计算相似度的策略 SimDegreeStrategy simDegreeStrategy = new SimDegreeStrategy(algorithm); for (Sentence sentence1 : sentencesA) { // 当前句子匹配到的最大的相似度 double maxSimDegree = 0f; // 记录 B 里的，与 A 中最大相似度的那个句子 Sentence temp = null; for (Sentence sentence2 : sentencesB) { // 计算相似度 simDegree = simDegreeStrategy.getSimDegree(sentence1.getText(), sentence2.getText()); // 打印信息 printSim(sentence1, sentence2, simDegree, algorithm); // 相似度大于60，认为文本重复 if (simDegree * 100 > 60) { sentence1.setDuplicatesState(1); // 记录该句子在 B 中的位置 sentence1.getDuplicatesIndex().add(sentencesB.indexOf(sentence2)); } // 记录最大的相似度 if (simDegree * 100 > maxSimDegree) { maxSimDegree = simDegree * 100; temp = sentence2; } } // 如果当前句子匹配到的最大相似度是大于60的，那么说明该句子在 B 中至少有一个句子是相似的，即该句子是重复的 if (maxSimDegree > 60) { ++simSentenceCnt; } // 记录句子的相似度以及与哪条相似 sentence1.setSimilar(maxSimDegree); sentence1.setMaxSimilarSentence(temp); } return simSentenceCnt; } private static void printSim(Sentence sentence1, Sentence sentence2, double simDegree, SimDegreeAlgorithm algorithm) { BigDecimal bigDecimal = new BigDecimal(simDegree); DecimalFormat decimalFormat = new DecimalFormat("0.00%"); String format = decimalFormat.format(bigDecimal); System.out.println("----------------------------------------------------------------"); System.out.println(algorithm.getClass().getSimpleName()); System.out.println("句子1：" + sentence1.getText()); System.out.println("句子2：" + sentence2.getText()); System.out.println("相似度：" + format); } } 测试
测试两个句子。
public static void testLogic() { String content = "你笑起来真好看，像春天的花一样！"; String t = "你赞起来真好看，像夏天的阳光！"; List<Sentence> sentencesA = SentenceUtil.breakSentence(content); List<Sentence> sentencesB = SentenceUtil.breakSentence(t); BigDecimal analysisResult = AnalysisUtil.getAnalysisResult(sentencesA, sentencesB, new CosSim()); System.out.println("重复率：" + analysisResult); } 输出结果：
句子1：你笑起来真好看，像春天的花一样！ 句子2：你赞起来真好看，像夏天的阳光！ 相似度：55.56% 重复率：0.0000 public static void testLogic() { String content = "你笑起来真好看，像春天的花一样！"; String t = "你笑起来真好看，像夏天的花一样！"; List<Sentence> sentencesA = SentenceUtil.breakSentence(content); List<Sentence> sentencesB = SentenceUtil.breakSentence(t); BigDecimal analysisResult = AnalysisUtil.getAnalysisResult(sentencesA, sentencesB, new CosSim()); System.out.println("相似度：" + analysisResult); } 输出结果：
句子1：你笑起来真好看，像春天的花一样！ 句子2：你笑起来真好看，像夏天的花一样！ 相似度：88.89% 重复率：1.0000 总结
思路：将输入的论文内容与论文数据库中存在的论文内容进行一一对比。
思考：
- 如何对比？是一句一句进行对比，还是一段一段的进行对比？
- 对比的时候，如何才能说明对比的内容是重复的？也就是说判断重复的标准是什么？
查重的基本思路就是，把待查重的内容进行短句，然后一条一条句子与数据库中的进行对比，计算相似度。当然，这里的实现是比较简单粗暴的，两层 for 循环，外层遍历带查重的句子，内层遍历对比的句子，时间复杂度为 $O(n^2)$ 。
进一步的想法，就是使用多线程，这个后续再更新吧。
目前还没想到还能如何进一步优化。如果屏幕前的你有什么宝贵的建议或者想法，非常欢迎留下你的评论~~~
最后的最后
由本人水平所限，难免有错误以及不足之处， 屏幕前的靓仔靓女们 如有发现，恳请指出！
最后，谢谢你看到这里，谢谢你认真对待我的努力，希望这篇博客对你有所帮助！
你轻轻地点了个赞，那将在我的心里世界增添一颗明亮而耀眼的星！
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/1.jpg&w=218&h=124&zc=1)
