算法 - 字符串相似度评分/哈希
有没有一种方法可以计算字符串的一般“相似度分数”？也就是说，我不是在比较两个字符串，而是为每个字符串生成一个数字或分数（哈希），这样我就可以知道两个字符串是否相似。两个相似的字符串应该有相似（接近）的分数或哈希。
我们来看几个字符串和它们的分数作为例子：
Hello world 1000
Hello world! 1010
Hello earth 1125
Foo bar 3250
FooBarbar 3750
Foo Bar! 3300
Foo world! 2350
你可以看到“Hello world!”和“Hello world”是相似的，它们的分数也很接近。
这样的话，找到与给定字符串最相似的字符串的方法就是把给定字符串的分数从其他字符串的分数中减去，然后对它们的绝对值进行排序。
我的最终目标是：会有一些流式日志消息（只有纯消息），我想找到这些消息的模式（某种正则表达式类型）。但这只有在我能把相似的字符串归类之后才能开始。我再次强调我需要为每个字符串生成一个数字/分数（哈希），并且这个分数可以告诉我两个字符串是否相似。
8 个回答
简而言之：Python BK-tree
这个问题很有意思。我在这个领域的经验有限，但因为Levenshtein距离满足三角不等式，我想应该有办法计算某种绝对距离，以便找到彼此相近的字符串，而不需要直接比较整个数据库中的所有条目。
在网上搜索相关术语时，我发现了一篇特别有意思的论文：计算中的度量空间的各个方面，作者是Matthew Adam Skala。
在第26页，他讨论了基于kd树等的相似性度量，但得出的结论是：
然而，一般的度量空间并没有提供这些技术所需的几何结构。对于没有其他假设的一般度量空间，必须基于距离使用一种仅根据彼此距离来索引点的方法。Burkhard和Keller [35] 在1973年提出了这样一种索引结构，现在称为BK树，以他们的名字命名。在BK树中，度量被假设为有几个离散的返回值，每个内部节点包含一个视点，子树对应于度量的不同值。
关于BK树如何工作的博客文章可以在这里找到。
在这篇论文中，Skala还描述了其他解决这个问题的方法，包括VP树和GH树。第6章分析了基于Levenshtein编辑距离的距离。他还介绍了一些其他有趣的字符串距离度量。
我还找到了一本似乎与您的问题相关的书：多维和度量数据结构的基础。