4

我正在用 PHP 创建一个网络应用程序，人们可以在其中尝试翻译他们需要在学校学习的单词。

例如，有人需要将荷兰语单词“weer”翻译成英语中的“weather”，但不幸的是他输入了“whether”。因为他几乎打错了字，我想再试一次，.在他打错的地方加点“”：

Language A:   weer
Language B:   weather
Input:        whether
Output:       w..ther

或者，例如

Language A:   fout
Language B:   mistake
Input:        mitake
Output:       mi.take

或者：

Language A:   echt
Language B:   genuine
Input:        genuinely
Output:       genuinely (almost good, shorten the word a little bit)

但是，如果输入与所需的翻译相差太大，我不想得到像这样的输出........

我听说过 Levenshtein 距离，我认为我需要一种与该算法非常相似的算法，但我不知道如何将点放在正确的位置，而不是回显要完成多少操作。

那么，如何在某人犯错的地方返回拼写错误的单词呢？

4

3 回答 3

4

首先，看一下wikipedia 上的 Levenshtein 算法。然后继续查看d文章页面上的示例和生成的矩阵：

                *k*     *i*     *t*     *t*     *e*     *n*
        >0       1       2       3       4       5       6 
*s*      1      >1       2       3       4       5       6 
*i*      2       2      >1       2       3       4       5 
*t*      3       3       2      >1       2       3       4 
*t*      4       4       3       2      >1       2       3 
*i*      5       5       4       3       2      >2       3 
*n*      6       6       5       4       3       3      >2 
*g*      7       7       6       5       4       4      >3

距离位于矩阵的右下角，d[m, n]。但现在可以从那里回溯到矩阵左上角的最小步长 d[1, 1]。您只需在每个步骤中向左、左上或向上走，以最小化路径为准。在上面的示例中，您会找到由“>”符号标记的路径：

  s i t t i n g      k i t t e n
0 1 1 1 1 2 2 3    0 1 1 1 1 2 2 3
  ^       ^   ^      ^       ^   ^
  changes in the distance, replace by dots

现在，您可以在位置 d[i,j] 处的距离变化的最小路径上找到（在上面的示例中由 ^ 标记），并且对于您在第一个（或第二个）单词中放置的那些字母，在位置 i (或 j 分别）。

结果：

  s i t t i n g      k i t t e n
  ^       ^   ^      ^       ^   ^
  . i t t . n .      . i t t . n .
于 2009-12-31T16:06:33.693 回答
3

您要查找的术语称为“编辑距离”。使用Levenshtein distance之类的东西会告诉您将一个字符串转换为另一个字符串所需的操作数（插入、删除、替换等）。

这是其他“编辑距离”算法的列表。

一旦您确定一个词“足够接近”（即它不超过所需编辑的某个阈值），您就可以显示需要进行编辑的位置（通过显示点）。

那么你怎么知道把点放在哪里呢？

“Levenshtein 距离”的有趣之处在于它使用 M x N 矩阵，每个轴上都有一个单词（请参阅Levenshtein 文章中的示例矩阵）。创建矩阵后，您可以确定哪些字母需要“额外编辑”才能正确。那就是你放点的地方。如果这封信需要“没有额外的编辑”，您只需打印这封信。很酷。

于 2009-12-31T16:02:03.103 回答
0

我认为你需要做一个多步骤的过程，而不仅仅是 Levenshtein。首先，我会检查输入词是否是目标词的一种形式。这会抓住你的第三个例子，也不必担心添加点。您还可以使用此步骤来捕获同义词。下一步是检查两个字符串的长度差异。

如果差异为 0，您可以对字母进行比较以放置点。如果您不想显示所有点，那么您应该保留放置的点数，一旦超过限制就会显示一些错误消息。（对不起，不正确）

如果差异显示输入更长，您需要检查要删除的字母将解决问题。在这里，您可以使用 Levenshtein 查看它们的距离，如果它们太远，则显示您的错误消息，如果它在范围内，您将需要反向执行 Levenshtein 的步骤并以某种方式标记更改。不知道你想如何表明一封信需要删除。

如果差异显示输入更短，您可以使用 Levenshtein distance 来查看两个单词是否足够接近或显示错误。然后再次反向执行步骤，为插入添加点，为替换添加点。

实际上，最后两个步骤可以组合成一个函数，该函数贯穿算法并记住插入删除或替换并相应地更改输出。

于 2009-12-31T16:01:35.897 回答