字符串相似性算法
您还记得这样的字谜么--每次只允许修改单词的一个字母，就能把它变换成另外一个单词？例如， ship可以通过逐步修改变成 crow，通过中间单词 shop、 chop和 crop。这种游戏为您提供了一条路，可以清楚地理解两个单词之间的距离这一概念。 距离是从一个单词变换成另外一个单词所需要的步数，要求是每次只能改变一个字母，而且每步都要使用字典中实际存在的单词。我把这叫做 字谜距离（puzzle distance）。在这个示例里， ship和 crow之间的字谜距离是 4。
虽然我们经常把距离当作是空间中二点之间的物理度量，但是数学家则用更具一般性的概念把它定义为 度量（metric）。这个定义让您可以在不同的应用程序中使用距离的概念；在这里，您感兴趣的是两个字符串或两个单词之间的距离。它的意义在于，对于拼写错误的单词，您应当查找和它“接近”(这就使用了距离的定义)的单词。距离度量的任何定义都必须满足一些可以度量的属性；例如，距离永远不可能为负。
虽然顺序比较有许多方面（请参阅 参考资料），但是您的目的是找到距离的定义，使距离有助于实现良好的拼写校正。前面定义的字谜距离至少有一个理由不适合做这项工作：拼写错误的单词比起正确拼写的单词来说，通常不止错了一个字母。例如，对于拼错的 puzzel，找不到“路碑”可以到达拼写正确的英文单词。幸运的是，已经设计了大量适用于拼写检查的度量方式。
动态编程算法
动态编程算法从本质上看是一种穷举方法，它会考虑到把源单词转换成目标单词的所有不同方法，从而找到成本最小、或者单词间距离最短的方法。 Levenshtein 距离算法是动态编程算法的一个具体实现，它允许进行三类操作，把源单词 x转换成目标单词 y：
把单词 x中的一个字符 替换成单词 y中的一个字符
把单词 x中的一个字符 删除
在单词 y中 插入一个字符
每个操作都会有一定的成本，而总距离就是从单词 x变换到单词 y 的最小成本。从直观上看，基于这些操作的算法应当可以很好地进行拼写校正，因为打字错误无外乎是这些操作所涉及的键入错误。（实际上， Levenshtein 距离也称作 编辑距离。）例如，当我把单词 wrong打成 wromg（按了 m键，而不是 n 键）的时候，就是一个替换错误；当我打成 wromng（按了 m键，还有 n键）的时候，就是一个删除错误；而当我打成 wrog（遗漏了 n 键），就是一个插入错误。
计算距离
为了更好地理解动态编程算法，可以画一个表格，它的行对应源单词的字母，它的列对应目标单词的字母。处在 (i, j)位置的单元格代表从源单词的 i字母到目标单词的 j字母的最小距离。
对于 Levenshtein 距离，删除和插入的成本为 1。如果字符有差异，那么替换的成本为 1，否则为 0。开始算法的时候，您先填充第一行，第一行对应着空的源单词，这样它就是插入 0,1，...， j个字母的成本。同样，第一列对应着空的目标单词，所以它就是删除 0, 1, ..., i个字母的成本。如果您以 pzzel到 puzzle 的转换为例，那么您会得到如 图 1 所示的网格。
图1. Levenshtein 算法的第一阶段
您还记得这样的字谜么--每次只允许修改单词的一个字母，就能把它变换成另外一个单词？例如， ship可以通过逐步修改变成 crow，通过中间单词 shop、 chop和 crop。这种游戏为您提供了一条路，可以清楚地理解两个单词之间的距离这一概念。 距离是从一个单词变换成另外一个单词所需要的步数，要求是每次只能改变一个字母，而且每步都要使用字典中实际存在的单词。我把这叫做 字谜距离（puzzle distance）。在这个示例里， ship和 crow之间的字谜距离是 4。
虽然我们经常把距离当作是空间中二点之间的物理度量，但是数学家则用更具一般性的概念把它定义为 度量（metric）。这个定义让您可以在不同的应用程序中使用距离的概念；在这里，您感兴趣的是两个字符串或两个单词之间的距离。它的意义在于，对于拼写错误的单词，您应当查找和它“接近”(这就使用了距离的定义)的单词。距离度量的任何定义都必须满足一些可以度量的属性；例如，距离永远不可能为负。
虽然顺序比较有许多方面（请参阅 参考资料），但是您的目的是找到距离的定义，使距离有助于实现良好的拼写校正。前面定义的字谜距离至少有一个理由不适合做这项工作：拼写错误的单词比起正确拼写的单词来说，通常不止错了一个字母。例如，对于拼错的 puzzel，找不到“路碑”可以到达拼写正确的英文单词。幸运的是，已经设计了大量适用于拼写检查的度量方式。
动态编程算法
动态编程算法从本质上看是一种穷举方法，它会考虑到把源单词转换成目标单词的所有不同方法，从而找到成本最小、或者单词间距离最短的方法。 Levenshtein 距离算法是动态编程算法的一个具体实现，它允许进行三类操作，把源单词 x转换成目标单词 y：
把单词 x中的一个字符 替换成单词 y中的一个字符
把单词 x中的一个字符 删除
在单词 y中 插入一个字符
每个操作都会有一定的成本，而总距离就是从单词 x变换到单词 y 的最小成本。从直观上看，基于这些操作的算法应当可以很好地进行拼写校正，因为打字错误无外乎是这些操作所涉及的键入错误。（实际上， Levenshtein 距离也称作 编辑距离。）例如，当我把单词 wrong打成 wromg（按了 m键，而不是 n 键）的时候，就是一个替换错误；当我打成 wromng（按了 m键，还有 n键）的时候，就是一个删除错误；而当我打成 wrog（遗漏了 n 键），就是一个插入错误。
计算距离
为了更好地理解动态编程算法，可以画一个表格，它的行对应源单词的字母，它的列对应目标单词的字母。处在 (i, j)位置的单元格代表从源单词的 i字母到目标单词的 j字母的最小距离。
对于 Levenshtein 距离，删除和插入的成本为 1。如果字符有差异，那么替换的成本为 1，否则为 0。开始算法的时候，您先填充第一行，第一行对应着空的源单词，这样它就是插入 0,1，...， j个字母的成本。同样，第一列对应着空的目标单词，所以它就是删除 0, 1, ..., i个字母的成本。如果您以 pzzel到 puzzle 的转换为例，那么您会得到如 图 1 所示的网格。
图1. Levenshtein 算法的第一阶段
接下来，您要计算余下的每个单元格的值，通过考虑它的三个邻居来计算：上、左、对角上和左。图 2 显示了这个计算方案。
图2：如何计算单元格的成本
对角 上
左 Min(
对角+ 替换成本,
上+ 删除成本,
左+ 插入成本
)
例子结果网格如图 3 如示。右下角单元格的成本是 3，是 pzzel和 puzzle之间的 Levenshtein 成本。
图3. Levenshtein 算法的最后阶段
Levenshtein 算法的属性
作为额外优点， Levenshtein 算法还为您提供了一系列操作，也叫做 校准（alignment），它构成了转换。一对单词通常有不止一次校准。校准对应着沿图表的箭头从左上角单元格到右下角单元格的最小成本路径。例如， 清单 4表示的校准（在 图 3中以红色箭头表示），可以按照下面的操作顺序，一个字母一个字母地读成：
把 p替换成 p（成本为 0）
插入 u（成本为 1）
把 z替换成 z（成本为 0）
把 z替换成 z（成本为 0）
插入 l（成本为 1）
把 e替换成 e（成本为 0）
删除 l（成本为 1）
清单4. pzzel 和 puzzle 之间的校准
p-zz-el
puzzle-
Levenshtein 算法的 Java 实现
清单 5 列出了 Levenshtein 算法的一个简单而直观的 Java 实现。 LevenshteinDistanceMetric 类有些类似于 Apache Jakarta Commons 项目的 StringUtils 类。这些实现的限制是：它们不能处理大型字符串，因为它们的存储需求为 O(mn), 其中 m和 n 分别是源单词和目标单词的长度。如果您只需要计算距离，不需要校准，就像通常情况那样，那么可以很容易地把空间需求降到 O(n)，因为计算下一行只需要前面一行。针对 Apache 版本已经提出了一个修正建议（请参阅 参考资料），但是它在本文写作的时候还没有被合并进来（2.0版）。
请注意： Levenshtein 算法的运行时间总是 O(mn)。所以，如果在非常大的字典里查找拼写错误的最相近匹配，这个算法就太慢了。
清单 5. Levenshtein 距离算法的实现
public class LevenshteinDistanceMetric implements SequenceMetric {
/**
* Calculates the distance between Strings x and y using the
* Dynamic Programming algorithm.
*/
public final int distance(String x, String y) {
int m = x.length();
int n = y.length();
int[][] T = new int[m + 1][n + 1];
T[0][0] = 0;
for (int j = 0; j < i =" 0;" j =" 0;" suggestions =" event.getSuggestions();" i =" suggestions.iterator();">");
System.exit(1);
}
SpellDictionary dictionary = new SpellDictionaryHashMap(new File(args[0]));
SpellChecker spellChecker = new SpellChecker(dictionary);
spellChecker.addSpellCheckListener(new SuggestionListener());
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
while (true) {
System.out.print("Enter line to spell check (return to exit): ");
String line = in.readLine();
if (line.length() == 0) {
break;
}
spellChecker.checkSpelling(new StringWordTokenizer(line));
}
}
}
main() 方法用命令行指定的文件建立了一个 SpellDictionary 。 SpellDictionaryHashMap 实现在内存中保存单词，这样比较快，但是对于大型字典不适合。 (对于容易引起内存不足的应用程序，还提供了基于磁盘的实现。) SpellDictionary 被用来构造 SpellChecker 对象，在用标准输入填充之前，先用它注册 SpellCheckListener 。拼写检查器通常内嵌在用户驱动的应用程序里，而事件驱动的设计本身就适合这类程序。在这个例子里，侦听器（ SuggestionListener ）只是在接收到 SpellCheckEvent 事件时，向标准输出写出拼写错误和建议列表。清单 7 显示了一个运行示例。
清单7. 用 Jazzy 进行拼写检查
Enter line to spell check (return to exit): choklut biskit
Misspelling: choklut
Suggestions: chocolate
Misspelling: biskit
Suggestions: biscuit
Enter line to spell check (return to exit):
这个例子非常简单，更复杂的应用程序可以利用 Jazzy 对用户字典管理的支持，执行向字典增加单词、忽略单词、用选中的修正自动替换重复错误拼写等任务。要获得详细信息，请参阅 SpellCheckEvent （在 参考资料中）的 API 文档。
结束语
在撰写这篇文章的时候，Jazzy API 仍然是一个 alpha 软件，版本号为 0.5。作为一个相对年轻的 API，Jazzy 的改进和扩展是公开的。对于初学者，Jazzy 更多地表现出相对于它的近亲 Aspell 所做的一些改进。如果更进一步的话，Jazzy 对于设计上下文感知或语法感知的拼写检查器来说，会是一个理想的框架（使用自然语言处理的一些特性而不是简单的单词列表）。
事实上，Jazzy 是稳固的。虽然对于在 Java 平台上开发拼写检查软件来说仍然是个相对简单的 API，但是因为 Jazzy 是开放源代码的，所以任何人都可对它未来的发展做出贡献。而 API 也可以被用作框架，对其进行扩展后用于内部应用程序开发。请参阅 参考资料一节，了解更多本文所讨论的算法，以及 Java 平台的新拼写检查器 API--Jazzy。
图2：如何计算单元格的成本
对角 上
左 Min(
对角+ 替换成本,
上+ 删除成本,
左+ 插入成本
)
例子结果网格如图 3 如示。右下角单元格的成本是 3，是 pzzel和 puzzle之间的 Levenshtein 成本。
图3. Levenshtein 算法的最后阶段
Levenshtein 算法的属性
作为额外优点， Levenshtein 算法还为您提供了一系列操作，也叫做 校准（alignment），它构成了转换。一对单词通常有不止一次校准。校准对应着沿图表的箭头从左上角单元格到右下角单元格的最小成本路径。例如， 清单 4表示的校准（在 图 3中以红色箭头表示），可以按照下面的操作顺序，一个字母一个字母地读成：
把 p替换成 p（成本为 0）
插入 u（成本为 1）
把 z替换成 z（成本为 0）
把 z替换成 z（成本为 0）
插入 l（成本为 1）
把 e替换成 e（成本为 0）
删除 l（成本为 1）
清单4. pzzel 和 puzzle 之间的校准
p-zz-el
puzzle-
Levenshtein 算法的 Java 实现
清单 5 列出了 Levenshtein 算法的一个简单而直观的 Java 实现。 LevenshteinDistanceMetric 类有些类似于 Apache Jakarta Commons 项目的 StringUtils 类。这些实现的限制是：它们不能处理大型字符串，因为它们的存储需求为 O(mn), 其中 m和 n 分别是源单词和目标单词的长度。如果您只需要计算距离，不需要校准，就像通常情况那样，那么可以很容易地把空间需求降到 O(n)，因为计算下一行只需要前面一行。针对 Apache 版本已经提出了一个修正建议（请参阅 参考资料），但是它在本文写作的时候还没有被合并进来（2.0版）。
请注意： Levenshtein 算法的运行时间总是 O(mn)。所以，如果在非常大的字典里查找拼写错误的最相近匹配，这个算法就太慢了。
清单 5. Levenshtein 距离算法的实现
public class LevenshteinDistanceMetric implements SequenceMetric {
/**
* Calculates the distance between Strings x and y using the
* Dynamic Programming algorithm.
*/
public final int distance(String x, String y) {
int m = x.length();
int n = y.length();
int[][] T = new int[m + 1][n + 1];
T[0][0] = 0;
for (int j = 0; j < i =" 0;" j =" 0;" suggestions =" event.getSuggestions();" i =" suggestions.iterator();">");
System.exit(1);
}
SpellDictionary dictionary = new SpellDictionaryHashMap(new File(args[0]));
SpellChecker spellChecker = new SpellChecker(dictionary);
spellChecker.addSpellCheckListener(new SuggestionListener());
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
while (true) {
System.out.print("Enter line to spell check (return to exit): ");
String line = in.readLine();
if (line.length() == 0) {
break;
}
spellChecker.checkSpelling(new StringWordTokenizer(line));
}
}
}
main() 方法用命令行指定的文件建立了一个 SpellDictionary 。 SpellDictionaryHashMap 实现在内存中保存单词，这样比较快，但是对于大型字典不适合。 (对于容易引起内存不足的应用程序，还提供了基于磁盘的实现。) SpellDictionary 被用来构造 SpellChecker 对象，在用标准输入填充之前，先用它注册 SpellCheckListener 。拼写检查器通常内嵌在用户驱动的应用程序里，而事件驱动的设计本身就适合这类程序。在这个例子里，侦听器（ SuggestionListener ）只是在接收到 SpellCheckEvent 事件时，向标准输出写出拼写错误和建议列表。清单 7 显示了一个运行示例。
清单7. 用 Jazzy 进行拼写检查
Enter line to spell check (return to exit): choklut biskit
Misspelling: choklut
Suggestions: chocolate
Misspelling: biskit
Suggestions: biscuit
Enter line to spell check (return to exit):
这个例子非常简单，更复杂的应用程序可以利用 Jazzy 对用户字典管理的支持，执行向字典增加单词、忽略单词、用选中的修正自动替换重复错误拼写等任务。要获得详细信息，请参阅 SpellCheckEvent （在 参考资料中）的 API 文档。
结束语
在撰写这篇文章的时候，Jazzy API 仍然是一个 alpha 软件，版本号为 0.5。作为一个相对年轻的 API，Jazzy 的改进和扩展是公开的。对于初学者，Jazzy 更多地表现出相对于它的近亲 Aspell 所做的一些改进。如果更进一步的话，Jazzy 对于设计上下文感知或语法感知的拼写检查器来说，会是一个理想的框架（使用自然语言处理的一些特性而不是简单的单词列表）。
事实上，Jazzy 是稳固的。虽然对于在 Java 平台上开发拼写检查软件来说仍然是个相对简单的 API，但是因为 Jazzy 是开放源代码的，所以任何人都可对它未来的发展做出贡献。而 API 也可以被用作框架，对其进行扩展后用于内部应用程序开发。请参阅 参考资料一节，了解更多本文所讨论的算法，以及 Java 平台的新拼写检查器 API--Jazzy。
没有评论:
发表评论