JAVA 一个简单查重的实现

1. 前言

最近在做一个教育网站时，有一个考试的模块，其中学生编写的文章需要有一个查重的功能。到网上找了下，感觉这方面的资料还是比较少，大部分都需要收费，由于公司家境贫寒（不愿意花钱），且需求不是特别难，只需要一个建议版本的功能。于是只能亲自动手做一个 simple 版本的。

2. 实现思路

思路的话比较简单，想法是利用双指针的模式，找出两个文本中相似的文本。不过这样算法复杂度是 O(n2) ，不过由于我们是小网站，文章本来也不多。

核心就是有一个双层的循环做遍历，然后判断最小字符串是否相同，如果不相同，则指针B递增直到找到相同的文本

如果指针位置找到了相同文本，则增加最小字符串长度，直到找到最大的匹配的文本。

3. 代码实现

public static class SameResult {
// 存储相似文本关键词
private String keyword;
// 存储与关键词详细信息
private String detail;

public String getKeyword() {
return keyword;

    }

public void setKeyword(String keyword) {
this.keyword = keyword;

    }

public String getDetail() {
return detail;

    }

public void setDetail(String detail) {
this.detail = detail;

    }

}

/**

 * 获取两个字符串中的相似文本片段

 * @param a 文本a

 * @param b 文本b

 * @param minSize 最小相似字符数

 * @return 返回相似文本片段的列表

 */
public static List<SameResult> getSameTextList(String a, String b, Integer minSize) {


    List<SameResult> result = new ArrayList<>();

    Map<String, String> stash = new HashMap<>();
if (a == null || b == null) {
return result;

    }
if (a.length() < minSize || b.length() < minSize) {
return result;

    }
int i = 0;
while (i <= a.length() - minSize) {
// 初始化窗口大小为最小相似字符数
int nowWindowSize = minSize;
// 遍历文本b，寻找与文本a当前片段相似的片段
int j = 0;
String nowMate = null; // 存储当前相似片段
String nowDetail = null; // 存储当前相似片段的详细信息
SameResult sameResult = new SameResult(); 
Boolean isMate = false; // 标记是否找到相似片段
while (j <= b.length() - minSize) {
// 如果文本a和文本b的当前片段相等
if (a.substring(i, nowWindowSize + i).equals(b.substring(j, nowWindowSize + j))) {
// 记录相似片段

                nowMate = a.substring(i, nowWindowSize + i); 
// 记录详细信息, 这里的5表示详细信息取前五个和后五个字符

                nowDetail = b.substring(Math.max(j - 5, 0), Math.min(nowWindowSize + j + 5, b.length())); 

                sameResult.setKeyword(nowMate); 

                sameResult.setDetail(nowDetail); 
// 设置找到相似片段的标记

                isMate = true; 
// 增加窗口大小

                nowWindowSize++; 
// 继续在文本b中寻找更长的相似片段
while (j <= b.length() - nowWindowSize) {
String ma1 = a.substring(i, nowWindowSize + i);
String ma2 = b.substring(j, nowWindowSize + j);
// 如果找到更长的相似片段
if (ma1.equals(ma2)) { 

                        nowMate = a.substring(i, nowWindowSize + i); 

                        nowDetail = b.substring(Math.max(j - 5, 0), Math.min(nowWindowSize + j + 5, b.length())); 

                        sameResult.setKeyword(nowMate); 

                        sameResult.setDetail(nowDetail); 

                        nowWindowSize++;

                    } else {
// 如果不再相似，退出循环
break; 

                    }

                }
// 找到相似片段后，退出内部循环
break; 

            } else {
// 如果不相似，继续在文本b中寻找

                j++; 

            }

        }
// 如果找到相似片段，将其存储到映射中
if (isMate) {
// 移动文本a的索引

            i += nowWindowSize - 1;

            stash.put(sameResult.getKeyword(), sameResult.getDetail()); 

        } else {
// 如果没有找到相似片段，移动文本a的索引

            i++; 

        }

    }
for (String key : stash.keySet()) {
SameResult sameResult = new SameResult();

        sameResult.setKeyword(key);

        sameResult.setDetail(stash.get(key)); 

        result.add(sameResult); 

    }
return result;

}

public static void main(String[] args) {
// 调用getSameTextList方法，并打印结果

    System.out.println(getSameTextList("test1", "test2", 10));

}

代码总体比较简单，就是获取到所有最小长度文本长度的所有相似文本，并放到一个 List 中，以便后续的业务处理。

最后可以整理为一个类似下面的表格

4. 结尾

一般会用到查重的业务场景可能并不多，大部分都是学校、政府等才需要进行查重，本文算是抛砖引玉吧，只是为需要做查重内容展示时为大家提供一点点思路。