大数据场景下的去重方案（SimHash & 布隆过滤器）

大数据下的去重一般指的都是模糊去重，通常来讲不是真的去比较两个文件或者段文本，而是通过一些简单方式模糊粗略的比较；

一般来讲 如果两个文件或者文本完全相同，那么比较结果一定是相等的，但比较结果相等有极小概率两个文件不相等；

下面介绍两种常用的算法SimHash 和 布隆过滤器

SimHash算法

SimHash算法一般用于网页去重，下面简化为文本去重问题来对算法进行讲解：

对于一段文本，首先通过自然语言处理工具将文本处理成分词，并且标注每个词语的权重；

将每一个词语通过hash算法计算出一个整数，并用二进制的形式表示为一个向量，向量元素就是0和1；修改向量中的元素，将0修改为-1，之后每一个元素乘以这个词语的权重所有词语的向量按位相加对于向量相加结果进行修改，如果结果大于0，则用1表示，结果小于0则用0表示；这样就又得到了一个二进制的表示方式将二进制的表示方式转为对应的整数，作为这个文本的标识（或者成为指纹）算法为什么可以做到近似去重呢，试想两段文本大致相同，但是其中一个可能多了某个不重要的词语，这时候第二步可以约束这个词语加权之后的数值，而第四步仅仅是看正负号，不考虑值本身的大小，综合来讲对最终结果的影响不大，甚至是不影响；

最终比较的时候可以比较两个二进制各个位的异同，比如，如果相同位数占比超过95%则判定为相同；

布隆过滤器

布隆过滤器同样使用hash算法与0、1长向量；

布隆过滤器一般事先设定0、1长向量为m位，初始值均为0；

选择n个独立并且不相同的hash算法，n远远小于m；

对于每一个元素，分别用n个hash算法计算hash值，并且将这n个hash值通过某种方式映射位在向量中的位置，将对应位置元素改为1。

当一个新元素进来时，按照相同的逻辑计算hash值并且对应到向量中的位置，如果这些位置全部为1，则表示已经有重复元素。

码字不易，恳请关注；