第8课:海量文本数据相似度计算之局部敏感哈希

对于搜索引擎收录来说,判断数据是否重复很重要,道理很简单,我们不能收录很多近似的数据,没有多大价值
当然了,还有很多其他场景,需要进行文件近似度的比较计算

那么问题来了,我们怎么高效的来做比对呢?什么样才算相似

我感觉局部敏感哈希就是为了解决这个问题的而生的
其中最风行的算法是simhash

他的原理分为下面几步:
1.分词
2.计算hash值
3.对分词进行加权,每个词的权重可根据项目灵活调整
4.合并
5.降维

通俗点说,就是想把文本分词,提取关键字,计算hash值,然后根据文本来源对词进行加权计算,算好之后合并产生一个hash字符串
不同文本的比较变成了hash字符串的比较

有的人可能就问了,你这个hash如何做到局部敏感的,怎么感觉和求文本md5 sha1 sha256值之类没啥区别呢?
关键就在于分词与加权合并

我们来举个例子说明:
两个相差只有一个字符的文本串,"你妈妈喊你回家吃饭哦,回家罗回家罗" 和 "你妈妈叫你回家吃饭啦,回家罗回家罗"。

通过simhash计算结果为:

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为:

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到

如何计算两个simhash的相似度呢?因为最终我们是要解决文本相似问题的,难道是比较两个simhash的01有多少个不同吗?对的,其实就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。对于二进制字符串的a和b,海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。

为了高效比较,我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code,然后和内存里的simhash code 进行比较