algorithm - 在词典中查找最接近一对的字符串

Question

我目前正在尝试通过以下公式提出一个有效的解决方案:

给定一个输入字符串 s 和一个固定的词典，找到与 s 具有最小编辑距离的字符串 w1||w2(|| 表示连接，w1 和 w2 是词典中的单词)。

最简单的解决方案是:

for word1 in lexicon:
   for word2 in lexicon:
       if lev_dist(word1 + word2) < lev_dist(lowest):
          lowest = word1 + word2

我相信一定有更好的解决方案来解决这个问题。谁能提供任何见解？

Answer 1

您可以通过对单个字符串的成本设置下限来做得更好。

查看 http://en.wikipedia.org/wiki/Levenshtein_distance 中的算法，当你关心计算 d[i, j] 的距离时，你知道你正在添加一个依赖于 s[i] 和 t[j] 的贡献，其中 s 和 t 是被比较的字符串，所以你可以使更改/删除/插入的成本取决于操作在两个字符串中的位置。

这意味着您可以使用成本函数计算 abcXXX 和 abcdef 之间的距离，其中对标记为 XXX 的字符的操作是免费的。这允许您计算将 abcXXX 转换为 abcdef 的成本，如果字符串 XXX 实际上是可能的最有利字符串。

因此，对于词典中的每个单词 w1，计算 w1XXX 与目标字符串以及 XXXw1 与目标字符串之间的距离。生成词典的两份副本，按 w1XXX 距离和 XXXw1 距离排序。现在按照左手和右手成本之和的顺序尝试所有对，这是该对成本的下限。跟踪到目前为止的最佳答案。当最佳答案至少与您遇到的下一个成本下限一样好时，您就会知道您可以尝试的任何事情都无法改进这个最佳答案，因此您可以停下来。