通过计算Min-Hash比较两个对象
通过计算Min-Hash比较两个对象
提问于 2016-02-15 18:27:21
我需要比较Java/Type-script对象的不同状态。这些对象在执行过程中会发生变化，所以我不能直接比较它们。我需要根据我能够存储的计算出的“哈希值”来比较它们。
通常，Min-Hash算法非常适合解决这类问题。然而，Min-Hash纯粹基于比较字符串集，因此不能比较内容以某种方式“排序”的集，即数字。
让我解释一下我的意思。考虑一个由以下组成的对象
"FirstValue"
"SecondValue"
"42"它被散列到100101010。在不同的时间，相同的对象由
"FirstValue"
"SecondValue"
"41"这将导致散列100010010
现在，通常通过检查汉明距离来比较这些散列。
100101010 XOR
100010010
=========
000111000 --> Hamming Distance = 3这允许根据作为(9-3)/9=0.66的Jaccard index来计算它们的相似度。
但是，我希望看到从42到41的微小更改以某种方式反映在散列中。也就是说，两个状态之间的相似性应该更像0.95。确切的数字并不重要。
在不需要存储大量附加值的情况下，我该如何做呢？
回答 1
Stack Overflow用户
发布于 2016-02-15 21:40:36
我将使用随机位翻转。
常规字符串通过Min-Hash进行哈希处理。由此产生的散列被随机的位翻转所改变。散列的每个位置的位翻转的概率与要比较的整数成正比。
"FirstValue"
"SecondValue"
"42"通过首先对"FirstValue"和"SecondValue"进行散列得到散列，这将导致100101011。
42现在以以下方式合并到散列中：
因为我期望的是介于20和50之间的值，所以42位于该范围的73.3%。，，
- ，每个位置发生位翻转的概率为
但是，我仍然需要摆弄随机数生成器的种子，以使散列具有确定性。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/35406895
复制相关文章
相似问题
腾讯云开发者
