hamming-lsh

为汉明空间的特征包生成局部敏感哈希（LHS）

这允许您为特征包生成相对平衡的局部敏感哈希（LSH）哈希。这还可以将单个汉明特征减少到较小的汉明空间，但在这样做时，稍微有些不平衡，尤其是在对较小的输入汉明空间（输入比特数）进行操作时。

工作原理

这是通过使用 hamming-dict 在汉明空间中创建尽可能分散的码字来实现的。

当对输入密钥进行哈希处理时，密钥与所有码字进行比较。对于每个小于或等于输入密钥汉明空间位数的半个密钥的码字，输出哈希中相应位置设置位为 1，否则为 0。这样做的原因是因为输入汉明空间的半个比特封装了大约一半的空间，尽管这并不完美，会封装稍微多于一半的空间。由于这种不完美，它不会生成完美的平衡哈希。然而，由于它相当接近中位数，输出哈希是有用的，并且其维度已减少。

当对包（特征集）进行哈希处理时，它会对每个特征执行上述相同的过程。然后它计算在阈值半径内（输入密钥汉明空间位数的半个）的特征的数量。然后应用一个修正因子。修正因子通过减去遇到的 1 数量来纠正每个比特比 0 更频繁出现的情况。这样做的原因是因为，如果没有这种纠正，添加到最终哈希中的项目越多，哈希值就越不具区分性，因为所有的位都倾向于 1。通过执行这种纠正，我们实际上增加了从特征中保留的信息量，使其接近最大值（每个输出比特保留 1 比特）随着包中特征数量的增加。

致谢

此算法灵感来源于这篇博客文章（由Google创建），其中核心概念也应用于汉明空间的降维，并被应用于此处创建此crate。