# simtool-duplicate-check

**Repository Path**: li-zhengyang2023/simtool-duplicate-check

## Basic Information

- **Project Name**: simtool-duplicate-check
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-05-15
- **Last Updated**: 2024-05-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# simtool-duplicate-check

#### 介绍

大规模文档去重分析

【问题描述】

谷歌、百度等大型搜索引擎需要定期抓取全球网站的网页数据，并建立索引用于支持关键词的快速查询。通常搜索引擎需要判断抓取的网页是否在已经索引的数据集中，来决定是否更新索引，从而提高搜索引擎的更新效率。这需要高效文本去重算法进行支持。

Simhash是Google用来处理海量文本去重的算法（参考论文《Detecting Near-duplicates for web crawling》），借助于文本向量的构建以及局部敏感哈希技术，可以将每个网页文本生成一串二进制编码（文本指纹fingerprint），再利用高效的索引方法，加速大规模文本数据集中相似文本的检测。网页指纹生成原理如下图所示：

[](https://judge.buaa.edu.cn/userfiles/image/2022/166616309529401009347.png)

1．首先统计网页（Doc）特征向量feature中每个特征的权重（w1, w2,…, w-n）（如何确定特征及其权重详见下面的具体实现方法）;

2．依据每个特征对应的哈希值（hashvalue，一个由01组成的长度为M的串，其中1表示1，0表示-1，M为指纹长度）得到一组符号化权重值。如图所示，“100110”为长度为6的哈希串，“100110 w1”将得到一组（6个）符号化w1值“w1 -w1 -w1 w1 w1 -w1”。

3．特征向量所有特征对应位置符号化权重值相加，将得到一组整数，如图所示“13, 108, -22, -5, -32, 55”。

4．获取上步得到的一组整数的符号值（1表示正数，0表示负数和零），将其组成符号值串，即为该网页的指纹（fingerprint）。如图所示，“13, 108, -22, -5, -32, 55”其符号值串为“110001”，也就是网页（Doc）的指纹。



  基于Simhash原理实现一个相似网页（文本）检测工具，方法如下：

1．获取网页特征向量。对所有网页（文本）的非停用词（stopword）英文单词进行词频（出现次数）统计，并将单词词频由高到低进行排序（频度相同时，按字典序），取前N个单词构成网页特征向量feature=（word1, word2 , … , word-N）。N为特征向量维度，或长度。

注意：英文单词为仅由字母构成的字符串，不区分大小写。统计时要将大写字母转换为小写字母。在自然语言处理中，停用词（stop-word）指的是文本分析时不会提供额外语义信息的词的列表，如英文单词a，an，he，you等就是停用词。

2．统计每个网页（文本）的特征向量中每个特征（单词）的频度（权重），得到特征向量对应的权重向量weight=（w1, w2 , … , wN）。

3．每个特征wordi均有一个对应哈希值串hashi，每个网页的特征向量对应的权重向量中权重wi（i=1,2,…,N）按对应哈希值串hashi进行符号取值，得到一组由wi和-wi组成的符号化权重值向量SignWeighti。（权重值为0时符号化后值仍为0）。

4．计算网页指纹fingeprint。对每个网页，特征向量的所有特征对应的符号化权重向量对应位置值累加，并对累加结果，大于0置1，小于等于0置0，得到网页（文本）指纹（fingerprint）（一个由01组成的长度为M的编码串串）：

![](https://judge.buaa.edu.cn/userfiles/image/2022/166616329873203863347.png)

其中：

Sign(X) = { 1 | 0，当X>0时为1，X<=0时为0}

5．按上面方法计算新抓取的网页的指纹。

6．基于文本指纹相似度可以对新抓取的网页与已有的网页数据集进行相似比较。指纹相似度可通过汉明距离（Hamming distance）进行计算：两个文本指纹的汉明距离是指其二进制编码串中01取值不同的数量。举例如下：文本指纹10101 和 00110 从第1位开始依次有第1、第4、第5位不同，海明距离为3。

基于汉明距离可以筛选出大概率相同的网页文本，一般超过某个阈值（在此，阈值设置为3）则判定为不相似，小于等于阈值判定为相似。

7．按输出形式要求，依次将新抓取网页与已有相似网页（指纹汉明距离阈值为3以内的）按汉明距离由小到大网页输出到屏幕和指定文件中。


【输入形式】

从命令行输入特征向量长度N以及指纹长度M。

具体形式如下：
```
simtool N M
```
其中simtool为网页相似检测程序。其根据当前目录下的停用词文件“stopwords.txt”、哈希值文件“hashvalue.txt”、已有网页数据文件“article.txt”、待查重（即新提取）的网页数据文件“sample.txt”，按上面要求依次对sample.txt中每个网页文档在article.txt文件中查找相似网页，并按输出要求输出检测结果。

注意：

1．在课程网站“课件下载”区提供了project2023.zip，其中包括英文停用词表“stopwords.txt”文件(文件中只包含单词，不含其解释，且已按字典序排序）和哈希值文件“hashvalue.txt”。该hashvalue.txt文件中包含了10000（行）x128（列）由01组成的数据，每一行为一个哈希值串，若程序命令行输入的特征向量N为1000和指纹长度M为16时，则取该文件前1000行，每行取前16列作为实际哈希值表在程序中使用。哈希值文件的规模决定了本题的特征向量最大长度不超过10000，指纹最大长度不超过128。

2．由于Windows系统下文本文件中的’\n’回车符在（评测环境）Linux系统下会变为’\r’和’\n’2个字符，建议用fscanf(fp,”%s”,…)来处理停用词文件中英文单词。

3．为了简化相似检测程序的实现，已从互联网上爬取（Web Crawling）相关网页(文档)的工作已经完成，并将爬取的网页文档数据已存入一个文本文件（aritcle.txt）中，其中每个网页第一行为网页标识号（如XX-XXXX，可按字符串来输入），然后为网页内容，网页文档间以换页符\f分隔。在课程网站下载区提供了一个用于测试的article.txt文件。sample.txt文件中每个网页的标识号为“Sample-XXX”，其它格式同article.txt文件。


【输出形式】

按下面形式依次输出sample.txt文件中每个网页在article.txt中找到的相似网页信息到文本文件result.txt中：
```
X1

0:ID01 ID02 …

1: ID11 ID12 …

2: ID21 ID22 …

3: ID31 ID32 …

X2

...
```
其中X1,X2…为sample.txt中网页标识号，次序同原文件中序；“0:ID01 ID02 …”表示在article.txt中与相应网页指纹汉明距离为0的所有网页标识号，按article.txt文件中出现序排列，中间以一个空格分隔。若不存在相关网页，则无汉明距离为0的信息输出，即无“0:…”一行信息输出，其它部分含义相同。汉明距离相同的最后一个网页标识后也有一个空格分隔符。行末换行时输出字符“\n”即可。

同时，将sample.txt文件中第一个网页相似检测结果信息输出到屏幕上，即输出下面信息到屏幕上：
```
X1

0:ID01 ID02 …

1: ID11 ID12 …

2: ID21 ID22 …

3: ID31 ID32 …
```

【样例输入】

假设simtool.exe为网页相似检测程序，以下面方式运行该程序：

```simtool 1000 16```

（运行程序前，从课程网站下载区下载project2023.zip文件，其中包括：article.txt, sample.txt, hashvalue.txt, stopwords.txt, results(example).txt）

说明：若本地编程环境为dev-C++，可点击菜单Execute\Parameters…，在下面对话框中输入相应命令行参数。

![](https://judge.buaa.edu.cn/userfiles/image/2022/166616368515907725847.png)

【样例输出】



假设simtool.exe为网页相似检测程序，以下面方式（特征向量长度为1000，指纹长度为16）运行该程序：
```
simtool 1000 16
```
程序运行后，屏幕上输出的结果为：

![](https://judge.buaa.edu.cn/userfiles/image/2022/166616383747009010647.png)

所生成的结果文件“result.txt”内容应与下载区文件“result(example).txt”完全相同。

若以下面方式（特征向量长度为1000，指纹长度为32）运行该程序：
```
simtool 1000 32
```
程序运行后，屏幕上输出的结果为：

![](https://judge.buaa.edu.cn/userfiles/image/2022/166623327165501414747.png)

【样例说明】

以上面屏幕输出为例，其中第一行Sample-1为sample.txt中第一个网页标识号；第二行开始输出汉明距离（值为0，1，2，3）及在文件article.txt中与给定网页汉明距离为相应值的网页编号，网页编号间以一个空格分隔。若article.txt中不存在与给定网页汉明距离为某个值的网页，则该行不输出，如上面第2个屏幕输出，由于不存在汉明距离为1和3的网页，则该行不输出。输出文件result.txt中信息含意与此类同。

【评分标准】

本题为综合功能测试题，其评分标准为通过测试数据即可得分。程序运行无结果或结果错误将不得分。