《在路上 …》 Locality Sensitive Hash

==================== 全部为转载 ====================

发件人 王盈

simhash 是 Locality Sensitive Hash 的一种。
Locality Sensitive Hash 缩写 LSH
http://old.nabble.com/Locality-Sensitive-Hashing-td21471609.html
http://hi.baidu.com/hxk622/blog/item/f978491384f2c0cba7ef3fb6.html

下面是一种Locality Sensitive Hash算法。
http://ixazon.dynip.com/~cmeclax/nilsimsa.html

nilsimsa 的 python版本。
http://pypi.python.org/pypi/nilsimsa/0.1

LSH-python。
http://bitbucket.org/knzm/lsh-python/src

http://bitbucket.org/knzm/lsh-python/src
http://matpalm.com/resemblance/simhash/

=======================================
nilsimsa

kanji le nilsimsa sucta be lo notci gi'e karbi le sucta gi'e tolcri lo smigunma mu'i lonu fespu'i lo se maldustisna
computes nilsimsa codes of messages and compares the codes and finds clusters of similar messages so as to trash spam
What's a nilsimsa code?

A nilsimsa code is something like a hash, but unlike hashes, a small change in the message results in a small change in the nilsimsa code. Such a function is called a locality-sensitive hash. For example, here's a spam I got:
Dear Sir / Madam,
         It is a great honour to have the chance to introduce our company(Guangdong
Kestar Electronic Co.Ltd.) and our main products.
     Guangdong Kestar Electronic Co.Ltd. is located in Guangdong province mainland
China.It is a professional manufcturer on Varistors ,equipped with a complete
set of advanced machinery,possessed high abilities of development & exploitation.We
have 10 years experience in managing large size production.
     Our main seven series varistors are WYG current varistor, MYL lihtningproof
varistor,MYE high load varistor,MYA minitype varistor,MYP squareness varistor,MYR
highly reliable&varistor,low-pressure power supply lightning arrester.. The
Varistors conform to ISO9002 .The products have passed several international
authentication.
      if you are interested in our products, please contact us without hesitate.

yours truely Lin Cang.

Guangdong Kestar Electronic Co.Ltd
Here's the same spam with spacing and spelling cleaned up:
Dear Sir / Madam,
     It is a great honour to have the chance to introduce our company (Guangdong
Kestar Electronic Co. Ltd.) and our main products.
     Guangdong Kestar Electronic Co.Ltd. is located in Guangdong province, mainland
China. It is a professional manufacturer of varistors, equipped with a complete
set of advanced machinery, possessing high abilities of development & exploitation. We
have 10 years experience in managing large size production.
     Our main seven series varistors are WYG current varistor, MYL lightningproof
varistor, MYE high load varistor, MYA minitype varistor, MYP squareness varistor, MYR
highly reliable varistor, low-pressure power supply lightning arrester. The
Varistors conform to ISO9002. The products have passed several international
authentications.
      if you are interested in our products, please contact us without hesitation.

yours truly, Lin Cang.

Guangdong Kestar Electronic Co. Ltd
The nilsimsa codes of the two messages are:
773e2df0a02a319ec34a0b71d54029111da90838cbc20ecd3d2d4e18c25a3025 spam1
47182cf0802a11dec24a3b75d5042d310ca90838c9d20ecc3d610e98560a3645 spam2
The nilsimsa of these two codes is 92 on a scale of -128 to +128. That means that 36 bits are different and 220 bits the same. Any nilsimsa over 24 (which is 3 sigma) indicates that the two messages are probably not independently generated.

=======================================
nilsimsa的大概算法

1. 有一个5个字节的window,沿着文本向右滑动，每次滑动一个字节
2. 每一个window里面的5个字节，分别可以N个组成3元组。 例如igram，可以分为：igr iga igm iga igm gra grm gam ram
3. 每一个三元组通过一个hash函数，算出来一个结果，设为i ,i的区间是(0,256)， 最下面有一个数组，也是共256位，刚好对应存放。  例如igr，假设算出来是15，那么在数组的15那个位置累加1
4. 计算完全部文本，这时数组的每个位置都有一个累加值
5. 通过计算累加值的平均值得到一个阈值，然后数组的每个位分别与该阈值比较，如果大于平均值则为1，小于平均值则为0. 
6. 最后就得到一个256位长度的值，就用来表征这个文本。

=======================================
最早接触simhash是从07年google的论文“detecting near-duplicates for web
crawling”中知道的，这篇论文的重要之处，是给出了一种解决方案，解决从海量文本中快速搜索和已知simhash相差小于k位的simhash集合，这里每个文本都可以用一个simhash值来代表，一个simhash有64bit，相似的文本，64bit也相似，论文中k的经验值为3。该方法的缺点如优点一样明显，主要有两点，对于短文本，k值很敏感；另一个是由于算法是以空间换时间，系统内存吃不消。

simhash值的计算参见http://burtleburtle.net/bob/hash/doobs.html，但具体此算法的数学原理，我是无能为力的。

对于短文本，另一个思路是，将短文本抽象出有序关键字，计算此有序字串的simhash值，寻找simhash相等的集合，在这个缩小的范围里，可以利用COS计算相似度。

在学习过程中，有另外两个算法引起了我的注意，一个是并查集(http://en.wikipedia.org/wiki/Union-Find)，另一个是
bloom filter。前者一般用于海量文本聚类，后者一般用于网页查重，看着要比google的方法省空间多了。

=======================================
利用simhash来进行文本去重复 收藏
原文http://d3s.mff.cuni.cz/~holub/sw/shash/#a1

传统的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 represented by its hash value; 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
           print (t)
           for i in range(self.hashbits):
               bitmask = 1 << i
               print(t,bitmask, t & bitmask)
               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
#整个文档的fingerprint为最终各个位大于等于0的位的和
       return fingerprint

   def _string_hash(self, v):
       # A variable-length version of Python's builtin hash
       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 = '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.97584098811 percent similar
14 bits differ out of 128

=======================================


Simhash算法

Charikar的simhash算法对检测数万亿的存储级别的相似网页是非常实用的。作为指纹技术的simhash具有相似文档的指纹代写论文
只存在很小位数的不同特性。在detecting near-duplicates for
webcrawling一文中验证了,对于8B的网页,64位的指纹和k=3是合适的。Simhash是一种降维技术,可以将高维向量映射为位数较小的指纹。它在网页中的应用过程如下:首先将文档转化为特征码的集合,每个特征码附有一个权值。特征码的生成采用IR技术,比如分词、大小写转换、停止词去除。一个附有权值的特征码的集合构成一个高维向量,通过simhash可以将这个高维向量转化为f位的指纹,f的值很小,比如64[3]。

给出一个从文档中提取的带有权值的特征码集合,通过simhash生成f位指纹的过程如下:首先生成一个f维的向量V,每一维都初始化为0。将每个特征码哈希为f位的哈希值。这些f位的哈希值可以将V的f个元素增加或减少它所对应的权值大小的值。过程如下:如果哈希值的第i位对应的值是1,就将V的第i个元素增加它所对应的权值大小的值;如果哈希值的第i位为0,就将V的第i个元素减去它对应的权值大小的值。当所有的特征码都这样处理完,V中有的元素为正,有的
为负。这些元素的符号决定了最终指纹的相应位数上的值[4~5]。

那给出一个刚抓取的网页的64位的指纹,如何快速发现有哪些指纹和它最多相差3位呢?假设有8B的64位的指纹,我们要在微秒级的时间里判断其中是否有和要查询的指纹F最多有3位不同,首先探讨两种简单但并不切合实际的方法。第一种,为所有存储的指纹建立一张排序表,给定要查询的指纹F,检索该表查找和F的海明距离最大是K的指纹F′。因要检索的次数太大而不切合实际,如果是64位的指纹,K的值为3,那么需要C(64,3)=41664次。另一个改进的方法是预先计算出和所有F′的海明距离最大是K的指纹。这种方法的预先计算量也因太大而不切实际:是表中指纹数的41664倍之多。

设想一个2d由f位随机指纹组成的排序表,其中最高的d位几乎相当于一个计数器,因为对很少有这d位重复的,另一方面,低f-d位几乎是随机的。

选择一个d′,使得|d′-d|的值很小,因为表是有序的,一次检测就能够找出所有和F′在最高的d′位相同的指纹,因为|d′-d|的值很小,所有符合要求的指纹数目也比较小,对于其中的每一个符合要求的指纹,我们可以轻易的判断出它是否和F最多有K位不同(这些不同很自然的限定在低f-d′位)。上面介绍的方法帮我们定位和F有K位不同的指纹,多有不同的位被限定在低
f-d′位中。这对大部分情况来说是合适的,为了覆盖所有的情况,需要建立一小部分附加的表。

我们建t个表:T1,T2,……Tt。每一个表都有两个相关的量:一个整数pi和一个f位指纹上的排列πi。Ti是对每一个指纹应用排列πi后形成的有序表。给定一个指纹F和整数值K,我们并行的检索这些表:

第一步:找出Ti中所有排列后最高Pi位是和πi(F)的最高Pi位相同的指纹。第二步:对所有第一步中查找出的排列后的指纹,
查看它是否和πi(F)最多有K位不同。举例如下:假设f=64,k=3,那么近似网页的指纹最多有3位不同。假设我们有8B=234的已有指纹,即
d=34。我们有不同的设计,每种设计有不同的排列集和PI值。

20个表:把64位分成6块,分别是11,11,11,11,10和10
位。共有C(6,3)=20种方法从6块中选择3块。对于每种选择,排列π使得选出的块中的位成为最高位(有几种这样的排列,我们统一的随机选择其中一种)。Pi的值就是选出的块中的位数的总和。因此Pi=31,32,或者33。平均每次检测返回最多234~31个排列后的指纹。16个表:把64位分成
4块,每块有16位,共有C(4,1)=4种方法从4块中选择一块,对于每种选择,我们把这48位再分割成4块,每块有12位。共有C(4,1)=4种选择方法。对表的排列使得选出的块中的位成为最高位。Pi的值是28。平均每次检测返回最多234-28个排列后的指纹。

订阅到Google 分享到 豆瓣 Buzz Twitter 人人 新浪

文章同步自 http://kanrss.com/~onway/t/61
同步程序见 这里
作者 张沈鹏