1

我正在实施拼写检查算法。我已经构建了一个Trie存储我的单词的快速搜索。

当传递给定的输入字符串时，我想做的是为该字符串生成潜在的删除、插入、替换和转置，编辑距离为 1。使用这个超集，我可以尝试在 my 中找到单词Trie并提供给用户“你的意思是？” 键入结果。

我在网上看过，大多数解决方案都提到了计算莱文斯坦距离。仅当您已经知道这两个字符串并且想要找到两者之间的编辑距离时，这才有效。

建议？

4

1 回答 1

2

我会使用 2 pass 算法：

通过 1

查找并计算所有以与要拼写检查的单词相同的字母开头的单词的距离。这会很快。当字符数大于拼写单词长度 + 2（那么这显然是另一个单词）时，您可以停止深度搜索
显示 pass1 的结果，例如将单词标记为红色下划线

Pass 2

查找所有单词并在 length + 3 或 4 时停止更新在 pass 1 中找到的结果

于 2012-12-03T01:39:16.023 回答