这是我的伪代码：
// 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,但是：“误导”.因此,我不想反复哈希/检查相同的单词(以计算费用),我想了解是否有一种方法可以编程方式丢弃已经被散列和拒绝的单词,但是以一种比哈希/检查本身. (我正在使用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帖子,我正在努力做到彻底.我在发布之前进行了搜索,但大多数其他“拼写检查”帖子与“如何”而不是“改进”相关.我很感激能够让我指出正确方向的建议.
解决方法
四个字：
root-> [a]-> [a]-> [r]-> [d]-> [v]-> [a]-> [r]-> [k*]->[s*]
[b]
\> [a]-> [c]-> [i*]
[u]-> [s*]
这将代表“aardvark”,“aardvarks”,“abaci”和“abacus”.节点是垂直连续的,因此第二个字母[ab]是一个节点,第五个字母[i * u]是一个节点.
逐个字符遍历特里字符,并在您触及空格时检查有效字.如果你不能用你所拥有的角色进行遍历,那么这就是一个坏词.如果你在击中太空时找不到有效的东西,这是一个坏词.
这是O(n)处理(n =字长),它非常非常快.构建trie将占用大量内存,但你不关心我的想法.
