流水不争先,争的是滔滔不绝

IM客户端的聊天消息全文检索技术

IM安全 macgrady 71℃

在IM客户端的使用场景中,基于本地数据的全文检索功能扮演着重要的角色,最常用的比如:查找聊天记录、联系人,就像下图这样。类似于IM中的聊天记录查找、联系人搜索这类功能,有了全文检索能力后,确实能大大提高内容查找的效率。


什么是全文检索


所谓全文检索,就是要在大量内容中找到包含某个单词出现位置的技术。

在传统的关系型数据库中,只能通过 LIKE 条件查询来实现,这样有几个弊端:


  • 1)无法使用数据库索引,需要遍历全表,性能较差;
  • 2)搜索效果差,只能首尾位模糊匹配,无法实现复杂的搜索需求;
  • 3)无法得到内容与搜索条件的相关性。



因为在 Web 端,由于浏览器环境限制,能使用的本地存储数据库只有 IndexDB,暂不在讨论的范围内。但在 Electron 上,虽然也是内置了 Chromium 的内核,但是因为可以使用 Node.js 的能力,于是乎选择的范围就多了一些。

我们先来具体看下该如何实现全文检索。

要实现全文检索,离不开以下两个点:


  • 1)倒排索引;
  • 2)分词。


这两个技术是实现全文检索的技术以及难点,其实现的过程相对比较复杂,在聊全文索引的实现前,我们具体学习一下这两个技术的原理。

全文检索知识点1:倒排索引


先简单介绍下倒排索引,倒排索引的概念区别于正排索引:


  • 1)正排索引:是以文档对象的唯一 ID 作为索引,以文档内容作为记录的结构;
  • 2)倒排索引:是以文档内容中的单词作为索引,将包含该词的文档 ID 作为记录的结构
  • 以倒排索引库 search-index 举个实际的例子:

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

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

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

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

search-index 除了以上这些内容,还有一些其他内容,例如 Weight、Count 以及正排的数据等,这些是为了排序、分页、按字段搜索等功能而存在的.

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

jieba 分词的流程图:

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,子结构里的最优解即是全局最优解的一部分。

对于未登陆词,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 的概率,满足齐次性假设,结构可以用一个嵌套的对象表示:

123456P = {    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,说明当一个字处于开头时,下一个字处于结尾的概率高于下一个字处于中间的概率,符合直觉,因为二个字的词比多个字的词要更常见。

状态发射概率表明当前状态,满足观察值独立性假设,结构同上,也可以用一个嵌套的对象表示:

123456P = {    B: {'突': -2.70366861046, '肃': -10.2782270947, '适': -5.57547658034},    M: {'要': -4.26625051239, '合': -2.1517176509, '成': -5.11354837278},    S: {……},    E: {……},}

P[‘B’][‘突’] 的含义就是状态处于 B,观测的字是“突”的概率的对数值等于 -2.70366861046。

最后,通过 Viterbi 算法,输入观察值集合,将状态初始概率、状态转移概率、状态发射概率作为参数,输出状态值集合(即最大概率的分词结果)。

————————————————
版权声明:本文为博主「JackJiang 」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:http://www.52im.net/thread-3651-1-1.html

版权声明:部分文章、图片等内容为用户发布或互联网整理而来,仅供学习参考。如有侵犯您的版权,请联系我们,将立刻删除。
点击这里给我发消息