在大型数组上查找编辑距离的更有效方法

Question

我有一个很大的单词数组（300k 个单词），我想找到每个单词之间的编辑距离，所以我只是迭代它并运行这个版本的 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 个单词的输入，一种简单的方法是进行 n(n-1)/2 次比较，但是当 L 位于编辑距离（字符串的度量空间）中时，可能需要较少的比较中时，可能需要较少的比较。

\n\n

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

\n\n

编辑：

\n\n

鉴于此，我们可以使用 Sergey Brin（Google 联合创始人）在 1995 年的论文《大度量空间中的近邻搜索》中提出的方法来解决我们的问题。

\n\n

引用论文：给定一个度量空间 (X, d)，一个数据集 Y \xe2\x8a\x86 X，一个查询点 x \xe2\x88\x88 X，以及一个范围 r \xe2\x88\x88 R ，x 的近邻是点集 y \xe2\x88\x88 Y，使得 d(x, y) \xe2\x89\xa4 r。

\n\n

在这篇论文中，Brin 介绍了 GNAT（几何近邻访问树）——一种解决这个问题的数据结构。布林实际上使用 Levenshtein 距离（他称之为“编辑距离”）针对两个文本语料库测试了他的算法的性能。

\n\n

多年来，GNAT 变得众所周知并被广泛使用。重新审视几何近邻访问树 (GNAT) - Fredriksson 2016中建议对 GNAT 进行一些改进。

\n