文本指纹算法和系统简述

文本指纹算法和系统简述

 
文章转载于：   https://zhuanlan.zhihu.com/p/  作者：陈运文

【导读】 互联网网页存在大量的重复内容网页，无论对于搜索引擎的网页去重和过滤、新闻小说等内容网站的内容反盗版和追踪、还是社交媒体等文本去重和聚类，都需要对网页或者文本进行去重和过滤，因此需要一个好的文本指纹算法，本文将重点给大家分析文本指纹算法和系统简述

文本指纹介绍

互联网网页存在大量的重复内容网页，无论对于搜索引擎的网页去重和过滤、新闻小说等内容网站的内容反盗版和追踪、还是社交媒体等文本去重和聚类，都需要对网页或者文本进行去重和过滤。

最简单的文本相似性计算方法可以利用空间向量模型，计算分词后的文本的特征向量的相似性，这种方法存在效率的严重弊端，无法针对海量的文本进行两两的相似性判断。模仿生物学指纹的特点，对每个文本构造一个指纹，来作为该文本的标识，从形式上来看指纹一般为固定长度较短的字符串。

最简单的指纹构造方式就是计算文本的md5或者sha哈希值，但易发生“雪崩效应”，极小的文本差异通过md5或者sha计算出来的指纹就会不同(冲撞的概率极低)。

因此，一个好的指纹应该具备如下特点：

指纹是确定性的，相同的文本的指纹是相同的;

指纹越相似，文本相似性就越高;

指纹生成和匹配效率高。

业界关于文本指纹去重的算法众多，如k-shingle算法、google提出的simhash算法、Minhash算法、top k最长句子签名算法等等，本文将简单介绍各算法以及达观指纹系统的基本架构和思路。

常用的指纹算法

k-shingle算法

shingle在英文中表示相互覆盖的瓦片。对于一段文本，分词向量为[w1, w2, w3, w4, … wn]， 设k=3，那么该文本的shingle向量表示为[(w1,w2,w3), (w2,w3,w4), (w3,w4,w5), …… (wn-2,wn-1,wn)]，计算两个文本的shingle向量的相似度(jarccard系数)来判断文本是否重复。由于k-shingle算法的shingle向量空间巨大(特别是k特别大时)，相比vsm更加耗费资源，一般业界很少采用这类算法。

Simhash算法

Simhash是google用来处理海量文本去重的算法，同时也是一种基于LSH(locality sensitive hashing)的算法。简单来说，和md5和sha哈希算法所不同，局部敏感哈希可以将相似的字符串hash得到相似的hash值，使得相似项会比不相似项更可能的hash到一个桶中，hash到同一个桶中的文档间成为候选对。这样就可以以接近线性的时间去解决相似性判断和去重问题。

simhash算法通过计算每个特征(关键词)的哈希值，并最终合并成一个特征值即指纹。

图1 simhash算法示意图

Simhash指纹匹配过程

经过simhash指纹生成算法生成的指纹是一个f位的二进制字符串，如一个32位的指纹，‘00011011’。对于两个文本的f位0-1字符串，simhash算法采用hamming distance来计算两个指纹之间的相似度。当面对海量指纹集合时，一个简单的思想就是以空间换时间，对于一个32位的指纹来说，将该指纹划分成4段，即4个区间，每个区间8位，如果两个指纹至多存在3(设k=3)位差异，那么至少有一段的8位是完全相同的，因此可以考虑利用分段来建立索引，来减少需要匹配的候选指纹数量。

Simhash算法效率较高，比较适用于对于长文本，同时simhash算法没有考虑去重的粒度以及词的顺序，面对高精度时可能会带来准确度问题。

Minhash算法

Minhash也是一种LSH算法，同时也是一种降维的方法。Minhash算法的基本思想是使用一个随机的hash函数h(x)对集合A和B中的每个元素进行hash，hmin(A)、hmin(B)分别表示hash后集合A和集合B的最小值，那么P(hmin(A) == hmin(B)) = Jaccard(A, B)。这是minhash算法的核心，其中hmin(A)为哈希函数h(x)对集合A的最小哈希值。(达观数据 文辉)

图2： 最小签名矩阵生成示意图

Minhash算法采用最小哈希函数族(一组随机的最小哈希函数)来构建文档的最小哈希签名。文档的最小哈希签名矩阵是对原始特征矩阵降维的结果。应用过程中，可以使用k个最小函数分别计算出集合的哈希最小值。设hi表示第i个最小hash函数，最小签名矩阵中列向量为样本si的最小签名向量，其中wij表示第j个最小hash函数对样本i的最小哈希值。

当k小于原始集合的长度(k << n)时，就相当于对数据降维。

关于minhash的原理和推导，以及在大量文本及高维特征下如何快速进行最小签名矩阵的构建操作可以参考https://en.wikipedia.org/wiki/MinHash及《大数据互联网大规模数据挖掘与分布式处理》。

内容型网页文本指纹算法

本节将给出我们在对内容型网页(小说、新闻等)去重任务中总结出来的算法和实践经验，特别在当前内容版权日益受到重视和保护的背景下，对于内容版权方来说，如何从网络上发现和追踪侵权和盗版行为日益重要。

从前文可以看出，指纹识别算法是实现指纹识别的关键，它直接决定了识别率的高低，是指纹识别技术的核心。特别是类似新闻类、小说类网页在转载或者盗版过程中，文字的个数、顺序上一般都保持一致，当然不排除个别字错误或者少一个字的情况。

指纹生成的过程主要包括将文本全部转换成拼音、截取每个字拼音的首字母、统计该粒度内字母的频率分布、通过和参考系比较，将结果进行归一化、按字母序，将数字表征转换成数字。

图3 指纹生成算法

算法描述：

1. 转拼音：可以解决字符集编码不一致的问题，可以利用成熟的英文指纹算法，减小分布空间，同时可以解决同音字替代问题;

2. 截取拼音首字：减小存储长度和分布空间(26个字母);

3. 提取首字母频率：选择多少字来计算指纹，统计频率分布。需要设置颗粒度的大小(分段大小)以及重叠率。

大粒度容错性高，但是匹配率低;小粒度容错性低，但是误报率高且敏感度高。

重叠率是设置指纹计算片段移动的窗口大小：

假设拼音内容长为2n，颗粒长度为n，重叠率为50%，则需要计算的指纹片段分别为[1-n]，[n/2,3*n/2]，[n,2n]

4. 减去参考系：频率减去参考系

5. 归一化：将每个字母的数字特征归一化到一个闭区间内，如[0,9],按照字母顺序连接数字特征，变成一个数字，即指纹。

若空间为[0,9],即一个20位的整数，2^64，需要 8 byte

若空间为[0,7],可用一个20位的8进制数，8^20,需要 8 byte

若空间为[0,3],只需要 4^20, 共40 bit, 5 byte

若空间为[0,1],需要2^20,20 bit,3 byte

归一化过程的算法步骤如下，假设颗粒长度为m：

达观指纹系统结构

4.1 基本架构

达观指纹追踪系统主要由爬虫系统、指纹生成系统、指纹存储、指纹查询和比对、数据分析、后台管理系统等几个主要模块构成，如图4所示。其中存储层包括匹配结果信息库、网页库以及指纹库。

图4 指纹追踪系统模块图

爬虫系统

爬虫系统从目的上看主要在于抓取互联网上的特定领域的网页(如新闻类网页)，爬虫系统是原始数据的唯一来源，只有通过爬虫系统才能从浩瀚的互联网中抓取相似的网页内容。爬虫系统需要拥有较高的抓取能力和反爬取能力，为整个系统提供大量的待检测页面。

指纹存储模块

指纹存储模块计算母体(海量文本)的指纹，指纹可以理解为一行文本的向量表示，本系统的指纹存储系统采用mongo DB进行存储。

指纹生成模块

指纹生成模块的输入是一行文本，其输出为该文本的指纹表示，为了达到较高的对比准确率，一个好的指纹生成系统至关重要。

指纹查询和比对模块

指纹库中存储着大量的母体指纹，对于某一文本，指纹查询和比对模块要快速的判断该文本是否在母体库中存在重复。

数据分析

数据分析系统需要对大量的文本及其对比结果进行统计数据分析。

后台管理平台

提供数据分析的展示，并提供用户使用查询和输出分析报告等。

数据存储模块

网页库

主要存放爬虫系统抓取的网页信息、站点信息，本系统网页库采用mongo DB。

指纹库

主要存放母体指纹，本系统采用mongo DB存放指纹。为了加快指纹的查询和比对，本系统采用redis来对指纹建立索引，加快匹配速度。

匹配信息库

存储指纹匹配结果， 包括待匹配的两个指纹， 原始网页id， 匹配相似度等。

4.2 系统架构

图5 系统架构图

4.3 系统处理流程

本系统的处理流程如图6所示，系统支持每天自动化从母体库中调度新的任务进行去重操作。

图6 系统流程图

4.4 查询和比对系统

查询和比对的系统的目的就是快速和高效的找出与目标指纹相似性较高的母体指纹。针对指纹查询的特点，对母体指纹库建立索引，待查询指纹通过查询索引，即可发现最可能匹配的母体。

指纹查询比对流程如下：

建立索引

每个母体指纹描述的是母体ID -> 特征的关系，可以通过以特征为key，母体ID为value建立倒排索引。如母体为: 1->[a,b,c,d], 2->[b,e,f], 3->[a,c,g]，则索引为：a->[1,3], b->[1,2], c->[1,3], d->[1], e->[2], f->[2], g->[3]。与其他算法一样的是，也需要考虑索引的粒度，粒度的大小同时应考虑指纹算法选择的粒度。

采样

根据待匹配文本的特点(长度)，选择合适的粒度和片段，重要的是保证匹配的正确性的同时，减少生成指纹的运算量。

提取指纹

根据指纹生成算法生成待查询指纹。

查询指纹

将待查询指纹进行索引查询，统计命中母体和命中次数，并按照次数排序，选择命中次数高的母体作为可疑对象，次数低于阈值，可忽略。

后处理

结合历史统计模型，筛选结果。匹配结果不确定，可进行第二轮细致比对或人工验证。

总结

对于网页去重、内容盗版追踪、内容聚类等应用来说，指纹模块都是极其重要的模块。本文介绍了一些比较常用的指纹算法，包括k-shingle、simhash、minhash;同时介绍了达观数据自主开发的指纹追踪系统及其关键算法，达观数据在指纹系统构建和算法方面积累了丰富的经验，没有最好的算法，只有合适的算法，在实际的使用过程中，需要根据具体业务场景，确定架构和算法。

作者简介

文辉，同济大学计算机应用技术专业硕士，现任达观数据联合创始人，主要负责据推荐系统、数据采集系统、大数据平台架构等主要系统的研究和开发。曾就职于盛大文学数据中心部门，负责推荐系统、爬虫系统、数据挖掘和分析等大数据系统的研发工作，在数据挖掘和采集、Hadoop/Hive、Spark等方面具备充足的研发和实践经验。

本文版权归 达观数据(http://www.datagrand.c