algorithm - 编辑距离算法

Question

我有一个包含“n”个单词的字典，并且有“m”个查询要响应。我想输出字典中编辑距离为 1 或 2 的单词数。鉴于 n 和 m 大约为 3000，我想优化结果集。

根据以下答案添加编辑:

我会尝试用不同的方式表达它。

最初有“n”个单词作为一组字典单词给出。给出下一个“m”个词，它们是查询词，对于每个查询词，我需要查找该词是否已存在于词典中(编辑距离“0”)或词典中编辑距离为 1 或2 来自字典的单词。

我希望问题现在已经清楚了。

好吧，如果时间复杂度是 (m*n)n 就会超时。天真的使用 DP 编辑距离算法会超时。即使计算 2k+1 的对角线元素也会超时，其中 k 是阈值，这里 k=3 在上述情况下。

Answer 1

您想使用 Levenshtein distance在两个词之间，但我假设您知道这一点，因为问题的标签就是这么说的。

您必须遍历您的列表(假设)并将列表中的每个单词与您正在执行的当前查询进行比较。你可以 build 一个 BK-tree限制您的搜索空间，但如果您只有约 3000 个单词，这听起来有点矫枉过正。

var upperLimit = 2;
var allWords = GetAllWords();
var matchingWords = allWords
        .Where(word => Levenshtein(query, word) <= upperLimit)
        .ToList();

修改原始问题后添加

如果您有不区分大小写的字典，则查找 distance=0 的情况很容易包含查询。距离 <= 2 的情况需要对搜索空间进行完整扫描，每个查询词进行 3000 次比较。假设相同数量的查询词会产生 900 万次比较。

你提到它超时，所以我假设你配置了超时？您的速度可能是由于 Levenshtein 计算的实现不当或缓慢造成的吗？

_{(来源:itu.edu.tr)}
上图盗自CLiki: bk-tree

如上所示，使用编辑距离 <= 2 的 bk-tree 只会访问大约 1% 的搜索空间，但这是假设您有非常大的输入数据，在他们的情况下高达 50 万个单词。我会假设你的情况类似的数字，但即使存储在列表/字典中，如此少的输入量也不会造成太多麻烦。