本文来自微信开发团队WeMobileDev公众号的技术分享。
1、前言
微信的移动客户端全文搜索中的多音字问题一直是搜索体验的痛点之一。微信客户端全文搜索在上线以后，也经常收到用户关于多音字问题的反馈。所以，微信全文搜索中的多音字搜索成了一个迫切需要解决的问题。本文重点讲述微信安卓客户端在SQLite FTS5的基础上，多音字问题的解决方案。
另外：微信团队在另一个文章《微信手机端的本地数据全文检索优化之路》 中，分享了更为详细的全文检索优化思路，建议有兴趣的开发者可以深入的看看。
建议：您也可以在微信客户端的sqlite数据库中找到本文中相关技术的真实实现，微信的SQLite样本库可在此下载《微信本地数据库破解版(含iOS、Android)，仅供学习研究 [附件下载]》（特别申明：微信的SQLite样本库仅供研究和学习之外，严禁用于商用业目的，所有权归微信所有）。
学习交流：
- 即时通讯开发交流群：320837163[推荐]
- 移动端IM开发入门文章：《新手入门一篇就够：从零开发移动端IM》
（本文同步发布于：http://www.52im.net/thread-1545-1-1.html）
2、相关文章
《腾讯技术分享：Android版手机QQ的缓存监控与优化实践》
《微信团队分享：iOS版微信的高性能通用key-value组件技术实践》
《微信团队分享：iOS版微信是如何防止特殊字符导致的炸群、APP崩溃的？》
《腾讯技术分享：Android手Q的线程死锁监控系统技术实践》
《腾讯团队分享 ：一次手Q聊天界面中图片显示bug的追踪过程分享》
《微信团队披露：微信界面卡死超级bug“15。。。。”的来龙去脉》
《微信客户端团队负责人技术访谈：如何着手客户端性能监控和优化》
《微信团队原创分享：微信客户端SQLite数据库损坏修复实践》
《移动端IM实践：Android版微信如何大幅提升交互性能（一）》
《移动端IM实践：Android版微信如何大幅提升交互性能（二）》
《信鸽团队原创：一起走过 iOS10 上消息推送(APNS)的坑》
3、微信的全文检索需求
搜索形式：
拼音前缀搜索，中文和拼音不能混合搜索，输入拼音必须为连续汉字的全拼音或者短拼音。
搜索内容：
联系人、群聊以及公众号的备注和昵称（最大长度为16个中文字符）。
例如。
联系人A，昵称为“王宏伟”，那么通过以下几种方式都需要搜索到联系人A的昵称：
4、词表方案
中文全文搜索引擎如果需要支持拼音，就需要把输入的中文字符，转化为拼音字母，如果不考虑多音字的情况，我们只需要一张单个汉字的拼音表即可实现转化，但是在多音字的情况下，由于每个汉字在不同的词语当中的读音都有可能不一样，所以，为了使得每个中文字符能够获取到准确的拼音，就需要引入一份词语拼音对应表。
众所周知，汉语博大精深，常用的汉字有20777个，而词语（包括成语）的汉字个数为2到16个，同一个汉字在不同词语中读音有可能不一样。
所以汉语词语转化为拼音有如下两个方案：
1）穷举词语表；
2）采用概率模型，通过训练分类器模型，获取中文字符拼音。
第一种方案对存储空间的要求非常高，对资源的消耗过大。
第二种方案，通过在现有的TTS（Text To Speech）模型中，把汉字转拼音读音的模型拆出来，初步搭建一个概率模型，在初步的调优后，得到一个1个G的拼音模型，识别拼音的准确在可接受范围内。由于模型大小为GB级别，初步考虑是将模型放到后台处理。
处理流程如下图：
优点：
客户端无改动，可以快速覆盖所有版本客户端。
缺点：
用户修改备注或者昵称后，需要等待后台下发拼音后才能有正确的拼音索引，导致拼音索引建立不够及时。微信用户量巨大，用户修改备注和昵称的频次非常高，每天都有几十亿次修改，导致后台处理这部分的运算量和耗时非常严重，需要增加较大成本。
5、字表方案
常用汉字有20777个，总体大小为200KB，可以直接带到客户端中，并且查询的时间复杂度为O(1)，在数据量方面是可以接受的。
优点：
用户修改昵称或者备注以后，能够快速响应并及时建立索引；
将后台巨大的计算量均摊到用户手机上，节省成本；
对于姓名中汉字的读音，可以用任意一个读音搜索出来。
缺点：
在用户体验上，词语中的多音字可以用任意该汉字的拼音搜索出来；
在综合考虑用户体验和性能问题后，最后微信选择了字表方案。
6、客户端索引方案
在确定字表方案后，需要在客户端本地使用SQLite FTS5建立索引。因为拼音搜索主要是采用前缀搜索的方式，所以建立索引的内容以及方式需要考虑FTS5前缀搜索的过程。
路径（1）是在建立索引表时使用Prefix索引，所以用户在输入Query时，直接通过Hash方法查找前缀索引表即可找到所有以Query为前缀的结果。
路径（2）是在建立索引表时未使用Prefix索引，所以用户在输入Query时，FTS5通过临时搭建一个前缀树来查找以Query为Preifx的索引集合。
从时间复杂度上，路径1具有明显优势，所以在建立索引时，需要加入Prefix配置：
6.1 索引方案一
考虑到用户输入时是连续输入，并不会考虑跨拼音问题。
例如，用户搜索备注“市委书记”的拼音，会可能采用如下的Query：
shi
shiweishuj
sw
根据以上用户输入习惯以及FTS5前缀搜索原理，采用第一个索引方案：
在FTS5匹配以上Query时，用户1、2两种输入都作为"shiweishuji"的前缀被匹配，而3的输入会作为“swsj”的前缀被匹配。
6.2 索引方案二
索引方案一仅考虑用户从拼音的头部开始搜索，并没有考虑从中间开始搜索。
例如以下的Query：
shuji
sj
所以，需要建立索引时，需要把每个汉字的拼音作为前缀建立到索引中，如下表：
6.3 索引方案三
方案一和方案二是在不考虑多音字的情况的索引方案，当引入了多音字以后，在组合拼音字符串时，每一个拼音都可能存在多种情况。
以下为用户备注“张靓颖”的索引：
当昵称“张靓颖”建立索引以后，得到如下索引结构：
TermOffset：表示一个词语在某一个Document中的偏移；
DocId：Document的唯一ID。
通过一个DocId和一个TermOffset可以定位一个词语。而SQLite FTS5正是通过搜索一个词语来找到对应的DocId，通过TermOffset来定位该词语在Document中的位置。
方案优点：
实现较为简单；
可覆盖所有多音字情况。
方案缺点：
索引数据量过大；
考虑常用汉字一共20777个，其中多音字2659个，多音字占比12.7%，平均每个多音字有2.14个拼音。
在微信场景中，联系人的备注和昵称最大字符长度为16个字符，所以我们假设每个昵称的字符为16个汉字，其中，每个汉字的拼音长度为最长度（7个英文字母+1个短拼音英文字母）。
一般场景：
其中20777个汉字当中，出现在昵称中的概率一样，所以16个字符中，大约会出现3个多音字，得到如下公式：
极限场景：
昵称中每一个字都是多音字，每个多音字都有4个读音，例如“么么么么么么么么么么么么么么么么”，得到如下公式：
从以上两种场景中可以看出，方案三在极限场景中会出现占用超大数据量的情况，所以方案三不可用。
6.4 索引方案四
方案三通过穷举法来列举所有拼音组合，核心在于通过空间换区时间，在所需要的空间过于巨大时，可以采取折中的方案来实现。
在汉语中，一个同样意义的实体通过两个不同的词语来表示，称这两个不同的词语为同义词，在数据上表示为（词语A，词语B）=（意义C），那么在多音字的情况来看，同样可以表示为（拼音A，拼音B）=（汉字C）。方案四的核心在于通过同义词的方式来表示多种拼音的组合。
在SQLite FTS5中，一个词语可以通过一个DocId和一个TermOffset来定位，所以当两个词语拥有同一个DocId和TermOffset时，就可以说这两个词语为同义词了，也就有了如下的索引方案：
方案优点：
索引数据量小：
1）一般情况：
2）极限情况：
建立索引速度快。
方案缺点：
默认分词器不能适配多音字的拼音数据；
索引中的数据不能直接对应用户输入。
为了解决方案四的两个问题，我们引入了多音字分词器，并且做了用户输入预处理。
7、多音字分词器
SQLite FTS5默认的分词器的分隔符都是固定的，所以，在识别拼音字符时，会当成英文字母来分词。为了能够达到需要的索引结构，我们引入了二级分隔符，使用分号“；”分隔不同汉字以及“，”分隔同一个汉字的不同拼音。
以下是多音字分词器的分词流程：
8、用户输入预处理
当用户的输入为连续拼音时，由于索引中不存在直接对应的Term，所以需要把用户输入的Query拆解成为索引当中可能存在的Term。
假设用户输入拼音：zhuang，根据短拼音和全拼音的规则，可得到如下7中搜索组合：
考虑到最后一个拼音为前缀搜索，所以，在列举拼音组合时，前面都需要考虑符合完整的拼音，最后一个可以只考虑是否是某个拼音的前缀。
实现这个算法可以通过把所有的拼音作为输入，构建一颗前缀树，能够把整个Query拼音拆解的时间复杂度降低到O(nlgn)。
最后，把所有的拼音组合情况都写到SQL中：
9、方案的实际效果
对比方案三和方案四，在拼音数据上有较为明显的提升，提升的范围在50%左右。
由于联系人拼音数据的减少，使得单个联系人的数据量下降，减少了Insert SQL的执行时间，建立联系人索引的时间也有较为明显的降低，减少30%左右。
在搜索Query的时间上，多音字方案因为拼音组合的多样性，增加了查找HashTable的次数，但是由于搜索HashTable的时间复杂度为O(1)，而拼音组合在有限字符的query下不多（小于20个），所以增加时间不多，但是由于数据量的减少，ORM的时间缩短，搜索Query的时间有15%左右的提升。
更为详细的微信全文检索优化思路请见《微信手机端的本地数据全文检索优化之路》。微信的本地SQLite研究样本可从此下载《微信本地数据库破解版(含iOS、Android)，仅供学习研究 [附件下载]》（特别申明：微信的SQLite样本库仅供研究和学习之外，严禁用于商用业目的，所有权归微信所有）。
附录：更多微信、QQ的文章
[1] QQ、微信团队原创技术文章：
《腾讯技术分享：Android版手机QQ的缓存监控与优化实践》
《微信团队分享：iOS版微信的高性能通用key-value组件技术实践》
《微信团队分享：iOS版微信是如何防止特殊字符导致的炸群、APP崩溃的？》
《腾讯技术分享：Android手Q的线程死锁监控系统技术实践》
《QQ音乐团队分享：Android中的图片压缩技术详解（上篇）》
《QQ音乐团队分享：Android中的图片压缩技术详解（下篇）》
《腾讯团队分享 ：一次手Q聊天界面中图片显示bug的追踪过程分享》
《微信团队分享：微信Android版小视频编码填过的那些坑》
《微信团队披露：微信界面卡死超级bug“15。。。。”的来龙去脉》
《月活8.89亿的超级IM微信是如何进行Android端兼容测试的》
《微信客户端团队负责人技术访谈：如何着手客户端性能监控和优化》
《微信团队原创分享：Android版微信的臃肿之困与模块化实践之路》
《微信团队原创分享：微信客户端SQLite数据库损坏修复实践》
《腾讯原创分享(一)：如何大幅提升移动网络下手机QQ的图片传输速度和成功率》
《腾讯原创分享(二)：如何大幅压缩移动网络下APP的流量消耗（下篇）》
《腾讯原创分享(二)：如何大幅压缩移动网络下APP的流量消耗（上篇）》
《如约而至：微信自用的移动端IM网络层跨平台组件库Mars已正式开源》
《开源libco库：单机千万连接、支撑微信8亿用户的后台框架基石 [源码下载]》
《微信新一代通信安全解决方案：基于TLS1.3的MMTLS详解》
《微信团队原创分享：Android版微信后台保活实战分享(进程保活篇)》
《微信团队原创分享：Android版微信后台保活实战分享(网络保活篇)》
《Android版微信从300KB到30MB的技术演进(PPT讲稿) [附件下载]》
《微信团队原创分享：Android版微信从300KB到30MB的技术演进》
《微信技术总监谈架构：微信之道——大道至简(PPT讲稿) [附件下载]》
《微信海量用户背后的后台系统存储架构(视频+PPT) [附件下载]》
《微信异步化改造实践：8亿月活、单机千万连接背后的后台解决方案》
《架构之道：3个程序员成就微信朋友圈日均10亿发布量[有视频]》
《微信团队原创分享：Android内存泄漏监控和优化技巧总结》
《微信团队原创Android资源混淆工具：AndResGuard [有源码]》
《移动端IM实践：Android版微信如何大幅提升交互性能（一）》
《移动端IM实践：Android版微信如何大幅提升交互性能（二）》
《移动端IM实践：WhatsApp、Line、微信的心跳策略分析》
《移动端IM实践：谷歌消息推送服务(GCM)研究（来自微信）》
《信鸽团队原创：一起走过 iOS10 上消息推送(APNS)的坑》
>> 更多同类文章 ……
[2] 有关QQ、微信的技术故事：
《技术往事：微信估值已超5千亿，雷军曾有机会收编张小龙及其Foxmail》
《2017微信数据报告：日活跃用户达9亿、日发消息380亿条》
《技术往事：创业初期的腾讯——16年前的冬天，谁动了马化腾的代码》
《技术往事：史上最全QQ图标变迁过程，追寻IM巨人的演进历史》
《开发往事：深度讲述2010到2015，微信一路风雨的背后》
《开发往事：记录微信3.0版背后的故事（距微信1.0发布9个月时）》
>> 更多同类文章 ……
（本文同步发布于：http://www.52im.net/thread-1545-1-1.html）
