最小哈希
Template:TA 在计算机科学领域，最小哈希（或最小哈希式独立排列Template:Tsl）方法是一种快速判断两个集合是否相似的技术。这种方法是由Template:Harvs,[1]发明的，最初在AltaVista搜索引擎中用于在搜索结果中检测并消除重复Web页面。[2]
它同样也应用于大规模聚类问题，比如通过文档间包含的词语相似性进行聚类。[1]
雅可比相似度与最小哈希值
雅可比相似度系数通常用来表示两个集合的相似度，定义Template:Math 是一个集合，Template:Math 和 Template:Math 是 Template:Math的子集。雅可比相似度定义如下：[3]
它是一个0到1之间的数值上，当其为0时表示两个集合不相交，当其为1时表示两个集合相等，其他的情况则在0和1之间。它广泛地用于两集合间相似性的判断：当雅可比系数趋向于1时，两个集合更相似；反之，当雅可比系数趋向于0时，两个集合更不相似。
定义h是一个将Template:Math中的元素映射到一些不相交整数的哈希函数，Template:Math 是集合 Template:Math中元素的排列排列，对于任意集合S，定义Template:Math为S集合中具有最小h(x)函数值的元素x，对应Template:Math（集合Template:Math的元素Template:Math是Template:Math的最小值）。将Template:Math应用于 集合Template:Math 和 Template:Math，假定没有发生哈希碰撞。有Template:Math，当且仅当最小哈希值的并集Template:Math依赖于交集Template:Math时。 因此，
也就是说，Template:Math是真的概率等于Template:Math 另一方面来说，如果Template:Math是一个当Template:Math时值为1，其它情况下值为0的随机变量，那么Template:Math可认为是Template:Math的无偏估计。尽管Template:Math的方差很高时，不能很好的估计雅可比相似度，因为总是0或1。最小哈希思想通过以相同方式构造的几个变量，将其平均在一起来减少这种方差
算法
多哈希函数的变种
最简单的最小哈希方法是使用Template:Math个不同的哈希函数，其中Template:Math是固定的整数参数，使用这Template:Math个函数所对应的Template:Math个Template:Math值来描述每个集合Template:Math。 使用这种最简单的版本来判断Template:Math，假定y是使得Template:Math的哈希函数个数，使用Template:Math作为估计。则此估计是Template:Math个不同的0-1随机变量的平均值，其中每个随机变量当Template:Math值为1，反之为0，并且是Template:Math的无偏估计。因此，该平均值同样也是一个无偏估计，而且通过0-1随机变量之和的标准Template:Tsl可得知，其期望误差是Template:Math。所以，针对任意给定的常数Template:Math，存在另一常数Template:Math，其估计的期望误差不超过Template:Math。例如，使用400个哈希函数值来估计Template:Math，其期望误差将小于或等于.05。
单一哈希函数的变种
计算多个哈希函数的代价是相当昂贵的，因此有关最小哈希方法的另一种实现方法是仅使用单一的哈希函数来避免这个问题。对于每个集合，使用这个单一的哈希函数选出其中的多个值，而不是每个哈希函数选择一个值。假定Template:Math是一个哈希函数，Template:Math是一个固定整数。如果Template:Math是Template:Math域上Template:Math或更多元素的集合，则定义Template:Math为Template:Math中具有最小Template:Math值的Template:Math个元素所组成的子集。该子集Template:Math可用作集合Template:Math的一个签名，任意两个集合间的相似度可通过比较它们的签名来计算。
特别地，假定A and B为任意两个集合，Template:Math是Template:Math的k个元素的集合，如果h是随机变量并且k个元素的任意子集等可能地被选择。也就是说，Template:Math是Template:Math的Template:Tsl。Template:Math是集合Template:Math中属于Template:Math交集的元素。因此，|Template:Math|/Template:Math是Template:Math的无偏估计。单一哈希函数的估计与多个哈希函数产生的估计的不同在于Template:Math总是有Template:Math个元素，而多个哈希函数由于两个不同的哈希函数可能会产生相同的最小值，因此可能会产生更少的样本元素。然而，当Template:Math相对集合大小来说很小时，该区别可忽略不计。
通过不重复取样的标准Template:Tsl，该估计的期望误差为Template:Math，其性能与多个哈希函数方法相匹配。
耗时分析
|Template:Math|/Template:Math估计通过给定集合的两个签名能够在Template:Math能够计算出来，因此，当Template:Math and Template:Math为常数时，从签名中计算相似度估计的时间也为常数，这样当众多两两相似度需要计算时，该方法在运行时间上与每个集合中元素的完全比较相比，能够有实质性的优化。
最小哈希式独立排列
为了实现上述的最小哈希方法，哈希函数Template:Math需要定义Template:Math元素上的一个随机排列，这里的Template:Math是指待比较的所有集合并集中不相交元素的总数。 但是由于存在Template:Math个不同的排列，仅仅指定一个真正随机的排列就需要Template:Math位，即使Template:Math一般时，这个数值也很大。基于这样的事实，与Template:Tsl相类似的理论，有大量的研究工作寻找“最小哈希式独立的”一簇排列，意指针对域的任意子集，任何元素都与其最小值是等可能的。已经证明，最小哈希式独立的排列簇至少必须包含:个不同的排列，因此它需要Template:Math位来指定一个排列，这个数值仍然很大。[2]
由于实践上不可行，引入了最小哈希式独立的两个变型概念：严格最小哈希式独立排列簇和近似最小哈希式独立排列簇。 严格的最小哈希式独立是指最小哈希式独立属性被限制在集合基数至多为Template:Math的一些集合中。[4] 近似最小哈希式独立最多有一个固定的概率Template:Math变化为完全独立。[5]
应用
最小哈希的最初应用包括在Web文档中聚类并消除近似重复，这通过在那些文档中出现的词语集合来描述。[1][2] 相似的技术也应用于其他类型数据的聚类和近似重复消除，如图片：在图片数据中，一张图片可以通过分割用很多更小的子图片集合或更多复杂图片特征的描述集合来表示。[6]
Template:Harvtxt使用最小哈希技术作为数字文档剽窃检测方法的一部分，他们的方法将文档表示成给定长度的子串集合，将文档划分成更大固定长度的窗口，然后使用子串的最小哈希值作为每个窗口的描述值。如果文本的拷贝部分比两倍窗口尺寸还要长，则该描述值将肯定匹配保存在数据库中众多描述值中的一个，这样那个窗口就可以用来检查有多少内容是拷贝的。[7]
在数据挖掘领域，Template:Harvtxt使用最小哈希技术作为关联规则学习的工具。给定一个数据库，其中每一项都有多个属性（可看作是每行为一个数据库项， 每列为一个属性的0-1矩阵），他们将最小哈希的近似度方法应用于Jaccard系数，用来辨别频繁共同出现的属性候选对，然后仅计算这些候选对的确切系数值，以确定哪些项目共同出现的频度低于一个给定的严格阈值。[8]
相关主题
最小哈希方法可看作是Template:Tsl的一个实例。局部性敏感哈希是使用哈希将大集合的数据对象映射到更小的哈希值的技术集合，通过这样的方法当两个对象距离相近时，它们的哈希值也可以相同。在最小哈希方法实例中，一个集合的签名可看作是它的哈希值。其它局部性敏感哈希技术还有针对集合间的海明距离，以及向量间的余弦距离等。另外，局部性敏感哈希还在最近邻搜索算法有着重要的应用。[9]