如何计算相似字符串的同等散列值？

Question

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

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

是否有计算等的方法散列这些行？

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

Answer 1

哈希的问题在于，在逻辑上，您将碰到2个字符串，这些字符串会因散列为不同值的单个字符而不同。

小证明：

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

我能想到的一些选项：字符串

• 哈希多个部分，并检查这些哈希。可能不会工作得太好，因为单个字符的省略会导致哈希值的显着差异。

• 检查散列的范围。散列是一维的，但字符串相似性不是，因此这可能也不起作用。

总而言之，哈希可能不是要走的路。

Answer 2

这个问题是有点老，但在AT & T.他们采用的技术是让人联想到Nilsimsa散列时类似短信已被视为“异常”号检测到您可能感兴趣的this paper由两名研究人员时间窗口中的时间。

这听起来Locality Sensitive hashing也将与您的问题有关。