算法 - 字符串相似度评分/哈希

Question

有没有一种方法可以计算字符串的“相似度得分”？通过这种方式，我不是在比较两个字符串，而是为每个字符串获取一些数字/分数（哈希），以后可以告诉我两个字符串是否相似。相似的字符串应该有类似（接近）的分数/哈希值。

让我们以这些字符串和分数为例：

Hello world 1000

Hello world! 1010

Hello earth 1125

Foo bar 3250

FooBarbar 3750

Foo Bar! 3300

Foo world! 2350

您可以看出Hello world! 和 Hello world 是相似的，它们的分数很接近。

这样，找到与给定字符串最相似的字符串将通过将给定字符串的分数减去其他分数，然后对其绝对值进行排序来完成。

我的最终目的是：有流式日志消息（仅纯消息），我想找到这些消息的模式（某种正则表达式类型）。但只有当我可以将相似的字符串分成桶时，才会开始。我再次强调 我应该为每个字符串获取一些数字/分数（哈希），以便以后可以告诉我两个字符串是否相似。

- Ajay

---

可能是字符串相似度算法？的重复问题（以及许多其他之前的问题）。 - Fred Foo

@larsmans 这篇文章的解决方案有些偏离我的期望（即它们集中于比较字符串的字符串相似性）。对我而言，数据量非常大且是流式的，因此不能通过比较字符串来判断。我只有一种方法可以解决：对每个字符串进行打分（也许是不太好的哈希类型），然后可以在后面得知这两个字符串是否相似。 - Ajay

相似性是否可以通过哈希值的距离阈值来定义？例如，如果函数为f()，且|f("hello world")-f("hello worth")| < t，其中t是阈值，则"hello world"与"hello worth"相似。否则它们不相似。 - Bloodmoon

关于我的进展，我无法计算字符串的整数simhash，但可以使用128位向量计算字符串之间的汉明距离。每个聚类中包含超过5个值后，计算代表性向量，并仅将传入的字符串与这些代表性聚类进行比较（有助于计算）。请参阅Charikar Hash。 但是还有很多事情要做。无法完全专注于此。如果我获得研究生学位的资金支持，我将继续进行... - Ajay

我明白了。如果你想要对某些东西进行聚类，我认为你可以看一下模式分类。它可以通过使用贝叶斯公式来自动确定新进入的字符串属于哪个簇，基于之前的训练。这种方法不是100％准确的，但具有非常高的精度和广泛的适应性。也许将模式分类和汉明距离结合起来会有所帮助。 - Bloodmoon

Answer 1

请看 局部敏感哈希。

基本思想是将输入项进行哈希，使得相似的项目有很高的概率映射到同一个桶中（桶的数量远小于可能的输入项的宇宙）。 这里提供了非常好的解释以及一些样本代码。

- Jeff Foster

---

这是我迄今为止遇到的最好的概念。我很快会阅读所有相关文件。非常感谢。 - Ajay

Answer 2

TL;DR: Python BK-tree（Python BK树）

这是一个有趣的问题。我在这个领域的经验有限，但由于Levenshtein距离满足三角不等式，我想肯定有一种计算某种绝对距离到原点的方法，以便找到彼此相邻的字符串，而无需直接与整个数据库中的所有条目进行比较。

在搜索与此相关的一些术语时，我发现了一篇特别有趣的论文：计算中度量空间的方面，作者是Matthew Adam Skala。

在第26页，他讨论了基于kd树和其他树的相似度测量方法，但得出结论：

然而，一般的度量空间并不能提供这些技术所需的几何形态。对于没有其他假设的一般度量空间，需要使用基于距离的方法来索引点，仅基于它们彼此之间的距离。Burkhard和Keller [35]在1973年提出了最早的一种这样的索引结构，现在被称为BK-tree。在BK-tree中，度量被假定具有一些离散的返回值，每个内部节点都包含一个关键点，子树对应于度量的不同值。可以在这里找到有关BK-trees工作原理的博客文章。

在论文中，Skala 进一步描述了解决这个问题的其他方案，包括VP-trees和GH-trees。第6章分析了基于Levenshtein编辑距离的距离。他还介绍了一些有趣的字符串距离度量。

我还发现《多维度和度量数据结构基础》这本书，它似乎与你的问题相关。

- Alexander Torstling

Answer 3

有几个这样的“分数”，但它们都取决于您如何定义相似性。

• 我认为Python库已经有了soundex实现。
• 您还可以计算两个字符串的Levenshtein距离
• NYSIIS？

- Daren Thomas

---

soundex 在这里可能不起作用，因为我的消息包含数字值和一些特殊字符。关于 Levenshtein 距离，我想将哈希值分桶，而不是直接比较字符串本身，因为对于数量庞大的流数据来说，直接比较可能会很慢。也许这可以作为后备想法在以后使用...无论如何，感谢您的帮助 :) - Ajay

Answer 4

如果您想快速确定字符串的相似度，您可能需要使用模糊哈希。

- Abhay Buch

Answer 5

我不知道你是否还对此感兴趣，但在信息论中有一种方法可以衡量一个字符串或文本块所含的信息量，也许你可以将该值用作哈希值以便对字符串进行排序。这被称为熵，并且维基百科有一篇很好的文章介绍它：https://en.wikipedia.org/wiki/Entropy_(information_theory)

- Rafael Rios

Answer 6

您可以始终使用Levenshtein距离，此外，还有一个已编写的实现： http://code.google.com/p/pylevenshtein/

但是，为了简单起见，您可以使用内置的difflib模块：

>>> import difflib
>>> l
{'Hello Earth', 'Hello World!', 'Foo Bar!', 'Foo world!', 'Foo bar', 'Hello World', 'FooBarbar'}
>>> difflib.get_close_matches("Foo World", l)
['Foo world!', 'Hello World', 'Hello World!']

http://docs.python.org/library/difflib.html#difflib.get_close_matches

- utdemir

---

编辑距离方法仅适用于一次比较两个字符串。由于空间复杂度（大量数据...我认为我提到了流数据），不可能存储数据并使用Levenshtein距离一个一个地检查。 - Ajay

Answer 7

你可能想考虑使用BK-Tree。这里有一个讨论和Python实现。

BK-Tree将字符串存储在一棵树中，按与父节点的Levenshtein距离排序。通常用于修剪查找相似字符串的搜索空间，但似乎该树会形成一种自然排序，可用于创建聚类。

- Ryan Ginstrom

Answer 8

你可能会对汉明距离感兴趣。Python函数hamming_distance()计算两个字符串之间的汉明距离。

def hamming_distance(s1, s2):
    assert len(s1) == len(s2)
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))

- Wolfwyrd

---

OP在示例中明确列出了一些长度不相等的字符串，因此Hamming距离不适用。更普遍地说，Hamming距离对于文本字符串来说是一个相当弱的度量标准。 - Fred Foo

OP还说他想比较哈希值而不是字符串。 - Brett Stottlemyer

我想根据计算出的哈希值将字符串分组。 - Ajay