本文作者网易云信高级前端开发工程师李宁，本文有修订。
1、引言
在IM客户端的使用场景中，基于本地数据的全文检索功能扮演着重要的角色，最常用的比如：查找聊天记录、联系人等。
类似于IM中的聊天记录查找、联系人搜索这类功能，有了全文检索能力后，确实能大大提高内容查找的效率，不然，让用户手动翻找，确实降低了用户体验。
本文将要分享的是，网易云信基于Electron的PC端是如何实现IM客户端全文检索能力的。
学习交流：
（本文已同步发布于：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的跨平台桌面技术》。
我们先来具体看下该如何实现全文检索。
要实现全文检索，离不开以下两个知识点：
这两个技术是实现全文检索的技术以及难点，其实现的过程相对比较复杂，在聊全文索引的实现前，我们具体学习一下这两个技术的原理。
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、参考资料
[1]微信移动端的全文检索优化之路
[2]微信移动端的全文检索多音字问题解决方案
[3]微信iOS端的最新全文检索技术优化实践
[4]蘑菇街基于Electron开发IM客户端的技术实践
[5]融云基于Electron的IM跨平台SDK改造实践总结
[6]闲鱼IM基于Flutter的移动端跨端改造实践
（本文已同步发布于：http://www.52im.net/thread-4065-1-1.html）