#Mini项目 (单词纠错)

[TOC]

#1. 编辑距离 : 需要动作的次数(比较多种组合的编辑距离,找到编辑距离最小的)

插入 删除 修改

##1.1. 动态规划(找出最小编辑距离) 1. 找出编辑最小的集合 2. 在通过排序 找出查询频率最高的 3. 编辑距离过高(>3)可以直接抛弃 4. 每个候选词可以放到优先级队列里

##1.2. 数据结构设计 <最小编辑距离,搜索频率>(只推荐给用户一个词条) (小根堆)

单词 最小编辑距离 搜索词频

#2. 优化过程 减少计算编辑距离的范围(剪枝): 限制编剧距离

1. 字符串长度的差值大于极限值(自定义1, 2, 3的编辑距离),直接舍弃
2. 建立索引: 找出查询词每个单词取并集
3. 剔除高频出现的字母
4. 缓存(定时器)

#3. UDP服务器 监听和调度 线程池(随机调度或者轮询) 运行以上工作 计算后 返回客户端

##3.1. 线程函数设计 线程函数

1. 候选词集
2. cache
3. cache更新磁盘(定期汇总cache的变量到一个专门的扫描线程,统一写入磁盘,再由线程读取回去) map hashmap

#4. 中文纠错 GBK编码

• ASCII 0-127
• GBK编码 2个字节表示

#5. 其他无关事件 ASN google protobuffer 将数据结构转换成头文件

#建立索引 key i value ipad phone

src bin conf(端口文件路径) log(出错路径,操作记录) data inc lib makefile

读数据文件