algorithm - 以这样一种方式转换两个字符串，使输入字符串之间的距离“反映”在输出字符串之间的距离中？

Question

我有一个很长的用户标识符列表。每次 HTTP 请求附带的标识符可能并不完全相同，因此我使用模糊字符串比较来验证用户身份。出于这个原因，我无法对标识符进行哈希处理，因为我的模糊字符串比较算法不适用于哈希值，因为即使是稍微不同的纯文本在哈希处理时也会产生完全不同的值。现在是否有一些算法algx使得距离（s1，s1'）在某种程度上与距离（algx（s1），algx（s1'））成正比？或者有没有其他方法可以解决这个问题？注意：这种意义上的距离是指将一个文本转换为另一个文本所需的编辑量。

Answer 1

您可以使用Levenshtein distance之类的方法来测量 2 个字符串之间的差异。还有一个同名的PHP 函数。

Answer 2

听起来您正在寻找locality-sensitive hashing。

Answer 3

一种解决方案是对每个字母进行计数并比较计数数组。计数之间的不匹配意味着字符串绝对不相似。