百度笔试题目剖析――拼写纠错 - summerbell - ITeye技术网站
在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典，请你设计一个拼写纠错的程序。
(1)请描述你解决这个问题的思路；
(2)请给出主要的处理流程，算法，以及算法的复杂度；
(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。
网上流传解答：
(1)思路：
字典以字母键树组织，在用户输入同时匹配
(2)流程：
每输入一个字母：
沿字典树向下一层，
a)若可以顺利下行，则继续至结束，给出结果；
b)若该处不能匹配，纠错处理，给出拼写建议,继续至a)；
算法：
1.在字典中查找单词
字典采用27叉树组织，每个节点对应一个字母,查找就是一个字母一个字母匹配.算法时间就是单词的长度k。
2.纠错算法
情况:当输入的最后一个字母不能匹配时就提示出错,简化出错处理，动态提示可能处理方法：
(a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议；
(b)当前字母拼写错误：当前字母的键盘相邻作为提示；(只是简单的描述，可以有更多的)根据分析字典特征和用户单词已输入部分选择(a)，(b)处理
Read full article from 百度笔试题目剖析――拼写纠错 - summerbell - ITeye技术网站
No comments:
Post a Comment