python 中的hash

Hash 直观的来讲就是函数，在数学里的函数是一个空间到另外一个空间的转换，而hash也是一种函数，一种将任意的输入映射成固定长度的输出，是一种压缩映射。这样很容易想到，假如你把任意的输入映射到4位固定长度的输出上，这个函数空间只能容纳16个不同的数值，所以无论固定长度是64位还是128位亦或者更多总会出现这种所谓的“碰撞”（不同的输入导致散列成相同的输出，所以不可能从散列值来唯一的确定输入值），hash 算法很多但基本的思想都相似，然而simhash我忍为却是其中比较特殊的一类，simhash期初是用来网页去重，速度很快。我接触simhash 是在遇到短文本的时候翻看论文看到的（《基于特征迭代的短文本去重算法》），这篇文章是simhash的思想：在原始空间相近的2个点，经过了相同的变换和映射后，在变换空间里，这2个点仍然是相近的，利用这个思想，距离相近的文本可以通过变换到“指纹空间”上仍然是相近。并利用SNN聚类算法（改进）对所有的指纹进行聚类（SNN基本思想：指纹的周围指纹可以用共享近邻来量化，如果2个指纹具有大部分的相同的最近邻指纹，则两个指纹是在同一簇里。）文章中考虑到短文本相近互为近邻，摒弃了传统的SNN中需要设置K值，所以使用相近短文本数来代替最近邻K的个数，避免了设定最近邻K值（人为的设定K的最有很大的局限性和随意性，具体可参考K—means）。定义了最近邻居：设定距离阈值为min_distance ,如果两个短文的Simhash 指纹之间的海明距离小于min_distance ,则认为是相近的，并定义了指纹相似度与密度。simHash在短文处理优势在于可以结合空间向量模型和聚类算法的，每一次的处理就会提高整体方法的精度。利用TFIDF或者其他的算法，给予词向量权重，经过simHash 形成指纹，计算指纹距离，利用共享近邻算法进行聚类或者去重等等！！

simhash

import re from simhash import Simhash def get_features(s): withd=4 s=s.lower() s=re.sub(r'[^\w]+','',s) return [s[i:i+withd] for i in range(max(len(s)-withd+1,1))] Simhash(get_features("how are you ? I am fine,Thanks")).value Simhash("aa").distance(Simhash("bb")) 31 Simhash("aa").distance(Simhash("aa")) 0 dad=Simhash("I love you,dad") mom=Simhash("I love you,mom") mom.value 15601311244373921150L Simhash("12").value 12260945298305541904L hi=Simhash("Hi mom,I love you") hi.distance(mom) 17

python-hashes

from hashes.simhash import simhash hash1 = simhash('This is a test string one.') print hash1 10203485745788768176630988232 hash2 = simhash('This is a test string TWO.') print hash2 10749932022170787621889701832 hash1.similarity(hash2) 0.875

布隆过滤器

from hashes.bloom import bloomfilter hash3=bloomfilter("test") hash3.hashbits,hash3.num_hashes (28756, 7) hash3.add("test string") "test string" in hash3 True "weiyudang" in hash3 False hash4 = simhash('this is yet another test', hashbits=8) hash5 = bloomfilter(capacity=1000000, false_positive_rate=0.0001)

hashlib

import hashlib m=hashlib.md5() m.update('Nobody insepects') m.digest(),m.digest_size,m.block_size,m.name,m.hexdigest() ('\xf5n\x8e\xaaMc\x05m\xcf\x9b\x1bKR\x14\xf8\xf9', 16L, 64L, 'md5', 'f56e8eaa4d63056dcf9b1b4b5214f8f9') hashlib.algorithms ('md5', 'sha1', 'sha224', 'sha256', 'sha384', 'sha512') hashlib.algorithms_available {'DSA', 'DSA-SHA', 'MD4', 'MD5', 'RIPEMD160', 'SHA', 'SHA1', 'SHA224', 'SHA256', 'SHA384', 'SHA512', 'dsaEncryption', 'dsaWithSHA', 'ecdsa-with-SHA1', 'md4', 'md5', 'ripemd160', 'sha', 'sha1', 'sha224', 'sha256', 'sha384', 'sha512', 'whirlpool'} print hashlib.md5('liminghao') <md5 HASH object @ 0000000003717B70> import itertools from pandas import DataFrame str_list=["你是谁 ","我是谁","草拟吗","谁是谁的谁"] str_list=[line.decode('utf-8') for line in str_list] Sims=map(Simhash,str_list) A=[] for x,y in itertools.product(Sims,Sims): A.append(x.distance(y)) A [0, 35, 30, 40, 35, 0, 29, 31, 30, 29, 0, 36, 40, 31, 36, 0]