本文作者为网易云信资深前端开发工程师李宁，本文已被转载修改。1.简介在IM客户端的使用场景中，基于本地数据的全文搜索功能发挥着重要的作用。最常用的有：搜索聊天记录、联系人等。类似于IM中的聊天记录搜索、联系人搜索等功能，通过全文搜索能力，可以大大提高内容搜索的效率。否则要求用户手动搜索确实会降低用户体验。本文将分享的是网易云信基于Electron的PC端如何实现IM客户端的全文搜索能力。学习交流：移动IM开发入门文章：《新手入门一篇就够：从零开发移动端IM》开源IM框架源码：https://github.com/JackJiang2...（备用地址点此）（本文已同步发表于：http://www.52im.net/thread-40...)2、作者简介李宁：网易云信高级前端开发工程师，负责音视频的应用开发、组件开发和方案开发IMSDK，对React，PaaS组件设计，多平台的开发和编译有丰富的实战经验。3.系列文章本文是系列文章的第六篇。本系列的总目录如下：《IM跨平台技术学习(一)：快速了解新一代跨平台桌面技术——Electron》《IM跨平台技术学习(二)：Electron初体验(快速开始、跨进程通信、打包、踩坑等)》《IM跨平台技术学习(三)：vivo的Electron技术栈选型、全方位实践总结》《IM跨平台技术学习(四)：蘑菇街基于Electron开发IM客户端的技术实践》《IM跨平台技术学习(五)：融云基于Electron的IM跨平台SDK改造实践总结》《IM跨平台技术学习(六)：网易云信基于Electron的IM消息全文检索技术实践》(*文章)4.什么是全文搜索所谓全文搜索就是在大量的内容中找到某个词的出现技术。在传统的关系数据库中，只能通过LIKE条件查询来实现，有几个缺点：1）不能使用数据库索引，需要遍历整张表，性能较差；2）搜索效果差，只能将首末位进行模糊匹配，无法实现复杂的搜索需求；3）无法获得内容与搜索条件的相关性。我们已经在IM的iOS、Android和桌面端实现了基于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是一个数组组成包含中文消息对象的idClients。当然：search-index除了以上内容外，还有一些其他的内容，比如Weight、Count、前排的data，这些内容是为了排序、分页、按字段搜索等功能而存在的。本文不做详细展开。向上。6.什么是分词6.1基本概念分词是将一个原始消息的内容按照语义划分成多个词或句子。考虑到中文分词的效果和需要在Node上运行，我们选择了Nodejieba作为基础分词库。下面是jieba分词的流程图：以“去北大玩”为例，我们选取??最重要的模块进行分析。6.2载入词典jieba分词在初始化时会先载入词典，大致内容如下：6.3构建前缀词典接下来，会根据词典构建前缀词典，结构如下：其中：“北京大学”是“北京大学”的前缀，其词频为0，这是为了方便后续构建DAG图。6.4构建DAG图DAG图是DirectedAcyclicGraph的缩写，即有向无环图。基于前缀字典，对输入内容进行切分。其中：1）“Go”没有前缀，所以只有一种切分方法；2）对于“北方”，有“北方”、“北京”、“北大”三种切分方式；3）对于“北京”，“只有一种切分方法；4）对于“大”，有“大”和“大学”两种切分方法；5）对于“学习”和“玩”，有仍然只有一种切分方法，这样就可以得到每个字符作为前缀的切分方法，其DAG图如下图所示：6.5最大概率路径计算上面DAG图中的所有路径如下：go/bei/jing/university/xue/wanqu/Beijing/da/xue/wanqu/Beijing/university/wanqu/PekingUniversity/Play因为每个节点都有一个权重（Weight），对于前缀字典中的一个词，其权重是它的词频。因此，我们的问题是求一条最大路径，使得整个句子的权重最高。这是一个典型的动态规划问题。首先，我们确认动态规划的两个条件。1）重复子问题：对于节点i及其可能的多个后继节点j和k：1）任一条路径经过的权值itoj=经过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（HiddenModel的缩写）模型进行分词。它将分词问题看成一个序列标注问题，句子是一个观察序列，分词结果是一个状态序列。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,'Su':-10.2782270947,'适当'的意思是状态是在B中，观察到的词是“突然”的概率的对数值等于-2.70366861046。最后通过维特比算法，输入观测值集，以状态初始概率、状态转移概率、状态发射概率为参数，输出状态值集（即概率最大的分词结果).关于维特比算法，本文不做详细展开，感兴趣的读者可以自行查阅。7.技术实现上一节介绍的全文检索两项技术是我们架构的技术核心。基于此，我们改进了IM的Electron端的技术架构。下面将对其进行详细介绍。7.1详细架构图考虑到全文搜索只是IM中的一个功能，为了不影响其他IM功能，满足更快的迭代需求，采用如下架构方案。架构图如下：如上图所示，右侧是之前的技术架构。底层存储库使用indexDB，上层有读写两个模块。读写模块的具体作用是：1）当用户主动发送消息、主动同步消息、主动删除消息、接收消息时，会将消息对象同步到indexDB；2）当用户需要查询关键字时，会去indexDB中遍历所有消息对象，然后使用indexOf判断每个消息对象是否包含查询关键字（类似LIKE）。那么，当数据量很大的时候，查询速度就很慢了。左边是新的架构方案，增加了分词和倒排索引数据库。该方案不会对之前的方案产生任何影响，只是在之前的方案之前增加了一层。现在，读写模块的工作逻辑：1）当用户主动发送一条消息，主动同步一条消息，主动删除一条消息，接收一条消息时，每个消息对象中的消息都会同步到倒排索引中分词后的数据库；2）当用户需要查询关键词时，会先在倒排索引数据库中找到对应消息的idClient，然后根据idClient在indexDB中找到对应的消息对象返回给用户。7.2架构优势该方案有以下四大优势：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）写入性能：在实际使用中，我们发现当数据量很大时，底层数据库levelDB会搜索-索引依赖会存在写性能瓶颈，并且会消耗大量的CPU和内存。经过考察，SQLite的写入性能要好很多。据观察，写入速度只与数据量成正比，CPU和内存都比较稳定。因此，你可以考虑将SQLite编译成一个Node原生模块，以备日后替代之用。搜索索引。2）可扩展性：目前业务逻辑的解耦还不够彻底。某些业务字段存储在倒排索引库中。以后可以考虑倒排索引库只根据关键字查找消息对象的idClient，将带有业务属性的查找放在indexDB中，将倒排索引库与主业务库完全解耦。以上就是本文的全部分享。希望我的分享能对大家有所帮助。9.参考资料[1]微信移动端全文搜索优化之路[2]微信移动端全文搜索多音字问题解决方案[3]微信移动端全文搜索最新技术优化实践微信iOS端[4]蘑菇街基于Electron开发IM客户端[5]融云基于Electron的IM跨平台SDK改造实践总结[6]闲鱼IM基于Flutter的移动跨端改造实践（本文同步发表于:http://www.52im.net/thread-40...)
