Leveinshtein 和哈希 - 找到一种导致相关性的哈希算法（更近的距离）

Question

我正在寻找一种哈希类算法，它不提供任何安全性，而是为字符串提供固定且不同的模式，这样可以使用 Leveinshtein 距离计算或任何距离来关联接近相似的字符串公制。

假设我有两个字符串 "hello/friend/my?" 和 "hello/friend/my"，我在 python:

中计算不带和带散列的距离 (Levenshtein)

>>> import Levenshtein as lev
>>> Str1 = "hello/friend/my?"
>>> Str2 = "hello/friend/my"
>>> Distance = lev.distance(Str1.lower(),Str2.lower()),
>>> print(Distance)
>>> Ratio = lev.ratio(Str1.lower(),Str2.lower())
>>> print(Ratio)

(1,)

0.967741935483871

>>> Str1hash = hash(Str1)
>>> Str2hash = hash(Str2)
>>> Distance = lev.distance(str(Str1hash), str(Str2hash)),
>>> print(Distance)
>>> Ratio = lev.ratio(str(Str1hash), str(Str2hash))
>>> print(Ratio)

(16,)

0.41025641025641024

你可以看到没有散列生成的值显示更近的距离 (1) 而有散列的距离太远 (16)。

我想找到一种散列函数或算法，returns 相似字符串之间的距离和比率更近。有什么线索吗？

Answer 1

哈希函数按照定义应该把相似的对象尽量放在一起，所以你要找的东西不存在。您可以尝试使用某种简单的字符替换编码，例如 ROT13，这可能是您问题的答案，但请不要将其称为 hashing =)

https://en.wikipedia.org/wiki/ROT13

Answer 2

我想要的解决方案是LSH：https://en.wikipedia.org/wiki/Locality-sensitive_hashing

它解决了我提出的问题。这是信息检索中用于查找重复文档或网页的技术。因此我可以使用它来比较我的两个字符串并获得它们的相似性指数。

Leveinshtein 和哈希 - 找到一种导致相关性的哈希算法（更近的距离）

Leveinshtein and hash - finding one hash algorithm that results in correlation (closer distance)

python

algorithm

hash

checksum