引言
网络爬虫让我们高效地从网页获取到信息，但网页的重复率很高，网页需要按内容做文档排重，而判断文档的内容重复有很多种方法，语义指纹是其中比较高效的方法。
本文选自《网络爬虫全解析——技术、原理与实践》。
用途
文章相似度，杜绝论文抄袭等等。
语义指纹的由来
提到“指纹”就想到了人手的指纹。
那么指纹能干嘛呢？
我们看到最多的是警匪片中验指纹，还有公司考勤打卡用指纹等。其目的在于识别个体。
当然作为指纹特征，需要它是可唯一确定的、不容易更改的、方便携带的。
信息需要“指纹”的目的也有两个：一是检索，二是防假。
指纹可用于检索，主要是在做一些关键字查询时不可能拿这些关键字与所有的信息原文进行比对，时间上是不可能的，比对的一定是事前整理好的特征信息，能“代表”信息的规律的信息，这就是信息的指纹。
所以信息提取指纹是我们在信息海洋中搜寻的前提。
信息指纹技术也是搜索公司特别关注的新技术之一。
信息指纹还可以用于防假。
将信息打上相关的指纹就可以防止他人侵占革命成果，这有此类似于数据签名、CA验证之类的。例如，对博客文章进行语义指纹提取就能很好地识别重复，另如将不同密级的信息进行指纹提取给信息本身一个指纹更方便而且安全的识别信息密级。
二、语义指纹提取的几种方法
判断论文重复的方式
判断文档的内容重复有很多种方法，语义指纹的方法比较高效。
语义指纹是直接提取一个文档的二进制数组表示的语义，通过比较相等来判断网页是否重复。
语义指纹是一个很大的数组，全部存放在内存会导致内存溢出，普通的数据库效率太低，所以采用内存数据库Berkeley DB，可以通过Berkeley DB判断该语义指纹是否已经存在。
另外一种方法是通过布隆过滤器来判断语义指纹是否重复。
提取网页语义指纹的方法是
从净化后的网页中，选取最有代表性的一组关键词，并使用该关键词组生成一个语义指纹。
通过比较两个网页的语义指纹是否相同来判断两个网页是否相似。
同义词处理
为了提高语义指纹的准确性，需要考虑到同义词，例如，“北京华联”和“华联商厦”可以看成相同意义的词。
最简单的判断方法是做同义词替换。
把“开业之初，比这还要多的质疑的声音环绕在北京华联决策者的周围”替换为“开业之初，比这还要多的质疑的声音环绕在华联商厦决策者的周围”。
语义指纹生成算法如下所示。
第1步：将每个网页分词表示成基于词的特征项，使用TF*IDF作为每个特征项的权值。地名、专有名词等，名词性的词汇往往有更高的语义权重。
第2步：将特征项按照词权值排序。
第3步：选取前n个特征项，然后重新按照字符排序。如果不排序，关键词就找不到对应关系。
第4步：调用MD5算法，将每个特征项串转化为一个128位的串，作为该网页的指纹。
Hash 算法的选择
MD5可以将字符串转化成几乎无冲突的hash值，但是MD5速度比较慢，MurmurHash或者JenkinsHash也可以生成冲突很少的hash值，在Lucene的企业搜索软件Solr1.4版本中提供了JenkinsHash实现的语义指纹，叫作Lookup3Signature。
调用MurmurHash生成64位的Hash值的代码如下所示。
public static long stringHash64(String str, int initial) {
byte[] bytes = str.getBytes();
return MurmurHash.hash64(bytes, initial);
}
二、语义指纹提取的几种方法
语义指纹是一种高效率的信息处理方式，它不仅节约了时间成本还节约了计算成本，在现实生活中应用较多，例如搜索引擎、全文检索系统、论文防剽窃系统等。
指纹是对有用的信息进行的提取，故在此将信息指纹称为“语义指纹”。
不同的应用需求，会有不同的语义指纹提取方法。
（一）文本信息指纹提取
统计信息表明：对一个文本信息提取指纹，当选取8个关键词及其词频作为其指纹时，准确度在98%以上，查全率在30%左右。
这说明要能“概括”该信息，找出其8个使用频率最高的词汇，基本可以代表这个信息。
因此文字信息提取指纹的要素一般为下面信息：
n 标题
n 作者
n 发布时期、修改日期
n 主要关键词
其中关键词的选取可以有几种方法：
作者提供的关键词
作者提供的摘要，或整理人员编写的摘要
提取信息中出现频率高的8个关键词
文章开头或结尾一段话
文章中固定位置的一段话(如第5行的第一句话)
有了这些代表信息后，便可以形成指纹信息，若再对这些信息进行Hash运算、MD5等方式加密、变化，生成一段定长(如256字节)的信息，就可以作为该信息的“指纹”，经过加密主要是防止对信息内容的篡改和对指纹的替换。
这种方法有些象数字签名技术，但要相对简单，并且不进行加密运算时的标题等信息可以直接作为检索的关键字使用。
具体应用例如：运用一种基于网页关键词概念之间关系的关键词选取方法，来计算出网页中关键词权重并进行排序，然后选取权重最高的L个关键词，并称这L个关键词为长度为L的网页指纹或者因为如果以这一关键词集合来描述网页文本时，它们是具有最丰富的网页语义表达的选择。
具体算法
下面给出一个具体的算法：
该方法通过分解文档、构建文本块序列、Hash文本块序列、指纹提取等步骤自动检测文档间的重叠信息。
文本块是检测的基本单位，较大的粒度可以有效地减少检测结果中误差的数目，但是粒度越大，丢失复制文本的机率越大。
因此文本块的长度直接关系检测结的准确性和精确程度。
本文分别选取两种检测粒度的文本块：
1）句子文本块。
句子作为文本块，不仅可以减少块的数量，降低存储空间消耗，提高检测效率，同时句子也是位置相对独立的结构单元，改变它在文档中的顺序，不影响检测结果。
短句包含较少的语义知识，对文档的贡献也少，因此没必要参与计算。
这就需要方对句子的选择进行限制，即句子中应该包含一定数量的有效关键词。
定义噪声粒度，从检测文档中消解噪声。
例如对句子进行分词后去除停用词，如果其关键词的数目不小于阈值，则认为是有效的，否则丢弃；
2） k-words文本块。
对长句进行分解，使用连续的k个词语构建重叠的文本块序列。不仅能够发现文档句子间的重叠文本，同时又抑制噪声有效地提高了检测结果的精确度。
例如，对于句子 ，构建的文本块序列分别为 。同时方法定义检测粒度g，目的是要检测文档间任何大于该粒度的复制文本。
把文本块看作是一个k位的数字，使各个词语取其词汇库中对应的映射值，利用Karp-Rabin函数可以把文本块数值化。
令散列值序列为h1h2h3h4…hn（n为句子长度）。
如果要找出所有粒度大于g的文本匹配，那么当n>g-k时，在该序列中应该至少选择出一个hi才满足条件。
令窗口长度为g-k+1。散列值序列h1h2h3h4…hi…hn中对于任意的1<=i<=n-g+k(重叠窗口个数)都定义了一个散列值窗口hihi+1…hi+g-k，如果在各个窗口中提取相应的文本特征，方法就可以保证发现所有粒度大于g的文本匹配。
选择出的文本特征称为纹。
本文算法
本文的指纹提取算法如下：
输入：句子序列、噪声粒度k和检测粒度g
输出：[指纹，全局位置]
1）利用Hash函数把关键词数目不小于k的句子数值化，选择所有句子散列值作为指纹并标记全局位置；
2）分解句子，构建 k-words文本块序列。并标记散列值所在的全局位置，将散列值分配到长度为g-k+1的重叠窗口中；
3）提取文本块指纹：
① 在第一个窗口中选择最小的数值作为指纹，并记录指纹的全局位置。若存在相同的最小值，选择全局位置最大的数值作为指纹（指针指在指纹位置）；
② 若指针不大于窗口的个数（句子散列没有结束），则指针后移。否则，转4）；
③ 设前一个提取出的指纹为fi，若fi不存在于当前窗口中，从右向左查找最小的数值（当前最小的最大位置），并记录该值以及全局位置，返回②；
④ 若fi存在于当前窗口中，比较fi和窗口中位置最大的数值hg-k。若fi < hg-k，返回②；否则选择hg-k作为指纹，返回②；（感觉像是最小值所负责的范围）
4）算法结束。
该算法的优势在于算法能检测出任何，粒度大于的复制文本。算法的时间复杂度为o(n)。
（二）多媒体信息指纹提取
文字信息的指纹提取不容易，对语音、图像指纹的提取就更困难了，因为对图像、语音的描述本身就比文字要麻烦。
一般的思路是：在语音、图像先进行特征编码，也就是选取有代表意义的局部，语音中的某段频率(人的声音都有自己的音色特点)，图像中的明暗对比强烈的地方、或关键图像的区域等，再对编码进行变换、加密等处理，形成指纹。
色阶图方法
下面我们介绍一个图像提取指纹的简单方法：色阶图方法。
色阶图(Color histograms)：就是从图像中产生出，可以描述图像的色彩分布。
图像与文本信息不同，是以点阵的色彩存放，信息量非常大，算法的目的就是进行信息简化，具体步骤如下：
-
大小：对图像进行切割，根据颗粒度不同，小块大小为
m*n，图像分割为M*N个块 -
模糊：对每个图像块进行色彩的平均处理，也就是用该块最多的颜色代表该块
-
减色：将色彩从真彩的65536色减少，合并颜色，当然颜色数量可以根据颗粒度选择8色、16色、256色等，本例选择为8色
-
替换：简化后信息为
M*N*8，每个颜色用一个字母符号替代，如：采用xpm格式，每个颜色用一个字符表示：
B 对 black . 对blue X 对green o对cyan
O 对 red + 对magenta @ 对yellow # 对gray100
- 编码：把每个图像块用其字母替代，再按顺序排列，就形成一个 M*N 的字符串。该字串作为图像的指纹信息。
三、语义指纹应用
语义指纹应用也主要来源于它的两个功能，一是检索，二是防假。
信息复制性检测
主要应用场景有：网页（文档）去重、文本复制检测。
在网页去重应用中，通过对网页的特征信息进行提取，建立网页指纹，如果有相同指纹的网页进入，则可判断为“同一”网页。
在文本复制检测中，将文本进行分块，分别对目标块和源块进行指纹提取，通过比对指纹即可判断是否存在文本抄袭或者复制。
具体过程要复杂得多，可以参阅相关论文。
检索
这一功能是指纹的反向利用，简单举例，如在新闻搜索中，相似新闻的检索就可以通过新闻指纹查到同一指纹关联的多个新闻。
引 言
随着各种各样信息的不断增长， 可供用户使用的信息资源不断增多， 同时用户的信息搜寻成本也越来越大，“信息迷航” 问题越来越突出。
导致这一问题的原因之一是信息复制的边际成本接近于零， 相似或重复内容增多。
从信息资源集合中去除重复内容能提升用户使用信息资源的效率， 是信息资源管理中的一个重要工作。
目前， 信息内容去重已应用于多种应用场景。
在搜索引擎方面， 大量重复网页的存在一方面增加了搜索引擎在系统存储和运行上的负担， 同时也影响到检索算法的性能， 重复网页的检测和去除能在一定程度上减轻系统负担、 提升检 索效果， 也能增加用户对搜索结果排序的满意度［1 ］ 。
在垃圾信息过滤方面， 垃圾信息往往表现出多次发布现象，重复内容检测也是识别垃圾信息的手段之一， 例如针对博客评论中广泛存在的广告机器人特点， 采用信息指纹的方法对博客中的垃圾评论进行识别和过滤［2 ］ 。
在文件去重方面， 利用内容去重方法可以识别文件内容的相似性，用于追踪科技文献中的相似性， 从而识别论文抄袭现象［3 ］ 。
在目前大数据环境下， 需要快速地处理文本内容， 实现快速文本去重， 以满足对大数据量处理的要求。
在此背景下， 本文针对中文文本， 先提取出文本特征， 运用 Simhash 算法根据中文文本特征生成语义指纹， 通过判断不同文本语义指纹的比特位差异程度来识别文本间的相似程度， 并在语义指纹基础上应用 Single － Pass 快速聚类算法， 实现文本语义指纹快速聚类， 达到中文文本快速去重的目的。
文本内容去重方法
文本内容去重任务关注的是从文本数据集中找到相同或者高度相似的文本。
在搜索引擎领域和目前大数据环境下， 如何快速地识别相同或相似文本是文本内容去重的挑战之一。
目前主要的文本内容去重方法有两种:
基于相似性的方法和基于摘要技术的方法。
基于相似性的方法
基于相似性的方法是用文本的内容或结构的相似性来判断文本是否属于重复文本。
在内容相似性识别方面， 常见方法是利用多种途径提取出内容的特征信息， 通过匹配两个文本的内容特征， 来判断文本相似性。
其中， Shingle 算法是一种比较知名的基于相似性的内容去重方法［4］ 。
该方法将文本视为词项序列， 将固定长度的相邻词项视为一个 Shingle， 从而将文本转化为 Shingle 集合加以表示， 并通过对比两个文本的Shingle 集合匹配程度来识别两者是否在内容上相似。
在 Shingle 算法中， 每一个 Shingle 实质上是文本的一个特征码， 因此该算法也是一种基于特征码的方法。
特征码的提取在具体应用中有多种方法:
文献［5］面向短文本提取短文本中的特征码， 并利用关联规则方法判别文本之间的相似性;
文献［6］通过将文本进行简单自然分句， 利用分句首尾字符生成文本的特征字符串作为文本的特征码;
文献［7］在元搜索引擎的网页去重任务中， 根据用户查询词所在分句生成摘要特征码。
另外， 文献［8］利用 B － Tree 数据结构进行索引， 极大地提升了处理速度， 从而使特征码方法适用于大数据量的文本内容去重场景。
然而， 基于特征码的方法并未考虑语义因素， 只单纯从字符串匹配的角度进行内容识别， 部分研究也尝试在一定程度上理解文本的语义内容， 得到文本的语义表示。
文献［9］和文献［10］将文本表示为词向量，通过余弦相似度计算文本间相似度， 从而将文本内容的相似性上升到语义层次的相似性， 但该方法在相似性阈值设置以及大数据量的处理方面存在缺陷。
内容相似的文本在结构上也可能具有一定的相似性， 例如互联网上近似镜像的网页在内容和结构上有可能高度一致［11］。
因此， 结构识别也能为相似内容的发现提供一定的依据。
文献［11］利用重复网页的结构特点， 利用正文结构树的形式来表达网页正文内容，并结合指纹计算方法， 实现网页去重。
基于摘要技术的方法
基于摘要技术的方法是利用摘要算法计算文本的摘要值， 即将文本表示为一个较小的数值或者较短的字符串， 以判断两个文本是否相同。
基于摘要技术的方法可以单独使用， 即直接将文本的摘要值进行匹配，也可以与基于内容相似度的方法结合使用， 在内容特征提取基础上， 进一步计算摘要值。
目前该类方法主要有 MD5、 DSA 等摘要算法。
若直接用文本摘要值进行匹配， 往往只能判断内容是否完全相同。
因为只有完全相同的文本才能产生完全相同的摘要值， 即使原始文本差别很小， 所得到的摘要值也可能差别非常大，即从文本生成摘要的过程往往是不可逆的。
针对文本内容去重任务， 需要一种能够识别出文本近似相同(只做过少量修改)的摘要算法， 该类算法在进行摘要计算前， 往往需要对文本内容特征进行一定的预处理。
文献［12］提出一种新的哈希算法， 在文本 N －gram 基础之上利用常用汉字编码表进行特征映射， 将文本映射为哈希值序列， 通过比较文本的哈希值序列来实现文本内容的重复性检测。
文献［13］提出一种I － Match方法， 通过统计语料库词典与从文档中抽取词项的交集， 为每个文档产生一个摘要值， 从而保证每一个文档被映射到单个聚类上， 以聚类来表示相似的文档集。
文献［14］ 在该方法的基础上， 提出采用多个语料库词典， 分别为每篇文章生成多个摘要值， 从而改变摘要值过分依赖于词典的现象， 提升了识别算法的性能。
可以看出， 以上算法都是先提取出文本的内容特征， 再利用摘要技术进行处理， 将变化较小的文本识别为相同文本。
然而， 尽管如此， 这些方法也无法通过比较摘要值的差异来判断原始文本的差别程度。
目前，Simhash 算法是一种实现该目标的较好算法［15］。
Sim-hash 算法能够在将文本内容特征转化为摘要值的同时， 根据摘要值的差别大小， 判断原始文本内容的差别程度。
整合语义指纹和 Single －Pass 的文本
去重流程
Simhash 算法由 Charikar ［15 ］ 于 2002 年提出， 目前被认为是文本内容近似去重最有效的方法［16 ］。
Sim-hash 实质上是一种语义指纹技术， 它能将文本内容的语义特征映射到相应的比特(Bit)上， 并以这些比特所组成的数值来表示文本内容的指纹(Fingerprint)。
一般而言， 该指纹的比特位数相对较小， 例如32 或64， 故也可将 Simhash 算法理解为一种降维技术。
区别于其他指纹技术， Simhash 算法能用于识别相似内容， 而不是像简单的摘要算法那样只能判断内容是否完全一致。
相似的文本内容通过该算法生成的指纹值也只在少量的比特位(Bit Position)上不同， 因此可以根据语义指纹值的比特位差异来判断文本间的相似程度。
常用的内容去重方法是利用文本聚类技术将相似或相同文本聚集在一起， 从而达到文本去重的目的。
本文在 Simhash 算法的基础上， 整合 Single － Pass 快速聚类算法实现面向中文文本的文本内容去重， 整体流程如图 1 所示:
该方法主要分为两大环节:
文本的语义指纹值计算; 利用 Single － Pass 聚类算法对语义指纹值进行聚类。
在文本的语义指纹值计算过程中， 根据 Simhash算法， 需要先提取文本内容的语义特征， 常规的方法是对中文文本进行分词处理， 利用语词代表文本的语义特征， 然后再根据语义特征利用 Simhash 算法计算出文本的语义指纹值。
该过程可以独立计算， 针对固定文本集， 一次性批量地计算所有文本的语义指纹值， 而针对流式的、 动态的文本集， 则可以在文本加入时计算语义指纹值， 以备后续使用。
在语义指纹聚类过程中，根据语义指纹的数值特征应用 Single － Pass 聚类方法，以实现对语义指纹的快速聚类， 单个聚类类别代表去重后的一个文本。在后续处理中， 只保留聚类中心， 去除单个聚类类别中其他文本。
3．1 文本特征提取
文本特征提取是从原始文本中抽取出能表征文本语义内容的词项作为文本特征， 将文本表示为词项集合， 并以词频作为特征的权重。
文本特征提取过程主要包括如下三个环节:
(1) 中文文本预处理。
中文文本语义指纹生成流程中的第一步是对中文文本进行预处理， 得到文本内容字符串。
中文文本数据源的常见格式有 HTML 网页、 XML 文件、 Word 文件、 Excel 文件等各种结构化或半结构化数据， 需要从这些文件中解析出文本内容字符串， 以便后续处理。
(2) 文本分词。
在英文文本中， 文本特征往往指从单个单词经过处理后得到的词项， 而针对中文文本，需要借助文本分词工具得到文本的语词， 作为文本特征项。
(3) 停用词过滤。
在中文文本中往往存在一些对语义贡献较小或者出现频率过高的词， 例如“的” 、“是” 等， 称作 “停用词” 。
因此， 在得到最终特征项前，需要先将这些停用词去掉， 以减少这些词项对文本内容特征的干扰。
通过以上步骤， 经过文本分词和停用词过滤后所得的词项即为文本的最终特征， 并交由 Simhash 算法处理， 以生成语义指纹。
语义指纹生成
将文本特征作为 Simhash 算法的输入， 通过 Sim-hash 算法计算得到文本的语义指纹值， 详细算法过程描述如下［15 ］ :
- 输入:
n 维特征向量 v = {w 1 ， w 2 ， …， w n }， 其中 w 1 ， w 2 ，…， w n 分别是文本内容特征 v 1 ， v 2 ， …， v n 的权重;
- 输出:
一个 b 位的指纹 f = {f 1 ， f 2 ， …， f b }， 其中 f 1 ， f 2 ， …，f b 取值为 0 或 1。
- 计算过程:
① 维持一个 b 维向量 f c ， 每一维度值初始化为 0;
② 通过运用某种普通字符串哈希函数， 将文本的特征 v i 映射为一个具有 b 个比特的数值 h i ;
③ 根据 h i ， 应用如下规则更新 f c : 如果 h i 的第 j 位是 1， 那么将 f c 的第 j 维值加上该特征 v i 的权值 w i ; 如果 h i的第 j 位是 0， 那么将 f c 的第 j 维值减去该特征 v i 的权值 w i ;
④ 针对所有的特征， 重复步骤②和③;
⑤根据 f c 得到最终的指纹 f: 如果 f c 中的第 i 维向量值为正， 则 f 中第 i 位的比特值为 1， 否则为 0。
常用的普通字符串哈希函数有 RS、 JS、 PJW、 EFL、SDBM 等［17 ］ ， 本文采用 SDBM 函数作为普通字符串哈希函数， 其来源于 SDBM 开源软件项目［18 ］ ， 并已在多个数据集中广泛应用。
通过以上算法， 将一个具有 n 维特征的文本内容表示为一个 b 位的语义指纹值， 可转化为一个数值加以表示。
由于一般情况下 n 远大于b， 同时语义指纹中直接采取比特位进行计算， 语义指纹所使用的计算空间远小于对 n 维特征直接存储所使用的空间。
本文沿袭文献［16］ 的做法， 将 b 设置为 64。
基于 Single － Pass 的语义指纹快速聚类
Single － Pass 算法是一种面向流式数据的经典增量式聚类算法， 也称作单通道法或单遍法［19］。
该算法的基本思路是对于流式数据， 一次取出一个文本， 进行增量式动态聚类， 将文本与已有的聚类类别进行相似度匹配。
如果与某一类别的相似度大于某阈值， 则将该文本归入这一聚类类别;如果与所有类别的相似度都小于某个阈值， 则新建一个聚类类别。
Single － Pass聚类算法的优势在于算法复杂度低， 只需要一次扫描数据集即可完成聚类过程。
详细算法流程
结合文本语义指纹的数值特点， 利用 Single － Pass实现聚类过程， 详细算法描述如下［20 ］ :
- 输入:
中文文本流 p 1 ， p 2 ， …， p n ; 内容相似一致性判断阈值 HD;
- 输出:
网页去重后文本集 DistSet = ( ds1， ds2， …， dsi) ， 及对应的相似内容文本集 SimSet( S) ;
- 数据结构:
网页去重后文本集 DistSet 按语义指纹值升序排列。
算法执行过程:
①接收一篇文本 d i ， 利用 Simhash 算法计算该文本的语义指纹值 f i ;
②将该文本的 Simhash 值与已有聚类的聚类中心文本的语义指纹值进行对比， 比较两者比特值的海明距离( Ham-ming Distance) h， 找到与 f i 海明距离最小的聚类中心 ds j ( 其语义指纹值为 f dsj ) ;
③判断海明距离最小者 h min 是否小于给定阈值 HD;
④如果 h min ≤HD， 则认为该文本与该聚类类别内容相似， 将该文本加入到该类别相似内容文本集 SimSet( ds j ) 中;
⑤如果 h min ＞ HD， 则认为在已有的类别中未找到与该文本相似的类别， 新建一个聚类类别 ds new ， 并以该文本作为聚类中心， 更新 DistSet。更新方法为: 如果 f i ＜ f dsj ， 则将 ds new 放置在 ds j 前， 否则放置在其后;
⑥本次聚类结束， 等待新的文本到来。
其中， 海明距离是指两个二进制数的对应比特位不同的比特位数， 例如二进制数 10101 和 00110 从左往右第 1 位、 第 4 位和第 5 位不同， 则两个二进制数的海明距离为 3。
同时， 在上面计算过程中， 将阈值 HD取值设为 3。
这里沿用文献［16］的取值， 即如果两个文本语义指纹值的海明距离小于等于 3， 则认为两者内容相似。
拓展阅读
simhash
