代码之家 › 专栏 › 技术社区 › Harmen

在单词拼写错误处放置点

levenshtein-distance algorithm php

4

Harmen · 技术社区 · 16 年前

我正在用PHP创建一个Web应用程序,人们可以在其中翻译他们上学需要学习的单词。

例如,有人需要将荷兰语“weer”翻译成英语“weather”,但不幸的是,他输入了“if”。因为他几乎输入了正确的单词,我想再给他一次尝试,用点 . “在他犯错误的地方:

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)

但是,如果输入与所需的翻译有太大的差异,我不希望得到像 ........

我听说了列文斯坦距离,我想我需要一个类似的算法,但我不知道如何在正确的地方放置点,而不是重复要做多少操作。

那么,我怎样才能在有人出错的地方用圆点返回拼写错误的单词呢?

3 回复 | 直到 14 年前

1

4

catchmeifyoutry 16 年前

首先,看看列文斯坦 algorithm on wikipedia . 然后继续看例子和得到的矩阵 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 .

2

3

Robert Cartaino 16 年前

你要找的术语叫做“编辑距离”。 Levenshtein distance 将告诉您将一个字符串转换为另一个字符串所需的操作数(插入、删除、替换等)。

Here is a list of other "editing distance" algorithms .

一旦你决定一个词“足够接近”(即它不超过所需编辑的阈值),你就可以显示需要编辑的地方(通过显示点)。

那么你怎么知道把这些点放在哪里呢?

关于“Levenshtein距离”,有趣的是它使用了一个m x n矩阵,每个轴上有一个单词(参见中的示例矩阵 Levenshtein article )。创建矩阵后,可以确定哪些字母需要“附加编辑”才能正确。这就是你放置圆点的地方。如果信件需要“无需额外编辑”,只需打印信件即可。很酷。

3

0

Jeff Beck 16 年前

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

如果差异为0,可以进行字母对字母的比较以放置点。如果你不想显示所有的点,那么你应该保持点的计数,一旦超过限制,就会显示一些错误信息。(抱歉,这是错误的)

如果差异显示输入的时间较长,则需要检查要删除的字母,这样可以解决问题。在这里,您可以使用levenshtein查看它们的距离有多近,如果它们太远,则显示错误消息如果它在范围内,则需要反向执行levenshtein的步骤并以某种方式标记更改。不确定如何显示需要删除的信件。

如果差异显示输入较短,可以使用Levenshtein距离来查看两个词是否足够接近或显示错误。然后按相反的步骤再次添加插入点和替换点。

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