9015人阅读
传统的hash函数能够将一样的文本生成一样的hash函数，但是，通过simhash方法，能够差不多相同的文档得到的hash函数也比较相近。
Charikar's hash
通过Charikar‘s hash，能够将比较相似度的文档得到比较相近的fingerprint。
该算法的流程如下：
Document is split into tokens (words for example)
or super-tokens (word tuples)
* Each token is represent a traditional
hash function is used
* Weights are associated with tokens
* A vector V of integers is initialized to 0, length of the vector
corresponds to the desired hash size in bits
* In a cycle for all token's hash values (h), vector V is updated:
o ith element is decreased by token's weight if the ith bit of
the hash h is 0, otherwise
o ith element is increased by token's weight if the ith bit of
the hash h is 1
* Finally, signs of elements of V corresponds to the bits of the
final fingerprint
&&& 该hash不是将文档总体计算hash值，而是将文档中的每个token计算哈希值，对文档中每个token的hash值，按照位 对hash值进行求和，如果当前token的hash值在该位上是0，则减去1，如果在该位上是1，则加上1.将所有的token按照这种方式累加，求的最终的值作为fingerprint。
python对应的代码如下：
#!/usr/bin/python
# Implementation of Charikar simhashes in Python
# See: http://dsrg.mff.cuni.cz/~holub/sw/shash/#a1
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
print(t,bitmask, t & bitmask)
if t & bitmask:
v[i] += 1 #查看当前bit位是否为1，是的话则将该位+1
v[i] –= 1 #否则得话，该位减1
fingerprint = 0
for i in range(self.hashbits):
if v[i] &= 0:
fingerprint += 1 && i
#整个文档的fingerprint为最终各个位大于等于0的位的和
return fingerprint
def _string_hash(self, v):
# A variable-length version of Python's builtin hash
if v == &&:
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:
def hamming_distance(self, other_hash):
x = (self.hash ^ other_hash.hash) & ((1 && self.hashbits) - 1)
tot += 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 = 'This is a test string for testing'
hash1 =simhash(s.split())
#print(&0x%x& % hash1)
#print (&%s/t0x%x& % (s, hash1))
s = 'This is a test string for testing also!'
hash2 = simhash(s.split())
#print (&%s/t[simhash = 0x%x]& % (s, hash2))
print (hash1.similarity(hash2), &percent similar&)
print (hash1.hamming_distance(hash2), &bits differ out of&, hash1.hashbits)
上述代码运行的结果如下：
0. percent similar
14 bits differ out of 128
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：351546次
积分：4373
积分：4373
排名：第6800名
原创：85篇
转载：47篇
评论：43条
(1)(1)(2)(4)(7)(1)(4)(3)(7)(1)(5)(7)(8)(12)(5)(8)(17)(15)(20)(4)新手园地& & & 硬件问题Linux系统管理Linux网络问题Linux环境编程Linux桌面系统国产LinuxBSD& & & BSD文档中心AIX& & & 新手入门& & & AIX文档中心& & & 资源下载& & & Power高级应用& & & IBM存储AS400Solaris& & & Solaris文档中心HP-UX& & & HP文档中心SCO UNIX& & & SCO文档中心互操作专区IRIXTru64 UNIXMac OS X门户网站运维集群和高可用服务器应用监控和防护虚拟化技术架构设计行业应用和管理服务器及硬件技术& & & 服务器资源下载云计算& & & 云计算文档中心& & & 云计算业界& & & 云计算资源下载存储备份& & & 存储文档中心& & & 存储业界& & & 存储资源下载& & & Symantec技术交流区安全技术网络技术& & & 网络技术文档中心C/C++& & & GUI编程& & & Functional编程内核源码& & & 内核问题移动开发& & & 移动开发技术资料ShellPerlJava& & & Java文档中心PHP& & & php文档中心Python& & & Python文档中心RubyCPU与编译器嵌入式开发驱动开发Web开发VoIP开发技术MySQL& & & MySQL文档中心SybaseOraclePostgreSQLDB2Informix数据仓库与数据挖掘NoSQL技术IT业界新闻与评论IT职业生涯& & & 猎头招聘IT图书与评论& & & CU技术图书大系& & & Linux书友会二手交易下载共享Linux文档专区IT培训与认证& & & 培训交流& & & 认证培训清茶斋投资理财运动地带快乐数码摄影& & & 摄影器材& & & 摄影比赛专区IT爱车族旅游天下站务交流版主会议室博客SNS站务交流区CU活动专区& & & Power活动专区& & & 拍卖交流区频道交流区
家境小康, 积分 1158, 距离下一级还需 842 积分
论坛徽章:1
我想比较两个字符串的相似度，用到了simhash和hamming distance。网上都是Python和java的例子，我拿来改了改。应该是正确的，但是又没有把握，感觉我的算法和网上的特别是python版本的差距很大。请各位看看。
我的perl版本：#!/bin/perl
sub hash{
my ($input)=@_;
my @chars=split &&,$
my $hash=5381;
foreach(@chars){
&&$hash += ($hash && 5) + ord($_);
}
return $
}
sub simhash{
my @tokens=@_;
my @simhash=();
foreach (@tokens){
my $hash=hash($_);
foreach (0 .. 31){
&&my $current_bit=$hash & 0x1;
&&if ($current_bit == 0){
& &$simhash[$_]--;
&&}else {
& &$simhash[$_]++;
&&}
&&
$hash = $hash &&1;
}
}
my $simhash=0;
@simhash= reverse @
foreach(@simhash){
if ($_ & 0){
$simhash=($simhash && 1)+ 0x1;
$simhash=$simhash && 1;
}
}
return $
}
sub hamming_distance{
my ($ourhash,$otherhash)=@_;
my $x=$ourhash ^ $
printf &ourhash=%x,otherhash=%x,x=%d\n&,$ourhash,$otherhash,$x;
my $tot=0;
while ($x) {
$tot += 1;
$x &=$x -1;
}
return $
}
while (chomp ($_ = &STDIN&)){
my @test=qw (ok are you ready go);
my @test2=split /\s+/, $_;
my $sim1=simhash(@test);
my $sim2=simhash(@test2);
printf &test=%x,test2=%x\n&,$sim1,$sim2;
my $simi=$sim1 & $sim2 ? $sim1 / $sim2 : $sim2 / $sim1;
print $simi . &\n&;
my $hamming=hamming_distance($sim1,$sim2);
print $hamming . &\n&;
#exit(0);
}复制代码下面是网上的python版本：#!/usr/bin/python
# coding=utf-8
class simhash:
& &
& & #构造函数
& & def __init__(self, tokens='', hashbits=128):& && &
& && &&&self.hashbits = hashbits
& && &&&self.hash = self.simhash(tokens);
& &
& & #toString函数& &
& & def __str__(self):
& && &&&return str(self.hash)
& &
& & #生成simhash值& &
& & def simhash(self, tokens):
& && &&&v = [0] * self.hashbits
& && &&&for t in [self._string_hash(x) for x in tokens]: #t为token的普通hash值& && && &
& && && && &for i in range(self.hashbits):
& && && && && & bitmask = 1 && i
& && && && && & if t & bitmask :
& && && && && && &&&v[i] += 1 #查看当前bit位是否为1,是的话将该位+1
& && && && && & else:
& && && && && && &&&v[i] -= 1 #否则的话,该位-1
& && &&&fingerprint = 0
& && &&&for i in range(self.hashbits):
& && && && &if v[i] &= 0:
& && && && && & fingerprint += 1 && i
& && &&&return fingerprint #整个文档的fingerprint为最终各个位&=0的和
& &
& & #求海明距离
& & def hamming_distance(self, other):
& && &&&x = (self.hash ^ other.hash) & ((1 && self.hashbits) - 1)
& && &&&tot = 0;
& && &&&while x :
& && && && &tot += 1
& && && && &x &= x - 1
& && &&&return tot
& &
& & #求相似度
& & def similarity (self, other):
& && &&&a = float(self.hash)
& && &&&b = float(other.hash)
& && &&&if a & b : return b / a
& && &&&else: return a / b
& &
& & #针对source生成hash值& &(一个可变长度版本的Python的内置散列)
& & def _string_hash(self, source):& && &
& && &&&if source == &&:
& && && && &return 0
& && &&&else:
& && && && &x = ord(source[0]) && 7
& && && && &m = 1000003
& && && && &mask = 2 ** self.hashbits - 1
& && && && &for c in source:
& && && && && & x = ((x * m) ^ ord(c)) & mask
& && && && &x ^= len(source)
& && && && &if x == -1:
& && && && && & x = -2
& && && && &return x
& && && && &
if __name__ == '__main__':
& & s = 'This is a test string for testing'
& & hash1 = simhash(s.split())
& &
& & s = 'This is a test string for testing also'
& & hash2 = simhash(s.split())
& &
& & s = 'nai nai ge xiong cao'
& & hash3 = simhash(s.split())
& &
& & print(hash1.hamming_distance(hash2) , && && , hash1.similarity(hash2))
& & print(hash1.hamming_distance(hash3) , && && , hash1.similarity(hash3))复制代码
&&nbsp|&&nbsp&&nbsp|&&nbsp&&nbsp|&&nbsp&&nbsp|&&nbsp
丰衣足食, 积分 611, 距离下一级还需 389 积分
论坛徽章:3
use Text::Levenshtein qw(distance);
print distance(&foo&,&four&);
# prints &2&
my @words& &&&= qw/ four foo bar /;
my @distances = distance(&foo&,@words);
print &@distances&;
# prints &2 0 3&复制代码
大富大贵, 积分 14808, 距离下一级还需 5192 积分
论坛徽章:72170人阅读
作者原创，转载请注明出处。
一直想写个总结来回顾simhash，一直没抽出时间，现在还是好好写写总结一下。作者随笔，废话有点多，不喜勿喷，欢迎指教。
谷歌每天从网上抓取海量的信息，怎么样区分重复的呢，据说就采用了simhash算法，当然肯定也不仅仅就只采用它，不过至少可以说明其性能。
预备知识：
我们知道，在文本去重的时候，有很多方式，在文本与文本之间对比，如果是整篇对比，费时费力，有人就想到用什么东西代表每篇文章，如摘要，当然，对计算机来说，摘要和整篇的区别只是缩小了篇幅，所以又有人想到了采用关键字来对比。这样确实可以大大缩减我们对比的复杂性。那我们怎么得到一篇文章的关键字呢？一般采用词频（TF），但是只用词频，如中文出现类似“的”、“我们”之类的词语很多，应该怎么去掉这些词语呢，手动去掉实在是麻烦，于是可以结合逆向词频（IDF)，这就是著名的TD-IDF，一种提取一个文章的关键词的算法。词频我们很好理解，一个词语在整篇文章中出现的次数与词语总个数之比。IDF又怎么算呢，假如一个词语，在我们所有文章中出现的频率都非常高（例如“的”在我们多个文本中出现的次数很多），我们就认为，这个词语不具有代表性，就可以降低其作用，也就是赋予其较小的权值。
那这个权重，我们怎么计算呢，（这里敲公式比较麻烦，直接找来图片），如下图，分子代表文章总数，分母表示该词语在这些文章（|D|）出现的篇数。一般我们还会采取分母加一的方法，防止分母为0的情况出现，在这个比值之后取对数，就是IDF了。
好了，在得到idf之后，最终用tf*idf得到一个词语的权重。这里我知道了TD-IDF可以计算一篇文章的关键词。在我们取得一篇的文章的关键词，之后，我们可以采取每篇文章对比其关键词的方法来去重。
这里又有一个权衡，假如我们取的关键词过少，就不能很好代表一篇文章，假如我们取很多，又会降低效率。有没有一种方法，既可以很少的对比，又能有好的代表性呢。答案肯定是有的，于是simhash产生了。
（汗，终于讲到正题来了）
simhash是一种局部敏感hash。我们都知道什么是hash。那什么叫局部敏感呢，假定A、B具有一定的相似性，在hash之后，仍然能保持这种相似性，就称之为局部敏感hash。
在上文中，我们得到一个文档的关键词，取得一篇文章关键词集合，又会降低对比效率，我们可以通过hash的方法，把上述得到的关键词集合hash成一串二进制，这样我们直接对比二进制数，看其相似性就可以得到两篇文档的相似性，在查看相似性的时候我们采用海明距离，即在对比二进制的时候，我们看其有多少位不同，就称海明距离为多少。在这里，我是将文章simhash得到一串64位的二进制，一般取海明距离为3作为阈值，即在64位二进制中，只有三位不同，我们就认为两个文档是相似的。当然了，这里可以根据自己的需求来设置阈值。
就这样，我们把一篇文档用一个二进制代表了，也就是把一个文档hash之后得到一串二进制数的算法，称这个hash为simhash。
具体simhash步骤如下：
（1）将文档分词，取一个文章的TF-IDF权重最高的前20个词（feature）和权重（weight）。即一篇文档得到一个长度为20的（feature：weight）的集合。
（2）对其中的词（feature），进行普通的哈希之后得到一个64为的二进制，得到长度为20的（hash : weight）的集合。
（3）根据（2）中得到一串二进制数（hash）中相应位置是1是0，对相应位置取正值weight和负值weight。例如一个词进过（2）得到（）进过步骤（3）之后可以得到列表[-5,5,-5,5,5,5]，即对一个文档，我们可以得到20个长度为64的列表[weight，-weight...weight]。
（4）对（3）中20个列表进行列向累加得到一个列表。如[-5,5,-5,5,5,5]、[-3,-3,-3,3,-3,3]、[1,-1,-1,1,1,1]进行列向累加得到[-7，1，-9，9，3，9]，这样，我们对一个文档得到，一个长度为64的列表。
（5）对（4）中得到的列表中每个值进行判断，当为负值的时候去0，正值取1。例如，[-7，1，-9，9，3，9]得到010111，这样，我们就得到一个文档的simhash值了。
（6）计算相似性。连个simhash取异或，看其中1的个数是否超过3。超过3则判定为不相似，小于等于3则判定为相似。
呼呼呼，终于写完大致的步骤，可参考下图理解步骤。
python实现：
在下面python实现中，用的结巴分词，得到tf-idf的权值。
# -*- coding: utf-8 -*-
import jieba
import jieba.analyse
import numpy as np
import json
class simhash:
def __init__(self,content):
self.simhash=self.simhash(content)
def __str__(self):
return str(self.simhash)
def simhash(self,content):
seg = jieba.cut(content)
jieba.analyse.set_stop_words('stopword.txt')
keyWord = jieba.analyse.extract_tags(
'|'.join(seg), topK=20, withWeight=True, allowPOS=())#在这里对jieba的tfidf.py进行了修改
#将tags = sorted(freq.items(), key=itemgetter(1), reverse=True)修改成tags = sorted(freq.items(), key=itemgetter(1,0), reverse=True)
#即先按照权重排序，再按照词排序
keyList = []
# print(keyWord)
for feature, weight in keyWord:
weight = int(weight * 20)
feature = self.string_hash(feature)
for i in feature:
if(i == '1'):
temp.append(weight)
temp.append(-weight)
# print(temp)
keyList.append(temp)
list1 = np.sum(np.array(keyList), axis=0)
print(list1)
if(keyList==[]): #编码读不出来
return '00'
simhash = ''
for i in list1:
if(i & 0):
simhash = simhash + '1'
simhash = simhash + '0'
return simhash
def string_hash(self,source):
if source == &&:
x = ord(source[0]) && 7
m = 1000003
mask = 2 ** 128 - 1
for c in source:
x = ((x * m) ^ ord(c)) & mask
x ^= len(source)
if x == -1:
x = bin(x).replace('0b', '').zfill(64)[-64:]
print(source,x)
return str(x)
以下是使用系统自带hash生成，虽然每次相同的会生成的一样，
不过，对于不同的汉子产生的二进制，在计算海明码的距离会不一样，
即每次产生的海明距离不一致
所以不建议使用。
# x=str(bin(hash(source)).replace('0b','').replace('-','').zfill(64)[-64:])
# print(source,x,len(x))
# return x
def hammingDis(self,com):
t1 = '0b' + self.simhash
t2 = '0b' + com.simhash
n=int(t1, 2) ^ int(t2, 2)
n &= (n-1)
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3599次
排名：千里之外
原创：17篇
(1)(1)(1)(13)(1)(2)本文讲的是python实现simhash算法实例_python，
Simhash的算法简单的来说就是，从海量文本中快速搜索和已知simhash相差小于k位的simhash集合，这里每个文本都可以用一个simhash值来代表，一个simhash有64bit，相似的文本，64bit也相似，论文中k的经验值为
Simhash的算法简单的来说就是，从海量文本中快速搜索和已知simhash相差小于k位的simhash集合，这里每个文本都可以用一个simhash值来代表，一个simhash有64bit，相似的文本，64bit也相似，论文中k的经验值为3。该方法的缺点如优点一样明显，主要有两点，对于短文本，k值很敏感；另一个是由于算法是以空间换时间，系统内存吃不消。
复制代码 代码如下:
#!/usr/bin/python# coding=utf-8class simhash:
def __init__(self, tokens='', hashbits=128):
self.hashbits = hashbits
self.hash = self.simhash(tokens);
#toString函数
def __str__(self):
return str(self.hash)
#生成simhash值
def simhash(self, tokens):
v = [0] * self.hashbits
for t in [self._string_hash(x) for x in tokens]: #t为token的普通hash值
for i in range(self.hashbits):
bitmask = 1 && i
if t & bitmask :
v[i] += 1 #查看当前bit位是否为1,是的话将该位+1
v[i] -= 1 #否则的话,该位-1
fingerprint = 0
for i in range(self.hashbits):
if v[i] &= 0:
fingerprint += 1 && i
return fingerprint #整个的fingerprint为最终各个位&=0的和
#求海明距离
def hamming_distance(self, other):
x = (self.hash ^ other.hash) & ((1 && self.hashbits) - 1)
x &= x - 1
return tot
def similarity (self, other):
a = float(self.hash)
b = float(other.hash)
if a & b : return b / a
else: return a / b
#针对source生成hash值
(一个可变长度版本的Python的内置散列)
def _string_hash(self, source):
if source == "":
x = ord(source[0]) && 7
m = 1000003
mask = 2 ** self.hashbits - 1
for c in source:
x = ((x * m) ^ ord(c)) & mask
x ^= len(source)
if x == -1:
if __name__ == '__main__':
s = 'This is a test string for testing'
hash1 = simhash(s.split())
s = 'This is a test string for testing also'
hash2 = simhash(s.split())
s = 'nai nai ge xiong cao'
hash3 = simhash(s.split())
print(hash1.hamming_distance(hash2) , "
" , hash1.similarity(hash2))
print(hash1.hamming_distance(hash3) , "
" , hash1.similarity(hash3))
以上是云栖社区小编为您精心准备的的内容，在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索python
simhash算法 python、simhash算法实现、simhash python实现、id3算法实例python、java实现推荐算法实例，以便于您获取更多的相关知识。
弹性可伸缩的计算服务，助您降低 IT 成本，提升运维效率
稳定可靠、可弹性伸缩的在线数据库服务，全球最受欢迎的开源数据库之一
6款热门基础云产品6个月免费体验；2款产品1年体验;1款产品2年体验
开发者常用软件，超百款实用软件一站式提供
云栖社区()为您免费提供相关信息，包括
的信息，还有simhash算法 python、simhash算法实现、simhash python实现、id3算法实例python、java实现推荐算法实例等
，所有相关内容均不代表云栖社区的意见！1 Introduction According to statistics, the duplication of pages on the Internet about 30% to 45%. This image is reproduced which caused because the pages are identical, there are only minor differences existing pages, such as advertising, counters,
通过采集系统我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析.分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法?常见的有余弦夹角算法.欧式距离.Jaccard相似度.最长公共子串.编辑距离等.这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重.最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复.看起来很简单,我们来做个测试,就拿最简单的两个
第一次听说google的simhash算法[1]时,我感到很神奇.传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法.传统hash算法产生的两个签名,如果相等,说明原始内容在一定概率下是相等的:如果不相等,除了说明原始内容不相等外,不再提供任何信息,因为即使原始内容只相差一个字节,所产生的签名也很可能差别极大.从这个意义上来说,要设计一个hash算法,对相似的内容产生的签名也相近,是更为艰难的任务,因为它的签名值除了提供原始内容是否相等的信息外,还能额
这篇文章主要介绍了.NET下文本相似度算法余弦定理和SimHash浅析及应用,实例形式详细讲述了相似度算法余弦定理和SimHash的原理与用法,需要的朋友可以参考下 本文实例讲述了.NET下文本相似度算法余弦定理和SimHash浅析及应用.分享给大家供大家参考.具体分析如下: 余弦相似性 原理:首先我们先把两段文本分词,列出来所有单词,其次我们计算每个词语的词频,最后把词语转换为向量,这样我们就只需要计算两个向量的相似程度. 我们简单表述如下 文本1:我/爱/北京/天安门/ 经过分词求词频得出向
在前一篇文章 &海量数据相似度计算之simhash和海明距离& 介绍了simhash的原理,大家应该感觉到了算法的魅力.但是随着业务的增长 simhash的数据也会暴增,如果一天100w,10天就1000w了.我们如果插入一条数据就要去比较1000w次的simhash,计算量还是蛮大,普通PC 比较1000w次海明距离需要 300ms ,和5000w数据比较需要1.8 s.看起来相似度计算不是很慢,还在秒级别.给大家算一笔账就知道了: 随着业务增长需要一个小时处理100w次,一个小时为3600
这篇文章主要介绍了python实现simhash算法实例,需要的朋友可以参考下 Simhash的算法简单的来说就是,从海量文本中快速搜索和已知simhash相差小于k位的simhash集合,这里每个文本都可以用一个simhash值来代表,一个simhash有64bit,相似的文本,64bit也相似,论文中k的经验值为3.该方法的缺点如优点一样明显,主要有两点,对于短文本,k值很敏感:另一个是由于算法是以空间换时间,系统内存吃不消. #!/usr/bin/python # coding=utf-8
simhash 网站 : /yanyiwu/simhash 专门针对中文文档的simhash算法库 简介 此项目用来对中文文档计算出对应的 simhash 值. simhash 是谷歌用来进行文本去重的算法,现在广泛应用在文本处理中. 详见SimhashBlog 特性 使用 CppJieba 作为分词器和关键词抽取器 使用 jenkins 作为 hash 函数 hpp 风格,所有源码都是 .hpp 文件里面,方便使用. 没有链接,就没有伤害. 依赖 g++ (
说到文本相似性计算,大家首先想到的应该是使用向量空间模型VSM(Vector Space Model).使用VSM计算相似度,先对文本进行分词,然后建立文本向量,把相似度的计算转换成某种特征向量距离的计算,比如余弦角.欧式距离.Jaccard相似系数等.这种方法存在很大一个问题:需要对文本两两进行相似度比较,无法扩展到海量文本的处理.想想像Google这种全网搜索引擎,收录了上百亿的网页,爬虫每天爬取的网页数都是百万千万级别的.为了防止重复收录网页,爬虫需要对网页进行判重处理.如果采用VSM方法
网上疯传巨NB的simhash算法,谁也不知道这个是怎么推导出来,有什么凭据可以以一维的字符串指示俩篇文章的相似程度.怀着对google无比崇拜,在最近的项目中使用过后,却感觉效果很不理想. 项目中选用的是32位,2汉明距离去重.吭哧俩天把这个功能加入后发现,爬下来的网页开始大面积重复,达到95%的重复度. 做simhash最重要的有俩个步骤, 第一是关键字抽取,简单采用了去stopwords,tf.这样的效果很差,估计有各种噪声. 第二是hash算法,我采用jdk里的,据说6000个单词的碰撞
传统的 hash 算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法.产生的两个签名,如果相等,说明原始内容在一定概 率 下是相等的:如果不相等,除了说明原始内容不相等外,不再提供任何信息,因为即使原始内容只相差一个字节,所产生的签名也很可能差别极大.从这个意义 上来 说,要设计一个 hash 算法,对相似的内容产生的签名也相近,是更为艰难的任务,因为它的签名值除了提供原始内容是否相等的信息外,还能额外提供不相等的 原始内容的差异程度的信息. 而 Google 的
基于simhash的海量文章排重的实践 简单介绍 simhash是一种能计算文档相似度的hash算法.通过simhash能将一篇文章映射成64bit,再比较两篇文章的64bit的海明距离,就能知道文章的相似程序.若两篇文章的海明距离&=3,可认为这两篇文章很相近,可认为它们是重复的文章. 这篇博客有详细的介绍 simhash-py 要更准确的对文章进行排重,需要找到好的simhash算法.目前我知道的有python-hashes,simhash-py.两个库通过简单的修改,再加上中文分词库,可以
一.Simhash简介 SimHash是用来网页去重最常用的hash方法,速度很快.Google采用这种算法来解决万亿级别的网页去重任务. SimHash算法的主要思想是降维.将高维的特征向量映射成一个低维的特征向量,通过两个向量的Hamming Distance来确定文章是否重复或者高度近似. 在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明,&量子图灵&得出的证明simhash是由随机超平面hash算法演变而来的. 参考文献:&Dete
All is reproduced ==================== ==================== From Wang Ying simhash is a Locality Sensitive Hash. Locality Sensitive Hash initials LSH /Locality-Sensitive-Hashing-td.html /hxk622/blog/ite
A chart Search Web crawler framework where the major e-commerce site for crawling data, analysis, storage, indexing. Reptile: Reptile responsible for crawling, parsing, processing e-commerce web site content Database: goods information storage Index:
jiebaR 网站 : /qinwf/jiebaR &结巴&中文分词的R语言版本,支持最大概率法(Maximum Probability),隐式马尔科夫模型(Hidden Markov Model),索引模型(QuerySegment),混合模型(MixSegment),共四种分词模式,同时有词性标注,关键词提取,文本Simhash相似度比较等功能.项目使用了Rcpp和CppJieba进行开发. 特性 支持 Windows , Linux操作系统(M
引言 相似度计算用于衡量对象之间的相似程度,在数据挖掘.自然语言处理中是一个基础性计算.其中的关键技术主要是两个部分,对象的特征表示,特征集合之间的相似关系.在信息检索.网页判重.推荐系统等,都涉及到对象之间或者对象和对象集合的相似性的计算.而针对不同的应用场景,受限于数据规模.时空开销等的限制,相似度计算方法的选择又会有所区别和不同.下面章节会针对不同特点的应用,进行一些常用的相似度计算方法进行介绍. 2向量空间模型 向量空间模型(Vector space model)是应用最广泛的一个基础相
山坡网的用户抱怨&为什么搜索'二鬼子李富贵'找不到'二鬼子汉奸李富贵'?我用百度搜都能找到.& 当时我就滴汗了,用户说的有道理,应该要能搜索到. 之前的方案很简单,用户输入的字串会在数据库里做正则表达式匹配,以便用&二鬼子&能搜到&二鬼子汉奸李富贵&.事实证明,我想当然了,即便是这么简单的一个书名搜索,也不能马虎. 那就来分析一下怎么做吧,即便不是专业做搜索的,思路上也可以先YY一下.按照本能,先把问题大而化小. 1. 先把搜索字符串进行中文分词
1.概述 跟SimHash一样,MinHash也是LSH的一种,可以用来快速估算两个集合的相似度.MinHash由Andrei Broder提出,最初用于在搜索引擎中检测重复网页.它也可以应用于大规模聚类问题. 2.Jaccard index 在介绍MinHash之前,我们先介绍下Jaccard index. Jaccard index是用来计算相似性,也就是距离的一种度量标准.假如有集合A.B,那么, 也就是说,集合A,B的Jaccard系数等于A,B中共同拥有的元素数与A,B总共拥有的元素数
2013年计划: 1. 学习 ruby 语言 1.1 学习 ruby 的基本语法 1.2 使用 ruby 写一个小蜘蛛 1.3 使用 rack 1.4 skynet, starfish 1.5 EventMachine: fast, simple event-processing library for Ruby programs 2. 在项目中使用 Jafka Jafka的文档还是比较弱,还是转向Kafka.2013/05 在项目中使用了Kafka 0.7.2版本.disk IO有时挺重的.
R是什么? 记得刚接触R的时候,有一种莫名的抵触,A.B.C.D.E那么多种语言了,为什么又多冒出来一个R?为了时间序列的课程,我又要多记忆一大堆乱七八糟的语法.当发现居然有dd&--&ee 这样的语法时,更瞬间奠定了R语言在我心中的逗比地位. 因为老师没有专门教授R的相关细节,毕竟课程的主题不是那个,加之R的语法与众不同,这导致我的R语言相关作业的绝大部分时间一般都在百度.谷歌各种R语言的表达.实现方法中度过. 记得有位哲人说过:&人并没有真正喜欢吃的东西,只
Copyright (C) , All Rights Reserved.
版权所有 闽ICP备号
processed in 0.044 (s). 9 q(s)