最近研究汉字转拼音，想到了拼音模糊搜索，每个网站都有关键字提示系统，自己粗略的写了一个，速度还不错，但一看内存，吓了一大跳，200多个关键字4G多内存，于是研究了一下关键字提示的算法，也就有了本文。
由于这个算法的细节过多，只放片段代码有可能误导读者，所以本篇文章不放代码，有兴趣的同学可以下载源码研究一下。
一、目前各大网站的关键字提示系统测试：
关键字：程序员
检验标准：在搜索栏输入“程序员”相关字符或拼音，弹出的关键字是否包含“程序员”，包含为判断为成功，否则为失败
百度：程xy （成功） 程xuy（成功）程xuyuan（成功）程xyuan（失败）cxy（成功）chengxy（成功）cxuy （成功）cheng序y（成功）c序y（成功）c序yuan（失败）cx员（成功）
淘宝：程xy （失败） 程xuy（成功）程xuyuan（成功）程xyuan（失败）cxy（失败）chengxy（失败）cxuy （失败） cheng序y（失败）c序y（失败）c序yuan（失败）cx员（失败）
知乎：程xy （失败） 程xuy（失败）程xuyuan（成功）程xyuan（成功）cxy（失败）chengxy（成功）cxuy （失败） cheng序y（失败）c序y（失败）c序yuan（失败）cx员（失败）
搜狗：程xy （失败） 程xuy（成功）程xuyuan（成功）程xyuan（失败）cxy（失败）chengxy（失败）cxuy （失败） cheng序y（成功）c序y（失败）c序yuan（失败）cx员（成功）
360搜索：程xy （成功） 程xuy（成功）程xuyuan（成功）程xyuan（失败）cxy（失败）chengxy（失败）cxuy （失败） cheng序y（成功）c序y（成功）c序yuan（失败）cx员（成功）
统计：百度9，淘宝2，知乎3，搜狗4，360搜索6
关键字提示能力：百度>360搜索>搜狗>知乎>淘宝
个人评价：百度的提示方案是最好的，也符合一些容易忘字的用户输入观。(什么？你说输入法能解决，嗯，这是一个方法，但是，对于专业词汇，一些懒汉和电脑小白，他们才不会去下特定的词库)
二、当前绝大数网站使用的技术：
网上有关关键字提示的技术方案主要有以下两种：
1、使用sql语名的like。
2、使用搜索引擎：lucene、solr、elasticsearch等。
简略评论一下：
第一种是最简单的，数据表一列放关键字，另一列存放关键字所对应的拼音首字母，这种方案只支持纯汉字或拼音首字母的搜索，不支持汉字+拼音，也不支持全拼。这种方案最简单，问题也最多。在手机端搜索时，谁会删除前面打好的字，转成拼音首字母。
第二种是有效的方法，要加机器，加机器就意味着要拿钱，更重要的是增加学习成本，动手写什么类。
三、我的关键字提示系统算法原理：
我的目标是写出一个能支持汉字、拼音、拼音首字母混合的提示系统，速度要快，内存消耗不要太大。
方案如下：
1、速度要快，第一个就想到tried tree。
2、如果tried tree的节点都设置返回值，内存消耗严重。所以每个节点设置返回值所在的区间。
3、节点返回的是区间，这需要关键字排列。
4、提示系统要支持汉字、拼音、拼音首字母混合，就要将每个节点划分成三个节点：拼音首字母、拼音、汉字。
5、关键字排列方式为：首字母+拼音+汉字+下一个汉字排列。
6、匹配方式跟 tried tree一样，注意的是：在匹配拼音、拼音首字母时，将子节点全部记录，用于下一次匹配。
上面方案，对应的类是PinYinSearch，详见开源项目。
四、关键字提示系统算法改进：
PinYinSearch对于10W以下的关键字来说，绰绰有余。然而现实中，关键字大于10W的情况很多，如：关键字111.9W个，总字数达到512.6W字时，我们会发现这程序占内存太多了，2799M多。所以我们要改成这代码。
于是我们开始查找相关方案：
1、网上搜索代替tried tree的解决方案，找到“双数组trie树”。
2、研究代码我们会发现几点：1、汉字首拼音最多26个，用byte类型足够了，2、拼音最多500个，用ushort足够了。
3、当我们将汉字、拼音转成ushort类型时，我们会发现一个好处，当输入汉字进来匹配时，我们必须将汉字转成ushort，当汉字不存在，就没有相就的ushort，我们就可以直接返回空集合。
上面方案，对应的类是PinYinSearchEx，详见开源项目。
五、关键字提示系统算法测试：
测试环境：win10 cpu：i5-5200U 内存：12G DEBUG环境下
关键字：总共111.9W个，总字数达到512.6WW。
测试关键字：程xy、程xuy、程xuyuan、程xyuan、cxy、chengxy、cxuy、cheng序y、c序y、c序yuan、cx员。
运行内存：186M。
输出大小：122M。
运行速度：4秒钟运行1000次。
六、开源项目：
项目名称：ToolGood.Words
GitHub：https://github.com/toolgood/ToolGood.Words
码云：http://git.oschina.net/toolgood/ToolGood.Words
测试代码：【ToolGood.Words.Test】->【PinYinSearch】->【PinYinSearchExTest.cs】
注：
感觉运行速度才有改善的地方，就不发到首页了。