1

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

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

显而易见的幼稚解决方案是：

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

我确信必须有更好的解决方案来解决这个问题。任何人都可以提供任何见解吗？

4

3 回答 3

1

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

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

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

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

于 2012-06-24T05:36:42.200 回答
0

如果您在同一个词典上运行大量查询并希望缩短查询时间，但可以花一些时间进行预处理，您可以创建一个包含 w1 || 形式的所有可能单词的 trie。w2。然后你可以使用这里描述的算法：使用 Trie 的快速和简单的 Levenshtein 距离来找到你需要的任何单词的答案。

该算法所做的基本上是遍历树的节点并跟踪当前的最小值。然后，如果您最终到达某个节点并且 Levenshtein 距离（从根到当前节点和输入字符串 s 的单词）已经大于迄今为止达到的最小值，您可以修剪以该节点为根的整个子树，因为它无法给出答案。

在我使用英语单词词典和随机查询词进行的测试中，这比测试词典中每个单词的正常方法快 30 到 300 倍，具体取决于您在其上运行的查询类型。

于 2012-06-24T14:28:54.480 回答
0

我假设您想为同一个词典多次执行此操作。例如，您有一个拼写错误的单词并怀疑这是由于它们之间缺少空格造成的。

您肯定需要的第一件事是估计字符串“接近度”的方法。我喜欢标准化技术。例如，将每个字母替换为等价类的代表。（也许 M 和 N 都去 M 因为它们听起来很相似。也许 PH --> F 出于类似的原因。）

现在，您需要将规范化的词典前后输入到 trie 或类似结构中。

现在，向前和向后搜索您的针，但要跟踪两个方向的中间结果。换句话说，在搜索字符串的每个位置，跟踪已在该位置选择的候选树节点列表。

现在，比较中间结果的前向和后向数组，寻找看起来像是单词之间良好连接点的地方。您也可以逐个检查连接点。（换句话说，您已经找到了第一个单词的结尾和第二个单词的开头。）

如果你这样做了，那么你已经找到了你的单词对。

于 2012-06-24T08:04:48.583 回答