c - 如何改进 C 程序中的拼写检查时间？

Question

作为哈佛 CS50 类(class)中的一项作业，学生的任务是创建一个拼写检查程序。这项任务的主要目的是速度——纯粹的速度——我已经达到了击败员工实现的地步，但我觉得我可以做得更好，并且正在寻找正确方向的插入。

这是我的伪代码:

// read the dictionary word list
Read entire dictionary in one fread into memory
rawmemchr through and pick out the words
send each word through the hash function
create chain links for any index where collisions occur

// accept the incoming test words
Run the test word through the hash function
compare to the existing table / linked list
return the result of the comparison

有了 150K 单词的字典和高达 6MB 的输入文本，我能够在大约半秒内准确地进行拼写检查。

但是，当我查看来自输入文本的单词时，很明显这些单词中有很大一部分是常见的(例如“the”、“and”、“for”)，而且大部分拼写错误的单词也会被多次检查。

我的直觉告诉我应该能够“缓存”“好的命中”和“坏的命中”，这样我就不会一遍又一遍地散列相同的词来进行表查找。尽管当前结果非常接近 O(1)，但我觉得我应该能够通过重新评估我的方法来缩短几微秒的时间。

例如，在我加载字典后，输入的文本可能只有 8MB，只有这个:“missspeling”。因此，与其一遍又一遍地散列/检查同一个词(以计算费用为代价)，我想了解是否有一种方法可以以编程方式丢弃已经被散列和拒绝的词，但是比散列/检查本身。 (我正在使用 MurmurHash3，fwiw)。

我意识到理论上的性能改进仅限于输入文本较长且重复拼写错误较多的情况。根据我评估过的一些输入文本，以下是一些结果:

Unique Misspellings: 6960
Total Misspellings:  17845
Words in dictionary: 143091
Words in input text: 1150970
Total Time:          0.56 seconds

Unique Misspellings: 8348
Total Misspellings:  45691
Words in dictionary: 143091
Words in input text: 904612
Total Time:          0.83 seconds 

在第二个示例运行中，您可以看到我必须为每个拼错的单词返回哈希表大约 5.5 次!这对我来说似乎很疯狂，而且我觉得必须有一种更有效的方法来解决这种情况，因为我的程序的大部分时间都花在了哈希函数上。

我可以实现 Posix 线程(它在 8 核系统上运行)来缩短程序时间，但我更感兴趣的是改进围绕该问题的方法和思维过程。

抱歉，啰嗦了这么久，但这是我的第一篇 Stack Overflow 帖子，我正在努力做到全面。我在发布前进行了搜索，但大多数其他“拼写检查”帖子都与“如何”相关，而不是“改进”。我很感谢让我指出正确方向的建议。

http://github.com/Ganellon/spell_check

Answer 1

这是一个很好解决的问题。 ;-) 您应该查看一个名为 trie 的数据结构.特里树是由单个字符构成的树，因此路径 表示信息。每个节点都包含您可以合法添加到当前前缀的字母。当一个字母是一个有效的单词时，它也会被记录下来。

四个字:

root-> [a]-> [a]-> [r]-> [d]-> [v]-> [a]-> [r]-> [k*]->[s*]
             [b]
                \> [a]-> [c]-> [i*]
                               [u]-> [s*]

这将代表“aardvark”、“aardvarks”、“abaci”和“abacus”。节点是垂直连续的，所以第2个字母[ab]是一个节点，第5个字母[i*u]是一个节点。

一个字符一个字符地遍历 trie 树，并在您按下空格时检查一个有效的词。如果你不能用你拥有的角色遍历，那就是一个坏词。如果您在按下空格时找不到有效的词，那就是一个坏词。

这是 O(n) 的处理时间(n = 字长)，而且速度非常非常快。构建 trie 会消耗大量 RAM，但我认为您不关心这个。