13

假设构建了字典单词的一般 Trie，那么在遍历期间检查 4 种拼写错误的最佳方法是什么 - 替换、删除、转置和插入？

一种方法是找出给定单词 n 个编辑距离内的所有单词，然后在 Trie 中检查它们。这不是一个坏选择，但这里更好的直觉似乎是使用动态编程（或递归等效）方法来确定在遍历期间修改单词后的最佳子尝试。

欢迎任何想法！

PS，会欣赏实际的输入，而不仅仅是答案中的链接。

4

4 回答 4

9

前几天我实际上写了一些代码来做到这一点：

https://bitbucket.org/teoryn/spell-checker/src/tip/spell_checker.py

它基于 Peter Norvig ( http://norvig.com/spell-correct.html ) 的代码，但将字典存储在 trie 中，以便更快地查找给定编辑距离内的单词。

该算法通过消耗输入单词中的字母，递归地在每个步骤中应用可能的编辑（或不进行）。递归调用的参数说明可以进行多少次编辑。trie 通过检查我们给定的前缀实际上可以到达哪些字母来帮助缩小搜索空间。例如，当插入一个字符时，我们只添加从当前节点可到达的字母，而不是添加字母表中的每个字母。不进行编辑相当于从 trie 中的当前节点沿输入单词的当前字母获取分支。如果该分支不存在，那么我们可以回溯并避免搜索可能找不到真正单词的大空间。

于 2010-07-15T15:14:15.667 回答
2

我认为您可以通过在树上进行简单的广度优先搜索来做到这一点：选择您要查找的错误数量的阈值，只需一次遍历要匹配的单词的字母，生成一组(prefix, subtrie) 对到目前为止与前缀匹配，当您低于错误阈值时，添加到您的下一个子目标集：

  1. 此字符位置没有错误：在单词的下一个字符处添加trie的子目标
  2. 在此位置插入、删除或替换的字符：在此处找到适当的 trie，并增加错误计数；
  3. 不是一个额外的目标，但请注意，转置是与早期删除或插入匹配的插入或删除：如果此测试成立，则不要增加错误计数。

这似乎很幼稚：这是否有问题导致您想到动态编程？

于 2010-07-15T09:07:54.217 回答
2

假设单词中的每个连续字符代表树中的一个级别，那么您有五个案例要检查每个字符（匹配、删除、插入、替换和转置）。我假设换位是两个相邻的字符。

您将需要一个接受树节点和要检查的字符的函数 (CheckNode)。它将需要返回一组表示匹配的（子/孙子）节点。

您将需要一个接受单词的函数 (CheckWord)。它依次对照一组节点检查每个字符。它将返回一组表示匹配单词的（叶）节点。

这个想法是树中的每个级别（子级，孙子级等）都匹配单词中字符的位置。如果您调用顶级树节点，级别 0，那么您将拥有级别 1、级别 2 等。

显然，对于没有错误的单词，字符位置和树中的级别之间存在一对一的匹配。

对于删除，您需要跳过树中的一个级别。

对于插入，您需要跳过单词中的一个字符。

对于替换，您需要跳过一个级别和一个字符。

对于换位，您需要（暂时）交换单词中的字符。

于 2010-07-15T12:00:09.787 回答
1

看一下计算Levenshtein 距离，它提供了一种动态规划解决方案来查找两个序列之间的距离。

于 2010-07-14T23:14:30.113 回答