1

我需要比较 Java/Type-script 对象的不同状态。这些对象在执行过程中会发生变化，所以我无法直接比较它们。我需要根据我能够存储的计算出的“哈希值”来比较它们。

通常，Min-Hash算法非常适合这类问题。但是，Min-Hash 纯粹基于比较字符串集，因此无法比较内容以某种方式“有序”的集合，即数字。

让我解释一下我的意思。考虑一个由以下组成的对象

 "FirstValue"
 "SecondValue"
 "42"

被散列到100101010. 在不同的时间，同一对象由

 "FirstValue"
 "SecondValue"
 "41"

这导致哈希100010010

现在通常通过检查汉明距离来比较这些哈希值。

 100101010 XOR
 100010010 
 =========
 000111000 --> Hamming Distance = 3

这允许根据Jaccard 指数计算它们的相似性 (9-3)/9=0.66。

但是，我希望看到从 到 的细微变化42以41某种方式反映在哈希中。即两个状态之间的相似度应该更像0.95。确切的数字无关紧要。

在不需要存储大量附加值的情况下，我将如何做到这一点？

4

1 回答 1

0

我将使用随机位翻转。

常规字符串由 Min-Hash 散列。生成的散列由随机位翻转改变。在散列的每个位置发生位翻转的概率与要比较的整数成正比。

"FirstValue"
"SecondValue"
"42"

通过第一次散列进行散列"FirstValue"，"SecondValue"结果为100101011.

现在42通过以下方式合并到哈希中：

  • 正如我所期望的那样，介于20该50范围42内73.3%的值。
  • 然后在每个位置发生位翻转的概率为0.733*weight

但是，我仍然需要摆弄随机数生成器的种子以使哈希具有确定性。

于 2016-02-15T13:40:36.473 回答