移动客户端多音字搜索
本文首次发表在《程序员》杂志 2018 年 02 月期。
前言
移动客户端全文搜索中的多音字问题一直是搜索体验的痛点之一。微信客户端全文搜索在上线以后，也经常收到用户关于多音字问题的反馈。所以，微信全文搜索中的多音字搜索成了一个迫切需要解决的问题。本文重点讲述微信安卓客户端在SQLite FTS5的基础上，多音字问题的解决方案。
搜索形式：拼音前缀搜索，中文和拼音不能混合搜索，输入拼音必须为连续汉字的全拼音或者短拼音
搜索内容：联系人、群聊以及公众号的备注和昵称（最大长度为16个中文字符）
例如
联系人A，昵称为“王宏伟”，那么通过以下几种方式都需要搜索到联系人A的昵称
中文全文搜索引擎如果需要支持拼音，就需要把输入的中文字符，转化为拼音字母，如果不考虑多音字的情况，我们只需要一张单个汉字的拼音表即可实现转化，但是在多音字的情况下，由于每个汉字在不同的词语当中的读音都有可能不一样，所以，为了使得每个中文字符能够获取到准确的拼音，就需要引入一份词语拼音对应表。
众所周知，汉语博大精深，常用的汉字有20777个，而词语（包括成语）的汉字个数为2到16个，同一个汉字在不同词语中读音有可能不一样，所以汉语词语转化为拼音有如下两个方案：
穷举词语表
采用概率模型，通过训练分类器模型，获取中文字符拼音
第一种方案对存储空间的要求非常高，对资源的消耗过大。
第二种方案，通过在现有的TTS（Text To Speech）模型中，把汉字转拼音读音的模型拆出来，初步搭建一个概率模型，在初步的调优后，得到一个1个G的拼音模型，识别拼音的准确在可接受范围内。由于模型大小为GB级别，初步考虑是将模型放到后台处理。
处理流程如下图：
优点：
客户端无改动，可以快速覆盖所有版本客户端。
缺点：
用户修改备注或者昵称后，需要等待后台下发拼音后才能有正确的拼音索引，导致拼音索引建立不够及时。
微信用户量巨大，用户修改备注和昵称的频次非常高，每天都有几十亿次修改，导致后台处理这部分的运算量和耗时非常严重，需要增加较大成本。
常用汉字有20777个，总体大小为200KB，可以直接带到客户端中，并且查询的时间复杂度为O(1)，在数据量方面是可以接受的。
优点：
用户修改昵称或者备注以后，能够快速响应并及时建立索引
将后台巨大的计算量均摊到用户手机上，节省成本
对于姓名中汉字的读音，可以用任意一个读音搜索出来
缺点：
在用户体验上，词语中的多音字可以用任意该汉字的拼音搜索出来
在综合考虑用户体验和性能问题后，最后微信选择了字表方案。
在确定字表方案后，需要在客户端本地使用SQLite FTS5建立索引。因为拼音搜索主要是采用前缀搜索的方式，所以建立索引的内容以及方式需要考虑FTS5前缀搜索的过程
路径（1）是在建立索引表时使用Prefix索引，所以用户在输入Query时，直接通过Hash方法查找前缀索引表即可找到所有以Query为前缀的结果。
路径（2）是在建立索引表时未使用Prefix索引，所以用户在输入Query时，FTS5通过临时搭建一个前缀树来查找以Query为Preifx的索引集合。
从时间复杂度上，路径1具有明显优势，所以在建立索引时，需要加入Prefix配置。
索引方案一
考虑到用户输入时是连续输入，并不会考虑跨拼音问题。例如，用户搜索备注“市委书记”的拼音，会可能采用如下的Query：
shi
shiweishuj
sw
根据以上用户输入习惯以及FTS5前缀搜索原理，采用第一个索引方案。
在FTS5匹配以上Query时，用户1、2两种输入都作为"shiweishuji"的前缀被匹配，而3的输入会作为“swsj”的前缀被匹配。索引方案二
索引方案一仅考虑用户从拼音的头部开始搜索，并没有考虑从中间开始搜索，例如以下的Query：
shuji
sj
所以，需要建立索引时，需要把每个汉字的拼音作为前缀建立到索引中，如下表：
索引方案三
方案一和方案二是在不考虑多音字的情况的索引方案，当引入了多音字以后，在组合拼音字符串时，每一个拼音都可能存在多种情况，以下为用户备注“张靓颖”的索引。
当昵称“张靓颖”建立索引以后，得到如下索引结构：
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个读音，例如“么么么么么么么么么么么么么么么么”，得到如下公式：
从以上两种场景中可以看出，方案三在极限场景中会出现占用超大数据量的情况，所以方案三不可用。索引方案四
方案三通过穷举法来列举所有拼音组合，核心在于通过空间换区时间，在所需要的空间过于巨大时，可以采取折中的方案来实现。
在汉语中，一个同样意义的实体通过两个不同的词语来表示，称这两个不同的词语为同义词，在数据上表示为（词语A，词语B）=（意义C），那么在多音字的情况来看，同样可以表示为（拼音A，拼音B）=（汉字C）。方案四的核心在于通过同义词的方式来表示多种拼音的组合。
在SQLite FTS5中，一个词语可以通过一个DocId和一个TermOffset来定位，所以当两个词语拥有同一个DocId和TermOffset时，就可以说这两个词语为同义词了，也就有了如下的索引方案：
方案优点：
索引数据量小
一般情况：
极限情况：
建立索引速度快
方案缺点：
默认分词器不能适配多音字的拼音数据
索引中的数据不能直接对应用户输入
为了解决方案四的两个问题，我们引入了多音字分词器，并且做了用户输入预处理。
SQLite FTS5默认的分词器的分隔符都是固定的，所以，在识别拼音字符时，会当成英文字母来分词。为了能够达到需要的索引结构，我们引入了二级分隔符，使用分号“；”分隔不同汉字以及“，”分隔同一个汉字的不同拼音。
以下是多音字分词器的分词流程：
用户输入预处理
当用户的输入为连续拼音时，由于索引中不存在直接对应的Term，所以需要把用户输入的Query拆解成为索引当中可能存在的Term。
假设用户输入拼音：zhuang，根据短拼音和全拼音的规则，可得到如下7中搜索组合
考虑到最后一个拼音为前缀搜索，所以，在列举拼音组合时，前面都需要考虑符合完整的拼音，最后一个可以只考虑是否是某个拼音的前缀。
实现这个算法可以通过把所有的拼音作为输入，构建一颗前缀树，能够把整个Query拼音拆解的时间复杂度降低到O(nlgn)。
最后，把所有的拼音组合情况都写到SQL中：
方案效果
对比方案三和方案四，在拼音数据上有较为明显的提升，提升的范围在50%左右
由于联系人拼音数据的减少，使得单个联系人的数据量下降，减少了Insert SQL的执行时间，建立联系人索引的时间也有较为明显的降低，减少30%左右。
在搜索Query的时间上，多音字方案因为拼音组合的多样性，增加了查找HashTable的次数，但是由于搜索HashTable的时间复杂度为O(1)，而拼音组合在有限字符的query下不多（小于20个），所以增加时间不多，但是由于数据量的减少，ORM的时间缩短，搜索Query的时间有15%左右的提升。