局部敏感Hash

标签: hash | 发表时间:2015-11-21 04:05 | 作者:
出处:http://xiaobaoqiu.github.io/

1.LSH简介

之前在项目中做数据聚合去重的逻辑的时候简单看过局部敏感Hash(Locality Sensitive Hashing,简称LSH)这个东东。今天整理一下个人的理解。

LSH可以理解为一种衡量文本相似度的算法,特点是散列前的相似点经过哈希之后,也能够在一定程度上相似,并且具有一定的概率保证。其有坚实的理论依据(98年左右理论就提出来了,99年有第一版实现)并且在高维数据空间中表现优异。简单的价格实验场景:

  1. 近似检测(Near-duplicate detection): 通常运用在网页去重方面。在搜索中往往会遇到内容相似的重复页面,它们中大多是由于网站之间转载造成的。可以对页面计算LSH,通过查找相等或相近的LSH值找到Near-duplicate。
  2. 图像、音频检索: 通常图像、音频文件都比较大,并且比较起来相对麻烦,我们可以事先对其计算LSH,用作信息指纹,这样可以给定一个文件的LSH值,快速找到与其相等或相近的图像和文件。
  3. 聚类: 将LSH值作为样本特征,将相同或相近的LSH值的样本合并在一起作为一个类别。
  4. 指纹匹配: 一个手指指纹通常由一些细节来表征,通过对比较两个手指指纹的细节的相似度就可以确定两个指纹是否相同或相似。

LSH的发展历史可以参考: http://jacoxu.com/?p=496

2.普通Hash

说到Hash,大家都很熟悉,是一种典型的Key-Value结构,最常见的算法莫过于MD5。其设计思想是使Key集合中的任意关键字能够尽可能均匀的变换到Value空间中,不同的Key对应不同的Value。通过建立Hash的方式我们能够得到O(1)的查找时间性能,其中关键在于选取一个hash function(md5就是一致hash function)。

md5这种hash函数通常情况下,Key值只有轻微变化,Value值也会发生很大地变化。比如下面实验中用到的文本,仅仅是邮箱号少了个.,其md5完全不同:

1
2
3
4
5
6
7
8
      xiaobaoqiu@xiaobaoqiu:~/temp/md5$ cat 1.dat 
xiaobaoqiu@qunar.com
xiaobaoqiu@xiaobaoqiu:~/temp/md5$ cat 2.dat 
xiaobaoqiu@qunarcom
xiaobaoqiu@xiaobaoqiu:~/temp/md5$ md5sum 1.dat 
ca201d44a9bb6f8e0ca761cdeb678948  1.dat
xiaobaoqiu@xiaobaoqiu:~/temp/md5$ md5sum 2.dat 
f585aa440eb3b8bbc46f1184e2944fb9  2.dat

原始文本是极其相似的,但是hash之后这种相似性就丢失了。

3.LSH

局部敏感哈希的最大特点就在于保持数据的相似性。需要注意的是这里说的保持数据的相似度不是说保持100%的相似度,而是保持最大可能的相似度。换个角度来看,可以将LSH理解为数据降维的方法。

数据对应的维度越高,信息量也就越大,相反,如果数据进行了降维,那么毫无疑问数据所反映的信息必然会有损失。哈希函数从本质上来看就是一直在扮演数据降维的角色。

LSH的基本思想是:将原始数据空间中的两个相邻数据点通过相同的映射或投影变换后,这两个数据点在新的数据空间中仍然相邻的概率很大,而不相邻的数据点被映射到同一个桶的概率很小。

参考: https://en.wikipedia.org/wiki/Locality-sensitive_hashing http://www.cnblogs.com/maybe2030/p/4953039.html http://blog.csdn.net/weiyuweizhi/article/details/8921973

相关 [hash] 推荐:

一致性hash

- - 互联网 - ITeye博客
一致性hash算法 - consistent hashing. 分类:  算法艺术2010-02-02 09:19 69836人阅读  评论(97)  收藏  举报. 算法 cache object 服务器 存储 c. 一致性 hash 算法( consistent hashing ).

Hash Collision DoS 问题

- mazhechao - 酷壳 - CoolShell.cn
最近,除了国内明文密码的安全事件,还有一个事是比较大的,那就是 Hash Collision DoS (Hash碰撞的拒绝式服务攻击),有恶意的人会通过这个安全弱点会让你的服务器运行巨慢无比. 这个安全弱点利用了各语言的Hash算法的“非随机性”可以制造出N多的value不一样,但是key一样数据,然后让你的Hash表成为一张单向链表,而导致你的整个网站或是程序的运行性能以级数下降(可以很轻松的让你的CPU升到100%).

局部敏感Hash

- - xiaobaoqiu Blog
之前在项目中做数据聚合去重的逻辑的时候简单看过局部敏感Hash(Locality Sensitive Hashing,简称LSH)这个东东. LSH可以理解为一种衡量文本相似度的算法,特点是散列前的相似点经过哈希之后,也能够在一定程度上相似,并且具有一定的概率保证. 其有坚实的理论依据(98年左右理论就提出来了,99年有第一版实现)并且在高维数据空间中表现优异.

Hash算法的使用

- khsing - Glider's home
在对语料文本进行2,3元切分时,需要借助hash表来获得切分内容在内存中的位置,以便能够记录语料库中出现的次数. 以前知道有很多hash算法,但没认真研究过,今天才知道hash算法差距还是很明显的. 首先我选择的是暴雪在魔兽里的hash算法,这个算法很高级,是time33类型的一个变种(有关time33的介绍,可以参考:http://www.cnblogs.com/napoleon_liu/articles/1911571.html),而且很巧妙的借助3次hash避免字符串比较这种费时的操作,并且不用链表来存储冲突,3次hash冲突值能相等的可能行只有1/10的23次方,应该说不可能冲突了.

Min-Hash和推荐系统

- - xlvector - Recommender System
前几年看Google News Recommendation的那篇Paper,对里面提到的MinHash的算法基本没有注意,因为之前的习惯都是只注意论文的模型那块,至于怎么优化模型一般都只是扫一眼. 不过最近看了大量的Google Paper,发现Google在实现一个算法方面确实有很多独到之处. 其实,Min-Hash是LSH(Locality Sensitive Hash)的一种,我之前对LSH的了解仅仅限于知道它能把两个相似的东西Hash成两个汉明距离接近的2进制数.

一致性HASH算法

- - 企业架构 - ITeye博客
一致性 hash 算法( consistent hashing ). consistent hashing 算法早在 1997 年就在论文 . Consistent hashing and random trees 中被提出,目前在cache 系统中应用越来越广泛;. 比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ;.

[翻译]最简单的无锁hash table

- - 博客园_首页
原文链接: http://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table. 无锁hash table可以提高多线程下的性能表现,但是因为实现一个无锁hash table本身的复杂度不小(ps:真正的复杂在于出错之后的调试,因为多线程下的调试本身就很复杂,引入无锁数据结构之后,传统的看堆栈信息和打印log都基本上没有意义了(堆栈中的数据可能被并发访问破坏,而打印log本身可能会改变程序执行时对数据访问的时序).

一致性Hash算法背景(转)

- - 开源软件 - ITeye博客
一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似. 一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用.   但现在一致性hash算法在分布式系统中也得到了广泛应用,研究过memcached缓存数据库的人都知道,memcached服务器端本身不提供分布式cache的一致性,而是由客户端来提供,具体在计算一致性hash时采用如下步骤:.

mysql 索引优化 btree hash rtree

- - 数据库 - ITeye博客
mysql里目前只支持4种索引分别是:b-tree,full-text,hash以及r-tree索引. b-tree索引应该是mysql里最广泛的索引的了,除了archive,基本所有的存储引擎都支持它. 1.b-tree在myisam里的形式和innodb稍有不同. 在innodb里面有两种形态:其一是primary key形态其leafnode里存放的是数据.而且不仅存放了索引键的数据,还存放了其他字段的数据.其二是secondary index,其leafnode和普通的b-tree差不多,只是还存放了指向主键的信息.

一致性hash算法测试

- - Java - 编程语言 - ITeye博客
package com.xll; //服务器对象 public class Server {. private void init() { // 初始化一致性hash环. for (int i = 0; i != servers.size(); ++i) { // 每个真实机器节点都需要关联虚拟节点.