IM 跨平台技术学习 (六)：网易云信基于 Electron 的 IM 消息全文检索技术实践
本文作者网易云信高级前端开发工程师李宁，本文有修订。
1、引言
在 IM 客户端的使用场景中，基于本地数据的全文检索功能扮演着重要的角色，最常用的比如：查找聊天记录、联系人等。
类似于 IM 中的聊天记录查找、联系人搜索这类功能，有了全文检索能力后，确实能大大提高内容查找的效率，不然，让用户手动翻找，确实降低了用户体验。
本文将要分享的是，网易云信基于Electron的 PC 端是如何实现 IM 客户端全文检索能力的。
学习交流：
- 移动端 IM 开发入门文章：《新手入门一篇就够：从零开发移动端IM》
- 开源 IM 框架源码：https://github.com/JackJiang2011/MobileIMSDK（备用地址点此）
（本文已同步发布于：http://www.52im.net/thread-4065-1-1.html）
2、关于作者
李宁：网易云信高级前端开发工程师，负责音视频 IM SDK 的应用开发、组件化开发及解决方案开发，对 React、PaaS 组件化设计、多平台的开发与编译有丰富的实战经验。
3、系列文章
本文是系列文章中的第 6 篇，本系列总目录如下：
4、什么是全文检索
所谓全文检索，就是要在大量内容中找到包含某个单词出现位置的技术。
在传统的关系型数据库中，只能通过 LIKE 条件查询来实现，这样有几个弊端：
1）无法使用数据库索引，需要遍历全表，性能较差；
2）搜索效果差，只能首尾位模糊匹配，无法实现复杂的搜索需求；
3）无法得到内容与搜索条件的相关性。
我们在 IM 的 iOS、安卓以及桌面端中都实现了基于 SQLite 等库的本地数据全文检索功能，但是在 Web 端和 基于 Electron 的 PC 端上缺少了这部分功能。
因为在 Web 端，由于浏览器环境限制，能使用的本地存储数据库只有 IndexDB，暂不在讨论的范围内。但在基于 Electron 的 PC 端上，虽然也是内置了 Chromium 的内核，但是因为可以使用 Node.js 的能力，于是乎选择的范围就多了一些。本文内容我们具体以基于 Electron 的 IM 客户端为例，来讨论全文检索技术实现。
PS：如果你不了解什么是 Electron 技术，读一下这篇《快速了解Electron：新一代基于Web的跨平台桌面技术》。
我们先来具体看下该如何实现全文检索。
要实现全文检索，离不开以下两个知识点：
1）倒排索引；
2）分词。
这两个技术是实现全文检索的技术以及难点，其实现的过程相对比较复杂，在聊全文索引的实现前，我们具体学习一下这两个技术的原理。
5、什么是倒排索引
先简单介绍下倒排索引，倒排索引的概念区别于正排索引：
1）正排索引：是以文档对象的唯一 ID 作为索引，以文档内容作为记录的结构；
2）倒排索引：是以文档内容中的单词作为索引，将包含该词的文档 ID 作为记录的结构。
以倒排索引库 search-index 举个实际的例子：
在我们的 IM 中，每条消息对象都有 idClient 作为唯一 ID，接下来我们输入「今天天气真好」，将其每个中文单独分词（分词的概念我们在下文会详细分享），于是输入变成了「今」、「天」、「天」、「气」、「真」、「好」。再通过 search-index 的 PUT 方法将其写入库中。
最后看下上述例子存储内容的结构：
如是图所示：可以看到倒排索引的结构，key 是分词后的单个中文、value 是包含该中文消息对象的 idClient 组成的数组。
当然：search-index 除了以上这些内容，还有一些其他内容，例如 Weight、Count 以及正排的数据等，这些是为了排序、分页、按字段搜索等功能而存在的，本文就不再细细展开了。
6、什么是分词
6.1 基本概念
分词就是将原先一条消息的内容，根据语义切分成多个单字或词句，考虑到中文分词的效果以及需要在 Node 上运行，我们选择了Nodejieba作为基础分词库。
以下是 jieba 分词的流程图：
以“去北京大学玩”为例，我们选择其中最为重要的几个模块分析一下。
6.2 加载词典
jieba 分词会在初始化时先加载词典，大致内容如下：
6.3 构建前缀词典
接下来会根据该词典构建前缀词典，结构如下：
其中：“北京大”作为“北京大学”的前缀，它的词频是 0，这是为了便于后续构建 DAG 图。
6.4 构建 DAG 图
DAG 图是 Directed Acyclic Graph 的缩写，即有向无环图。
基于前缀词典，对输入的内容进行切分。
其中：
1）“去”没有前缀，因此只有一种切分方式；
2）对于“北”，则有“北”、“北京”、“北京大学”三种切分方式；
3）对于“京”，也只有一种切分方式；
4）对于“大”，有“大”、“大学”两种切分方式；
5）对于“学”和“玩”，依然只有一种切分方式。
如此，可以得到每个字作为前缀词的切分方式。
其 DAG 图如下图所示：
6.5 最大概率路径计算
以上 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，子结构里的最优解即是全局最优解的一部分。
如上，最后计算得出最优路径为“去/北京大学/玩”。
6.6HMM 隐式马尔科夫模型
对于未登陆词，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']['E'] 表示从状态 B 转移到状态 E 的概率（结构中为概率的对数，方便计算）为 0.6，同理，P['B']['M'] 表示下一个状态是 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算法，本文不再详细展开，有兴趣的读者可以自行查阅。
7、技术实现
上节中介绍的全文检索这两块技术，是我们架构的技术核心。基于此，我们对 IM 的 Electron 端技术架构做了改进。以下将详细介绍之。
7.1 架构图详解
考虑到全文检索只是 IM 中的一个功能，为了不影响其他 IM 的功能，并且能更快的迭代需求，所以采用了如下的架构方案。
架构图如下：
如上图所示，右边是之前的技术架构，底层存储库使用了 indexDB，上层有读写两个模块。
读写模块的具体作用是：
1）当用户主动发送消息、主动同步消息、主动删除消息以及收到消息的时候，会将消息对象同步到 indexDB；
2）当用户需要查询关键字的时候，会去 indexDB 中遍历所有的消息对象，再使用 indexOf 判断每一条消息对象是否包含所查询的关键字（类似 LIKE）。
那么，当数据量大的时候，查询的速度是非常缓慢的。
左边是加入了分词以及倒排索引数据库的新的架构方案，这个方案不会对之前的方案有任何影响，只是在之前的方案之前加了一层。
现在，读写模块的工作逻辑：
1）当用户主动发送消息、主动同步消息、主动删除消息以及收到消息的时候，会将每一条消息对象中的消息经过分词后同步到倒排索引数据库；
2）当用户需要查询关键字的时候，会先去倒排索引数据库中找出对应消息的 idClient，再根据 idClient 去 indexDB 中找出对应的消息对象返回给用户。
7.2 架构优点
该方案有以下 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 的具体版本，并且插件支持自定义分词函数，满足不同用户不同分词需求的场景
7.3 使用效果
使用了如上架构后，经过我们的测试，在数据量 20W 的级别上，搜索时间从最开始的十几秒降到一秒内，搜索速度快了 20 倍左右。
8、本文小结
本文中，我们便基于Nodejieba和search-index在 Electron 上实现了 IM 聊天消息的全文检索，加快了聊天记录的搜索速度。
当然，后续我们还会针对以下方面做更多的优化，比如以下两点：
1）写入性能 ：在实际的使用中，发现当数据量大了以后，search-index 依赖的底层数据库 levelDB 会存在写入性能瓶颈，并且 CPU 和内存的消耗较大。经过调研，SQLite 的写入性能相对要好很多，从观测来看，写入速度只与数据量成正比，CPU 和内存也相对稳定，因此，后续可能会考虑用将 SQLite 编译成 Node 原生模块来替换 search-index。
2）可扩展性 ：目前对于业务逻辑的解耦还不够彻底。倒排索引库当中存储了某些业务字段。后续可以考虑倒排索引库只根据关键字查找消息对象的 idClient，将带业务属性的搜索放到 indexDB 中，将倒排索引库与主业务库彻底解耦。
以上，就是本文的全部分享，希望我的分享能对大家有所帮助。
9、参考资料
[5]融云基于Electron的IM跨平台SDK改造实践总结
（本文已同步发布于：http://www.52im.net/thread-4065-1-1.html）
还未添加个人签名 2019-08-26 加入
开源IM框架MobileIMSDK、BeautyEye的作者。
评论