字符串相似度分数/哈希

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很相似，它们的分数非常接近。

这样，找到与给定字符串最相似的字符串就是通过将给定字符串的得分从其他字符串的得分中减去，然后按绝对值排序。

- Josef Sábl

---

“类似”是什么意思？“hello world”、“world hello”和“dlrow olleh”是否相似？如果是或不是，为什么？ - smirkingman

当超过两个字符串彼此等距时会发生什么？你无法用一维分数来建模。 - mbeckish

@smirkingman 没关系，我主要是在考虑相似度得分的概念。但是我们可以说像Levenshtein算法中的相似度。 - Josef Sábl

你好，我也对这个问题非常感兴趣。你在这个问题上有任何进展了吗？ - Bloodmoon

@JosefSábl你解决了这个问题吗？我正在努力寻找类似而且不复杂的东西，但是遇到了困难！在机器学习中，有一些像Word2Vec这样的东西，看起来很复杂，但也许那就是我应该做的事情。 - Joe Booth

Answer 1

我相信你正在寻找的是所谓的局部敏感哈希算法（Locality Sensitive Hash）。与大多数哈希算法不同的是，这些哈希尝试相反的策略：输入的小变化会生成成比例较小的输出变化。

正如其他人所提到的，将多维映射强制转换为二维映射存在固有问题。这类似于在地球上创建一张平面图...你永远无法在平面表面准确地表示一个球体。最好的方法就是找到一种针对用于确定字符串是否“类似”的任何特征进行优化的LSH。

- DougW

Answer 2

Levenshtein距离或其派生算法是您想要的算法。 将给定字符串与字典中的每个字符串进行匹配。 （如果您只需要固定数量的最相似字符串，则可以使用min-heap。） 如果运行字典中所有字符串的Levenshtein距离太昂贵，则首先使用一些粗略的算法，从候选列表中排除距离太远的单词。 之后，在剩余的候选单词上运行Levenshtein距离。

---

一种排除距离较远的单词的方法是索引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元索引：

" 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的单词。

这样可以将候选项数量减少到合理的数量，并且您可以继续使用Levenshtein算法将给定字符串与剩余候选项中的每个字符串进行匹配。

---

如果您的字符串足够长，则可以通过使用min-hashing技术来减少索引大小：对于每个n-gram，您计算普通哈希，并仅使用K个最小哈希，其他哈希则被丢弃。

P.S. 这个演示文稿似乎是解决您问题的良好入门介绍。

- gudok

---

那太棒了！ - Javasick

Answer 3

通常情况下，这是不可能的，因为字符串之间的编辑距离形成了一个度量空间，但不是一个具有固定维度的度量空间。这意味着你不能提供一个将字符串映射到整数的映射，从而保留它们之间的距离测量。

例如，你无法为以下三个短语分配数字：

• one two
• one six
• two six

使得这些数字反映出所有三个短语之间的差异。

- Nick Johnson

---

我会做一些信息论的内容，并且认为你所声称的不可能已经完成了。每个字符串都可以表示为一个二进制数（即整数），而你刚刚证明了你能够识别该数字中描述所谓“差异”的结构。我认为实际上问的问题是，我们是否可以将字符串映射到一组更简单的数字，以便无损地表示可能关系的完整集合。这本质上是搜索空间的科尔莫戈洛夫复杂度。 - DougW

显然，对于任意定义为“相似”的字符串，其 Kolmogorov 复杂度要低是不可能的。然而，我认为通过限制集合或定义（例如，仅限于英语语言字符串），可以降低该复杂度。这个问题的复杂度可能远远小于无界的问题，并且可能映射到一个更小的整数空间。 - DougW

这就是K复杂度发挥作用的地方。如果我们将“相似性”定义为“字母A的数量”，那么该空间的复杂度足够小，可以映射到一个容易理解的数字上。随着我们对“相似”的定义复杂度的增加，问题空间的K复杂度也会增加，表示也变得更加复杂。我们可以通过丢弃不重要的信息来减少这种复杂性。这非常类似于在二维地图上表示地球。我们可以通过映射到较低的维度来近似我们关心的信息，但代价是失去一些信息。 - DougW

好的，显然这是你对问题的解释，我尊重你的看法。就个人而言，我没有看到他的问题中有任何关于“编辑距离”的迹象。他关心的是字符串的相似性（请参见他在评论中对mbeckish的回复），我认为这是一个不同的问题，可以通过哈希来近似解决（请参见我的答案）。 - DougW

计算编辑距离，选择：base="one two"; ED(base, "one two") = 0; ED(base, "one six") = 6; ED(base, "two six") = 8; 数字并不普遍代表字符串的值，但它可以在给定集合中确定差异的顺序。 - rocketspacer

Answer 4

虽然这个想法听起来非常甜蜜，但我从未听说过。

我已经阅读了许多有关拼写校正/错别字校正的技术、论文和科学论文，最快的建议都涉及索引和莱文斯坦距离。

有相当复杂的技术，我目前正在使用的技术结合了：

- 一个带有级别紧凑性的 Bursted Trie - 一个 Levenshtein 自动机

即使这并不意味着“不可能”得到一个分数，但如果这样的“评分”方法被证明有效，我认为不会有那么多最近的字符串比较研究。

如果你找到这样的方法，我非常感兴趣 :)

- Matthieu M.

Answer 5

你考虑使用Levenshtein距离吗？

- Karl Knechtel

---

它就是它本身：距离。它不能为一个字符串提供任何特征，只能用来比较两个特定的字符串。 - Nikita Rybak

Nikita是正确的，那就是问题所在。除此之外，这正是我所需要的。 - Josef Sábl

一个一维的“特征”是不起作用的，因为如果distance(a,b) = 1和distance(b,c) = 1，则并不意味着distance(a,c) = 2。你真正想做什么？ - Karl Knechtel

我一直在寻找类似的东西，但现在我怀疑这是不可能的，因为它是Levenshtein距离，而不是类似于欧几里得距离的dist(a,c) = dist(a,b) +/- dist(b,c)。 - Alvin

如果你选择一个基本字符串并计算它与所有字符串之间的距离，那么这个方法是有效的，可以查看我的答案。 - rocketspacer

即使它是一维的，也可能a和c是相同的，因此distance(a,c)将是0，即使它们中的任何一个到b的距离为1。 - ArtOfWarfare

Answer 6

在一个无限制的问题中，没有解决方案可以将任何可能的单词序列或任何可能的字符序列转换为描述局部性的单个数字。

想象一下在字符级别上的相似性。

stops
spots

hello world
world hello

在这两个例子中，信息不同但消息中的字符是相同的，因此需要保留一个位置值和一个字符值。(char 0 == 'h', char 1 == 'e' ...)。然后比较以下类似的消息。

hello world
ello world

尽管这两个字符串相似，但它们可能在开头或结尾有所不同，这使得按位置缩放变得困难。

在这种情况下，

spots
stops

这些单词只是字符位置不同，因此某种形式的位置很重要。

如果以下字符串类似

 yesssssssssssssss
 yessssssssssssss

那么你就有了一种悖论。如果在第二个字符串中添加2个s字符，它应该与第一个字符串之间保持相同的距离，但它应该是不同的。这可以重复进行，得到逐渐变长的字符串，所有这些字符串都需要接近比它们短和长的字符串。我看不出如何实现这一点。

通常情况下，这被视为多维问题-将字符串分解为向量。

[ 'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd' ]

但向量的值不能用固定大小的数字表示，也不能提供良好的差异度量。

• 如果单词数或字符串长度受到限制，则可能存在编码解决方案。

有界值

使用类似算术压缩的东西，然后可以将一系列单词转换为表示序列的浮点数。但是，这会将序列中较早的项视为比序列中的最后一项更重要。

数据挖掘解决方案

如果您接受问题是高维的，则可以将字符串存储在度量树（维基百科：度量树）中。这将限制您的搜索空间，同时不解决“单个数字”解决方案。

我在GitHub：聚类上有这样的代码。

靠近一起的项目应该存储在树的某个部分中，但实际上并没有保证。子树的半径用于修剪搜索空间。

编辑距离或Levenshtein距离

这在SQLite扩展中用于执行相似性搜索，但是没有单个数字的解决方案，它可以计算将一个字符串更改为另一个字符串所需的编辑次数。然后，这将导致分数，显示相似性。

- mksteve

Answer 7

我想到了这样的东西：

1. 移除所有非单词字符
2. 应用soundex函数

- alpha-mouse

---

还不错，但是：a）我的字符串不仅包含单词，b）我会得到 Soundexes，好的，但是如何比较它们是否相似呢 :-) - Josef Sábl

Answer 8

你的想法听起来像是应用于整个短语的本体论。两个短语越相似，它们在图中就越接近（假设你使用了加权边）。反之亦然：不相似的短语则相距甚远。

另一种方法是使用傅里叶变换来获取给定字符串的“索引”（它不会是一个单一的数字，但总是一个向量）。你可以在这篇论文中找到更多信息。

还有另一个基于Levenshtein距离的想法：你可以比较n-gram，这将为给定的两个短语提供一些相似性指数 - 它们越相似，值就越接近1。这可以用于计算图中的距离。我几年前写过一篇关于这个的论文，如果你愿意，我可以分享给你。

无论如何：虽然我不知道确切的解决方案，但我也对你的想法很感兴趣。

- Przemek Kryger

Answer 9

或许可以使用PCA，其中矩阵是字符串与固定字母表（如ABCDEFGHIJKLMNOP...）之间差异的列表。答案可以简单地是主成分的长度。

仅供参考。

C#中可直接运行的PCA

- smirkingman

Answer 10

从两个短语中得出一个相对较小的数字，以提供它们初始短语相似性的相关指示是不太可能的。

原因在于数字只在一个维度上提供指示，而短语则在长度和强度这两个维度上发展。

数字可以像长度和强度一样发展，但我不确定它会有多大帮助。

在两个维度上，您最好查看矩阵，其中一些属性（如行列式）可以给出短语趋势的粗略想法。

- Déjà vu