常见的网页去重算法有：
I-Match算法
Shingle算法
SimHash算法
Counting Bloom Filter算法
其中Shingling、SimHash最被搜索引擎广泛使用。
Shingle算法
第一步：特征抽取
抽取多个特征词汇，通过比较两个特征集合实现文档重查(Shingle算法)
Shingle算法：对长度L的文档，每个N个汉字取一个Shingle，一共渠道L-N+1个Shingle
第二步
相似度计算和评价 Shingle算法的比较方法为记录完全一致的Shingle个数，然后除以两个文档总个数减去一致的Shingle个数，计算出的数值为“jaccard系数”
再通过jaccard系数量化相似度后，可通过此数值判断是否相似，搜索引擎中达到0.2才能判断为相似
Shingle的python实现：
#encoding:utf-8
#计算文档相似性（shingle）
import time
start = time.time()
class ShingLing(object):
cut_step = 5 #切片字长
text = []
com_count = 0
def __init__(self,text1,text2):
self._cut(text1)
self._cut(text2)
def _cut(self,text):
if len(text) < self.cut_step:
return
text = list(text)
pice_list = []
for i in range(len(text) - self.cut_step):
pice = text[i:i + self.cut_step]
pice_list.append(pice)
re = {'pice':pice_list,'length':len(text)-self.cut_step}
self.text.append(re)
def com(self):
pice1 = self.text[0]['pice']
pice2 = self.text[1]['pice']
for item in pice1:
if item in pice2:
self.com_count += 1
total_length = self.text[0]['length'] + self.text[1]['length']
com_count = self.com_count*2
return com_count/float(total_length)
text1 = str(open('1.txt','r').read())
text2 = str(open('2.txt','r').read())
s = ShingLing(text1,text2)
end = time.time()
time = end-start
print s.com()
print '运行时间：' + str(time)
Simhash算法
Simhash是Google提出的一种用于网页判重的hash算法。
传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值，原理上相当于伪随机数产生算法。传统hash算法产生的两个签名，如果相等，说明原始内容在一定概率下是相等的;如果不相等，除了说明原始内容不相等外，不再提供任何信息，因为即使原始内容只相差一个字节，所产生的签名也很可能差别极大。
从这个意义上来说，要设计一个hash算法，对相似的内容产生的签名也相近，是更为艰难的任务，因为它的签名值除了提供原始内容是否相等的信息外，还能额外提供不相等的原始内容的差异程度的信息。
Simhash具有两个“冲突的性质”： 1. 它是一个hash方法 2. 相似的文本具有相似的hash值，如果两个文本的simhash越接近，也就是汉明距离越小，文本就越相似。 因此海量文本中查重的任务转换位如何在海量simhash中快速确定是否存在汉明距离小的指纹。也就是：在n个f-bit的指纹中，查询汉明距离小于k的指纹。
Simhash的python实现
#coding=utf-8
import time
start = time.time()
class simhash():
def __init__(self, tokens='', hashbits=128):
self.hashbits = hashbits
self.hash = self.simhash(tokens)
def __str__(self):
return str(self.hash)
def __long__(self):
return long(self.hash)
def __float__(self):
return float(self.hash)
def simhash(self, tokens):
# Returns a Charikar simhash with appropriate bitlength
v = [0]*self.hashbits
for t in [self._string_hash(x) for x in tokens]:
bitmask = 0
for i in range(self.hashbits):
bitmask = 1 << i
if t & bitmask:
v += 1 #查看当前bit位是否为1，是的话则将该位+1
else:
v += -1 #否则得话，该位减1
fingerprint = 0
for i in range(self.hashbits):
if v >= 0:
fingerprint += 1 << i
#整个文档的fingerprint为最终各个位大于等于0的位的和
return fingerprint
def _string_hash(self, v):
if v == "":
return 0
else:
x = ord(v[0])<<7
m = 1000003
mask = 2**self.hashbits-1
for c in v:
x = ((x*m)^ord(c)) & mask
x ^= len(v)
if x == -1:
x = -2
return x
def hamming_distance(self, other_hash):
x = (self.hash ^ other_hash.hash) & ((1 << self.hashbits) - 1)
tot = 0
while x:
tot += 1
x &= x-1
return tot
def similarity(self, other_hash):
a = float(self.hash)
b = float(other_hash)
if a>b: return b/a
return a/b
if __name__ == '__main__':
s = str(open('1.txt','r').read())
hash1 =simhash(s.split())
s = str(open('2.txt','r').read())
hash2 = simhash(s.split())
print '%f%% percent similarity on hash' %(100*(hash1.similarity(hash2)))
print hash1.hamming_distance(hash2),"bits differ out of", hash1.hashbits
end = time.time()
time = end - start
print '运行时间:' + str(time)
实际测试
从网易新闻随便找一篇文章做text1，然后用奶盘伪原创后在手动段落、短语错位用做text2
text1 = ”’
新华网休斯敦4月30日电 美国得克萨斯州西部一座油田4月30日发生爆炸，造成2名工人死亡，另有9人受伤。
据《休斯敦纪事报》网站报道，该油田所在地拉温县警方表示，工人们当时正在用重型设备更换一座油井的井口部件，由于压力加大，突然发生爆炸。2名工人当场被炸死，另外9人受伤。
警方说，油田地处偏僻的乡村地区，通信条件不佳，因此现场其他详情无法得知。
近年来，包括得克萨斯州在内的美国一些地区的油气行业一片兴旺。在拉温县，许多新油田如雨后春笋般涌现。
美国能源信息局近期公布的数据显示，去年美国的石油产量达到日均740万桶，其中，得克萨斯州占全美总产量的近35%。与此同时，得克萨斯州27家炼油厂的产能占全美炼油总量的29%。
”’
text2 = ”’
新华网休斯敦4月30日电 美国得克萨斯州西部一座油田4月30日发生爆炸，造成2名工人死亡，还有9人受伤。
警方说，油田地处偏远的村庄区域，通信条件欠安，因而现场其他概况无法得知。
这些年，包含得克萨斯州在内的美国一些区域的油气职业一片兴隆。据《休斯敦纪事报》网站报导，该油田所在地拉温县警方表示，工大家当时正在用重型设备更换一座油井的井口部件，因为压力加大，俄然发生爆炸。
2名工人当场被炸死，别的9人受伤。在拉温县，许多新油田如雨后春笋般出现。
美国能源信息局近期公布的数据显现，上一年美国的石油产值到达日均740万桶，其间，得克萨斯州27家炼油厂的产能占全美炼油总量的29%。与此同时，得克萨斯州占全美总产值的近35%。
”’
“原创”与“伪原创”测试后shingle值和simhash值分别如下：
由此可见，市面上一堆伪原创的东西压根不靠谱，这还是很粗糙的相似度判断 ……
在从网易找另一篇新闻做text2，测试相似度
new text2 = ”’
近些年来，银行固定收益类理财产品的收益率突破7%关口，主要在2013年明显发生过两回，分别是2013年6月末、12月末。
21世纪经济报道统计发现，与2013年情形相比，2014年超过7%收益的银行理财呈现三大特点，首先是门槛高，2013年的产品认购起点多为5万元，而最近则在10万元、30万元和50万元较为普遍。
其次2013年两次高收益理财，发生的背景都是市场流动性紧张，因此它们期限较短，多在1-3个月以内。而上述的理财产品期限基本都在1年、2年时间;再者，2013年的产品发行银行以股份行为主，最近则以中小城商行、农商行为主。
事实上21世纪经济报道统计，自2014年以来，银行似乎更愿意用收益较高的长期限理财产品，来锁定投资者的资金。银率网数据也证明这点，在一季度，投资期限大于六个月的中长期理财产品占发行总量的比例为13.61%，环比上升16.56个百分点。
投资期限在一年以上的人民币理财产品总计发行273款，占人民币理财产品发行总量的2.36%，环比上升60.59个百分点。
相反，今年1月-2月，“宝宝”类货基产品攀登上收益率的高峰，譬如表现最好的货基产品7天年化收益率达7.51%，达到6%的比比皆是。当时1-3个月的理财产品平均收益率仅在5.54%。最近余额宝已经跌至5.0480%、微信理财通则是5.0270%，仅钱大掌柜仍能保持在5.776%。
”’
两篇内容不想关的文档相似度测试结果如下：
|
