我在之前的博客已大致介绍了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对图片的边缘直方图特征进行建模,获得了不错的效果,可以用于近似图片的查找,效果如下:
- 大小: 90.3 KB
分享到:
相关推荐
Locality-sensitive hashing using stable distributions p稳定局部敏感哈希算法(e2lsh)论文。
A locality-sensitive hash for real vectorsTyler NeylonAbstract We present a simple and practical algorithm for the c−approximate near neighbor problem (c−NN): given n points P ⊂ Rd and radius R, ...
开源项目-glaslos-tlsh.zip,Feature complete golang port of the Trend Micro Locality Sensitive Hash (TLSH) library. Feedback welcome!
than locality sensitive hashing, which is the fastest current method. By using semantic hashing to filter the documents given to TF-IDF, we achieve higher accuracy than applying TF-IDF to the entire...
java笔试题算法 TLSH - Trend Micro Locality Sensitive Hash TLSH 是一个模糊匹配库。 给定一个最小长度为 50 字节的字节流 TLSH 生成一个哈希值,可用于相似性比较。 相似的对象将具有相似的散列值,这允许通过...
局部敏感哈希一个Scala库,用于局部敏感哈希。 当前的实现仅适用于文本,并且仅支持Jaccard相似性。 val lsh = new LSH(shingleLength , min hash Length , number of bands , processedDocuments, threshold)
TLSH(Trend Micro Locality Sensitive Hash)JavaScript端口 TLSH是设计的模糊匹配库(托管在) 给定最小长度为512个字符的字节流(以及最小的随机性),TLSH会生成可用于相似性比较的哈希值。 相似的对象将具有...
For fuzzy search, we will see a variant of a special type of hashing, called locality-sensitive hashing, that uses linear space and how the underlying ideas can be used in the kd-tree data structure ...
关于为计算机视觉学习哈希的调查 关于“学习哈希”领域的文献综述 这是调查文章的存储库:《关于计算机视觉的学习哈希的调查》和相关网站 。 请查看网站,以获取有关调查的更多信息,以及有关向网站贡献您的工作或...
基于哈希的最近邻居搜索已在许多应用程序中变得有吸引力。 但是,在使用汉明距离... 在三个著名基准上进行图像搜索的综合实验表明,与最新方法相比,该方法在单表和多表搜索中可分别实现17.11%和20.28%的性能提升。
用于golang中自然语言处理的选定机器学习算法的实现。 该软件包的主要重点是纯文本文档的统计语义,支持语义分析和语义相似文档的检索。 建立在软件包上,该软件包用于线性代数和科学计算,并从Python的和获得了...