精华内容
下载资源
问答
  • simhash

    2018-10-24 21:09:00
    公司在文本相似度比较上也有业务场景,以下是对其中核心的算法simHash的一些理解: 1、simHash也可以叫做文本指纹,其是一种局部敏感型的hash算法。 局部敏感的举例: 两个相差只有一个字符的文本串,“你妈妈喊...

    公司在文本相似度比较上也有业务场景,以下是对其中核心的算法simHash的一些理解:

    1、simHash也可以叫做文本指纹,其是一种局部敏感型的hash算法。

    局部敏感的举例:

    两个相差只有一个字符的文本串,“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。

    通过simhash计算结果为:

    1000010010101101111111100000101011010001001111100001001011001011

    1000010010101101011111100000101011010001001111100001101010001011

    通过 hashcode计算为:

    101000001100110100111011011110

    1010010001111111110010110011101

    大家可以看得出来,相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到,这个就是局部敏感哈希的魅力。

     

    2、应用场景一般是对文本大于500+的内容提前指纹做相似度比较,如果文本较短的话,相似度就会有较大的偏差。

     这一点比较好理解的,下面会提到其核心算法是分词后分别计算分词的hash:

        a、如果词数很多,其中某一个词的变更权重相对就小(对结果的影响小)

        b、如果分词很少,比如就2个词,其中一个词的改变(词占的词频较大,权重大),肯定对结果影响很大 

     

    3.simHash的算法概要:

     分词 》分别Hash 》向量加权 》向量合并 》 降维

    下图会有一个清晰的展示过程:

       

    4. 相似度中不能不理解之 汉明距离

    概念:在信息编码中,两个合法代码对应位上编码不同的位数称为码距,又称汗(海)明距离。

    其他参考:https://blog.csdn.net/chouisbo/article/details/54906909

    本质是:a替换为b所需要进行的最小替换次数。

    5. 其他相似性算法介绍:

        a、余弦相似性算法:

      

          非常好的文章,建议阅读:TF-IDF与余弦相似性的应用

                 http://www.ruanyifeng.com/blog/2013/03/tf-idf.html

          http://www.ruanyifeng.com/blog/2013/03/cosine_similarity.html

        b、其它的还有jaccard相似度,欧氏距离,马氏距离,闵可夫斯基距离等,这里不做一一介绍,大家有兴趣可以自行了解。

    6. 真实的业务场景和SimHash应用

    真实的业务场景往往有海量的文本,比如千万级,搜索网站都是亿级别,如果选择余弦相似性,那么其计算过程如下:

    计算输入的文本向量A > 千万级的余弦相似性向量计算。

    若网站qps大,可以想象这个计算压力是大的惊人啊!

    以下介绍Simhash在大文本相似性比较的绝妙想法:

     

     

     

     

     

     

    参考文章:

    http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity.html

    http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity2-html.html

    https://mp.weixin.qq.com/s/NVZ8VoIJEhY6XsngkUNltw

    https://mp.weixin.qq.com/s/G3c-h_29w4AwjqsPpHPuAw

    转载于:https://www.cnblogs.com/do-your-best/p/9846174.html

    展开全文
  • SimHash

    千次阅读 2019-01-10 14:03:24
    算法原理  前面我们讲到,一段文字所包含的信息,就是它的信息熵。如果对这段信息进行无损压缩编码,理论上编码后的最短长度就是它的信息熵大小。如果仅仅是用来做区分,则远不需要...SimHash是一种用来做文本查...

    算法原理
     前面我们讲到,一段文字所包含的信息,就是它的信息熵。如果对这段信息进行无损压缩编码,理论上编码后的最短长度就是它的信息熵大小。如果仅仅是用来做区分,则远不需要那么长的编码,任何一段信息(文字、语音、视频、图片等),都可以被映射(Hash编码)为一个不太长的随机数,作为区别这段信息和其他信息的指纹,只要Hash算法设计得好,任何两段信息的指纹都很难重复。
    SimHash是一种用来做文本查重的常用方法,是Google在2002年发明的一项技术,其特点是,如果两个文本的SimHash值差别越小,这两个网页的相似性就越高。下面我们来看一下它是怎么做到的?



    1.  将一个f维的向量V初始化为0,f位的二进制数S也初始化为0;

    2.  对每一个特征(分词),用传统的hash算法对该特征产生一个f位的二进制签名b;

    3.  对i=1到f,如果b的第i位为1,则该位的值即为该特征的权重值(TF-IDF),如果为0,则为负的权重值;

    4.  将所有特征的权重向量按位相加赋值给V;

    5.  如果V的第i个元素值大于0,则S的第i位为1,否则为0;

    6. 输出S作为最终签名,即SimHash值。

    对两篇文档的SimHash值,计算它们的海明距离(Simhash值之间不同位的个数)。可以有如下高效的实现:



    int hamdistance(uint64_t sim1, uint64_t sim2){
       uint64_t
    xor_val = sim1 ^ sim2;

       int distance =
    0;
       while(xor_val
    > 0){
           xor_val =
    xor_val & (xor_val - 1);
           distance++;
       }
       return
    distance;
    }

    int main(int argc, char *argv[]){
       uint64_t sim1 =
    851459198;
       uint64_t sim2 =
    847263864;
       int dis =
    hamdistance(sim1, sim2);
      
    printf("hamdistance of %lu and %lu is %d", sim1, sim2, dis);
    }


    加密算法(MD5、SHA-1等)也是将不定长的信息变成定长的128位或160位二进制随机数,但是加密算法的一个明显特征是,两段信息哪怕只有微小的不同,最终结果也会截然不同。 SimHash的最大特点就是它的局部敏感性。
    1.  
    因为SimHash算法最终是将权重值相加,而加法满足交换律,所以对词的顺序不敏感;
    2.  
    如果两篇文章只有少数权重小的词不相同,几乎可以肯定它的SimHash值也会相同。 SimHash去重非常高效:一是指纹的计算可以离线进行,而是海明距离的计算也非常高效(直接异或,还可以使用Hash分桶原理,假如我们认为海明距离在3以内的具有很高的相似性,我们可以将simhash值分成4段,那么至少有一段完全相等的情况下才能满足海明距离在3以内)。
    通过大量测试,simhash用于比较大文本,比如500字以上效果都还蛮好,距离小于3的基本都是相似,误判率也比较低。但是如果我们处理的是微博信息,最多也就140个字,使用simhash的效果并不那么理想,我们测试短文本很多看起来相似的距离确实为10,如果使用距离为3,短文本大量重复信息不会被过滤,如果使用距离为10,长文本的错误率也非常高。


    社群

    QQ交流群



    微信交流群




    微信公众号







    了解更富哦干货文章,可以关注小程序八斗问答




     

    展开全文
  • simHash

    2015-09-25 10:35:21
    simhash讲得很透彻,而且应用时候,怎么建索引的方法也有介绍。 原文链接:http://grunt1223.iteye.com/blog/964564 在工作学习中,我往往感叹数学奇迹般的解决一些貌似不可能完成的任务,并且十分希望...

    好文章!simhash讲得很透彻,而且应用时候,怎么建索引的方法也有介绍。

    原文链接:http://grunt1223.iteye.com/blog/964564



    在工作学习中,我往往感叹数学奇迹般的解决一些貌似不可能完成的任务,并且十分希望将这种喜悦分享给大家,就好比说:“老婆,出来看上帝”…… 


    随着信息爆炸时代的来临,互联网上充斥着着大量的近重复信息,有效地识别它们是一个很有意义的课题。例如,对于搜索引擎的爬虫系统来说,收录重复的网页是毫无意义的,只会造成存储和计算资源的浪费;同时,展示重复的信息对于用户来说也并不是最好的体验。造成网页近重复的可能原因主要包括: 
    • 镜像网站
    • 内容复制
    • 嵌入广告
    • 计数改变
    • 少量修改


    一个简化的爬虫系统架构如下图所示: 




    事实上,传统比较两个文本相似性的方法,大多是将文本分词之后,转化为特征向量距离的度量,比如常见的欧氏距离、海明距离或者余弦角度等等。两两比较固然能很好地适应,但这种方法的一个最大的缺点就是,无法将其扩展到海量数据。例如,试想像Google那种收录了数以几十亿互联网信息的大型搜索引擎,每天都会通过爬虫的方式为自己的索引库新增的数百万网页,如果待收录每一条数据都去和网页库里面的每条记录算一下余弦角度,其计算量是相当恐怖的。 

    我们考虑采用为每一个web文档通过hash的方式生成一个指纹(fingerprint)。传统的加密式hash,比如md5,其设计的目的是为了让整个分布尽可能地均匀,输入内容哪怕只有轻微变化,hash就会发生很大地变化。我们理想当中的哈希函数,需要对几乎相同的输入内容,产生相同或者相近的hashcode,换句话说,hashcode的相似程度要能直接反映输入内容的相似程度。很明显,前面所说的md5等传统hash无法满足我们的需求。 

    simhash是locality sensitive hash(局部敏感哈希)的一种,最早由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出。Google就是基于此算法实现网页文件查重的。我们假设有以下三段文本: 

    the cat sat on the matthe cat sat on a matwe all scream for ice cream

    使用传统hash可能会产生如下的结果: 
    引用
    irb(main):006:0> p1 = 'the cat sat on the mat' 
    irb(main):005:0> p2 = 'the cat sat on a mat' 
    irb(main):007:0> p3 = 'we all scream for ice cream' 
    irb(main):007:0> p1.hash 
    => 415542861 
    irb(main):007:0> p2.hash 
    => 668720516 
    irb(main):007:0> p3.hash 
    => 767429688


    使用simhash会应该产生类似如下的结果: 
    引用
    irb(main):003:0> p1.simhash 
    => 851459198 
    00110010110000000011110001111110 

    irb(main):004:0> p2.simhash 
    => 847263864 
    00110010100000000011100001111000 

    irb(main):002:0> p3.simhash 
    => 984968088 
    00111010101101010110101110011000


    海明距离的定义,为两个二进制串中不同位的数量。上述三个文本的simhash结果,其两两之间的海明距离为(p1,p2)=4,(p1,p3)=16以及(p2,p3)=12。事实上,这正好符合文本之间的相似度,p1和p2间的相似度要远大于与p3的。 

    如何实现这种hash算法呢?以上述三个文本为例,整个过程可以分为以下六步: 
    1、选择simhash的位数,请综合考虑存储成本以及数据集的大小,比如说32位 
    2、将simhash的各位初始化为0 
    3、提取原始文本中的特征,一般采用各种分词的方式。比如对于"the cat sat on the mat",采用两两分词的方式得到如下结果:{"th", "he", "e ", " c", "ca", "at", "t ", " s", "sa", " o", "on", "n ", " t", " m", "ma"} 
    4、使用传统的32位hash函数计算各个word的hashcode,比如:"th".hash = -502157718 
    ,"he".hash = -369049682,…… 
    5、对各word的hashcode的每一位,如果该位为1,则simhash相应位的值加1;否则减1 
    6、对最后得到的32位的simhash,如果该位大于1,则设为1;否则设为0 

    整个过程可以参考下图: 



    按照Charikar在论文中阐述的,64位simhash,海明距离在3以内的文本都可以认为是近重复文本。当然,具体数值需要结合具体业务以及经验值来确定。 
      
    使用上述方法产生的simhash可以用来比较两个文本之间的相似度。问题是,如何将其扩展到海量数据的近重复检测中去呢?譬如说对于64位的待查询文本的simhash code来说,如何在海量的样本库(>1M)中查询与其海明距离在3以内的记录呢?下面在引入simhash的索引结构之前,先提供两种常规的思路。第一种是方案是查找待查询文本的64位simhash code的所有3位以内变化的组合,大约需要四万多次的查询,参考下图: 



    另一种方案是预生成库中所有样本simhash code的3位变化以内的组合,大约需要占据4万多倍的原始空间,参考下图: 



    显然,上述两种方法,或者时间复杂度,或者空间复杂度,其一无法满足实际的需求。我们需要一种方法,其时间复杂度优于前者,空间复杂度优于后者。 

    假设我们要寻找海明距离3以内的数值,根据抽屉原理,只要我们将整个64位的二进制串划分为4块,无论如何,匹配的两个simhash code之间至少有一块区域是完全相同的,如下图所示: 



    由于我们无法事先得知完全相同的是哪一块区域,因此我们必须采用存储多份table的方式。在本例的情况下,我们需要存储4份table,并将64位的simhash code等分成4份;对于每一个输入的code,我们通过精确匹配的方式,查找前16位相同的记录作为候选记录,如下图所示: 



    让我们来总结一下上述算法的实质: 
    1、将64位的二进制串等分成四块 
    2、调整上述64位二进制,将任意一块作为前16位,总共有四种组合,生成四份table 
    3、采用精确匹配的方式查找前16位 
    4、如果样本库中存有2^34(差不多10亿)的哈希指纹,则每个table返回2^(34-16)=262144个候选结果,大大减少了海明距离的计算成本 

    我们可以将这种方法拓展成多种配置,不过,请记住,table的数量与每个table返回的结果呈此消彼长的关系,也就是说,时间效率与空间效率不可兼得,参看下图: 



    事实上,这就是Google每天所做的,用来识别获取的网页是否与它庞大的、数以十亿计的网页库是否重复。另外,simhash还可以用于信息聚类、文件压缩等。 

    也许,读到这里,你已经感受到数学的魅力了。
    展开全文
  • Simhash

    2018-08-20 20:36:01
    (特征,权重) => (hash,权重) => 加权 => 合并 => 降维 特征,权重:TF-IDF 海明距离

    (特征,权重) => (hash,权重) => 加权 => 合并 => 降维

    特征,权重:TF-IDF

    海明距离

    展开全文
  • simhash算法库simhash.zip

    2019-07-16 05:31:17
    专门针对中文文档的simhash算法库 简介 此项目用来对中文文档计算出对应的 simhash 值。 simhash 是谷歌用来进行文本去重的算法,现在广泛应用在文本处理中。 详见SimhashBlog 特性 使用 CppJieba 作为分词器和...
  • simhash源码

    2017-01-12 12:22:04
    simhash源码
  • simhash, Simhash算法的python 实现 simhash这是 Simhash的python 实现。正在启动http://leons.im/posts/a-python-implementation-of-simhash-algorithm/插件生成状态
  • 文本去重simhash

    2017-03-25 14:57:16
    simhash
  • add simhash

    2021-01-12 12:21:46
    I add the LSH search based on signature of simhash, during the implementation, I found that there are a lot of repeated code and we cannot reuse some code already has been implemented. I think we may...
  • Simhash vs Minhash

    2015-07-10 11:23:39
    simhash
  • simhash.zip

    2020-07-16 18:50:21
    simhash 高效的文本相似度去重算法实现 simhash是什么 Google发明的的文本去重算法,适合于大批量文档的相似度计算。 流程介绍 simhash是由 Charikar 在2002年提出来的,为了便于理解尽量不使用数学公式,分为...
  • simhash 算法的 java 实现。特点计算字符串的 simhash通过构建智能索引来计算所有字符串之间的相似性,因此可以处理大数据使用使用输入文件和输出文件运行 Maininputfile 的格式(参见 src / test_in):一个文件每...
  • SimHash源码.docx

    2020-05-27 10:32:46
    SimHash源码.docx

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 846
精华内容 338
关键字:

simhash