共计 5656 个字符,预计需要花费 15 分钟才能阅读完成。
本文作者网易云信高级前端开发工程师李宁,本文有订正。
1、引言
在 IM 客户端的应用场景中,基于本地数据的全文检索性能扮演着重要的角色,最罕用的比方:查找聊天记录、联系人等。
相似于 IM 中的聊天记录查找、联系人搜寻这类性能,有了全文检索能力后,的确能大大提高内容查找的效率,不然,让用户手动翻找,的确升高了用户体验。
本文将要分享的是,网易云信基于 Electron 的 PC 端是如何实现 IM 客户端全文检索能力的。
学习交换:
- 挪动端 IM 开发入门文章:《新手入门一篇就够:从零开发挪动端 IM》
-
开源 IM 框架源码:https://github.com/JackJiang2…(备用地址点此)
(本文已同步公布于:http://www.52im.net/thread-40…)2、对于作者
李宁:网易云信高级前端开发工程师,负责音视频 IM SDK 的利用开发、组件化开发及解决方案开发,对 React、PaaS 组件化设计、多平台的开发与编译有丰盛的实战经验。
3、系列文章
本文是系列文章中的第 6 篇,本系列总目录如下:
- 《IM 跨平台技术学习(一):疾速理解新一代跨平台桌面技术——Electron》
- 《IM 跨平台技术学习(二):Electron 初体验(疾速开始、跨过程通信、打包、踩坑等)》
- 《IM 跨平台技术学习(三):vivo 的 Electron 技术栈选型、全方位实际总结》
- 《IM 跨平台技术学习(四):蘑菇街基于 Electron 开发 IM 客户端的技术实际》
- 《IM 跨平台技术学习(五):融云基于 Electron 的 IM 跨平台 SDK 革新实际总结》
-
《IM 跨平台技术学习(六):网易云信基于 Electron 的 IM 音讯全文检索技术实际》(* 本文)
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,子结构里的最优解即是全局最优解的一部分。如上,最初计算得出最优门路为“去 / 北京大 Markov 学 / 玩”。6.6HMM 隐式马尔科夫模型
对于未登陆词,jieba 分词采纳 HMM(Hidden 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 算法,本文不再具体开展,有趣味的读者能够自行查阅。
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-40…)