专栏首页微信终端开发团队的专栏移动客户端多音字搜索

移动客户端多音字搜索

本文首次发表在《程序员》杂志 2018 年 02 月期。

前言


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

需求


  • 搜索形式:拼音前缀搜索,中文和拼音不能混合搜索,输入拼音必须为连续汉字的全拼音或者短拼音
  • 搜索内容:联系人、群聊以及公众号的备注和昵称(最大长度为16个中文字符)

例如

联系人A,昵称为“王宏伟”,那么通过以下几种方式都需要搜索到联系人A的昵称

词表方案


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

众所周知,汉语博大精深,常用的汉字有20777个,而词语(包括成语)的汉字个数为2到16个,同一个汉字在不同词语中读音有可能不一样,所以汉语词语转化为拼音有如下两个方案:

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

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

第二种方案,通过在现有的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:

  1. shi
  2. shiweishuj
  3. sw

根据以上用户输入习惯以及FTS5前缀搜索原理,采用第一个索引方案。

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

索引方案一仅考虑用户从拼音的头部开始搜索,并没有考虑从中间开始搜索,例如以下的Query:

  1. shuji
  2. sj

所以,需要建立索引时,需要把每个汉字的拼音作为前缀建立到索引中,如下表:

索引方案三

方案一和方案二是在不考虑多音字的情况的索引方案,当引入了多音字以后,在组合拼音字符串时,每一个拼音都可能存在多种情况,以下为用户备注“张靓颖”的索引。

当昵称“张靓颖”建立索引以后,得到如下索引结构:

TermOffset:表示一个词语在某一个Document中的偏移

DocId:Document的唯一ID

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

方案优点:
  1. 实现较为简单
  2. 可覆盖所有多音字情况
方案缺点:
  1. 索引数据量过大

考虑常用汉字一共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时,就可以说这两个词语为同义词了,也就有了如下的索引方案:

方案优点:

  1. 索引数据量小

一般情况:

极限情况:

  1. 建立索引速度快
方案缺点:
  1. 默认分词器不能适配多音字的拼音数据
  2. 索引中的数据不能直接对应用户输入

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

多音字分词器


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%左右的提升。

本文分享自微信公众号 - WeMobileDev(WeMobileDev),作者:jiaminchen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-04-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Tinker:技术的初心与坚持

    2016年3月10日,Tinker项目正式启动,并在同年9月23日举行的MDCC会议上开源。一年过去了,两个人,50%的工作时间。总的来说,填了一些坑,获得少许...

    微信终端开发团队
  • 微信 Android 模块化架构重构实践(上)

    重构整体架构不是一件容易事,通常也不太可能让整个团队停下来只做重构。本文主要分享模块化架构重构的一点点经验。

    微信终端开发团队
  • Hello Bonjour!

    Hello Bonjour! 一开始用Bonjour,我是拒绝的。 让我们以一个问题开头:如何能在本地网络找到自己想要的硬件设备及相应服务,并连接? 在这个以I...

    微信终端开发团队
  • 为什么要把系统拆分成分布式的,为啥要用Dubbo?

    从这个问题开始就进行分布式系统环节了,好多同学给我反馈说,现在出去分布式成标配了,没有哪个公司不问问你分布式的事儿。

    良月柒
  • Elasticsearch跨集群复制(CCR)之腾讯云ES跨地域容灾

    腾讯云ES目前已经提供了多可用区部署,即支持同地域跨机房的高可用容灾方案,满足了绝大多数客户的需求。但是依然会有部分客户希望进一步提升容灾级别,能够做到跨地域容...

    腾讯云大数据团队
  • 解决Eclipse/STS 中出现Resource is out of sync with the file system 的异常

    The error simply says, “you've made changes in files in your workspace from out...

    执笔记忆的空白
  • RabbitMQ的安装及集群搭建方法

    1 安装erlang 下载地址:http://www.erlang.org/downloads 博主这里采用的是otp_src_19.1.tar.gz (2...

    我是李超人
  • 开发者必知的8款App快速开发工具

    “我有一个好创意,就差一个CTO……” “原生APP开发难度大,周期长,成本高,还没上线市场已经被占领了。” “APP版本迭代更新,都是企业的一道难关,没有一个...

    非著名程序员
  • demo2动态加载显示商品详情页

    /* 要求:实现 头像+昵称(多余7位用...)           商品图片(根据商品实际的图片的大小进行动态的展示。按照一定的比例进行展示。)       ...

    用户1219438
  • 最好用的开源Web漏洞扫描工具梳理

    来自FreeBuf.COM *参考来源:geekflare,FB小编柚子编译 链接:www.freebuf.com/articles/web/155209.ht...

    企鹅号小编

扫码关注云+社区

领取腾讯云代金券