JAVA实现的Locality Sensitive Hash

我在之前的博客已大致介绍了LSH的原理及其的适用场景，有兴趣的朋友可以移步至
http://grunt1223.iteye.com/blog/937600

这里我给出它的具体实现及实验效果：

private int dimention; //维度大小，例如对于sift特征来说就是128
private int max; //所需向量中元素可能的上限，譬如对于RGB来说，就是255
private int hashCount; //哈希表的数量，用于更大程度地削减false positive
//LSH随机选取的采样位数，该值越小，则近似查找能力越大，但相应的false positive也越大；若该值等于size，则为由近似查找退化为精确匹配
private int bitCount; 
private int size; //转化为01字符串之后的位数，等于max乘以dimensions
private int[][] hashFamily; //LSH哈希族，保存了随机采样点的INDEX
VectorComparator comparator; 
// private HashMap<String, ArrayList<IdentifiedVector>> map;
private HashMap<String, ArrayList<String>> map;

public SimpleLSH(int dimention, int max, int hashCount, int bitCount) {
    this.dimention = dimention;
    this.max = max;
    this.hashCount = hashCount;
    this.bitCount = bitCount;
    this.size = this.dimention * this.max;
    this.hashFamily = new int[hashCount][bitCount];
    // map = new HashMap<String, ArrayList<IdentifiedVector>>();
    map = new HashMap<String, ArrayList<String>>();
    this.comparator = new VectorComparator(new int[] { 0 });
}

//生成随机的投影点
private void generataHashFamily() {
    Random rd = new Random();
    for (int i = 0; i < hashCount; i++) {
    for (int j = 0; j < bitCount; j++) {
        hashFamily[i][j] = rd.nextInt(size);
    }
}

//将向量转化为二进制字符串，比如元素的最大范围255，则元素65就被转化为65个1以及190个0
private int[] unAray(int[] data) {
    int unArayData[] = new int[size];
    for (int i = 0; i < data.length; i++) {
        for (int j = 0; j < data[i]; j++) {
	    unArayData[i * max + j] = 1;
        }
    }
    return unArayData;
}

//将向量映射为LSH中的key
private String generateHashKey(int[] list, int hashNum) {
    StringBuilder sb = new StringBuilder();
    int[] tempData = unAray(list);
    int[] hashedData = new int[bitCount];
    //首先将向量转为二进制字符串
    for (int i = 0; i < bitCount; i++) {
        hashedData[i] = tempData[hashFamily[hashNum][i]];
	sb.append(hashedData[i]);
	// System.out.print(hashedData[i]);
    }
    
    //再用常规hash函数比如MD5对key进行压缩
    MessageDigest messageDigest = null;
    try 
    {
        messageDigest = MessageDigest.getInstance("MD5");
    }
    catch (NoSuchAlgorithmException e) {
    }

    byte[] binary = sb.toString().getBytes();
    byte[] hash = messageDigest.digest(binary);
    String hashV = MathUtils.getHexDigest(hash);
    return hashV;
}

//将向量映射为LSH中的key，并保存至map中
private void generateHashMap(String id, int[] vercotr) {
    for (int j = 0; j < hashCount; j++) {
        String key = generateHashKey(vercotr, j);
        ArrayList<String> l;
        if (map.containsKey(key)) {
            l = map.get(key);
        } else {
            l = new ArrayList<String>();
        }
        l.add(id);
        map.put(key, l);
    }
}

// 查询与输入向量最接近（海明空间）的向量
public Set<String> query(int[] data) {
    // Set<IdentifiedVector> result = new HashSet<IdentifiedVector>();
    Set<String> result = new HashSet<String>();
    for (int j = 0; j < hashCount; j++) {
        String key = generateHashKey(data, j);
        if (map.containsKey(key)) {
            result.addAll(map.get(key));
        }
    }
    return result;
}

我利用上面的LSH对图片的边缘直方图特征进行建模，获得了不错的效果，可以用于近似图片的查找，效果如下：

评论

16 楼 夜的那种黑丶 2017-12-13  

博主，请教一个问题，我利用OpenCV3提取得到SIFT特征，是以Mat形式存在的，我要怎么利用将它降维匹配呢，希望博主能够指导一下。

15 楼 夜的那种黑丶 2017-12-10  

最近要用到这方面的内容，楼主贴出的代码少了一些工具类吧，求一份源码，谢谢！
[e-mail]

14 楼 wang_zhao 2017-04-03  

博主您好 ，能否求一份该博文对应源码，在下学生狗一枚，非常感谢！！！！[e-mail]

13 楼 qwertykln 2015-11-24  

博主，能不能发一份完整代码给我啊，我现在正在学习这个，邮箱：[e-mail]  谢谢了。

12 楼 reny0oo 2015-08-17  

soledad1030 写道

[size=x-large][size=large][size=medium]博主，您好，请问是否可以贡献出 MathUtils 和 VectorComparator 这两个类呢？

由于您的代码中也没有注释描述这两类实现的功能，所以我没办法自己编写代码，希望您能把代码发送至我的邮箱：xiao.feng@ia,ac.cn 非常感谢啦[/size][/size][/size]

给我也一份吧，[e-mail]，谢谢博主

11 楼 u010382571 2015-06-04  

u010382571 写道

博主，求发 一份代码给我，学生党毕设急用。。。

邮箱[e-mail]

10 楼 u010382571 2015-06-04  

博主，求发 一份代码给我，学生党毕设急用。。。

9 楼 huiyi1991 2015-05-18  

博主，看到你这有java实现的，很是高兴，同求一份java源码啊，急需学习使用，邮箱：[e-mail] ，十分谢谢！

8 楼 Flyer2015 2015-04-28  

博主，能不能发一份完整代码给我啊，我现在正在学习这个，看了好多资料都是一知半解的，好痛苦，邮箱：[e-mail]  谢谢了。

7 楼 sdrzbruce 2015-02-03  

博主，您好，能否发给我一份完整的代码，十分感谢!我的邮箱[e-mail]  谢了~

6 楼 艮离艮离 2014-08-24  

博主，我一直不太理解LSH的实现，能否请你把完整的代码发到我的邮箱，大恩大德感激不尽啊，对了，我也是杭州的，我请你吃饭啊   邮箱：[e-mail]  万分感谢~

5 楼 objsun 2014-05-07  

博主，既然是多哈希表存储，为什么你代码里只有一个map.而且对于同一个向量，hashcount次映射后的key都是存在一张哈希表里。。这不造成大量重复了吗

4 楼 soledad1030 2014-01-17  

不好意思，我的邮箱是 [e-mail] 上面打错了一个点

3 楼 soledad1030 2014-01-17  

[size=x-large][size=large][size=medium]博主，您好，请问是否可以贡献出 MathUtils 和 VectorComparator 这两个类呢？

由于您的代码中也没有注释描述这两类实现的功能，所以我没办法自己编写代码，希望您能把代码发送至我的邮箱：xiao.feng@ia,ac.cn 非常感谢啦[/size][/size][/size]

2 楼 qweaz2012 2013-12-16  

不知道博主能不能发一份详细代码给我，[e-mail]，最近正好在学习，非常感谢！！！

1 楼 longpo1988 2013-08-06  

您好，能不能给我发一份全的代码，谢谢，邮箱[e-mail],非常感谢！