项目一用户输入助手spellcorrect.pdfVIP

三、项目安排：

1.第一阶段：离线部分（独立的main函数）

1)创建词典，词典中的每一条记录的格式为：

Wordfrequency

注意：加载候选词文件时，把候选词中的大写全部转成小写，候选词文件的路径通过配置文

件读入。

涉及到类有Configuration,Dictionary

2)创建索引文件

查询词query没有必要与所有的候选词来比较，例如，查询词是nike，候选词是appl，这两

个词没有任何字符有交集，这种情况没有必要计算编辑距离。如何利用索引来缩小候选词，

以达到提高计算性能的目的：当query是nike的时候，我们只需要查找候选词包含n或者i

或者k或者e的这些词。

n：ipone，iphonei：ipone，iphone，

nikek：nike，kindlee：nike，

iphone，ipone，kindlel：loop，appl

s：snoopy

国中间其中

2.第二阶段：部分，搭框架。(独立的main函数)

将之前学过的线程池，网络编程模块的内容组合起来，形成一个可测试的框架。即将客

户端传递过来的查询词封装成一个任务，交给线程池处理，最后将处理好的结果直接发送给

客户端．

3.第三阶段：业务逻辑

任务的具体业务逻辑是：

获取到客户端传递过来的查询词，再从索引之中查找与之相近的候选词，选取到最

合适的候选词再将其发送给客户端。发送时采用JSON数据格式（开源库jsoncpp）封

包。

候选词的选取包括以下几个部分：

1)实现最小编辑距离算法计算候选词与查询词的相似度

2)候选词选择策略：

a.优先比较最小编辑距离；

b.在编辑距离相同的条件下，再比较候选词的词频；

C.在词频相同的条件下，按字母表顺序比较候选词

获取k个候选词（例如3个），需要使用优先级队列

4.第四阶段：优化扩展点

1)添加缓存系统【必做】

分为内存cache和磁盘cache，内存cache就是一个map或者hash_map,磁盘cache就是一

个文件，每次启动时从磁盘读入cache文件来初始化内存cache，服务时，每隔10分钟

将内存cache回写磁盘（数据持久化）。每个线程一个cache，这些cache的数据就会不一

致，轮询写磁盘。

【缓存扩展阅读】（重要，与找工作强相关）

缓存、缓存算法和缓存框架简介

我是分界线

【以下内容供学有余力的童鞋选做】

A.淘汰缓存策略：

如果每个cache中的记录个数不受限制，那总会有一个时刻，内存不够用了，从而

导致整个服务器程序。那应该如何解决该问题呢？

解决方案：可以考虑采用限制cache中记录的个数count（如10000个），当cache中记录的

个数达到10000时，应该采用一种机制或策略淘汰现有cache中的