共计 13366 个字符,预计需要花费 34 分钟才能阅读完成。
前言
我的项目中有一个查重的需要,就相似论文查重这种的需要,我的组长曾经写好了这个 Demo 了,我也挺感兴趣的,所以也看了看是如何实现的,看完后,感叹一声,噢!原来是这样实现的啊!当初呢,就记录下我从中学到的常识!
需要
输出:须要查重的内容,通常是十分长的文本,对于论文来说,可能上万字。
输入:显示反复的句子,将反复句子标红,以及整体内容的反复率。
标红是次要矛盾,查重是主要矛盾,须要先解决。
施展设想
咱们设想一下,纯人工查重的方法。工作人员拿到一篇论文,浏览这篇论文(假如该工作人员的大脑是超强大脑,工作人员对论文库中的论文十分相熟,根本能滚瓜烂熟的水平),每浏览一句就与大脑中的论文进行比照,如果发现反复的内容太多了(即反复的句子很多),那么计算下反复的内容大略占全文的多少,进而得出整篇论文的反复率。
很显著,人工查重,效率必定是不高的。
如何通过代码实现?
已有资源:
- 一篇待查重的论文,假如 论文内容两万字。
- 论文数据库中大量的论文数据,假如 数据库中的每篇论文的内容也两万字左右。
思路:将输出的论文内容与论文数据库中存在的论文内容进行一一比照。
思考:
- 如何比照?是一句一句进行比照,还是一段一段的进行比照?
- 比照的时候,如何能力阐明比照的内容是反复的?也就是说判断反复的规范是什么?
接触新畛域:
自然语言解决(NLP),自然语言解决工作中,咱们常常须要判断两篇文档是否类似、计算两篇文档的类似水平。
文本类似度算法
对于 如何阐明比照的内容是反复的 ,那么这里就波及到 文本类似度算法 了。通过查找材料,我理解到文本类似度算法有挺多的。
掘金 - 如何计算两个字符串之间的文本类似度?
掘金 - 文本类似度计算之余弦定理
上面我列举了几种:
- Jaccard 类似度算法
- Sorensen Dice 类似度系数
- Levenshtein
- 汉明间隔(海明间隔)(Hamming Distance)
- 余弦相似性
对于这些文本类似度的算法,次要就是对文本进行 分词,而后再对分好的词进行相干的计算,得出两个文本的类似度。
所以,对于两个文本,计算类似度的思路是:分词 -> 通过某种算法计算失去类似度
断句
当然,这些算法,都是两个文本进行的,这两个文本能够是句子,也能够是段落,还能够是超长文本。假如咱们间接是超长文本,间接应用类似度算法去匹配类似度,那么可能会误判,毕竟超长文本,分词进去的词语,雷同的数量必定是很多的,所以重复性也就会越高。
所以,首先要解决的问题就是,对于超长的文本,咱们该 如何进行中文断句?
通过理解,得悉 BreakIterator
这个类能够实现这件事。
BreakIterator:https://docs.oracle.com/javase/7/docs/api/java/text/BreakIterator.html
CSDN-Java 国际化:BreakIterator
分词
分词,将一个句子中的词语进行划分,分出有意义的词语。这里次要应用 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)$。
进一步的想法,就是应用多线程,这个后续再更新吧。
目前还没想到还能如何进一步优化。如果屏幕前的你有什么贵重的倡议或者想法,十分欢送留下你的评论~~~
最初的最初
由自己程度所限,不免有谬误以及不足之处,屏幕前的靓仔靓女们
如有发现,恳请指出!
最初,谢谢你看到这里,谢谢你认真对待我的致力,心愿这篇博客对你有所帮忙!
你轻轻地点了个赞,那将在我的心里世界削减一颗亮堂而夺目的星!