c++ - 在大型阵列上查找编辑距离的更有效方法

Question

我有大量的单词(30 万个单词)，我想找到每个单词之间的编辑距离，所以我只是迭代它并运行这个版本的 levenstein 算法:

unsigned int edit_distance(const std::string& s1, const std::string& s2)
{
    const std::size_t len1 = s1.size(), len2 = s2.size();
    std::vector<std::vector<unsigned int>> d(len1 + 1, std::vector<unsigned int>(len2 + 1));
d[0][0] = 0;
for (unsigned int i = 1; i <= len1; ++i) d[i][0] = i;
for (unsigned int i = 1; i <= len2; ++i) d[0][i] = i;

for (unsigned int i = 1; i <= len1; ++i)
    for (unsigned int j = 1; j <= len2; ++j)
        // note that std::min({arg1, arg2, arg3}) works only in C++11,
        // for C++98 use std::min(std::min(arg1, arg2), arg3)
        d[i][j] = std::min({ d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1) });
return d[len1][len2];
}

所以我想知道的是，如果有更有效的方法来做到这一点，我听说过 Levenshtein Autonoma，但我不确定那是否会更有效。

我想你可以通过预处理一些东西来避免一遍又一遍地处理同样的事情，但我不知道如何真正实现它(一些近似计算是预处理所有东西大约是 10^28 次操作，这样不会是一个改进)

Answer 1

正如他在评论中所述，OP 实际上正在寻找编辑距离小于 2 的所有对。

给定 n 个单词的输入，一个简单的方法是进行 n(n-1)/2 次比较，但当 L 处于 metric space for strings 的编辑距离时，可能需要较少的比较。 .

编辑距离是一个度量空间，满足 4 个必需的度量公理 - 包括三角不等式。

编辑:

鉴于此，我们可以使用 Sergey Brin(Google 的 union 创始人)在他的论文 Near Neighbor Search in Large Metric Spaces 中提出的方法。回到 1995 年，解决我们的问题。

引自论文:给定一个度量空间(X，d)，一个数据集Y⊆X，一个查询点x∈X，和一个范围r∈R，x的近邻是点y的集合∈ Y，使得 d(x, y) ≤ r。

在这篇论文中，Brin 介绍了 GNAT(Geometric Near-neighbor Access Tree)——一种解决这个问题的数据结构。 Brin 实际上使用 Levenshtein 距离(他称之为“编辑距离”)针对两个文本语料库测试了他的算法的性能。

多年来，GNAT 变得众所周知并被广泛使用。 Geometric Near-neighbor Access Tree (GNAT) revisited 中建议的对 GNAT 的一些改进- 弗雷德里克森 2016 年。