IM跨平台技术学习(六):网易云信基于Electron的IM消息全文检索技术实践

简介: 在IM客户端的使用场景中,基于本地数据的全文检索功能扮演着重要的角色,最常用的比如:查找聊天记录、联系人等。类似于IM中的聊天记录查找、联系人搜索这类功能,有了全文检索能力后,确实能大大提高内容查找的效率,不然,让用户手动翻找,确实降低了用户体验。本文将要分享的是,网易云信基于Electron的PC端是如何实现IM客户端全文检索能力的。

本文作者网易云信高级前端开发工程师李宁,本文有修订。

1、引言

在IM客户端的使用场景中,基于本地数据的全文检索功能扮演着重要的角色,最常用的比如:查找聊天记录、联系人等。

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


本文将要分享的是,网易云信基于Electron的PC端是如何实现IM客户端全文检索能力的。

cover-update.png

学习交流:

- 移动端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 作为记录的结构。

3.png

以倒排索引库 search-index 举个实际的例子:

在我们的 IM 中,每条消息对象都有 idClient 作为唯一 ID,接下来我们输入「今天天气真好」,将其每个中文单独分词(分词的概念我们在下文会详细分享),于是输入变成了「今」、「天」、「天」、「气」、「真」、「好」。再通过 search-index 的 PUT 方法将其写入库中。

最后看下上述例子存储内容的结构:

4.jpg

如是图所示:可以看到倒排索引的结构,key 是分词后的单个中文、value 是包含该中文消息对象的 idClient 组成的数组。

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

6、什么是分词

6.1基本概念

分词就是将原先一条消息的内容,根据语义切分成多个单字或词句,考虑到中文分词的效果以及需要在 Node 上运行,我们选择了Nodejieba作为基础分词库。

以下是 jieba 分词的流程图:

5.png

以“去北京大学玩”为例,我们选择其中最为重要的几个模块分析一下。

6.2加载词典

jieba 分词会在初始化时先加载词典,大致内容如下:

6.png

6.3构建前缀词典

接下来会根据该词典构建前缀词典,结构如下:

7.png

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

6.4构建 DAG 图

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

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

其中:

  • 1)“去”没有前缀,因此只有一种切分方式;
  • 2)对于“北”,则有“北”、“北京”、“北京大学”三种切分方式;
  • 3)对于“京”,也只有一种切分方式;
  • 4)对于“大”,有“大”、“大学”两种切分方式;
  • 5)对于“学”和“玩”,依然只有一种切分方式。

如此,可以得到每个字作为前缀词的切分方式。

其 DAG 图如下图所示:

8.png

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 的功能,并且能更快的迭代需求,所以采用了如下的架构方案。

架构图如下:

9.png

如上图所示,右边是之前的技术架构,底层存储库使用了 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、本文小结

本文中,我们便基于Nodejiebasearch-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

目录
相关文章
|
17天前
|
安全 前端开发 关系型数据库
IM即时通讯系统开发技术规则
IM即时通讯系统开发涵盖客户端与服务器端,涉及前端、后端、网络通信及多媒体处理等技术领域,支持文字、语音、图片、视频等多种实时交流方式。开发流程包括需求分析、技术选型、系统设计、开发实现、测试优化及部署维护等阶段,需关注网络通信、多媒体处理、安全性及可扩展性等关键技术点,广泛应用于社交、客服、团队协作及游戏等领域。
|
2月前
|
数据采集 监控 测试技术
大型IM稳定性监测实践:手Q客户端性能防劣化系统的建设之路
本文以iOS端为例,详细分享了手 Q 客户端性能防劣化系统从0到1的构建之路,相信对业界和IM开发者们都有较高的借鉴意义。
98 2
|
11天前
|
人工智能 自然语言处理 搜索推荐
AI技术在智能客服系统中的应用与挑战
【9月更文挑战第32天】本文将探讨AI技术在智能客服系统中的应用及其面临的挑战。我们将分析AI技术如何改变传统客服模式,提高服务质量和效率,并讨论在实际应用中可能遇到的问题和解决方案。
127 65
|
1天前
|
存储 自然语言处理 机器人
实战揭秘:当RAG遇上企业客服系统——从案例出发剖析Retrieval-Augmented Generation技术的真实表现与应用局限,带你深入了解背后的技术细节与解决方案
【10月更文挑战第3天】随着自然语言处理技术的进步,结合检索与生成能力的RAG技术被广泛应用于多个领域,通过访问外部知识源提升生成内容的准确性和上下文一致性。本文通过具体案例探讨RAG技术的优势与局限,并提供实用建议。例如,一家初创公司利用LangChain框架搭建基于RAG的聊天机器人,以自动化FAQ系统减轻客服团队工作负担。尽管该系统在处理简单问题时表现出色,但在面对复杂或多步骤问题时存在局限。此外,RAG系统的性能高度依赖于训练数据的质量和范围。因此,企业在采用RAG技术时需综合评估需求和技术局限性,合理规划技术栈,并辅以必要的人工干预和监督机制。
10 3
|
3天前
|
存储 安全 开发工具
百度公共IM系统的Andriod端IM SDK组件架构设计与技术实现
本文主要介绍了百度公共IM系统的Andriod端IM SDK的建设背景、IM SDK主要结构和工作流程以及建设过程遇到的问题和解决方案。
20 3
|
4天前
|
机器学习/深度学习 人工智能 自然语言处理
AI技术在智能客服中的应用:重塑客户体验
AI技术在智能客服中的应用:重塑客户体验
|
26天前
|
移动开发 前端开发 JavaScript
开源即时通讯IM框架MobileIMSDK的H5端技术概览
开源即时通讯IM框架MobileIMSDK的H5端技术概览
44 2
开源即时通讯IM框架MobileIMSDK的H5端技术概览
|
1月前
|
网络协议 程序员 5G
IM开发者的零基础通信技术入门(十五):理解定位技术,一篇就够
本系列文章尽量使用最浅显易懂的文字、图片来组织内容,力求通信技术零基础的人群也能看懂。但个人建议,至少稍微了解过网络通信方面的知识后再看,会更有收获。如果您大学学习过《计算机网络》这门课,那么一定不要错过本系列文章。
51 7
IM开发者的零基础通信技术入门(十五):理解定位技术,一篇就够
|
1月前
|
网络协议 算法 程序员
IM开发者的零基础通信技术入门(十四):高铁上无线上网有多难?一文即懂!
本系列文章尽量使用最浅显易懂的文字、图片来组织内容,力求通信技术零基础的人群也能看懂。但个人建议,至少稍微了解过网络通信方面的知识后再看,会更有收获。如果您大学学习过《计算机网络》这门课,那么一定不要错过本系列文章。
35 5
IM开发者的零基础通信技术入门(十四):高铁上无线上网有多难?一文即懂!
|
2月前
|
存储 人工智能 自然语言处理
利用AI技术实现智能客服系统
【8月更文挑战第27天】本文将介绍如何利用人工智能(AI)技术构建一个智能客服系统,以提高客户服务效率和质量。我们将从需求分析、系统设计、功能实现等方面进行详细阐述,并通过实际代码示例展示如何实现一个简单的智能客服系统。