字符串相似度得分/哈希

Question

有没有一种方法来计算字符串的一般"相似性得分"？在某种程度上,我不是将两个字符串比较在一起,而是为每个字符串得到一些数字(哈希),以后可以告诉我两个字符串是否相似.两个相似的字符串应该具有相似(近似)的哈希值.

让我们将这些字符串和分数视为一个例子:

Hello world                1000
Hello world!               1010
Hello earth                1125
Foo bar                    3250
FooBarbar                  3750
Foo Bar!                   3300
Foo world!                 2350

你可以看到Hello world!和Hello世界是相似的,他们的分数彼此接近.

这样,通过从其他分数中减去给定的字符串分数然后对其绝对值进行排序,可以找到与给定字符串最相似的字符串.

Answer 1

我相信你所寻找的东西被称为地方敏感哈希.尽管大多数散列算法的设计使输入的微小变化导致输出的大变化,但这些散列尝试相反:输入的微小变化会产生相应的输出变化.

正如其他人所提到的,将多维映射强制转换为二维映射存在固有问题.它类似于创建地球的平面地图......你永远无法准确地在平面上表示球体.你能做的最好就是找到一个LSH,它针对你用来确定字符串是否"相似"的任何特性进行了优化.

Answer 2

Levenstein距离或其衍生物是您想要的算法.将给定字符串与字典中的每个字符串匹配.(这里,如果你只需要固定数量的最相似的字符串,你可能想要使用min-heap.)如果为字典中的所有字符串运行Levenstein距离太昂贵,那么首先使用一些粗略的算法来排除太远的单词候选人名单.在那之后,在左候选人身上运行levenstein距离.

删除远程单词的一种方法是索引n-gram.通过将每个单词拆分为n-gram列表来预处理字典.例如,考虑n = 3:

(0) "Hello world" -> ["Hel", "ell", "llo", "lo ", "o w", " wo", "wor", "orl", "rld"]
(1) "FooBarbar" -> ["Foo", "ooB", "oBa", "Bar", "arb", "rba", "bar"]
(2) "Foo world!" -> ["Foo", "oo ", "o w", " wo", "wor", "orl", "rld", "ld!"]

接下来,创建n-gramms的索引:

" wo" -> [0, 2]
"Bar" -> [1]
"Foo" -> [1, 2]
"Hel" -> [0]
"arb" -> [1]
"bar" -> [1]
"ell" -> [0]
"ld!" -> [2]
"llo" -> [0]
"lo " -> [0]
"o w" -> [0, 2]
"oBa" -> [1]
"oo " -> [2]
"ooB" -> [1]
"orl" -> [0, 2]
"rba" -> [1]
"rld" -> [0, 2]
"wor" -> [0, 2]

当您需要为给定的字符串找到大多数相似的字符串时,您将给定的字符串拆分为n-gram,并仅从字典中选择至少具有一个匹配的n-gram的字.这会将候选人数量减少到合理数量,并且您可以对每个左候选人进行levenstein匹配给定字符串.

如果你的字符串足够长,你可以通过使用min-hashing technnique减少索引大小:你计算每个n-gram的普通哈希值,并且只使用K个最小的哈希值,其他的则被丢弃.

PS 这个演示文稿似乎是对你的问题的一个很好的介绍.

Answer 3

通常,这是不可能的,因为字符串之间的编辑距离集形成度量空间,而不是具有固定维度的度量空间.这意味着您无法在字符串和整数之间提供映射,以保留它们之间的距离度量.

例如,您无法为这三个短语指定数字:

• 一二
• 一六
• 二六

这样的数字反映了所有三个短语之间的差异.

Answer 4

编辑距离对您有用吗？