拼写检查

拼写检查

拼音

完整拼音

拼音缩写

中文纠错

比如输入”背天而驰”，返回“背道而驰”的相似词

输入“一股作气 背天而驰” 返回“一鼓作气 背道而驰”

即会将词组以空格分为两个词“一股作气”和“背天而驰”然后再分别进行拼写检查。

分别返回“一鼓作气”和“背道而驰”，可以合并结果或者不合并结果。

词库数组

词库来源以文件形式存在，文件中每一行为一个词，文件放在dict文件夹下

以方便扩展，只要将相同格式的词库文件增加到该目录下。

词如类似：

AB

BCD

CDE

DEF

。。。。

搜索词库：

搜索次数 关键词

100 ABC

90 BCD

80 CBD

...

词库的索引

为词库建立索引，采用一元切词，使用其它切词的方法可能会找不到相似的词

以TreeMap>结构存储，其中String为元切出的单个中文字符，list存储相应文档，文档有三个属性

/**

* 唯一的标识

*/

private int id;

/**

* 文档内容

*/

private String text;

/**

* 搜索次数

*/

private int freq;

例如：

词库为：AB,BCD,CDE,DEA...

下标 0 1 2 3

DOC为：[0,”AB”,0]，[1,”BCD”,0] ，[2,”CDE”,0] ，[3,”DEA”,0]

索引如下：

A->[0,”AB”,0],[3,”DEA”,0]

B->[0,”AB”,0], [1,”BCD”,0]

C-> [1,”BCD”,0]，[2,”CDE”,0]

D->[1,”BCD”,0] ，[2,”CDE”,0] ，[3,”DEA”,0]

E->[2,”CDE”,0] ，[3,”DEA”,0]

有个问题，索引对应的用什么结构来存储可以提升效率？HashSet？或者？ArrayList

这里跟光亚讨论后，不用HashSet了，用回ArrayList就可以了。关于可能重复的问题，在建索引时就可以去除，而建索引的时间多一点没所谓，只要搜索速度提升就可以了。

当然还有另一个优化方向，即是内存的优化，不一定是邮ArrayList来存储对象，可以

采用存储简单的基本类型数组，这样可节省些内存空间。

粗匹配

从查询结果中过滤掉自身

一元切词方法：

比如输入ABC->A,B,C，查找文档

A->[0,”AB”,0],[3,”DEA”,0]

B->[0,”AB”,0], [1,”BCD”,0]

C-> [1,”BCD”,0]，[2,”CDE”,0]

合并结果为文档 [0,”AB”,0]，[1,”BCD”,0] ，[2,”CDE”,0]

这里有个问题，到底应该是取出所有文档，还是只取出部分文档？

取出所有文档，则数量比较多，可能会影响性能？

如果不取出所有文档，取出部分文档，是如何取舍才可以做到最优？

我觉得这里可以优化。？

细匹配

计算查询结果中的每个单词和输入word的编辑距离，过滤掉部分距离过大的单词

有三种算法：NGram，Levenstein，JaroWinkler。

由于Ngram的性能比较好，所以采用它。

 Ngram

 一元切词的结果为：０，１，２，３对应的词为：

AB,BCD,CDE,DEA

与ABCD比较

AB＝１

BCD＝２

CDE＝１

DEA＝１

排序后结果为：１，０，２，３

 Levenstein

 JaroWinkler

拼写检查建议结果

结果的排序优先级：

1. 搜索次数优先比较，普通词库中的搜索次数默认为0，搜索词库有记录。搜索次数越大，则表示越优先

2. 编辑距离为衡量：1表示两个字符串完全相同，0表示两个字符串具有最大的不相似程度

3. public final int compareTo(SuggestWord a) {

4. // first criteria: the edit distance

5. if (freq > a.freq) {

6. return 1;

7. }

8. if (freq < a.freq) {

9. return -1;

10. }

11. // second criteria (if first criteria is equal): the popularity

12. if (score > a.score) {

13. return 1;

14. }

15. if (score < a.score) {

16. return -1;

17. }

18. return 0;

19. }

放入以搜索次数与编辑距离分数为衡量指标的堆中，堆的长度人为确定，具体根据要查询的建议单词的多少确定。

当堆的长度满之后，有几种情况可以考虑：

1) 立即返回结果

2) 继续匹配，得到最优结果

3) 以某个阈值作业比较，比如是建议单词的10倍的比较次数，当超过这个次数时，就不再比较

返回结果，注意此处的结果要是以编辑距离增序的结果（使用优先队列的函数可以达到此要求）。

跟关键词一样的词忽略，编辑距离太大也忽略。

返回排在前面的几个结果。

测试

//通过简单的测试，在80万左右的词汇量时，每一次粗匹配的文档数量大约在一万左右。

再经过细匹配后，得到相应的建议结果，所需的时间在40 ms左右，主要是本机测试，没有在服务器上测试 。

今天跟光亚讨论了一下，觉得这个性能瓶颈可以解决掉，采用循环二元切词，跟组合交集来减少文档数量。

 采用二元循环切词，比如ABCD-> AB ,BC,CD,DA

这个就可以解决找不到相应文档的方案，比如，黄飞鸿，如果用户输入的是，黄中鸿，以原先的二元切词方案：黄中，中鸿，这样就不会找到黄飞鸿这个词了。。

现在换回，黄飞鸿-> 黄飞，飞鸿 ，鸿黄

输入黄中鸿-》黄中，中鸿，鸿黄

鸿黄-》黄飞鸿，就可以找到了。

之前采用的是一元切词，每次取出的文档大约有一万个，可能就在这个瓶颈上。

改用二元切词应该可以小一个数量级了。控制在10ms内应该可以。

 减少文档方式，之前想到的是用并集，也即是将匹配到的文档全都拿出来，可能文档会多一些。但这里也是可以再优化的，即采用组合交集。

比如ABC->AB,BC,CA

AB找到集合X

BC找到集合 Y

CA找到集合Z

组合交集，XYZ,XY,XZ,YZ

如果上面得出的结果太少，则可以再运用并集，X,Y,Z。

拼音的检查

比如用户输入：kaihua

返回：开花，开化

准备词库。

转化相应的拼写

使用第三方包pinyin4j，将中文转换为相应的拼音。比如：中国-> zhongguo, zhong guo, zg(拼音缩写)

建立索引

因为一个拼音是对应多个中文词的，所以建立个数据结构，以Map>的形式

比如 kaihua-》开花，开化

检查

用户输入拼音，zhongguo

通过Map找到对应的中文集合，其中以某个权重来排序（可能是以搜索量），并反回某个数量的结果，结果以字符串数组形式返回。