java中的拼写检查器解决方案

Question

我需要在java中实现拼写检查器，让我给你一个字符串的例子让我们说“sch aproblm iseasili解决了”我的输出是“这样的问题很容易解决”。最大长度要纠正的字符串是64.正如你所看到的，我的字符串可能会在错误的地方插入空格或者根本没有插入空格，甚至拼写错误的单词。我需要一些帮助来找到纠正字符串的有效算法。我现在试图删除我的字符串中的所有空格，并在每个可能的位置插入空格，所以让我们说这个单词（它也适用于一个句子）“热”我生成下一个可能的字符串后续字逐字使用levenshtein距离：热; hot; ho;热。正如你所看到的，我已经生成了2 ^（string.length（）-1）可能的字符串。所以对于一个长度为64的字符串，它会生成2^63个可能的字符串，这个字符非常高，后面我需要逐个处理它们，并通过一组不同的参数来选择最好的字符串，例如： - 总编辑距离（必须是最小的一个） - 如果我有更多的字符串具有相同的编辑距离，我不得不选择字数较少的字符串 - 如果我有更多的字符串与我需要选择的字数相同与单词总的最大频率（我有一个最常见的8000字的字典及其频率） - 最后如果有更多的字符串具有相同的总频率，我必须采取最小的字典。所以基本上我生成所有可能的字符串（在所有可能的位置插入原始字符串中的空格），然后一个一个地计算它们的总编辑距离，单词nr等等。然后选择最好的一个，然后输出正确的字符串。我想知道是否有一个更容易（在效率方面）这样做，如不需要生成所有可能的字符串组合等。

编辑：所以我认为我应该采取另一种方法在这一个这里是我想到的：我从字符串中取出第一个字母，并从字典中提取所有以该字母开头的单词。之后，我处理所有单词并从字符串中提取所有可能的第一个单词。我将继续以我以前的例子来说，通过生成所有可能的组合，我会得到4个结果，但通过我的新算法，我只获得2个“热”和“浩”，所以它已经是一种改进。尽管我在创建递归或PD算法时需要一点帮助。我需要一种方法来为第一个单词存储所有可能的字符串，然后为第二个单词存储所有可能的字符串，最后将所有可能性连接起来并将它们添加到数组或其他内容中。对于大字符串，仍然会有很多组合，但是不必做所有这些组合。有人可以用伪码或其他东西来帮助我，因为这不是我的强项。

EDIT2：这里是代码，我从我的字符串中生成所有可能的第一个单词http://pastebin.com/d5AtZcth。我需要以某种方式执行此操作来为其余部分执行相同的操作，并将每个第一个单词与每个第二个单词相结合，并将所有这些连接成一个数组或其他东西。

Answer 1

你一些提示：

1. 尝试修正一次字符串的只是一小部分，不能代表一切。

2. 90％的错误（IIRC）与源有1个编辑距离。

3. 您可以使用拼音索引将单词与听起来相似的单词进行匹配。

4. 你可以假定大部分拼写错误都是QWERTY错误（j => k，h => g），并且试着先检查它们。

更多思路可这个漂亮的文章中找到：

http://norvig.com/spell-correct.html