在Redis位图文章中,曾说过利用位图做登录统计,今天就来看下是如何实现统计功能的, JDK中又是如何设计实现的....先说明下统计要求: 统计一个数字其二进制表达式中数字位数为1(或者说非0) 的个数. 这种统计也叫汉明重量(Hamming weight). 1....优化后的与运算 为了解决负数的问题,需要对上述方式做些调整. 待统计的数字n保持不变, 将与其进行位操作的flag进行左移操作, 再进行比较统计....JDK实现的位统计 在JDK中的Integer类中也有位统计的具体实现. public static int bitCount(int i) { // HD, Figure 5-2 i = i...每8位一组,统计1的个数 操作过程与上述步骤类似,每2个相邻的4位一组数据相加,并排除高位干扰.
为了表征原始文本的相似度，可以计算两个01串之间在多少个位置上不同，这便是汉明距离，用来表征simHash算法下两个文本之间的相似度，通常来说，越相似的文本，对应simHash映射得到的01串之间的汉明距离越小...通常来说，用于相似文本检测中的汉明距离判断标准就是3，也就是说，当两个文本对应的simHash之间的汉明距离小于或等于3，则认为这两个文本为相似，如果是要去重的话，就只能留下其中一个。...那就变成汉明距离为4了）。...但是在短文本场景下，这种度量方法的效果将会变得很差，通常情况下，用来度量长文本相似的汉明距离阈值为3，但是短文本中，相似文本之间的汉明距离通常是大于3的，并且该算法中，基于汉明距离的相似性阈值选取的越高...，该算法的时间复杂度也会越高，此时汉明距离无法继续作为短文本相似性的度量标准应用到短文本去重中。
因此海量文本中查重的任务转换位如何在海量simhash中快速确定是否存在汉明距离小的指纹。也就是：在n个f-bit的指纹中，查询汉明距离小于k的指纹。...在文章的实验中，simhash采用64位的哈希函数。在80亿网页规模下汉明距离=3刚好合适。...因此在一次完整的查找中，限定前q位精确匹配（假设这些指纹已经是q位有序的，可以采用二分查找，如果指纹量非常大，且分布均匀，甚至可以采用内插搜索），之后的2d-q个指纹剩下64-q位需要比较汉明距离小于3...同样的假设，其次我们按B的16位精确匹配到另一个区间，这个区间的所有指纹需要在ACD位上比较汉明距离是否小于3。 ...例如：将64位平分成4份ABCD，每份16位，在BCD的48位上，我们再分成4份，WXZY，每份12位， 汉明距离的3位可以散落在任意三块，那么A与WXZY任意一份合起来做精确的28位…剩下3份用来检查汉明距离
对图像数据库中的图像逐一进行特征提取，并将其以图像文件名和图像特征一一对应的方式添加到特征库中； (2) 哈希编码。...3) 汉明距离排序。...在汉明距离排序阶段，对于给定的查询图像，逐一计算查询图像对应的哈希编码到其他各个哈希编码之间的汉明距离，然后按从小到大的顺序进行相似性排序，从而得到检索结果； (4) 重排。...针对步骤(3)汉明排序后的结果，可以前M个结果或者对汉明距离小于某一设置的汉明距离d 的结果进行重排。一般地，在重排的时候采用欧式距离作为相似性度量得到重排后的结果。...在采用哈希方法进行大规模图像检索的应用系统中，通常会有重排这一步，但是在设计哈希算法的时候，对性能进行指标评价直接采用的是汉明距离，也就是在评价哈希算法性能的时候，不需要重排这一步。
对GPSM生成能力更直接的测试是比较生成序列与数据集MSA的统计特性。本文测试了三个标准度量：成对协方差相关性，汉明距离分布和统计能量相关性。...对于每个GPSM，作者使用皮尔逊相关系数ρ({},{})(图2)将它们各自评估MSA中所有位置和残基对的成对协方差分数与目标MSA中相应的目标对进行比较。...由于该方法是根据使用频率最高的20个单词的皮尔逊相关性计算出来的，因此作者将它命名为。 图3 r20测试结果 如图所示，在二阶模型中，所有方法表现相近。...汉明距离分布 两个蛋白质序列之间的汉明距离表示它们之间不同的氨基酸的数量，作者通过比较所有序列对得到一个MSA的分布。对每个GPSM方法，观察其成对汉明距离分布，与目标概率分布进行比较。...图4 汉明距离测试结果 图4表明Indep在汉明距离度量上的表现，比在其他三个度量上都更接近Mi3和VAE，并且汉明距离度量不能很好地区分Mi3和VAE，作者认为对于GPMS，再现汉明距离分布比再现高阶协变更容易
汉明距离： 假如一组二进制数据为101，另外一组为111，那么显然把第一组的第二位数据0改成1就可以变成第二组数据111，所以两组数据的汉明距离就为1。...简单点说，汉明距离就是一组二进制数据变成另一组数据所需的步骤数，显然，这个数值可以衡量两张图片的差异，汉明距离越小，则代表相似度越高。汉明距离为0，即代表两张图片完全一样。...平均哈希算法（aHash）： 该算法是基于比较灰度图每个像素与平均值来实现。...最后比对两张图片的指纹，获得汉明距离即可。...结果显示img1和img2的相似度高一些，和计算hash值的汉明距离得到的结果是相一致的。
浮点型向量计算方式内积（IP）欧式（L2）余弦（Cosine）二值型向量计算方式汉明距离 (Hamming)杰卡德距离 (Jaccard)谷本距离 (Tanimoto)介绍距离计算之前，简单了解一下向量归一化公式...2.4 汉明距离汉明距离计算二进制字符串之间的距离。两个等长字符串之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。比如，假设有两条字符串 1101 1001 和 1001 1101。...比较时，如果字符相同用 0 表示，如果字符不同则用 1 表示。11011001 ⊕ 10011101 = 01000100所以以上两条字符串之间的汉明距离为 2。...（b）如果此时S中不足k个点，则将当前结点加入到S中；如果S中已有k个点，且当前结点与p点的距离小于S中最长距离，则用当前结点替换S中距离最远的点。（c）计算p点和当前结点切分线的距离。...LSH定义：将这样的一族hash函数 H={h:S→U} 称为是(r1,r2,p1,p2)敏感的，如果对于任意H中的函数h，满足以下2个条件：如果d(O1,O2)r1，那么Pr[h(O1)=h(O2)
之前写关于R语言实现的博客： R语言实现︱局部敏感哈希算法（LSH）解决文本机械相似性的问题（一，基本原理） R语言实现︱局部敏感哈希算法（LSH）解决文本机械相似性的问题（二，textreuse.... 2、感知哈希算法(pHash) 节选自： 图像检索︱图像的相似性搜索与图像向量化、哈希化（文献、方法描述） 平均哈希算法过于严格，不够精确，更适合搜索缩略图，为了获得更精确的结果可以选择感知哈希算法...最后比对两张图片的指纹，获得汉明距离即可。 这等同于”汉明距离”(Hamming distance,在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数)。...得到哈希值之后，需要求距离，这里较多使用海明距离（来源）。 这等同于”汉明距离”(Hamming distance,在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数)。...我们如果插入一条数据就要去比较1000w次的simhash，计算量还是蛮大，普通PC 比较1000w次海明距离需要 300ms ，和5000w数据比较需要1.8 s。
皮尔森相关系数(Pearson Correlation Coefficient)： 即相关分析中的相关系数r，分别对X和Y基于自身总体标准化后计算空间向量的余弦夹角。公式如下： ?...如果比较X与Y的Jaccard相似系数，只比较xn和yn中相同的个数，公式如下： ?...哈明距离（汉明距离） 汉明距离是使用在数据传输差错控制编码里面的，汉明距离是一个概念，它表示两个（相同长度）字对应位不同的数量，我们以d（x,y）表示两个字x,y之间的汉明距离。...对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离。 比如： 1011101 与 1001001 之间的汉明距离是 2。...2143896 与 2233796 之间的汉明距离是 3。 "toned" 与 "roses" 之间的汉明距离是 3。 这种方法往往可以进行一定的模板匹配，计算与模板的接近程度。
图2 余弦相似度 5 欧式距离和余弦相似度 通过三维坐标系可以很直观的看到两者的区别，如图3所示： ?...文本转换为SimHash后，我们通过海明距离（Hamming distance）计算两个SimHash是否相似。 如果向量空间中的元素a和b之间的汉明距离等于它们汉明重量的差a-b。...汉明重量分析在包括信息论、编码理论、密码学等领域都有应用。 8 降维比较 Google的论文给出的数据中，64位的签名，在汉明距离为3的情况下， 可认为两篇文档是相似。...给定场景：给出一个64位的SimHash集合F和一个SimHash f，找出F中是否存在与f只有3位差异的SimHash 为了查询相似，我们依然需要两两比较。但汉明距离算法给了我们降维的捷径。...，计算最终汉明距离 9 SimHash的利弊 优点： 速度快，效率高。
a.jpg和c.jpg的汉明距离是8； a.jpg和d.jpg的汉明距离是7。 说明在这3张图片中，d.jpg和a.jpg最相似。 大致算法就是这样，汉明距离的代码我没给出，这个比较简单。...90度)的汉明距离是13；1.jpg和3.jpg(旋转5度)的汉明距离是5。...(汉明距离是两个字符串对应位置对比，总共不同的个数) 很明显，旋转了90度汉明距离变得很大。在dHash算法中，它们是不同的。而我们肉眼可以看出其实是一样的。前面说过dHash算法比较较真、比较敏感。...16进制，得到哈希值 = '73610000ffff1c00' Python代码如下： 用这个算法计算2.jpg和3.jpg的哈希值和与1.jpg对比的汉明距离分别是： 2.jpg：7ffc0000ffffe000...，汉明距离是5 3.jpg：7fff0000fffff800，汉明距离是5 很明显，pHash算法得到的汉明距离更加符合我们的要求。
Infi-chu: http://www.cnblogs.com/Infi-chu/ 以图搜图的使用已经非常广泛了，我现在来介绍一下简单的以图搜图的相关算法及其实践。...2.求两个字符串之间的相似度（汉明距离），字符串越相似，即图片越相似。 二、汉明距离 汉明距离： 汉明距离是两个字符串对应位置的不同字符的个数。...换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。 例如： 1011101 与 1001001 之间的汉明距离是 2。 2143896 与 2233796 之间的汉明距离是 3。...“toned” 与 “roses” 之间的汉明距离是 3。 三、均值hash 下面的例子是使用了像素平均值，又叫均值哈希。 优点：均值哈希较为简单。...5.求汉明距离 import numpy as np import cv2 def p_hash(path): # Step1.
适用： 单工链路、 对实时性要求比较高的应用。 3. 反馈校验 接收端： 将收到的数据原封不动发回发送端。 发送端： 通过对比接收端反馈的数据与发送的数据确认接收端是否正确接收的已发送数据。...差错编码的检错与纠错能力 1. 编码集的汉明距离 汉明距离： 两个等长码字之间， 对应位数不同的位数。 ? 编码集的汉明距离： 编码集中任意两个码字之间汉明距离的最小值。 ?...检错编码：编码集的汉明距离 ds=r+1， 则该检错编码可以检测 r 位的差错。 ? 纠错编码：编码集的汉明距离 ds=2r+1， 则该差错编码可以纠正 r 位的差错。 ? 纠错示例： ? 4....奇校验码 1位冗余位， 取值为 “0” 或 “1” ， 使得编码后的码字中1的个数为奇数。...写出多项式对应的位串，位串位数表示为R； 2. 在待编码位串后面添加0，加0的个数为R减1； 3. 用新的待编码位串除以多项式对应的位串； 4.
特征点提取与匹配 经典SLAM模型中以位姿-路标（Landmark）来描述SLAM过程 路标是三维空间中固定不变的点，能够在特定位姿下观测到 数量充足，以实现良好的定位 较好的区分性，以实现数据关联 在视觉...SLAM中，可以利用图像特征点作为SLAM中的路标 特征点：图像当中具有代表性的部分 可重复性 可区别性 高效 本地 特征点的信息： 位置、大小、方向、评分——关键点 特征点周围的图像信息——描述子（Descriptor...BRIEF BRIEF-128:在特征点附近的128次像素比较 ORB 旋转之后的BRIEF描述 BRIEF是一种二进制描述，需要用汉明距离度量 特征匹配 通过描述子的差异判断哪些特征为同一个点 暴力匹配...：比较图1中每个特征和图2特征的距离(汉明距离) 加速：快速最近邻居（FLANN） 特征匹配之后，得到特征点之间的对应关系 如果只有两个单目图像，得到2D-2D的关系——对极几何 如果匹配的是帧和地图，...2D-2D对极几何小结 2D-2D情况下，只知道图像坐标之间的对应关系 当特征点在平面上时，（例如俯视或者仰视），使用H恢复R,t 否则，使用E或F恢复R,t t没有尺度 求得R,t后： 利用三角化计算特征点的
缓解这个弱点有一个方法就是利用Image的crop方法把图片等分，然后再分别计算其相似度，最后综合考虑。 图像指纹与汉明距离 在介绍下面其他判别相似度的方法前，先补充一些概念。...汉明距离为0，即代表两张图片完全一样。...如何计算得到汉明距离，请看下面三种哈希算法 平均哈希法(aHash) 此算法是基于比较灰度图每个像素与平均值来实现的 一般步骤 1.缩放图片，可利用Image对象的resize(size)改变，一般大小为...最后比对两张图片的指纹，获得汉明距离即可。...最后比对两张图片的指纹，获得汉明距离即可。
一、 相似图片检测步骤： 分别计算两张图片的dHash值 通过dHash值计算两张图片的汉明距离（Hamming Distance），通过汉明距离的大小，判断两张图片的相似程度。...汉明距离表示将A修改成为B，需要多少个步骤。比如字符串“abc”与“ab3”，汉明距离为1，因为只需要修改“c”为“3”即可。 dHash中的汉明距离是通过计算差异值的修改位数。...我们的差异值是用0、1表示的，可以看做二进制。二进制0110与1111的汉明距离为2。 我们将两张图片的dHash值转换为二进制difference，并取异或。...计算异或结果的“1”的位数，也就是不相同的位数，这就是汉明距离。...值，而是直接比较两张图片，那么不需要生成dHash值，直接用Step3中的difference数组，统计不相同的位数，就是汉明距离。
二、计算方式 举个例子， 1011101 与 1001001 的 汉明距离 为 2 式1 1 0 1 1 1 0 1 式2 1 0 0 1 0 0 1 只要将 式1 中标红的部分换一下即可。...2143896 与 2233786 的 汉明距离 为 3 式1 2 1 4 3 8 9 6 式2 2 2 3 3 7 9 6 只要将 式1 中标红的部分换一下即可。...helloworld 与 hollowoold 式1 h e l l o w o r l d 式2 h o l l o w o o l d 只要将 式1 中标红的字母换一下即可。...三、汉明重量 汉明重量 就是字符串相对于相同长度的零字符串的汉明距离；也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是 1 的个数，所以 11101 的汉明重量是 4。...因此，如果向量空间中的元素 a 和 b 之间的汉明距离等于它们汉明重量的差 a-b。
由于汉明距离的比较完全可以基于位操作，相比基于数值特征的图像检索，查询速度可以得到数十倍的提升。...具体的查询过程如下，用事先定义好的哈希函数将查询图片映射成48bit的二进制码，与数据库中所有图片的二进制码比较汉明距离，按汉明距离从小到大排序即为本次图像检索的结果。...假设训练数据集拥有K类图片，目标二进制码长为N比特，该方法利用贪婪法生成拥有K个码字的二进制码组，两两之间的汉明距离可以达到最优。...经过训练后的网络不仅在训练集上得到汉明距离大的图像编码，在测试集上的泛化能力也十分出色。 2. 该方法的训练过程是单例(pointwise)损失函数进行的。...这类语义不平衡的情况通常需要用三例损失函数来训练，即一次输入三张图片告知其相似程度的不同。而该方法在理想码组的训练中可以接受语义不平衡系数，使更相近的类之间拥有更近的汉明距离，使得检索更加准确。
特性计算 - 相似性计算 对于两张图像的 pHash 值，具体如何计算其相似的程度？答案是 Hamming distance 汉明距离，汉明距离越小，图像内容越相似。 汉明距离又是什么？...就是对应位置不同比特位的个数。 例如： 第一个值： 0 1 0 1 0 第二个值： 0 0 0 1 1 以上两个值的对应位置上有 2 个比特位是不相同的，因此它们的汉明距离就是 2 。...OK ，相似性计算的原理我们知道了，那么下一个问题是：如何去计算亿级图片对应的亿级数据的汉明距离？简而言之，就是如何搜索？...在项目早期其实我并没有找到一个满意的能够快速计算汉明距离的工具（或者说是计算引擎），因此我的方案进行了一次变通。...变通的思想是：如果两个 pHash 值的汉明距离是接近的，那么将 pHash 值进行切割后，切割后的每一个小部分大概率相等。
主要的三种距离度量是：L2 或欧几里得距离、余弦相似度和内积。其他度量还有可用于二进制向量的汉明距离和杰卡德系数。...这意味着我们在使用倒排文件索引[10]或类似HNSW[11]的图索引时应该小心使用内积。 译注：在倒排文件索引或HNSW（一种图索引方法）这类数据结构中，我们通常希望快速找到与给定查询最相似的项。...汉明距离 hamming 汉明距离可以应用于向量或字符串。对于我们的用例，让我们继续使用向量。汉明距离衡量了两个向量的 条目 之间的“差异”。例如，“1011”和“0111”的汉明距离为 2。...正如你所看到的，两个向量嵌入之间的汉明距离几乎总是等于向量本身的长度。每个值的可能性太多了。这就是为什么汉明距离只能应用于二进制或稀疏向量。...计算杰卡德距离或指数是一项有趣的任务，因为乍一看它并不太有效。与汉明距离一样，杰卡德只适用于二进制数据。我发现传统的“并集”和“交集”形式令人困惑。我用逻辑上的方式理解它。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
云直播
