英文拼写纠错

　　在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典，请你设计一个拼写纠错的程序。

　　(1)请描述你解决这个问题的思路;

　　(2)请给出主要的处理流程，算法，以及算法的复杂度;

　　(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。

　　解答：

　　(1)思路 :

　　字典以字母键树组织，在用户输入同时匹配

　　(2)流程:

　　每输入一个字母：

　　沿字典树向下一层，

　　a)若可以顺利下行，则继续至结束，给出结果;

　　b)若该处不能匹配，纠错处理，给出拼写建议,继续至a);

　　算法:

　　1.在字典中查找单词

　　字典采用27叉树组织,每个节点对应一个字母,查找就是一个字母一个字母匹配.算法时间就是单词的长度k.

　　2.纠错算法

　　情况:当输入的最后一个字母不能匹配时就提示出错,简化出错处理，动态提示可能处理方法:

　　(a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议;

　　(b)当前字母拼写错误：当前字母的键盘相邻作为提示;(只是简单的描述，可以有更多的)

　　根据分析字典特征和用户单词已输入部分选择(a),(b)处理

　　复杂性分析：影响算法的效率主要是字典的实现与纠错处理

　　(a)字典的实现已有成熟的算法，改进不大，也不会成为瓶颈;

　　(b)纠错策略要简单有效 ,如前述情况，是线性复杂度;

　　(3)改进

　　策略选择最是重要，可以采用统计学习的方法改进。

　　寻找热门查询

　　搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

　　(1)请描述你解决这个问题的思路;

　　(2)请给出主要的处理流程，算法，以及算法的复杂度。

　　解答:

　　(1)思路：

　　用哈希做

　　(2)

　　首先逐次读入查询串，算哈希值，保存在内存数组中，同时统计频度(注意值与日志项对应关系)选出前十的频度，取出对应的日志串，简单不过了。

　　哈希的设计是关键。

　　集合合并

　　给定一个字符串的集合，格式如：

　　{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}

　　要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}

　　(1)请描述你解决这个问题的思路;

　　(2)请给出主要的处理流程，算法，以及算法的复杂度

　　(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。

　　解答:

　　(1)思路：先将集合按照大小排列后,优先考虑小的集合是否与大的集合有交集。有就合并，如果小集合与所有其他集合都没有交集，则独立。独立的集合在下一轮的比较中不用考虑。这样就可以尽量减少字符串的比较次数。当所有集合都独立的时候，就终止。

　　(2)处理流程：

　　1.将集合按照大小排序，组成集合合并待处理列表

　　2.选择最小的集合，找出与之有交集的集合，

　　如果有，合并之;

　　如果无，则与其它集合是独立集合，从待处理列表 中删除。

　　3.重复直到待处理列表为空

　　算法：

　　1。将集合按照大小从小到大排序,组成待处理的集合列表。

　　2。取出待处理集合列表中最小的集合，对于集合的每个元素，依次在其他集合中搜索是否有此元素存在：

　　1>若存在，则将此小集合与大集合合并，并根据大小插入对应的位置 。转3。

　　2>若不存在，则在该集合中取下一个元素。如果无下一个元素，即所有元素都不存在于其他集合。则表明此集合独立，从待处理集合列表中删除。并加入结果集合列表。转3。

　　3。如果待处理集合列表不为空，转2。如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。

　　算法复杂度分析：

　　假设集合的个数为n，最大的集合元素为m

　　排序的时间复杂度可以达到n*log(n)

　　然后对于元素在其他集合中查找，最坏情况下为(n-1)*m

　　查找一个集合是否与其他集合有交集的最坏情况是m*m*(n-1)

　　合并的时间复杂度不会超过查找集合有交集的最坏情况。

　　所以最终最坏时间复杂度为O(m*m*n*n)

　　需要说明的是：此算法的平均时间复杂度会很低，因为无论是查找还是合并，都是处于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先与最大的集合进行比较，这些都最大的回避了最坏情况。

　　(3)可能的改进：

　　首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及合并的效率增高。

　　另外，可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。

　　需要引入用户对搜索结果相关性的评分

　　需求：需要引入用户对搜索结果相关性的评分，100分制。希望用户的打分能帮助搜索引擎排序，但又避免恶意投票、作弊等。请设计一个比较公平的评分系统。

　　输入：N(整数)

　　输入：N(整数)

　　输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节

　　文件格式如下：

　　字符串/t数字/n

　　说明：

　　每行为1条记录;字符串中不含有/t。

　　数字描述的是该字符串的出现概率，小于等于100的整数。

　　多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出;

　　如果文件格式错误，程序也退出。

　　要求：

　　编写一个程序，输入为N(正整数)，读入文件A.txt，按照字符串出现概率随机地输出字符串，输出N条记录

　　例如：

　　输入文件A.txt

　　abc/t20

　　a/t30

　　de/t50

　　输入为：10

　　即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记录

　　以下为一次输出的结果,多次输出的结果可能不相同。

　　abc

　　a

　　de

　　de

　　abc

　　de

　　a

　　de

　　a

　　de

　　解答:

　　这个题目感觉意思有歧义。什么是按照字符串出现概率随机地输出字符串，输出N条记录?可以有几种理解。第一，每次掷骰子，掷出了哪个就输出哪个，不管前面输出了什么。第二，要考虑前面出现的字符串。按照题目里的例子，如果前面输出了两次abc，那接下来的无论随机出了什么数，都不能输出abc，最后的结果在数量上符合开始给的概率条件，只是顺序有所不同。这让我想起了排列组合里的袋中取黑球红球问题。把字符串abc，a，de当作2个红球，3个黑球和 5个白球，放入袋中。每次拿一个球出来，并记录拿出球的颜色。第一种情况就是拿出球后，把球放回袋中进行下一次抽取;而第二种自然就是不放回的抽取。