hash - 如何计算相似字符串的相等哈希？

Question

我创建了 Antiplagiat。我使用瓦片法。例如，我有以下带状疱疹：

1. 我去电影院
2. 我去电影院1
3. 我去电影院

有没有一种方法可以计算这些行的相等哈希？

我知道 Levenshtein 距离的存在。但是，我不知道我应该取什么源词。也许有比考虑 Levenshtein 距离更好的方法。

Answer 1

散列的问题在于，从逻辑上讲，您将遇到 2 个字符串，它们的不同之处在于散列为不同值的单个字符。

小证明：

考虑所有可能的字符串。
假设所有这些散列到至少 2 个不同的值。
取任意 2 个字符串 A 和 B 散列到不同的值。
您显然可以通过一次更改一个字符来从 A 转到 B。
因此，在某些时候哈希会改变。
因此，此时散列对于单个字符更改将是不同的。

我能想到的一些选择：

• 散列字符串的多个部分并检查每个散列。可能不会很好地工作，因为单个字符遗漏会导致散列值的显着差异。

• 检查一系列哈希值。哈希是一维的，但字符串相似性不是，因此这可能也不起作用。

总而言之，散列可能不是要走的路。

Answer 2

这个问题有点老了，但你可能对AT&T 的两位研究人员的这篇论文感兴趣。他们采用一种让人联想到 Nilsimsa 哈希的技术来检测类似的短信何时在一个时间窗口中出现“异常”次数。

听起来局部敏感散列也与您的问题有关。