1、引言
在IM客戶端的使用場景中，基于本地?cái)?shù)據(jù)的全文檢索功能扮演著重要的角色，最常用的比如：查找聊天記錄、聯(lián)系人，就像下圖這樣。
▲ 微信的聊天記錄查找功能
類似于IM中的聊天記錄查找、聯(lián)系人搜索這類功能，有了全文檢索能力后，確實(shí)能大大提高內(nèi)容查找的效率，不然，讓用戶手動(dòng)翻找，確實(shí)降低了用戶體驗(yàn)。
本文將具體來聊聊網(wǎng)易云信是如何實(shí)現(xiàn)IM客戶端全文檢索能力的，希望能帶給你啟發(fā)。
（本文同步發(fā)布于：http://www.52im.net/thread-3651-1-1.html）
2、關(guān)于作者
李寧：網(wǎng)易云信高級(jí)前端開發(fā)工程師，負(fù)責(zé)音視頻 IM SDK 的應(yīng)用開發(fā)、組件化開發(fā)及解決方案開發(fā)，對(duì) React、PaaS 組件化設(shè)計(jì)、多平臺(tái)的開發(fā)與編譯有豐富的實(shí)戰(zhàn)經(jīng)驗(yàn)。
3、相關(guān)文章
IM客戶端全文檢索相關(guān)文章：
- 《微信手機(jī)端的本地?cái)?shù)據(jù)全文檢索優(yōu)化之路》
- 《微信團(tuán)隊(duì)分享：微信移動(dòng)端的全文檢索多音字問題解決方案》
網(wǎng)易技術(shù)團(tuán)隊(duì)分享的其它文章：
- 《網(wǎng)易視頻云技術(shù)分享：音頻處理與壓縮技術(shù)快速入門》
- 《網(wǎng)易云信實(shí)時(shí)視頻直播在TCP數(shù)據(jù)傳輸層的一些優(yōu)化思路》
- 《網(wǎng)易云信技術(shù)分享：IM中的萬人群聊技術(shù)方案實(shí)踐總結(jié)》
- 《Web端即時(shí)通訊實(shí)踐干貨：如何讓你的WebSocket斷網(wǎng)重連更快速？》
- 《子彈短信光鮮的背后：網(wǎng)易云信首席架構(gòu)師分享億級(jí)IM平臺(tái)的技術(shù)實(shí)踐》
4、什么是全文檢索
所謂全文檢索，就是要在大量內(nèi)容中找到包含某個(gè)單詞出現(xiàn)位置的技術(shù)。
在傳統(tǒng)的關(guān)系型數(shù)據(jù)庫中，只能通過 LIKE 條件查詢來實(shí)現(xiàn)，這樣有幾個(gè)弊端：
- 1）無法使用數(shù)據(jù)庫索引，需要遍歷全表，性能較差；
- 2）搜索效果差，只能首尾位模糊匹配，無法實(shí)現(xiàn)復(fù)雜的搜索需求；
- 3）無法得到內(nèi)容與搜索條件的相關(guān)性。
我們?cè)?IM 的 iOS、安卓以及桌面端中都實(shí)現(xiàn)了基于 SQLite 等庫的本地?cái)?shù)據(jù)全文檢索功能，但是在 Web 端和 Electron 上缺少了這部分功能。
因?yàn)樵?Web 端，由于瀏覽器環(huán)境限制，能使用的本地存儲(chǔ)數(shù)據(jù)庫只有 IndexDB，暫不在討論的范圍內(nèi)。但在 Electron 上，雖然也是內(nèi)置了 Chromium 的內(nèi)核，但是因?yàn)榭梢允褂?Node.js 的能力，于是乎選擇的范圍就多了一些。本文內(nèi)容我們具體以基于Electron的IM客戶端為例，來討論全文檢索技術(shù)實(shí)現(xiàn)（技術(shù)思路是相通的，并不局限于具體什么端）。
PS：如果你不了解什么是Electron技術(shù)，讀一下這篇《快速了解Electron：新一代基于Web的跨平臺(tái)桌面技術(shù)》。
我們先來具體看下該如何實(shí)現(xiàn)全文檢索。
要實(shí)現(xiàn)全文檢索，離不開以下兩個(gè)知識(shí)點(diǎn)：
這兩個(gè)技術(shù)是實(shí)現(xiàn)全文檢索的技術(shù)以及難點(diǎn)，其實(shí)現(xiàn)的過程相對(duì)比較復(fù)雜，在聊全文索引的實(shí)現(xiàn)前，我們具體學(xué)習(xí)一下這兩個(gè)技術(shù)的原理。
5、全文檢索知識(shí)點(diǎn)1：倒排索引
先簡單介紹下倒排索引，倒排索引的概念區(qū)別于正排索引：
- 1）正排索引：是以文檔對(duì)象的唯一 ID 作為索引，以文檔內(nèi)容作為記錄的結(jié)構(gòu)；
- 2）倒排索引：是以文檔內(nèi)容中的單詞作為索引，將包含該詞的文檔 ID 作為記錄的結(jié)構(gòu)。
以倒排索引庫 search-index 舉個(gè)實(shí)際的例子：
在我們的 IM 中，每條消息對(duì)象都有 idClient 作為唯一 ID，接下來我們輸入「今天天氣真好」，將其每個(gè)中文單獨(dú)分詞（分詞的概念我們?cè)谙挛臅?huì)詳細(xì)分享），于是輸入變成了「今」、「天」、「天」、「氣」、「真」、「好」。再通過 search-index 的 PUT 方法將其寫入庫中。
最后看下上述例子存儲(chǔ)內(nèi)容的結(jié)構(gòu)：
如是圖所示：可以看到倒排索引的結(jié)構(gòu)，key 是分詞后的單個(gè)中文、value 是包含該中文消息對(duì)象的 idClient 組成的數(shù)組。
當(dāng)然：search-index 除了以上這些內(nèi)容，還有一些其他內(nèi)容，例如 Weight、Count 以及正排的數(shù)據(jù)等，這些是為了排序、分頁、按字段搜索等功能而存在的，本文就不再細(xì)細(xì)展開了。
6、全文檢索知識(shí)點(diǎn)2：分詞
6.1 基本概念
分詞就是將原先一條消息的內(nèi)容，根據(jù)語義切分成多個(gè)單字或詞句，考慮到中文分詞的效果以及需要在 Node 上運(yùn)行，我們選擇了 Nodejieba 作為基礎(chǔ)分詞庫。
以下是 jieba 分詞的流程圖：
以“去北京大學(xué)玩”為例，我們選擇其中最為重要的幾個(gè)模塊分析一下。
6.2 加載詞典
jieba 分詞會(huì)在初始化時(shí)先加載詞典，大致內(nèi)容如下：
6.3 構(gòu)建前綴詞典
接下來會(huì)根據(jù)該詞典構(gòu)建前綴詞典，結(jié)構(gòu)如下：
其中：“北京大”作為“北京大學(xué)”的前綴，它的詞頻是0，這是為了便于后續(xù)構(gòu)建 DAG 圖。
6.4 構(gòu)建 DAG 圖
DAG 圖是 Directed Acyclic Graph 的縮寫，即有向無環(huán)圖。
基于前綴詞典，對(duì)輸入的內(nèi)容進(jìn)行切分。
其中：
- 1）“去”沒有前綴，因此只有一種切分方式；
- 2）對(duì)于“北”，則有“北”、“北京”、“北京大學(xué)”三種切分方式；
- 3）對(duì)于“京”，也只有一種切分方式；
- 4）對(duì)于“大”，有“大”、“大學(xué)”兩種切分方式；
- 5）對(duì)于“學(xué)”和“玩”，依然只有一種切分方式。
如此，可以得到每個(gè)字作為前綴詞的切分方式。
其 DAG 圖如下圖所示：
6.5 最大概率路徑計(jì)算
以上 DAG 圖的所有路徑如下：
去/北/京/大/學(xué)/玩
去/北京/大/學(xué)/玩
去/北京/大學(xué)/玩
去/北京大學(xué)/玩
因?yàn)槊總€(gè)節(jié)點(diǎn)都是有權(quán)重（Weight）的，對(duì)于在前綴詞典里的詞語，它的權(quán)重就是它的詞頻。因此我們的問題就是想要求得一條最大路徑，使得整個(gè)句子的權(quán)重最高。
這是一個(gè)典型的動(dòng)態(tài)規(guī)劃問題，首先我們確認(rèn)下動(dòng)態(tài)規(guī)劃的兩個(gè)條件。
1）重復(fù)子問題：
對(duì)于節(jié)點(diǎn) i 和其可能存在的多個(gè)后繼節(jié)點(diǎn) j 和 k：
- 1）任意通過i到達(dá)j的路徑的權(quán)重 = 該路徑通過i的路徑權(quán)重 + j的權(quán)重，即 R(i -> j) = R(i) + W(j)；
- 2）任意通過i到達(dá)k的路徑的權(quán)重 = 該路徑通過i的路徑權(quán)重 + k的權(quán)重，即 R(i -> k) = R(i) + W(k)。
即對(duì)于擁有公共前驅(qū)節(jié)點(diǎn) i 的 j 和 k，需要重復(fù)計(jì)算到達(dá) i 路徑的權(quán)重。
2）最優(yōu)子結(jié)構(gòu)：
設(shè)整個(gè)句子的最優(yōu)路徑為 Rmax，末端節(jié)點(diǎn)為 x，多個(gè)可能存在的前驅(qū)節(jié)點(diǎn)為 i、j、k。
得到公式如下：
Rmax = max(Rmaxi, Rmaxj, Rmaxk) + W(x)
于是問題變成了求解 Rmaxi、Rmaxj 以及 Rmaxk，子結(jié)構(gòu)里的最優(yōu)解即是全局最優(yōu)解的一部分。
如上，最后計(jì)算得出最優(yōu)路徑為“去/北京大學(xué)/玩”。
6.6 HMM 隱式馬爾科夫模型
對(duì)于未登陸詞，jieba 分詞采用 HMM（Hidden Markov Model 的縮寫）模型進(jìn)行分詞。
它將分詞問題視為一個(gè)序列標(biāo)注問題，句子為觀測序列，分詞結(jié)果為狀態(tài)序列。
jieba 分詞作者在 issue 中提到，HMM 模型的參數(shù)基于網(wǎng)上能下載到的 1998 人民日?qǐng)?bào)的切分語料，一個(gè) MSR 語料以及自己收集的 TXT 小說、用 ICTCLAS 切分，最后用 Python 腳本統(tǒng)計(jì)詞頻而成。
該模型由一個(gè)五元組組成，并有兩個(gè)基本假設(shè)。
五元組：
- 1）狀態(tài)值集合；
- 2）觀察值集合；
- 3）狀態(tài)初始概率；
- 4）狀態(tài)轉(zhuǎn)移概率；
- 5）狀態(tài)發(fā)射概率。
基本假設(shè)：
- 1）齊次性假設(shè)：即假設(shè)隱藏的馬爾科夫鏈在任意時(shí)刻 t 的狀態(tài)只依賴于其前一時(shí)刻 t-1 的狀態(tài)，與其它時(shí)刻的狀態(tài)及觀測無關(guān)，也與時(shí)刻 t 無關(guān)；
- 2）觀察值獨(dú)立性假設(shè)：即假設(shè)任意時(shí)刻的觀察值只與該時(shí)刻的馬爾科夫鏈的狀態(tài)有關(guān)，與其它觀測和狀態(tài)無關(guān)。
狀態(tài)值集合即{ B: begin, E: end, M: middle, S: single }，表示每個(gè)字所處在句子中的位置，B 為開始位置，E 為結(jié)束位置，M 為中間位置，S 是單字成詞。
觀察值集合就是我們輸入句子中每個(gè)字組成的集合。
狀態(tài)初始概率表明句子中的第一個(gè)字屬于 B、M、E、S 四種狀態(tài)的概率，其中 E 和 M 的概率都是0，因?yàn)榈谝粋€(gè)字只可能 B 或者 S，這與實(shí)際相符。
狀態(tài)轉(zhuǎn)移概率表明從狀態(tài) 1 轉(zhuǎn)移到狀態(tài) 2 的概率，滿足齊次性假設(shè)，結(jié)構(gòu)可以用一個(gè)嵌套的對(duì)象表示：
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)中為概率的對(duì)數(shù)，方便計(jì)算）為 0.6，同理，P['B']['M'] 表示下一個(gè)狀態(tài)是 M 的概率為 0.4，說明當(dāng)一個(gè)字處于開頭時(shí)，下一個(gè)字處于結(jié)尾的概率高于下一個(gè)字處于中間的概率，符合直覺，因?yàn)槎€(gè)字的詞比多個(gè)字的詞要更常見。
狀態(tài)發(fā)射概率表明當(dāng)前狀態(tài)，滿足觀察值獨(dú)立性假設(shè)，結(jié)構(gòu)同上，也可以用一個(gè)嵌套的對(duì)象表示：
P = {
B: {'突': -2.70366861046, '肅': -10.2782270947, '適': -5.57547658034},
M: {'要': -4.26625051239, '合': -2.1517176509, '成': -5.11354837278},
S: {……},
E: {……},
}
P['B']['突'] 的含義就是狀態(tài)處于 B，觀測的字是“突”的概率的對(duì)數(shù)值等于 -2.70366861046。
最后，通過 Viterbi 算法，輸入觀察值集合，將狀態(tài)初始概率、狀態(tài)轉(zhuǎn)移概率、狀態(tài)發(fā)射概率作為參數(shù)，輸出狀態(tài)值集合（即最大概率的分詞結(jié)果）。關(guān)于 Viterbi 算法，本文不再詳細(xì)展開，有興趣的讀者可以自行查閱。
7、技術(shù)實(shí)現(xiàn)
上節(jié)中介紹的全文檢索這兩塊技術(shù)，是我們架構(gòu)的技術(shù)核心。基于此，我們對(duì)IM 的 Electron 端技術(shù)架構(gòu)做了改進(jìn)。以下將詳細(xì)介紹之。
7.1 架構(gòu)圖詳解
考慮到全文檢索只是 IM 中的一個(gè)功能，為了不影響其他 IM 的功能，并且能更快的迭代需求，所以采用了如下的架構(gòu)方案。
架構(gòu)圖如下：
如上圖所示，右邊是之前的技術(shù)架構(gòu)，底層存儲(chǔ)庫使用了 indexDB，上層有讀寫兩個(gè)模塊。
讀寫模塊的具體作用是：
- 1）當(dāng)用戶主動(dòng)發(fā)送消息、主動(dòng)同步消息、主動(dòng)刪除消息以及收到消息的時(shí)候，會(huì)將消息對(duì)象同步到 indexDB；
- 2）當(dāng)用戶需要查詢關(guān)鍵字的時(shí)候，會(huì)去 indexDB 中遍歷所有的消息對(duì)象，再使用 indexOf 判斷每一條消息對(duì)象是否包含所查詢的關(guān)鍵字（類似 LIKE）。
那么，當(dāng)數(shù)據(jù)量大的時(shí)候，查詢的速度是非常緩慢的。
左邊是加入了分詞以及倒排索引數(shù)據(jù)庫的新的架構(gòu)方案，這個(gè)方案不會(huì)對(duì)之前的方案有任何影響，只是在之前的方案之前加了一層。
現(xiàn)在，讀寫模塊的工作邏輯：
- 1）當(dāng)用戶主動(dòng)發(fā)送消息、主動(dòng)同步消息、主動(dòng)刪除消息以及收到消息的時(shí)候，會(huì)將每一條消息對(duì)象中的消息經(jīng)過分詞后同步到倒排索引數(shù)據(jù)庫；
- 2）當(dāng)用戶需要查詢關(guān)鍵字的時(shí)候，會(huì)先去倒排索引數(shù)據(jù)庫中找出對(duì)應(yīng)消息的 idClient，再根據(jù) idClient 去 indexDB 中找出對(duì)應(yīng)的消息對(duì)象返回給用戶。
7.2 架構(gòu)優(yōu)點(diǎn)
該方案有以下4個(gè)優(yōu)點(diǎn)：
- 1）速度快：通過 search-index 實(shí)現(xiàn)倒排索引，從而提升了搜索速度。
- 2）跨平臺(tái)：因?yàn)?search-index 與 indexDB 都是基于 levelDB，因此 search-index 也支持瀏覽器環(huán)境，這樣就為 Web 端實(shí)現(xiàn)全文檢索提供了可能性；
- 3）獨(dú)立性：倒排索引庫與 IM 主業(yè)務(wù)庫 indexDB 分離；
- 4）靈活性：全文檢索以插件的形式接入。
針對(duì)上述第“3）”點(diǎn)：當(dāng) indexDB 寫入數(shù)據(jù)時(shí)，會(huì)自動(dòng)通知到倒排索引庫的寫模塊，將消息內(nèi)容分詞后，插入到存儲(chǔ)隊(duì)列當(dāng)中，最后依次插入到倒排索引數(shù)據(jù)庫中。當(dāng)需要全文檢索時(shí)，通過倒排索引庫的讀模塊，能快速找到對(duì)應(yīng)關(guān)鍵字的消息對(duì)象的 idClient，根據(jù) idClient 再去 indexDB 中找到消息對(duì)象并返回。
針對(duì)上述第“4）”點(diǎn)：它暴露出一個(gè)高階函數(shù)，包裹 IM 并返回新的經(jīng)過繼承擴(kuò)展的 IM，因?yàn)?JS 面向原型的機(jī)制，在新的 IM 中不存在的方法，會(huì)自動(dòng)去原型鏈（即老的 IM）當(dāng)中查找，因此，使得插件可以聚焦于自身方法的實(shí)現(xiàn)上，并且不需要關(guān)心 IM 的具體版本，并且插件支持自定義分詞函數(shù)，滿足不同用戶不同分詞需求的場景
7.3 使用效果
使用了如上架構(gòu)后，經(jīng)過我們的測試，在數(shù)據(jù)量 20W 的級(jí)別上，搜索時(shí)間從最開始的十幾秒降到一秒內(nèi)，搜索速度快了 20 倍左右。
8、本文小結(jié)
本文中，我們便基于 Nodejieba 和 search-index 在 Electron 上實(shí)現(xiàn)了IM聊天消息的全文檢索，加快了聊天記錄的搜索速度。
當(dāng)然，后續(xù)我們還會(huì)針對(duì)以下方面做更多的優(yōu)化，比如以下兩點(diǎn)：
1）寫入性能 ：在實(shí)際的使用中，發(fā)現(xiàn)當(dāng)數(shù)據(jù)量大了以后，search-index 依賴的底層數(shù)據(jù)庫 levelDB 會(huì)存在寫入性能瓶頸，并且 CPU 和內(nèi)存的消耗較大。經(jīng)過調(diào)研，SQLite 的寫入性能相對(duì)要好很多，從觀測來看，寫入速度只與數(shù)據(jù)量成正比，CPU 和內(nèi)存也相對(duì)穩(wěn)定，因此，后續(xù)可能會(huì)考慮用將 SQLite 編譯成 Node 原生模塊來替換 search-index。
2）可擴(kuò)展性 ：目前對(duì)于業(yè)務(wù)邏輯的解耦還不夠徹底。倒排索引庫當(dāng)中存儲(chǔ)了某些業(yè)務(wù)字段。后續(xù)可以考慮倒排索引庫只根據(jù)關(guān)鍵字查找消息對(duì)象的 idClient，將帶業(yè)務(wù)屬性的搜索放到 indexDB 中，將倒排索引庫與主業(yè)務(wù)庫徹底解耦。
以上，就是本文的全部分享，希望我的分享能對(duì)大家有所幫助。
附錄：更多IM干貨技術(shù)文章
《新手入門一篇就夠：從零開發(fā)移動(dòng)端IM》
《從客戶端的角度來談?wù)勔苿?dòng)端IM的消息可靠性和送達(dá)機(jī)制》
《移動(dòng)端IM中大規(guī)模群消息的推送如何保證效率、實(shí)時(shí)性？》
《移動(dòng)端IM開發(fā)需要面對(duì)的技術(shù)問題》
《IM消息送達(dá)保證機(jī)制實(shí)現(xiàn)(一)：保證在線實(shí)時(shí)消息的可靠投遞》
《IM消息送達(dá)保證機(jī)制實(shí)現(xiàn)(二)：保證離線消息的可靠投遞》
《如何保證IM實(shí)時(shí)消息的“時(shí)序性”與“一致性”？》
《一個(gè)低成本確保IM消息時(shí)序的方法探討》
《IM單聊和群聊中的在線狀態(tài)同步應(yīng)該用“推”還是“拉”？》
《IM群聊消息如此復(fù)雜，如何保證不丟不重？》
《談?wù)勔苿?dòng)端 IM 開發(fā)中登錄請(qǐng)求的優(yōu)化》
《移動(dòng)端IM登錄時(shí)拉取數(shù)據(jù)如何作到省流量？》
《淺談移動(dòng)端IM的多點(diǎn)登錄和消息漫游原理》
《完全自已開發(fā)的IM該如何設(shè)計(jì)“失敗重試”機(jī)制？》
《通俗易懂：基于集群的移動(dòng)端IM接入層負(fù)載均衡方案分享》
《微信對(duì)網(wǎng)絡(luò)影響的技術(shù)試驗(yàn)及分析（論文全文）》
《微信技術(shù)分享：微信的海量IM聊天消息序列號(hào)生成實(shí)踐（算法原理篇）》
《自已開發(fā)IM有那么難嗎？手把手教你自擼一個(gè)Andriod版簡易IM (有源碼)》
《融云技術(shù)分享：解密融云IM產(chǎn)品的聊天消息ID生成策略》
《適合新手：從零開發(fā)一個(gè)IM服務(wù)端（基于Netty，有完整源碼）》
《拿起鍵盤就是干：跟我一起徒手開發(fā)一套分布式IM系統(tǒng)》
《適合新手：手把手教你用Go快速搭建高性能、可擴(kuò)展的IM系統(tǒng)(有源碼)》
《IM里“附近的人”功能實(shí)現(xiàn)原理是什么？如何高效率地實(shí)現(xiàn)它？》
《IM消息ID技術(shù)專題(一)：微信的海量IM聊天消息序列號(hào)生成實(shí)踐（算法原理篇）》
《IM開發(fā)寶典：史上最全，微信各種功能參數(shù)和邏輯規(guī)則資料匯總》
《IM開發(fā)干貨分享：我是如何解決大量離線消息導(dǎo)致客戶端卡頓的》
《零基礎(chǔ)IM開發(fā)入門(一)：什么是IM系統(tǒng)？》
《零基礎(chǔ)IM開發(fā)入門(二)：什么是IM系統(tǒng)的實(shí)時(shí)性？》
《零基礎(chǔ)IM開發(fā)入門(三)：什么是IM系統(tǒng)的可靠性？》
《零基礎(chǔ)IM開發(fā)入門(四)：什么是IM系統(tǒng)的消息時(shí)序一致性？》
《一套億級(jí)用戶的IM架構(gòu)技術(shù)干貨(下篇)：可靠性、有序性、弱網(wǎng)優(yōu)化等》
《IM掃碼登錄技術(shù)專題(三)：通俗易懂，IM掃碼登錄功能詳細(xì)原理一篇就夠》
《理解IM消息“可靠性”和“一致性”問題，以及解決方案探討》
《阿里技術(shù)分享：閑魚IM基于Flutter的移動(dòng)端跨端改造實(shí)踐》
《融云技術(shù)分享：全面揭秘億級(jí)IM消息的可靠投遞機(jī)制》
《IM開發(fā)干貨分享：如何優(yōu)雅的實(shí)現(xiàn)大量離線消息的可靠投遞》
《IM開發(fā)干貨分享：有贊移動(dòng)端IM的組件化SDK架構(gòu)設(shè)計(jì)實(shí)踐》
《IM開發(fā)干貨分享：網(wǎng)易云信IM客戶端的聊天消息全文檢索技術(shù)實(shí)踐》
>> 更多同類文章 ……
（本文同步發(fā)布于：http://www.52im.net/thread-3651-1-1.html）