IM跨平臺技術學習(六)：網易云信基于Electron的IM消息全文檢索技術實踐

Posted on 2022-10-27 11:18 Jack Jiang 閱讀(93) 評論(0) 編輯收藏

本文作者網易云信高級前端開發工程師李寧，本文有修訂。

1、引言

在IM客戶端的使用場景中，基于本地數據的全文檢索功能扮演著重要的角色，最常用的比如：查找聊天記錄、聯系人等。

類似于IM中的聊天記錄查找、聯系人搜索這類功能，有了全文檢索能力后，確實能大大提高內容查找的效率，不然，讓用戶手動翻找，確實降低了用戶體驗。

本文將要分享的是，網易云信基于Electron的PC端是如何實現IM客戶端全文檢索能力的。

學習交流：

- 移動端IM開發入門文章：《新手入門一篇就夠：從零開發移動端IM》
- 開源IM框架源碼：https://github.com/JackJiang2011/MobileIMSDK（備用地址點此）

（本文已同步發布于：http://www.52im.net/thread-4065-1-1.html）

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，子結構里的最優解即是全局最優解的一部分。

如上，最后計算得出最優路徑為“去/北京大學/玩”。

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

架構圖如下：

如上圖所示，右邊是之前的技術架構，底層存儲庫使用了 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 中，將倒排索引庫與主業務庫徹底解耦。

以上，就是本文的全部分享，希望我的分享能對大家有所幫助。