对HTML文档进行拼写检查的高效算法
我有一个HTML文档，还有一份常见拼写错误的列表，以及每个错误的正确拼写。
这个HTML文档可能有大约50页，而拼写修正的条目大约有3万条。
那么，有什么高效的方法可以纠正这个HTML文档中的所有拼写错误呢？
(注意：我会用Python来实现，如果你知道相关的库，请告诉我。)
我想到了两种可能的方法：
- 建立一个拼写数据的哈希表
- 从HTML中提取文本
- 根据空格把文本分割成一个个小词
- 如果小词在拼写哈希表中，就用正确的拼写替换掉它
- 用更新后的文本建立一个新的HTML文档
不过，这种方法对于多词拼写修正会失败，因为会有这种情况。下面是一种更简单但看起来效率稍低的方法，可以处理多词拼写：
- 遍历拼写数据
- 在HTML文档中查找单词
- 如果找到了，就用正确的拼写替换掉
2 个回答
2
我同意Rob的建议，使用基于字符的字典树（trie）。我以前写过一个拼写纠正的程序，那个程序就是用字典树来存储有效单词的。通过一种叫做分支限界的方法，我能够给拼写错误的单词提供可能正确的拼写建议，这个方法是基于Levenshtein距离。另外，字典树其实就是一个大型的有限状态机，所以添加常见的前缀和后缀也很简单，这样它就能处理像“postnationalizationalism's”这样的“单词”。
3
你说得对，第一种方法比第二种方法要快得多（另外，我建议你看看字典树，而不是直接使用哈希表，这样在处理3万单词时，节省的空间会非常明显）。
为了处理多词的情况，你可以记录下前一个词，然后检查你的哈希表，看是否有像“前一个 当前”这样的组合字符串。
或者，你也可以把多词的纠正放在哈希表之外，结合这两种方法，先用哈希表处理单个词，然后再扫描多词组合（或者反过来）。如果多词纠正的数量相对较少，这样做仍然可以比较快。
不过要小心，提取单词的过程比单纯根据空格分割要复杂。你可不想因为在哈希表中找不到带逗号的“instence”而错过纠正错误。