共计 4633 个字符，预计需要花费 12 分钟才能阅读完成。
前言
在 IM 场景的客户端需要上，基于本地数据的全文检索（Full-text search）扮演着重要的角色。所谓全文检索，就是要在大量文档中找到蕴含某个单词呈现地位的技术。在以往的关系型数据库中，只能通过 LIKE 来实现，这样有几个弊病：
- 无奈应用数据库索引，须要遍历全表，性能较差
- 搜寻成果差，只能首尾位含糊匹配，无奈实现简单的搜寻需要
- 无奈失去文档与搜寻条件的相关性
网易云信 IM 的 iOS、安卓以及桌面端中都实现了基于 SQLite 等库的本地数据全文检索性能，然而在 Web 端和 Electron 上短少了这部分性能。在 Web 端，因为浏览器环境限度，能应用的本地存储数据库只有 IndexDB，暂不在探讨的范畴内。在 Electron 上，尽管也是内置了 Chromium 的内核，然而因为能够应用 Node.js 的能力，于是乎抉择的范畴就多了一些。
咱们先来具体看下该如何实现全文检索。
根底技术知识点
要实现全文检索，离不开以下两个知识点：
- 倒排索引
- 分词
这两个技术是实现全文检索的技术以及难点，其实现的过程绝对比较复杂，再聊全文索引的实现前，咱们先来具体聊一下这两个技术的实现。
倒排索引
先简略介绍下倒排索引，倒排索引的概念区别于正排索引：
- 正排索引：是以文档对象的惟一 ID 作为索引，以文档内容作为记录的构造
- 倒排索引：是以文档内容中的单词作为索引，将蕴含该词的文档 ID 作为记录的构造
以倒排索引库 search-index 举个理论的例子。在网易云信的 IM 中，每条音讯对象都有 idClient 作为惟一 ID，接下来咱们输出「今天天气真好」，将其每个中文独自 分词（分词的概念咱们在下文会具体分享），于是输出变成了「今」、「天」、「天」、「气」、「真」、「好」，再通过 search-index 的 PUT 办法将其写入库中，最初看下存储内容的构造：
如图所示，能够看到倒排索引的构造，key 是分词后的单个中文，value 是蕴含该中文音讯对象的 idClient 组成的数组。当然，search-index 除了以上这些内容，还有一些其余内容，例如 Weight、Count 以及正排的数据等，这些是为了排序、分页、按字段搜寻等性能而存在的，本文就不再细细开展了。
分词
分词就是将原先一条音讯的内容，依据语义切分成多个单字或词句，思考到中文分词的成果以及须要在 Node 上运行，咱们抉择了 Nodejieba 作为根底分词库。以下是 jieba 分词的流程图：
以「去北京大学玩」为例，咱们抉择其中最为重要的几个模块剖析一下：
加载词典
jieba 分词会在初始化时先加载词典，大抵内容如下：
构建前缀词典
接下来会依据该词典构建前缀词典，构造如下：
其中，「北京大」作为「北京大学」的前缀，它的词频是 0，这是为了便于后续构建 DAG 图。
构建 DAG 图
DAG 图是 Directed Acyclic Graph 的缩写，即有向无环图。
基于前缀词典，对输出的内容进行切分。其中，「去」没有前缀，因而只有一种切分形式；对于「北」，则有「北」、「北京」、「北京大学」三种切分形式；对于「京」，也只有一种切分形式；对于「大」，有「大」、「大学」两种切分形式；对于「学」和「玩」，仍然只有一种切分形式。如此，能够失去每个字作为前缀词的切分形式，其 DAG 图如下图所示：
最大概率门路计算
以上 DAG 图的所有门路如下：
- 去 / 北 / 京 / 大 / 学 / 玩
- 去 / 北京 / 大 / 学 / 玩
- 去 / 北京 / 大学 / 玩
- 去 / 北京大学 / 玩
因为每个节点都是有权重（Weight）的，对于在前缀词典里的词语，它的权重就是它的词频。因而咱们的问题就是想要求得一条最大门路，使得整个句子的权重最高。
这是一个典型的动静布局问题，首先咱们确认下动静布局的两个条件：
- 重复子问题：对于节点 i 和其可能存在的多个后继节点 j 和 k：
任意通过 i 达到 j 的门路的权重 = 该门路通过 i 的门路权重 + j 的权重，即 R(i -> j) = R(i) + W(j)
任意通过 i 达到 k 的门路的权重 = 该门路通过 i 的门路权重 + k 的权重，即 R(i -> k) = R(i) + W(k) 即对于领有公共前驱节点 i 的 j 和 k，须要反复计算达到 i 门路的权重。
- 最优子结构：设整个句子的最优门路为 Rmax，末端节点为 x，多个可能存在的前驱节点为 i、j、k，失去公式如下：
Rmax = max(Rmaxi, Rmaxj, Rmaxk) + W(x) 于是问题变成了求解 Rmaxi、Rmaxj 以及 Rmaxk，子结构里的最优解即是全局最优解的一部分。
如上，最初计算得出最优门路为「去 / 北京大学 / 玩」。
HMM 隐式马尔科夫模型
对于未登陆词，jieba 分词采纳 HMM（Hidden Markov Model 的缩写）模型进行分词。它将分词问题视为一个序列标注问题，句子为观测序列，分词后果为状态序列。jieba 分词作者在 issue 中提到，HMM 模型的参数基于网上能下载到的 1998 人民日报的切分语料，一个 MSR 语料以及本人收集的 TXT 小说、用 ICTCLAS 切分，最初用 Python 脚本统计词频而成。
该模型由一个五元组组成，并有两个根本假如。
五元组：
- 状态值汇合
- 察看值汇合
- 状态初始概率
- 状态转移概率
- 状态发射概率
根本假如：
- 齐次性假如：即假如暗藏的马尔科夫链在任意时刻 t 的状态只依赖于其前一时刻 t - 1 的状态，与其它时刻的状态及观测无关，也与时刻 t 无关。
- 察看值独立性假如：即假如任意时刻的察看值只与该时刻的马尔科夫链的状态无关，与其它观测和状态无关。
状态值汇合即{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 Electron 端架构
架构图详解
思考到全文检索只是 IM 中的一个性能，为了不影响其余 IM 的性能，并且能更快的迭代需要，所以采纳了如下的架构计划：
左边是之前的技术架构，底层存储库应用了 indexDB，下层有读写两个模块：
- 当用户被动发送音讯、被动同步音讯、被动删除音讯以及收到音讯的时候，会将音讯对象同步到 indexDB；
- 当用户须要查问关键字的时候，会去 indexDB 中遍历所有的音讯对象，再应用 indexOf 判断每一条音讯对象是否蕴含所查问的关键字（相似 LIKE）。
那么，当数据量大的时候，查问的速度是十分迟缓的。
右边是退出了分词以及倒排索引数据库的新的架构计划，这个计划不会对之前的计划有任何影响，只是在之前的计划之前加了一层，当初：
- 当用户被动发送音讯、被动同步音讯、被动删除音讯以及收到音讯的时候，会将每一条音讯对象中的音讯通过分词后同步到倒排索引数据库；
- 当用户须要查问关键字的时候，会先去倒排索引数据库中找出对应音讯的 idClient，再依据 idClient 去 indexDB 中找出对应的音讯对象返回给用户。
架构长处
该计划有以下 4 个长处：
- 速度快：通过 search-index 实现倒排索引，从而晋升了搜寻速度。
- 跨平台：因为 search-index 与 indexDB 都是基于 levelDB，因而 search-index 也反对浏览器环境，这样就为 Web 端实现全文检索提供了可能性。
- 独立性：倒排索引库与 IM 主业务库 indexDB 拆散。当 indexDB 写入数据时，会主动告诉到倒排索引库的写模块，将音讯内容分词后，插入到存储队列当中，最初顺次插入到倒排索引数据库中。当须要全文检索时，通过倒排索引库的读模块，能疾速找到对应关键字的音讯对象的 idClient，依据 idClient 再去 indexDB 中找到音讯对象并返回。
- 灵活性：全文检索以插件的模式接入，它暴露出一个高阶函数，包裹 IM 并返回新的通过继承扩大的 IM，因为 JS 面向原型的机制，在新的 IM 中不存在的办法，会主动去原型链（即老的 IM）当中查找，因而，使得插件能够聚焦于本身办法的实现上，并且不须要关怀 IM 的具体版本，并且插件反对自定义分词函数，满足不同用户不同分词需要的场景。
应用成果
应用了如上架构后，通过咱们的测试，在数据量 20W 的级别上，搜寻工夫从最开始的十几秒降到一秒内，搜寻速度快了 20 倍左右。
总结
以上，咱们便基于 Nodejieba 和 search-index 在 Electron 上实现了网易云信 IM SDK 聊天音讯的全文检索，放慢了聊天记录的搜寻速度。当然，后续咱们还会针对以下方面做更多的优化，比方：
- 写入性能晋升：在理论的应用中，发现当数据量大了当前，search-index 依赖的底层数据库 levelDB 会存在写入性能瓶颈，并且 CPU 和内存的耗费较大。通过调研，SQLite 的写入性能绝对要好很多，从观测来看，写入速度只与数据量成正比，CPU 和内存也绝对稳固，因而，后续可能会思考用将 SQLite 编译成 Node 原生模块来替换 search-index。
- 可扩展性：目前对于业务逻辑的解耦还不够彻底。倒排索引库当中存储了某些业务字段。后续能够思考倒排索引库只依据关键字查找音讯对象的 idClient，将带业务属性的搜寻放到 indexDB 中，将倒排索引库与主业务库彻底解耦。
以上，就是本文的全副分享，欢送关注咱们，继续分享更多技术干货。最初，心愿我的分享能对大家有所帮忙。
作者介绍
李宁，网易云信高级前端开发工程师，负责网易云信音视频 IM SDK 的利用开发、组件化开发及解决方案开发，对 React、PaaS 组件化设计、多平台的开发与编译有丰盛的实战经验。有任何的问题，欢送留言交换。
更多技术干货，欢送关注【网易智企技术 +】微信公众号