技术干货 | 如何在 Electron 上实现 IM SDK 聊天消息全文检索
?
?
導(dǎo)讀:在 IM 場景的客戶端需求上,基于本地數(shù)據(jù)的全文檢索(Full-text search)扮演著重要的角色。本文具體來聊聊網(wǎng)易云信是如何實現(xiàn)全文檢索的。
?
文|李寧 網(wǎng)易云信高級前端開發(fā)工程師
所謂全文檢索,就是要在大量文檔中找到包含某個單詞出現(xiàn)位置的技術(shù)。在以往的關(guān)系型數(shù)據(jù)庫中,只能通過 LIKE 來實現(xiàn),這樣有幾個弊端:
-
無法使用數(shù)據(jù)庫索引,需要遍歷全表,性能較差
-
搜索效果差,只能首尾位模糊匹配,無法實現(xiàn)復(fù)雜的搜索需求
-
無法得到文檔與搜索條件的相關(guān)性
在網(wǎng)易云信 IM 的 iOS、安卓以及桌面端中都實現(xiàn)了基于 SQLite 等庫的本地數(shù)據(jù)全文檢索功能,但是在 Web 端和 Electron 上缺少了這部分功能。在 Web 端,由于瀏覽器環(huán)境限制,能使用的本地存儲數(shù)據(jù)庫只有 IndexDB,暫不在討論的范圍內(nèi)。在 Electron 上,雖然也是內(nèi)置了 Chromium 的內(nèi)核,但是因為可以使用 Node.js 的能力,于是乎選擇的范圍就多了一些。
我們先來具體看下該如何實現(xiàn)全文檢索。
?
1 基礎(chǔ)技術(shù)知識點
要實現(xiàn)全文檢索,離不開以下兩個知識點:
-
倒排索引
-
分詞
這兩個技術(shù)是實現(xiàn)全文檢索的技術(shù)以及難點,其實現(xiàn)的過程相對比較復(fù)雜,在聊全文索引的實現(xiàn)前,我們先來具體聊一下這兩個技術(shù)的實現(xiàn)。
?倒排檢索?
先簡單介紹下倒排索引,倒排索引的概念區(qū)別于正排索引:
-
正排索引:是以文檔對象的唯一 ID 作為索引,以文檔內(nèi)容作為記錄的結(jié)構(gòu)
-
倒排索引:是以文檔內(nèi)容中的單詞作為索引,將包含該詞的文檔 ID 作為記錄的結(jié)構(gòu)
以倒排索引庫 search-index 舉個實際的例子。在網(wǎng)易云信的 IM 中,每條消息對象都有 idClient 作為唯一 ID,接下來我們輸入「今天天氣真好」,將其每個中文單獨分詞(分詞的概念我們在下文會詳細(xì)分享),于是輸入變成了「今」、「天」、「天」、「氣」、「真」、「好」,再通過 search-index 的 PUT 方法將其寫入庫中,最后看下存儲內(nèi)容的結(jié)構(gòu):
如圖所示,可以看到倒排索引的結(jié)構(gòu),key 是分詞后的單個中文,value 是包含該中文消息對象的 idClient 組成的數(shù)組。當(dāng)然,search-index 除了以上這些內(nèi)容,還有一些其他內(nèi)容,例如 Weight、Count 以及正排的數(shù)據(jù)等,這些是為了排序、分頁、按字段搜索等功能而存在的,本文就不再細(xì)細(xì)展開了。
?分詞?
分詞就是將原先一條消息的內(nèi)容,根據(jù)語義切分成多個單字或詞句,考慮到中文分詞的效果以及需要在 Node 上運行,我們選擇了 Nodejieba 作為基礎(chǔ)分詞庫。以下是 jieba 分詞的流程圖:
以「去北京大學(xué)玩」為例,我們選擇其中最為重要的幾個模塊分析一下:
加載詞典
jieba 分詞會在初始化時先加載詞典,大致內(nèi)容如下:
構(gòu)建前綴詞典
接下來會根據(jù)該詞典構(gòu)建前綴詞典,結(jié)構(gòu)如下:
其中,「北京大」作為「北京大學(xué)」的前綴,它的詞頻是0,這是為了便于后續(xù)構(gòu)建 DAG 圖。
構(gòu)建 DAG 圖
DAG 圖是 Directed Acyclic Graph 的縮寫,即有向無環(huán)圖。
基于前綴詞典,對輸入的內(nèi)容進行切分。其中,「去」沒有前綴,因此只有一種切分方式;對于「北」,則有「北」、「北京」、「北京大學(xué)」三種切分方式;對于「京」,也只有一種切分方式;對于「大」,有「大」、「大學(xué)」兩種切分方式;對于「學(xué)」和「玩」,依然只有一種切分方式。如此,可以得到每個字作為前綴詞的切分方式,其 DAG 圖如下圖所示:
最大概率路徑計算
以上 DAG 圖的所有路徑如下:
-
去/北/京/大/學(xué)/玩
-
去/北京/大/學(xué)/玩
-
去/北京/大學(xué)/玩
-
去/北京大學(xué)/玩
因為每個節(jié)點都是有權(quán)重(Weight)的,對于在前綴詞典里的詞語,它的權(quán)重就是它的詞頻。因此我們的問題就是想要求得一條最大路徑,使得整個句子的權(quán)重最高。
這是一個典型的動態(tài)規(guī)劃問題,首先我們確認(rèn)下動態(tài)規(guī)劃的兩個條件:
-
重復(fù)子問題:對于節(jié)點 i 和其可能存在的多個后繼節(jié)點 j 和 k:
即對于擁有公共前驅(qū)節(jié)點 i 的 j 和 k,需要重復(fù)計算到達(dá) i 路徑的權(quán)重。
-
最優(yōu)子結(jié)構(gòu):設(shè)整個句子的最優(yōu)路徑為 Rmax,末端節(jié)點為 x,多個可能存在的前驅(qū)節(jié)點為 i、j、k,得到公式如下:
于是問題變成了求解 Rmaxi、Rmaxj 以及 Rmaxk,子結(jié)構(gòu)里的最優(yōu)解即是全局最優(yōu)解的一部分。
如上,最后計算得出最優(yōu)路徑為「去/北京大學(xué)/玩」。
HMM 隱式馬爾科夫模型
對于未登陸詞,jieba 分詞采用 HMM(Hidden Markov Model 的縮寫)模型進行分詞。它將分詞問題視為一個序列標(biāo)注問題,句子為觀測序列,分詞結(jié)果為狀態(tài)序列。jieba 分詞作者在 issue 中提到,HMM 模型的參數(shù)基于網(wǎng)上能下載到的 1998 人民日報的切分語料,一個 MSR 語料以及自己收集的 TXT 小說、用 ICTCLAS 切分,最后用 Python 腳本統(tǒng)計詞頻而成。
該模型由一個五元組組成,并有兩個基本假設(shè)。
五元組:
-
狀態(tài)值集合
-
觀察值集合
-
狀態(tài)初始概率
-
狀態(tài)轉(zhuǎn)移概率
-
狀態(tài)發(fā)射概率
基本假設(shè):
-
齊次性假設(shè):即假設(shè)隱藏的馬爾科夫鏈在任意時刻 t 的狀態(tài)只依賴于其前一時刻 t-1 的狀態(tài),與其它時刻的狀態(tài)及觀測無關(guān),也與時刻 t 無關(guān)。
-
觀察值獨立性假設(shè):即假設(shè)任意時刻的觀察值只與該時刻的馬爾科夫鏈的狀態(tài)有關(guān),與其它觀測和狀態(tài)無關(guān)。
狀態(tài)值集合即{ B: begin, E: end, M: middle, S: single },表示每個字所處在句子中的位置,B 為開始位置,E 為結(jié)束位置,M 為中間位置,S 是單字成詞。
觀察值集合就是我們輸入句子中每個字組成的集合。
狀態(tài)初始概率表明句子中的第一個字屬于 B、M、E、S 四種狀態(tài)的概率,其中 E 和 M 的概率都是0,因為第一個字只可能 B 或者 S,這與實際相符。
狀態(tài)轉(zhuǎn)移概率表明從狀態(tài) 1 轉(zhuǎn)移到狀態(tài) 2 的概率,滿足齊次性假設(shè),結(jié)構(gòu)可以用一個嵌套的對象表示:
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'] 表示從狀態(tài) B 轉(zhuǎn)移到狀態(tài) E 的概率(結(jié)構(gòu)中為概率的對數(shù),方便計算)為 0.6,同理,P['B']['M'] 表示下一個狀態(tài)是 M 的概率為 0.4,說明當(dāng)一個字處于開頭時,下一個字處于結(jié)尾的概率高于下一個字處于中間的概率,符合直覺,因為二個字的詞比多個字的詞要更常見。
狀態(tài)發(fā)射概率表明當(dāng)前狀態(tài),滿足觀察值獨立性假設(shè),結(jié)構(gòu)同上,也可以用一個嵌套的對象表示:
P = {B: {'突': -2.70366861046, '肅': -10.2782270947, '適': -5.57547658034},M: {'要': -4.26625051239, '合': -2.1517176509, '成': -5.11354837278},S: {……},E: {……}, }P['B']['突'] 的含義就是狀態(tài)處于 B,觀測的字是「突」的概率的對數(shù)值等于 -2.70366861046。
最后,通過 Viterbi 算法,輸入觀察值集合,將狀態(tài)初始概率、狀態(tài)轉(zhuǎn)移概率、狀態(tài)發(fā)射概率作為參數(shù),輸出狀態(tài)值集合(即最大概率的分詞結(jié)果)。關(guān)于 Viterbi 算法,本文不再詳細(xì)展開,有興趣的讀者可以自行查閱。
以上這兩塊技術(shù),是我們架構(gòu)的技術(shù)核心。基于此,我們對網(wǎng)易云信 IM 的 Electron 端技術(shù)架構(gòu)做了改進。
?
?
2 網(wǎng)易云信 IM Electron 端架構(gòu)
?架構(gòu)圖詳解?
考慮到全文檢索只是 IM 中的一個功能,為了不影響其他 IM 的功能,并且能更快的迭代需求,所以采用了如下的架構(gòu)方案:
右邊是之前的技術(shù)架構(gòu),底層存儲庫使用了 indexDB,上層有讀寫兩個模塊:
-
當(dāng)用戶主動發(fā)送消息、主動同步消息、主動刪除消息以及收到消息的時候,會將消息對象同步到 indexDB;
-
當(dāng)用戶需要查詢關(guān)鍵字的時候,會去 indexDB 中遍歷所有的消息對象,再使用 indexOf 判斷每一條消息對象是否包含所查詢的關(guān)鍵字(類似 LIKE)。
那么,當(dāng)數(shù)據(jù)量大的時候,查詢的速度是非常緩慢的。
左邊是加入了分詞以及倒排索引數(shù)據(jù)庫的新的架構(gòu)方案,這個方案不會對之前的方案有任何影響,只是在之前的方案之前加了一層,現(xiàn)在:
-
當(dāng)用戶主動發(fā)送消息、主動同步消息、主動刪除消息以及收到消息的時候,會將每一條消息對象中的消息經(jīng)過分詞后同步到倒排索引數(shù)據(jù)庫;
-
當(dāng)用戶需要查詢關(guān)鍵字的時候,會先去倒排索引數(shù)據(jù)庫中找出對應(yīng)消息的 idClient,再根據(jù) idClient 去 indexDB 中找出對應(yīng)的消息對象返回給用戶。
?架構(gòu)優(yōu)點?
該方案有以下4個優(yōu)點:
-
速度快:通過 search-index 實現(xiàn)倒排索引,從而提升了搜索速度。
-
跨平臺:因為 search-index 與 indexDB 都是基于 levelDB,因此 search-index 也支持瀏覽器環(huán)境,這樣就為 Web 端實現(xiàn)全文檢索提供了可能性。
-
獨立性:倒排索引庫與 IM 主業(yè)務(wù)庫 indexDB 分離。當(dāng) indexDB 寫入數(shù)據(jù)時,會自動通知到倒排索引庫的寫模塊,將消息內(nèi)容分詞后,插入到存儲隊列當(dāng)中,最后依次插入到倒排索引數(shù)據(jù)庫中。當(dāng)需要全文檢索時,通過倒排索引庫的讀模塊,能快速找到對應(yīng)關(guān)鍵字的消息對象的 idClient,根據(jù) idClient 再去 indexDB 中找到消息對象并返回。
-
靈活性:全文檢索以插件的形式接入,它暴露出一個高階函數(shù),包裹 IM 并返回新的經(jīng)過繼承擴展的 IM,因為 JS 面向原型的機制,在新的 IM 中不存在的方法,會自動去原型鏈(即老的 IM)當(dāng)中查找,因此,使得插件可以聚焦于自身方法的實現(xiàn)上,并且不需要關(guān)心 IM 的具體版本,并且插件支持自定義分詞函數(shù),滿足不同用戶不同分詞需求的場景。
?使用效果?
使用了如上架構(gòu)后,經(jīng)過我們的測試,在數(shù)據(jù)量 20W 的級別上,搜索時間從最開始的十幾秒降到一秒內(nèi),搜索速度快了 20 倍左右。
?
?
3 總結(jié)
以上,我們便基于 Nodejieba 和 search-index 在 Electron 上實現(xiàn)了網(wǎng)易云信 IM SDK 聊天消息的全文檢索,加快了聊天記錄的搜索速度。當(dāng)然,后續(xù)我們還會針對以下方面做更多的優(yōu)化,比如:
-
寫入性能提升?:在實際的使用中,發(fā)現(xiàn)當(dāng)數(shù)據(jù)量大了以后,search-index 依賴的底層數(shù)據(jù)庫 levelDB 會存在寫入性能瓶頸,并且 CPU 和內(nèi)存的消耗較大。經(jīng)過調(diào)研,SQLite 的寫入性能相對要好很多,從觀測來看,寫入速度只與數(shù)據(jù)量成正比,CPU 和內(nèi)存也相對穩(wěn)定,因此,后續(xù)可能會考慮用將 SQLite 編譯成 Node 原生模塊來替換 search-index。
-
可擴展性?:目前對于業(yè)務(wù)邏輯的解耦還不夠徹底。倒排索引庫當(dāng)中存儲了某些業(yè)務(wù)字段。后續(xù)可以考慮倒排索引庫只根據(jù)關(guān)鍵字查找消息對象的 idClient,將帶業(yè)務(wù)屬性的搜索放到 indexDB 中,將倒排索引庫與主業(yè)務(wù)庫徹底解耦。
以上,就是本文的全部分享,歡迎關(guān)注我們,持續(xù)分享更多技術(shù)干貨。最后,希望我的分享能對大家有所幫助。
?作者介紹?
李寧,網(wǎng)易云信高級前端開發(fā)工程師,負(fù)責(zé)網(wǎng)易云信音視頻 IM SDK 的應(yīng)用開發(fā)、組件化開發(fā)及解決方案開發(fā),對 React、PaaS 組件化設(shè)計、多平臺的開發(fā)與編譯有豐富的實戰(zhàn)經(jīng)驗。有任何的問題,歡迎留言交流。
?延伸閱讀?
-
網(wǎng)易實戰(zhàn)分享|云信IM SDK接口設(shè)計實踐
-
【網(wǎng)易實戰(zhàn)解讀】如何實現(xiàn)IM萬人群聊?
?
?
總結(jié)
以上是生活随笔為你收集整理的技术干货 | 如何在 Electron 上实现 IM SDK 聊天消息全文检索的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 娱乐社交,玩票大的!网易云信“2021融
- 下一篇: 探寻用户自定义定时任务的实践方案