simHash 文档指纹去重算法
1.simHash算法过程：
参考论文来源 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理，为了便于理解尽量不使用数学公式，分为这几步(标准做法)：
-
1、分词，把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别（1~5）。比如：“ 美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人 ” ==> 分词后为 “ 美国（4） 51区（5） 雇员（3） 称（1） 内部（2） 有（1） 9架（3） 飞碟（5） 曾（1） 看见（3） 灰色（4） 外星人（5）”，括号里是代表单词在整个句子里重要程度，数字越大越重要。
-
2、hash，通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。
-
3、加权，通过 2步骤的hash生成结果，需要按照单词的权重形成加权数字串，比如“美国”的hash值为“100101”，通过加权计算为“4 -4 -4 4 -4 4”；“51区”的hash值为“101011”，通过加权计算为 “ 5 -5 5 -5 5 5”。
-
4、合并，把上面各个单词算出来的序列值累加，变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”，“51区”的 “ 5 -5 5 -5 5 5”， 把每一位进行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。
-
5、降维，把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串，形成我们最终的simhash签名。 如果每一位大于0 记为 1，小于0 记为 0。最后算出结果为：“1 0 1 0 1 1”。
完整的算指纹的算法：
- 按照网上资料或者书本上常见的做法，权重为词频
// 传入分词与词频
public long simHash(Map<String, Integer> tokenWeightMap) {
int[] bits = new int[64];
tokenWeightMap.forEach((token, weight) -> {
long v = MurmurHash.hash64(token);
for (int c = 0; c < 64; c++) {
bits[c] += (v & (1l << c)) == 0 ? -weight : weight;
}
});
long simHash = 0;
for (int c = 0; c < 64; c++) {
long t = ((bits[c] >= 0) ? 1 : 0);
t <<= c;
simHash |= t;
}
return simHash;
}
按照这种市面上的通用做法，传入的map 可以是无序的
- nlp-cn 的做法
nlp-cn 默认采用murmur64的hash算法
private static final int BYTE_LEN = 64;
private static final long[] BITS = new long[BYTE_LEN];
static {
BITS[0] = 1;
for (int i = 1; i < BITS.length; i++) {
BITS[i] = BITS[i - 1] * 2;
}
}
public long fingerprint(String content) {
int[] values = new int[BYTE_LEN];
for (String word : analysis(content)) {
long hashCode = hash(word);
for (int i = 0; i < BYTE_LEN; i++) {
if ((hashCode & BITS[i]) != 0) {
values[BYTE_LEN - 1 - i]++;
} else {
values[BYTE_LEN - 1 - i]--;
}
}
}
long result = 0;
for (int i = 0; i < BYTE_LEN; i++) {
if (values[i] > 0) {
result = result | BITS[BYTE_LEN - 1 - i];
}
}
return result;
}
有一个小问题提请注意
直接用 1<<n 得到 2 的n 次方到31次方以上就会超出int 的取值范围，
运算时直接用 (long)1<<n 或者 1l << n 就行了
所以 nlp-cn 的算法可以简化如下：
public long fingerprint(String content) {
int[] values = new int[64];
for (String word : analysis(content)) {
long hashCode = MurmurHash.hash64(word);
for (int i = 0; i < 64; i++) {
if ((hashCode & 1l << i) != 0) {
values[64 - 1 - i]++;
} else {
values[64 - 1 - i]--;
}
}
}
long simHash = 0;
for (int i = 0; i < 64; i++) {
if (values[i] > 0) {
simHash = simHash | (1l << (64 - 1 - i));
}
}
return simHash;
}
- 比较海明距离
public int hmDistance(long a, long b) {
return Long.bitCount(a ^ b);
}
两种方式的比较：
2.simHash 算法去重时时间复杂度问题:
2.1 分桶
这里先引入一个概念： 抽屉原理
桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。
假设我们要寻找海明距离3以内的数值，根据抽屉原理，只要我们将整个64位的二进制串划分为4块，无论如何，匹配的两个simhash code之间至少有一块区域是完全相同的，如下图所示：
不同的比特位至多分布在三个区域
由于我们无法事先得知完全相同的是哪一块区域，因此我们必须采用存储多份table的方式。在本例的情况下，我们需要存储4份table，并将64位的simhash code等分成4份；对于每一个输入的code，我们通过精确匹配的方式，查找前16位相同的记录作为候选记录，如下图所示：
分桶哈希
让我们来总结一下上述算法的实质：
假定我们最大判重海明距离为MAX_HD
1、将64位的二进制串等分成MAX_HD+1块
2、PUT操作：调整上述64位二进制，将任意一块作为前16位，总共有MAX_HD+1种组合，生成MAX_HD+1份table
3、GET操作：采用精确匹配的方式在MAX_HD+1份table中查找前16位，若找不到，说明不重复，做PUT操作；若找到了，则对剩余链做海明距离计算。
4、如果样本库中存有2^34 （差不多10亿）的哈希指纹，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本
为何要分桶？
两个字符串通过SimHash码和海明距离比较好判断是否相似，假设计算海明距离的时间为基本操作时间。如果有海量的数据，一一比较计算的次数为 1 + 2 + 3 + ......+ n ，时间复杂度为 O(n^2) 级别。这样的时间复杂度肯定是不能接受的。
2.1 索引
构建索引
List<Long>[] lists = new List[2048];
将SimHashCode添加到索引
public void addHashCode(long hash) {
int[] indexs = makeCodeIndex(hash);
for (int i = 0; i < indexs.length; i++) {
int idx = indexs[i];
if (lists[idx] == null) {
lists[idx] = new ArrayList<Long>();
}
lists[idx].add(hash);
}
}
private int[] makeCodeIndex(long hashCode) {
return new int[]{
(int) (hashCode & (BITS[8] - 1)),
(int) ((hashCode >>> 8) & (BITS[8] - 1) + 256),
(int) ((hashCode >>> 16) & (BITS[8] - 1) + 512),
(int) ((hashCode >>> 24) & (BITS[8] - 1) + 768),
(int) ((hashCode >>> 32) & (BITS[8] - 1) + 1024),
(int) ((hashCode >>> 40) & (BITS[8] - 1) + 1280),
(int) ((hashCode >>> 48) & (BITS[8] - 1) + 1536),
(int) ((hashCode >>> 56) & (BITS[8] - 1) + 1792)};
}
查询与索引库中比较的最近的海明距离
public int nearest(long hashCode) {
int[] indexs = makeCodeIndex(hashCode);
int hmDistance = 64;
for (int i = 0; i < indexs.length; i++) {
List<Long> list = lists[indexs[i]];
if (list != null) {
for (Long hc : list) {
hmDistance = Math.min(hmDistance(hashCode, hc), hmDistance);
}
if (hmDistance == 0) {
return hmDistance;
}
}
}
return hmDistance;
}
其中 bit[n] = 2^n ,索引降低比较时算法时间复杂度的方法是
将SimHashCode 比特位分成8段
SimHash分段示意
-
先将第一段与上 2^8 -1 即 0111 1111，得出低七位的值作为第一个索引，将SimHash值放置到索引list中。
-
将SimHash逻辑右移8位,拿低2段的值与上 2^8 -1 即 0111 1111，再补上第八位1，作为第二个索引值,将SimHash值放置到索引list中。
-
以此类推，将SimHash 的分布作为特征建立了八个索引，查询的时候先查索引，再去索引里比较海明距离。
其实这里也是用上了抽屉原理的，各位看官自己思考下吧。
3.simHash 算法去重的基础：分词
分词 -->另写一篇博客说明
需要说明的一点： 分词的时候需要去掉停用词等噪音词，分词是该算法特征抽取的关键一步。
