IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案

JackJiang · 6 年前

本文来自微信开发团队WeMobileDev公众号的技术分享。

1、前言

微信的移动客户端全文搜索中的多音字问题一直是搜索体验的痛点之一。微信客户端全文搜索在上线以后，也经常收到用户关于多音字问题的反馈。所以，微信全文搜索中的多音字搜索成了一个迫切需要解决的问题。本文重点讲述微信安卓客户端在SQLite FTS5的基础上，多音字问题的解决方案。

本文是专题系列文章中的第2篇：

建议：您也可以在微信客户端的sqlite数据库中找到本文中相关技术的真实实现，微信的SQLite样本库可在此下载《微信本地数据库破解版(含iOS、Android)，仅供学习研究 [附件下载]》（特别申明：微信的SQLite样本库仅供研究和学习之外，严禁用于商用业目的，所有权归微信所有）。

2、相关文章

《微信手机端的本地数据全文检索优化之路》
《腾讯技术分享：Android版手机QQ的缓存监控与优化实践》
《微信团队分享：iOS版微信的高性能通用key-value组件技术实践》
《微信团队分享：iOS版微信是如何防止特殊字符导致的炸群、APP崩溃的？》
《腾讯技术分享：Android手Q的线程死锁监控系统技术实践》
《微信团队原创分享：iOS版微信的内存监控系统技术实践》
《iOS后台唤醒实战：微信收款到账语音提醒技术总结》
《腾讯团队分享：一次手Q聊天界面中图片显示bug的追踪过程分享》
《微信团队披露：微信界面卡死超级bug“15。。。。”的来龙去脉》
《微信客户端团队负责人技术访谈：如何着手客户端性能监控和优化》
《微信团队原创分享：微信客户端SQLite数据库损坏修复实践》
《移动端IM实践：iOS版微信界面卡顿监测方案》
《移动端IM实践：Android版微信如何大幅提升交互性能（一）》
《移动端IM实践：Android版微信如何大幅提升交互性能（二）》
《移动端IM实践：iOS版微信的多设备字体适配方案探讨》
《信鸽团队原创：一起走过 iOS10 上消息推送(APNS)的坑》

3、微信的全文检索需求

搜索形式：
拼音前缀搜索，中文和拼音不能混合搜索，输入拼音必须为连续汉字的全拼音或者短拼音。

搜索内容：
联系人、群聊以及公众号的备注和昵称（最大长度为16个中文字符）。

例如。

联系人A，昵称为“王宏伟”，那么通过以下几种方式都需要搜索到联系人A的昵称：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_1.jpeg

IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_1.jpeg

4、词表方案

中文全文搜索引擎如果需要支持拼音，就需要把输入的中文字符，转化为拼音字母，如果不考虑多音字的情况，我们只需要一张单个汉字的拼音表即可实现转化，但是在多音字的情况下，由于每个汉字在不同的词语当中的读音都有可能不一样，所以，为了使得每个中文字符能够获取到准确的拼音，就需要引入一份词语拼音对应表。

众所周知，汉语博大精深，常用的汉字有20777个，而词语（包括成语）的汉字个数为2到16个，同一个汉字在不同词语中读音有可能不一样。

所以汉语词语转化为拼音有如下两个方案：

1）穷举词语表；
2）采用概率模型，通过训练分类器模型，获取中文字符拼音。

第一种方案对存储空间的要求非常高，对资源的消耗过大。

第二种方案，通过在现有的TTS（Text To Speech）模型中，把汉字转拼音读音的模型拆出来，初步搭建一个概率模型，在初步的调优后，得到一个1个G的拼音模型，识别拼音的准确在可接受范围内。由于模型大小为GB级别，初步考虑是将模型放到后台处理。

处理流程如下图：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_2.png

优点：
客户端无改动，可以快速覆盖所有版本客户端。

缺点：
用户修改备注或者昵称后，需要等待后台下发拼音后才能有正确的拼音索引，导致拼音索引建立不够及时。微信用户量巨大，用户修改备注和昵称的频次非常高，每天都有几十亿次修改，导致后台处理这部分的运算量和耗时非常严重，需要增加较大成本。

5、字表方案

常用汉字有20777个，总体大小为200KB，可以直接带到客户端中，并且查询的时间复杂度为O(1)，在数据量方面是可以接受的。

优点：

1）用户修改昵称或者备注以后，能够快速响应并及时建立索引；
2）将后台巨大的计算量均摊到用户手机上，节省成本；
3）对于姓名中汉字的读音，可以用任意一个读音搜索出来。

缺点：

1）在用户体验上，词语中的多音字可以用任意该汉字的拼音搜索出来；
2）在综合考虑用户体验和性能问题后，最后微信选择了字表方案。

6、客户端索引方案

在确定字表方案后，需要在客户端本地使用SQLite FTS5建立索引。因为拼音搜索主要是采用前缀搜索的方式，所以建立索引的内容以及方式需要考虑FTS5前缀搜索的过程。

IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_3.jpeg

路径（1）是在建立索引表时使用Prefix索引，所以用户在输入Query时，直接通过Hash方法查找前缀索引表即可找到所有以Query为前缀的结果。

路径（2）是在建立索引表时未使用Prefix索引，所以用户在输入Query时，FTS5通过临时搭建一个前缀树来查找以Query为Preifx的索引集合。

从时间复杂度上，路径1具有明显优势，所以在建立索引时，需要加入Prefix配置：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_3.png

6.1索引方案一

考虑到用户输入时是连续输入，并不会考虑跨拼音问题。

例如，用户搜索备注“市委书记”的拼音，会可能采用如下的Query：

shi
shiweishuj
sw

根据以上用户输入习惯以及FTS5前缀搜索原理，采用第一个索引方案：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_5.png

在FTS5匹配以上Query时，用户1、2两种输入都作为"shiweishuji"的前缀被匹配，而3的输入会作为“swsj”的前缀被匹配。

6.2索引方案二

索引方案一仅考虑用户从拼音的头部开始搜索，并没有考虑从中间开始搜索。

例如以下的Query：

shuji
sj

所以，需要建立索引时，需要把每个汉字的拼音作为前缀建立到索引中，如下表：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_6.png

6.3索引方案三

方案一和方案二是在不考虑多音字的情况的索引方案，当引入了多音字以后，在组合拼音字符串时，每一个拼音都可能存在多种情况。

以下为用户备注“张靓颖”的索引：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_7.jpeg

当昵称“张靓颖”建立索引以后，得到如下索引结构：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_8.jpeg

TermOffset：表示一个词语在某一个Document中的偏移；
DocId：Document的唯一ID。

通过一个DocId和一个TermOffset可以定位一个词语。而SQLite FTS5正是通过搜索一个词语来找到对应的DocId，通过TermOffset来定位该词语在Document中的位置。

方案优点：

1）实现较为简单；
2）可覆盖所有多音字情况。

方案缺点：

1）索引数据量过大；
2）考虑常用汉字一共20777个，其中多音字2659个，多音字占比12.7%，平均每个多音字有2.14个拼音。

在微信场景中，联系人的备注和昵称最大字符长度为16个字符，所以我们假设每个昵称的字符为16个汉字，其中，每个汉字的拼音长度为最长度（7个英文字母+1个短拼音英文字母）。

一般场景：
其中20777个汉字当中，出现在昵称中的概率一样，所以16个字符中，大约会出现3个多音字，得到如下公式：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_9.png

极限场景：
昵称中每一个字都是多音字，每个多音字都有4个读音，例如“么么么么么么么么么么么么么么么么”，得到如下公式：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_10.jpeg

从以上两种场景中可以看出，方案三在极限场景中会出现占用超大数据量的情况，所以方案三不可用。

6.4索引方案四

方案三通过穷举法来列举所有拼音组合，核心在于通过空间换区时间，在所需要的空间过于巨大时，可以采取折中的方案来实现。

在汉语中，一个同样意义的实体通过两个不同的词语来表示，称这两个不同的词语为同义词，在数据上表示为（词语A，词语B）=（意义C），那么在多音字的情况来看，同样可以表示为（拼音A，拼音B）=（汉字C）。方案四的核心在于通过同义词的方式来表示多种拼音的组合。

在SQLite FTS5中，一个词语可以通过一个DocId和一个TermOffset来定位，所以当两个词语拥有同一个DocId和TermOffset时，就可以说这两个词语为同义词了，也就有了如下的索引方案：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_11.jpeg

IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_11.jpeg

方案优点：

1）索引数据量小：
a）一般情况：

12.png (7.53 KB, 下载次数: 1068)

下载附件保存到相册

6 年前上传

b）极限情况：

13.png (6.93 KB, 下载次数: 1085)

下载附件保存到相册

6 年前上传
2）建立索引速度快。

方案缺点：

1）默认分词器不能适配多音字的拼音数据；
2）索引中的数据不能直接对应用户输入。

为了解决方案四的两个问题，我们引入了多音字分词器，并且做了用户输入预处理。

7、多音字分词器

SQLite FTS5默认的分词器的分隔符都是固定的，所以，在识别拼音字符时，会当成英文字母来分词。为了能够达到需要的索引结构，我们引入了二级分隔符，使用分号“；”分隔不同汉字以及“，”分隔同一个汉字的不同拼音。

IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_14.png

IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_14.png

以下是多音字分词器的分词流程：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_15.jpeg

8、用户输入预处理

当用户的输入为连续拼音时，由于索引中不存在直接对应的Term，所以需要把用户输入的Query拆解成为索引当中可能存在的Term。

假设用户输入拼音：zhuang，根据短拼音和全拼音的规则，可得到如下7中搜索组合：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_16.jpeg

IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_16.jpeg

考虑到最后一个拼音为前缀搜索，所以，在列举拼音组合时，前面都需要考虑符合完整的拼音，最后一个可以只考虑是否是某个拼音的前缀。

实现这个算法可以通过把所有的拼音作为输入，构建一颗前缀树，能够把整个Query拼音拆解的时间复杂度降低到O(nlgn)。

最后，把所有的拼音组合情况都写到SQL中：
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_17.png

IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_17.png

IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_18.png

9、方案的实际效果

对比方案三和方案四，在拼音数据上有较为明显的提升，提升的范围在50%左右。
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_19.jpeg

由于联系人拼音数据的减少，使得单个联系人的数据量下降，减少了Insert SQL的执行时间，建立联系人索引的时间也有较为明显的降低，减少30%左右。
IM全文检索技术专题(二)：微信移动端的全文检索多音字问题解决方案_20.jpeg

在搜索Query的时间上，多音字方案因为拼音组合的多样性，增加了查找HashTable的次数，但是由于搜索HashTable的时间复杂度为O(1)，而拼音组合在有限字符的query下不多（小于20个），所以增加时间不多，但是由于数据量的减少，ORM的时间缩短，搜索Query的时间有15%左右的提升。

更为详细的微信全文检索优化思路请见《微信手机端的本地数据全文检索优化之路》。微信的本地SQLite研究样本可从此下载《微信本地数据库破解版(含iOS、Android)，仅供学习研究 [附件下载]》（特别申明：微信的SQLite样本库仅供研究和学习之外，严禁用于商用业目的，所有权归微信所有）。

附录：更多微信、QQ的文章

2 楼: 弱鸡哥 · 6 年前

微信的体量这么大，任何一个体验小问题都会被放大，不容易啊

3 楼: iamcxl · 6 年前

老板的放的破解数据库里面微信就没有实现FTS, 我之前破解的数据库里面也没有实现.

难道是我的姿势不对么? 或者是微信的数据库经历过重构?

因为一直在做数据库这方面的优化,所以一直在关注这个问题.

老板如果有研究麻烦,分享一下.谢谢了

4 楼: JackJiang · 6 年前

引用：iamcxl 发表于 2018-06-20 20:49
老板的放的破解数据库里面微信就没有实现FTS, 我之前破解的数据库里面也没有实现.

难道是我的姿势不 ...

以微信团队的技术追求，有些东西应该是他们自已进行底层的优化，你可以看看微信开源的WCDB《一篇文章get微信开源移动端数据库组件WCDB的一切！》

5 楼: iamcxl · 6 年前

引用：JackJiang 发表于 2018-06-20 21:18
以微信团队的技术追求，有些东西应该是他们自已进行底层的优化，你可以看看微信开源的WCDB《一篇文章get ...

感谢,这个内容之前看过了.

后面估计要抽时间看看WCDB了

本文目录

1、前言

2、相关文章

3、微信的全文检索需求

4、词表方案

5、字表方案