关于即时通讯:IM开发干货分享网易云信IM客户端的聊天消息全文检索技术实践

在 IM 客户端的应用场景中，基于本地数据的全文检索性能扮演着重要的角色，最罕用的比方：查找聊天记录、联系人，就像下图这样。

▲ 微信的聊天记录查找性能

相似于 IM 中的聊天记录查找、联系人搜寻这类性能，有了全文检索能力后，的确能大大提高内容查找的效率，不然，让用户手动翻找，的确升高了用户体验。

本文将具体来聊聊网易云信是如何实现 IM 客户端全文检索能力的，心愿能带给你启发。

学习交换：

即时通讯 / 推送技术开发交换 5 群：215477170 [举荐]

挪动端 IM 开发入门文章：《新手入门一篇就够：从零开发挪动端 IM》

开源 IM 框架源码：https://github.com/JackJiang2…

（本文同步公布于：http://www.52im.net/thread-36…）

李宁： 网易云信高级前端开发工程师，负责音视频 IM SDK 的利用开发、组件化开发及解决方案开发，对 React、PaaS 组件化设计、多平台的开发与编译有丰盛的实战经验。

IM 客户端全文检索相干文章：

《微信手机端的本地数据全文检索优化之路》
《微信团队分享：微信挪动端的全文检索多音字问题解决方案》

网易技术团队分享的其它文章：

《网易视频云技术分享：音频解决与压缩技术疾速入门》
《网易云信实时视频直播在 TCP 数据传输层的一些优化思路》
《网易云信技术分享：IM 中的万人群聊技术计划实际总结》
《Web 端即时通讯实际干货：如何让你的 WebSocket 断网重连更疾速？》
《子弹短信光鲜的背地：网易云信首席架构师分享亿级 IM 平台的技术实际》

所谓全文检索，就是要在大量内容中找到蕴含某个单词呈现地位的技术。

在传统的关系型数据库中，只能通过 LIKE 条件查问来实现，这样有几个弊病：

1）无奈应用数据库索引，须要遍历全表，性能较差；
2）搜寻成果差，只能首尾位含糊匹配，无奈实现简单的搜寻需要；
3）无奈失去内容与搜寻条件的相关性。

咱们在 IM 的 iOS、安卓以及桌面端中都实现了基于 SQLite 等库的本地数据全文检索性能，然而在 Web 端和 Electron 上短少了这部分性能。

因为在 Web 端，因为浏览器环境限度，能应用的本地存储数据库只有 IndexDB，暂不在探讨的范畴内。但在 Electron 上，尽管也是内置了 Chromium 的内核，然而因为能够应用 Node.js 的能力，于是乎抉择的范畴就多了一些。本文内容咱们具体以基于 Electron 的 IM 客户端为例，来探讨全文检索技术实现（技术思路是相通的，并不局限于具体什么端）。

PS： 如果你不理解什么是 Electron 技术，读一下这篇《疾速理解 Electron：新一代基于 Web 的跨平台桌面技术》。

咱们先来具体看下该如何实现全文检索。

要实现全文检索，离不开以下两个知识点：

1）倒排索引；
2）分词。

这两个技术是实现全文检索的技术以及难点，其实现的过程绝对比较复杂，在聊全文索引的实现前，咱们具体学习一下这两个技术的原理。

先简略介绍下倒排索引，倒排索引的概念区别于正排索引：

1）正排索引：是以文档对象的惟一 ID 作为索引，以文档内容作为记录的构造；
2）倒排索引：是以文档内容中的单词作为索引，将蕴含该词的文档 ID 作为记录的构造。

以倒排索引库 search-index 举个理论的例子：

在咱们的 IM 中，每条音讯对象都有 idClient 作为惟一 ID，接下来咱们输出「今天天气真好」，将其每个中文独自分词（分词的概念咱们在下文会具体分享），于是输出变成了「今」、「天」、「天」、「气」、「真」、「好」。再通过 search-index 的 PUT 办法将其写入库中。

最初看下上述例子存储内容的构造：

如是图所示：能够看到倒排索引的构造，key 是分词后的单个中文、value 是蕴含该中文音讯对象的 idClient 组成的数组。

当然：search-index 除了以上这些内容，还有一些其余内容，例如 Weight、Count 以及正排的数据等，这些是为了排序、分页、按字段搜寻等性能而存在的，本文就不再细细开展了。

分词就是将原先一条音讯的内容，依据语义切分成多个单字或词句，思考到中文分词的成果以及须要在 Node 上运行，咱们抉择了 Nodejieba 作为根底分词库。

以下是 jieba 分词的流程图：

以“去北京大学玩”为例，咱们抉择其中最为重要的几个模块剖析一下。

jieba 分词会在初始化时先加载词典，大抵内容如下：

接下来会依据该词典构建前缀词典，构造如下：

其中：“北京大”作为“北京大学”的前缀，它的词频是 0，这是为了便于后续构建 DAG 图。

DAG 图是 Directed Acyclic Graph 的缩写，即有向无环图。

基于前缀词典，对输出的内容进行切分。

其中：

1）“去”没有前缀，因而只有一种切分形式；
2）对于“北”，则有“北”、“北京”、“北京大学”三种切分形式；
3）对于“京”，也只有一种切分形式；
4）对于“大”，有“大”、“大学”两种切分形式；
5）对于“学”和“玩”，仍然只有一种切分形式。

如此，能够失去每个字作为前缀词的切分形式。

其 DAG 图如下图所示：

以上 DAG 图的所有门路如下：

去 / 北 / 京 / 大 / 学 / 玩
去 / 北京 / 大 / 学 / 玩
去 / 北京 / 大学 / 玩
去 / 北京大学 / 玩

因为每个节点都是有权重（Weight）的，对于在前缀词典里的词语，它的权重就是它的词频。因而咱们的问题就是想要求得一条最大门路，使得整个句子的权重最高。

这是一个典型的动静布局问题，首先咱们确认下动静布局的两个条件。

1）重复子问题：

对于节点 i 和其可能存在的多个后继节点 j 和 k：

1）任意通过 i 达到 j 的门路的权重 = 该门路通过 i 的门路权重 + j 的权重，即 R(i -> j) = R(i) + W(j)；
2）任意通过 i 达到 k 的门路的权重 = 该门路通过 i 的门路权重 + k 的权重，即 R(i -> k) = R(i) + W(k)。

即对于领有公共前驱节点 i 的 j 和 k，须要反复计算达到 i 门路的权重。

2）最优子结构：

设整个句子的最优门路为 Rmax，末端节点为 x，多个可能存在的前驱节点为 i、j、k。

失去公式如下：

Rmax = max(Rmaxi, Rmaxj, Rmaxk) + W(x)

于是问题变成了求解 Rmaxi、Rmaxj 以及 Rmaxk，子结构里的最优解即是全局最优解的一部分。

如上，最初计算得出最优门路为“去 / 北京大学 / 玩”。

对于未登陆词，jieba 分词采纳 HMM（Hidden Markov Model 的缩写）模型进行分词。

它将分词问题视为一个序列标注问题，句子为观测序列，分词后果为状态序列。

jieba 分词作者在 issue 中提到，HMM 模型的参数基于网上能下载到的 1998 人民日报的切分语料，一个 MSR 语料以及本人收集的 TXT 小说、用 ICTCLAS 切分，最初用 Python 脚本统计词频而成。

该模型由一个五元组组成，并有两个根本假如。

五元组：

1）状态值汇合；
2）察看值汇合；
3）状态初始概率；
4）状态转移概率；
5）状态发射概率。

根本假如：

1）齐次性假如：即假如暗藏的马尔科夫链在任意时刻 t 的状态只依赖于其前一时刻 t-1 的状态，与其它时刻的状态及观测无关，也与时刻 t 无关；
2）察看值独立性假如：即假如任意时刻的察看值只与该时刻的马尔科夫链的状态无关，与其它观测和状态无关。

状态值汇合即 {B: begin, E: end, M: middle, S: single}，示意每个字所处在句子中的地位，B 为开始地位，E 为完结地位，M 为两头地位，S 是单字成词。

察看值汇合就是咱们输出句子中每个字组成的汇合。

状态初始概率表明句子中的第一个字属于 B、M、E、S 四种状态的概率，其中 E 和 M 的概率都是 0，因为第一个字只可能 B 或者 S，这与理论相符。

状态转移概率表明从状态 1 转移到状态 2 的概率，满足齐次性假如，构造能够用一个嵌套的对象示意：

P = {

B: {E: -0.510825623765990, M: -0.916290731874155},
E: {B: -0.5897149736854513, S: -0.8085250474669937},
M: {E: -0.33344856811948514, M: -1.2603623820268226},
S: {B: -0.7211965654669841, S: -0.6658631448798212},

}

P’B’ 示意从状态 B 转移到状态 E 的概率（构造中为概率的对数，不便计算）为 0.6，同理，P’B’ 示意下一个状态是 M 的概率为 0.4，阐明当一个字处于结尾时，下一个字处于结尾的概率高于下一个字处于两头的概率，合乎直觉，因为二个字的词比多个字的词要更常见。

状态发射概率表明以后状态，满足察看值独立性假如，构造同上，也能够用一个嵌套的对象示意：

P = {

B: {'突': -2.70366861046, '肃': -10.2782270947, '适': -5.57547658034},
M: {'要': -4.26625051239, '合': -2.1517176509, '成': -5.11354837278},
S: {……},
E: {……},

}

P’B’ 的含意就是状态处于 B，观测的字是“突”的概率的对数值等于 -2.70366861046。

最初，通过 Viterbi 算法，输出察看值汇合，将状态初始概率、状态转移概率、状态发射概率作为参数，输入状态值汇合（即最大概率的分词后果）。对于 Viterbi 算法，本文不再具体开展，有趣味的读者能够自行查阅。

上节中介绍的全文检索这两块技术，是咱们架构的技术外围。基于此，咱们对 IM 的 Electron 端技术架构做了改良。以下将具体介绍之。

思考到全文检索只是 IM 中的一个性能，为了不影响其余 IM 的性能，并且能更快的迭代需要，所以采纳了如下的架构计划。

架构图如下：

如上图所示，左边是之前的技术架构，底层存储库应用了 indexDB，下层有读写两个模块。

读写模块的具体作用是：

1）当用户被动发送音讯、被动同步音讯、被动删除音讯以及收到音讯的时候，会将音讯对象同步到 indexDB；
2）当用户须要查问关键字的时候，会去 indexDB 中遍历所有的音讯对象，再应用 indexOf 判断每一条音讯对象是否蕴含所查问的关键字（相似 LIKE）。

那么，当数据量大的时候，查问的速度是十分迟缓的。

右边是退出了分词以及倒排索引数据库的新的架构计划，这个计划不会对之前的计划有任何影响，只是在之前的计划之前加了一层。

当初，读写模块的工作逻辑：

1）当用户被动发送音讯、被动同步音讯、被动删除音讯以及收到音讯的时候，会将每一条音讯对象中的音讯通过分词后同步到倒排索引数据库；
2）当用户须要查问关键字的时候，会先去倒排索引数据库中找出对应音讯的 idClient，再依据 idClient 去 indexDB 中找出对应的音讯对象返回给用户。

该计划有以下 4 个长处：

1）速度快：通过 search-index 实现倒排索引，从而晋升了搜寻速度。
2）跨平台：因为 search-index 与 indexDB 都是基于 levelDB，因而 search-index 也反对浏览器环境，这样就为 Web 端实现全文检索提供了可能性；
3）独立性：倒排索引库与 IM 主业务库 indexDB 拆散；
4）灵活性：全文检索以插件的模式接入。

针对上述第“3）”点： 当 indexDB 写入数据时，会主动告诉到倒排索引库的写模块，将音讯内容分词后，插入到存储队列当中，最初顺次插入到倒排索引数据库中。当须要全文检索时，通过倒排索引库的读模块，能疾速找到对应关键字的音讯对象的 idClient，依据 idClient 再去 indexDB 中找到音讯对象并返回。

针对上述第“4）”点： 它暴露出一个高阶函数，包裹 IM 并返回新的通过继承扩大的 IM，因为 JS 面向原型的机制，在新的 IM 中不存在的办法，会主动去原型链（即老的 IM）当中查找，因而，使得插件能够聚焦于本身办法的实现上，并且不须要关怀 IM 的具体版本，并且插件反对自定义分词函数，满足不同用户不同分词需要的场景

应用了如上架构后，通过咱们的测试，在数据量 20W 的级别上，搜寻工夫从最开始的十几秒降到一秒内，搜寻速度快了 20 倍左右。

本文中，咱们便基于 Nodejieba 和 search-index 在 Electron 上实现了 IM 聊天音讯的全文检索，放慢了聊天记录的搜寻速度。

当然，后续咱们还会针对以下方面做更多的优化，比方以下两点：

1）写入性能： 在理论的应用中，发现当数据量大了当前，search-index 依赖的底层数据库 levelDB 会存在写入性能瓶颈，并且 CPU 和内存的耗费较大。通过调研，SQLite 的写入性能绝对要好很多，从观测来看，写入速度只与数据量成正比，CPU 和内存也绝对稳固，因而，后续可能会思考用将 SQLite 编译成 Node 原生模块来替换 search-index。

2）可扩展性： 目前对于业务逻辑的解耦还不够彻底。倒排索引库当中存储了某些业务字段。后续能够思考倒排索引库只依据关键字查找音讯对象的 idClient，将带业务属性的搜寻放到 indexDB 中，将倒排索引库与主业务库彻底解耦。

以上，就是本文的全副分享，心愿我的分享能对大家有所帮忙。

《新手入门一篇就够：从零开发挪动端 IM》
《从客户端的角度来谈谈挪动端 IM 的音讯可靠性和送达机制》
《挪动端 IM 中大规模群音讯的推送如何保障效率、实时性？》
《挪动端 IM 开发须要面对的技术问题》
《IM 音讯送达保障机制实现 (一)：保障在线实时音讯的牢靠投递》
《IM 音讯送达保障机制实现 (二)：保障离线音讯的牢靠投递》
《如何保障 IM 实时音讯的“时序性”与“一致性”？》
《一个低成本确保 IM 音讯时序的办法探讨》
《IM 单聊和群聊中的在线状态同步应该用“推”还是“拉”？》
《IM 群聊音讯如此简单，如何保障不丢不重？》
《谈谈挪动端 IM 开发中登录申请的优化》
《挪动端 IM 登录时拉取数据如何作到省流量？》
《浅谈挪动端 IM 的多点登录和音讯漫游原理》
《齐全自已开发的 IM 该如何设计“失败重试”机制？》
《通俗易懂：基于集群的挪动端 IM 接入层负载平衡计划分享》
《微信对网络影响的技术试验及剖析（论文全文）》
《微信技术分享：微信的海量 IM 聊天音讯序列号生成实际（算法原理篇）》
《自已开发 IM 有那么难吗？手把手教你自撸一个 Andriod 版繁难 IM (有源码)》
《融云技术分享：解密融云 IM 产品的聊天音讯 ID 生成策略》
《适宜老手：从零开发一个 IM 服务端（基于 Netty，有残缺源码）》
《拿起键盘就是干：跟我一起徒手开发一套分布式 IM 零碎》
《适宜老手：手把手教你用 Go 疾速搭建高性能、可扩大的 IM 零碎 (有源码)》
《IM 里“左近的人”性能实现原理是什么？如何高效率地实现它？》
《IM 音讯 ID 技术专题 (一)：微信的海量 IM 聊天音讯序列号生成实际（算法原理篇）》
《IM 开发宝典：史上最全，微信各种性能参数和逻辑规定材料汇总》
《IM 开发干货分享：我是如何解决大量离线音讯导致客户端卡顿的》
《零根底 IM 开发入门 (一)：什么是 IM 零碎？》
《零根底 IM 开发入门 (二)：什么是 IM 零碎的实时性？》
《零根底 IM 开发入门 (三)：什么是 IM 零碎的可靠性？》
《零根底 IM 开发入门 (四)：什么是 IM 零碎的音讯时序一致性？》
《一套亿级用户的 IM 架构技术干货 (下篇)：可靠性、有序性、弱网优化等》
《IM 扫码登录技术专题 (三)：通俗易懂，IM 扫码登录性能具体原理一篇就够》
《了解 IM 音讯“可靠性”和“一致性”问题，以及解决方案探讨》
《阿里技术分享：闲鱼 IM 基于 Flutter 的挪动端跨端革新实际》
《融云技术分享：全面揭秘亿级 IM 音讯的牢靠投递机制》
《IM 开发干货分享：如何优雅的实现大量离线音讯的牢靠投递》
《IM 开发干货分享：有赞挪动端 IM 的组件化 SDK 架构设计实际》
《IM 开发干货分享：网易云信 IM 客户端的聊天音讯全文检索技术实际》

本文已同步公布于“即时通讯技术圈”公众号。

▲ 本文在公众号上的链接是：点此进入。同步公布链接是：http://www.52im.net/thread-36…

关于即时通讯:IM开发干货分享网易云信IM客户端的聊天消息全文检索技术实践

1、引言

2、对于作者

3、相干文章

4、什么是全文检索

5、全文检索知识点 1：倒排索引

6、全文检索知识点 2：分词

6.1 基本概念

6.2 加载词典

6.3 构建前缀词典

6.4 构建 DAG 图

6.5 最大概率门路计算

6.6 HMM 隐式马尔科夫模型

7、技术实现

7.1 架构图详解

7.2 架构长处

7.3 应用成果

8、本文小结

附录：更多 IM 干货技术文章