本文來自微信開發(fā)團隊WeMobileDev公眾號的技術(shù)分享。
1、前言
微信的移動客戶端全文搜索中的多音字問題一直是搜索體驗的痛點之一。微信客戶端全文搜索在上線以后,也經(jīng)常收到用戶關(guān)于多音字問題的反饋。所以,微信全文搜索中的多音字搜索成了一個迫切需要解決的問題。本文重點講述微信安卓客戶端在SQLite FTS5的基礎(chǔ)上,多音字問題的解決方案。
另外:微信團隊在另一個文章《微信手機端的本地數(shù)據(jù)全文檢索優(yōu)化之路》 中,分享了更為詳細的全文檢索優(yōu)化思路,建議有興趣的開發(fā)者可以深入的看看。
建議:您也可以在微信客戶端的sqlite數(shù)據(jù)庫中找到本文中相關(guān)技術(shù)的真實實現(xiàn),微信的SQLite樣本庫可在此下載《微信本地數(shù)據(jù)庫破解版(含iOS、Android),僅供學(xué)習(xí)研究 [附件下載]》(特別申明:微信的SQLite樣本庫僅供研究和學(xué)習(xí)之外,嚴禁用于商用業(yè)目的,所有權(quán)歸微信所有)。
學(xué)習(xí)交流:
- 即時通訊開發(fā)交流群:320837163[推薦]
- 移動端IM開發(fā)入門文章:《新手入門一篇就夠:從零開發(fā)移動端IM》
(本文同步發(fā)布于:http://www.52im.net/thread-1545-1-1.html)
2、相關(guān)文章
《微信手機端的本地數(shù)據(jù)全文檢索優(yōu)化之路》
《騰訊技術(shù)分享:Android版手機QQ的緩存監(jiān)控與優(yōu)化實踐》
《微信團隊分享:iOS版微信的高性能通用key-value組件技術(shù)實踐》
《微信團隊分享:iOS版微信是如何防止特殊字符導(dǎo)致的炸群、APP崩潰的?》
《騰訊技術(shù)分享:Android手Q的線程死鎖監(jiān)控系統(tǒng)技術(shù)實踐》
《微信團隊原創(chuàng)分享:iOS版微信的內(nèi)存監(jiān)控系統(tǒng)技術(shù)實踐》
《iOS后臺喚醒實戰(zhàn):微信收款到賬語音提醒技術(shù)總結(jié)》
《騰訊團隊分享 :一次手Q聊天界面中圖片顯示bug的追蹤過程分享》
《微信團隊披露:微信界面卡死超級bug“15。。。。”的來龍去脈》
《微信客戶端團隊負責(zé)人技術(shù)訪談:如何著手客戶端性能監(jiān)控和優(yōu)化》
《微信團隊原創(chuàng)分享:微信客戶端SQLite數(shù)據(jù)庫損壞修復(fù)實踐》
《移動端IM實踐:iOS版微信界面卡頓監(jiān)測方案》
《移動端IM實踐:Android版微信如何大幅提升交互性能(一)》
《移動端IM實踐:Android版微信如何大幅提升交互性能(二)》
《移動端IM實踐:iOS版微信的多設(shè)備字體適配方案探討》
《信鴿團隊原創(chuàng):一起走過 iOS10 上消息推送(APNS)的坑》
3、微信的全文檢索需求
搜索形式:
拼音前綴搜索,中文和拼音不能混合搜索,輸入拼音必須為連續(xù)漢字的全拼音或者短拼音。
搜索內(nèi)容:
聯(lián)系人、群聊以及公眾號的備注和昵稱(最大長度為16個中文字符)。
例如。
聯(lián)系人A,昵稱為“王宏偉”,那么通過以下幾種方式都需要搜索到聯(lián)系人A的昵稱:
4、詞表方案
中文全文搜索引擎如果需要支持拼音,就需要把輸入的中文字符,轉(zhuǎn)化為拼音字母,如果不考慮多音字的情況,我們只需要一張單個漢字的拼音表即可實現(xiàn)轉(zhuǎn)化,但是在多音字的情況下,由于每個漢字在不同的詞語當(dāng)中的讀音都有可能不一樣,所以,為了使得每個中文字符能夠獲取到準(zhǔn)確的拼音,就需要引入一份詞語拼音對應(yīng)表。
眾所周知,漢語博大精深,常用的漢字有20777個,而詞語(包括成語)的漢字個數(shù)為2到16個,同一個漢字在不同詞語中讀音有可能不一樣。
所以漢語詞語轉(zhuǎn)化為拼音有如下兩個方案:
1)窮舉詞語表;
2)采用概率模型,通過訓(xùn)練分類器模型,獲取中文字符拼音。
第一種方案對存儲空間的要求非常高,對資源的消耗過大。
第二種方案,通過在現(xiàn)有的TTS(Text To Speech)模型中,把漢字轉(zhuǎn)拼音讀音的模型拆出來,初步搭建一個概率模型,在初步的調(diào)優(yōu)后,得到一個1個G的拼音模型,識別拼音的準(zhǔn)確在可接受范圍內(nèi)。由于模型大小為GB級別,初步考慮是將模型放到后臺處理。
處理流程如下圖:
優(yōu)點:
客戶端無改動,可以快速覆蓋所有版本客戶端。
缺點:
用戶修改備注或者昵稱后,需要等待后臺下發(fā)拼音后才能有正確的拼音索引,導(dǎo)致拼音索引建立不夠及時。微信用戶量巨大,用戶修改備注和昵稱的頻次非常高,每天都有幾十億次修改,導(dǎo)致后臺處理這部分的運算量和耗時非常嚴重,需要增加較大成本。
5、字表方案
常用漢字有20777個,總體大小為200KB,可以直接帶到客戶端中,并且查詢的時間復(fù)雜度為O(1),在數(shù)據(jù)量方面是可以接受的。
優(yōu)點:
用戶修改昵稱或者備注以后,能夠快速響應(yīng)并及時建立索引;
將后臺巨大的計算量均攤到用戶手機上,節(jié)省成本;
對于姓名中漢字的讀音,可以用任意一個讀音搜索出來。
缺點:
在用戶體驗上,詞語中的多音字可以用任意該漢字的拼音搜索出來;
在綜合考慮用戶體驗和性能問題后,最后微信選擇了字表方案。
6、客戶端索引方案
在確定字表方案后,需要在客戶端本地使用SQLite FTS5建立索引。因為拼音搜索主要是采用前綴搜索的方式,所以建立索引的內(nèi)容以及方式需要考慮FTS5前綴搜索的過程。
路徑(1)是在建立索引表時使用Prefix索引,所以用戶在輸入Query時,直接通過Hash方法查找前綴索引表即可找到所有以Query為前綴的結(jié)果。
路徑(2)是在建立索引表時未使用Prefix索引,所以用戶在輸入Query時,F(xiàn)TS5通過臨時搭建一個前綴樹來查找以Query為Preifx的索引集合。
從時間復(fù)雜度上,路徑1具有明顯優(yōu)勢,所以在建立索引時,需要加入Prefix配置:
6.1 索引方案一
考慮到用戶輸入時是連續(xù)輸入,并不會考慮跨拼音問題。
例如,用戶搜索備注“市委書記”的拼音,會可能采用如下的Query:
shi
shiweishuj
sw
根據(jù)以上用戶輸入習(xí)慣以及FTS5前綴搜索原理,采用第一個索引方案:
在FTS5匹配以上Query時,用戶1、2兩種輸入都作為"shiweishuji"的前綴被匹配,而3的輸入會作為“swsj”的前綴被匹配。
6.2 索引方案二
索引方案一僅考慮用戶從拼音的頭部開始搜索,并沒有考慮從中間開始搜索。
例如以下的Query:
shuji
sj
所以,需要建立索引時,需要把每個漢字的拼音作為前綴建立到索引中,如下表:
6.3 索引方案三
方案一和方案二是在不考慮多音字的情況的索引方案,當(dāng)引入了多音字以后,在組合拼音字符串時,每一個拼音都可能存在多種情況。
以下為用戶備注“張靚穎”的索引:
當(dāng)昵稱“張靚穎”建立索引以后,得到如下索引結(jié)構(gòu):
TermOffset:表示一個詞語在某一個Document中的偏移;
DocId:Document的唯一ID。
通過一個DocId和一個TermOffset可以定位一個詞語。而SQLite FTS5正是通過搜索一個詞語來找到對應(yīng)的DocId,通過TermOffset來定位該詞語在Document中的位置。
方案優(yōu)點:
實現(xiàn)較為簡單;
可覆蓋所有多音字情況。
方案缺點:
索引數(shù)據(jù)量過大;
考慮常用漢字一共20777個,其中多音字2659個,多音字占比12.7%,平均每個多音字有2.14個拼音。
在微信場景中,聯(lián)系人的備注和昵稱最大字符長度為16個字符,所以我們假設(shè)每個昵稱的字符為16個漢字,其中,每個漢字的拼音長度為最長度(7個英文字母+1個短拼音英文字母)。
一般場景:
其中20777個漢字當(dāng)中,出現(xiàn)在昵稱中的概率一樣,所以16個字符中,大約會出現(xiàn)3個多音字,得到如下公式:
極限場景:
昵稱中每一個字都是多音字,每個多音字都有4個讀音,例如“么么么么么么么么么么么么么么么么”,得到如下公式:
從以上兩種場景中可以看出,方案三在極限場景中會出現(xiàn)占用超大數(shù)據(jù)量的情況,所以方案三不可用。
6.4 索引方案四
方案三通過窮舉法來列舉所有拼音組合,核心在于通過空間換區(qū)時間,在所需要的空間過于巨大時,可以采取折中的方案來實現(xiàn)。
在漢語中,一個同樣意義的實體通過兩個不同的詞語來表示,稱這兩個不同的詞語為同義詞,在數(shù)據(jù)上表示為(詞語A,詞語B)=(意義C),那么在多音字的情況來看,同樣可以表示為(拼音A,拼音B)=(漢字C)。方案四的核心在于通過同義詞的方式來表示多種拼音的組合。
在SQLite FTS5中,一個詞語可以通過一個DocId和一個TermOffset來定位,所以當(dāng)兩個詞語擁有同一個DocId和TermOffset時,就可以說這兩個詞語為同義詞了,也就有了如下的索引方案:
方案優(yōu)點:
索引數(shù)據(jù)量小:
1)一般情況:
2)極限情況:
建立索引速度快。
方案缺點:
默認分詞器不能適配多音字的拼音數(shù)據(jù);
索引中的數(shù)據(jù)不能直接對應(yīng)用戶輸入。
為了解決方案四的兩個問題,我們引入了多音字分詞器,并且做了用戶輸入預(yù)處理。
7、多音字分詞器
SQLite FTS5默認的分詞器的分隔符都是固定的,所以,在識別拼音字符時,會當(dāng)成英文字母來分詞。為了能夠達到需要的索引結(jié)構(gòu),我們引入了二級分隔符,使用分號“;”分隔不同漢字以及“,”分隔同一個漢字的不同拼音。
以下是多音字分詞器的分詞流程:
8、用戶輸入預(yù)處理
當(dāng)用戶的輸入為連續(xù)拼音時,由于索引中不存在直接對應(yīng)的Term,所以需要把用戶輸入的Query拆解成為索引當(dāng)中可能存在的Term。
假設(shè)用戶輸入拼音:zhuang,根據(jù)短拼音和全拼音的規(guī)則,可得到如下7中搜索組合:
考慮到最后一個拼音為前綴搜索,所以,在列舉拼音組合時,前面都需要考慮符合完整的拼音,最后一個可以只考慮是否是某個拼音的前綴。
實現(xiàn)這個算法可以通過把所有的拼音作為輸入,構(gòu)建一顆前綴樹,能夠把整個Query拼音拆解的時間復(fù)雜度降低到O(nlgn)。
最后,把所有的拼音組合情況都寫到SQL中:
9、方案的實際效果
對比方案三和方案四,在拼音數(shù)據(jù)上有較為明顯的提升,提升的范圍在50%左右。
由于聯(lián)系人拼音數(shù)據(jù)的減少,使得單個聯(lián)系人的數(shù)據(jù)量下降,減少了Insert SQL的執(zhí)行時間,建立聯(lián)系人索引的時間也有較為明顯的降低,減少30%左右。
在搜索Query的時間上,多音字方案因為拼音組合的多樣性,增加了查找HashTable的次數(shù),但是由于搜索HashTable的時間復(fù)雜度為O(1),而拼音組合在有限字符的query下不多(小于20個),所以增加時間不多,但是由于數(shù)據(jù)量的減少,ORM的時間縮短,搜索Query的時間有15%左右的提升。
更為詳細的微信全文檢索優(yōu)化思路請見《微信手機端的本地數(shù)據(jù)全文檢索優(yōu)化之路》。微信的本地SQLite研究樣本可從此下載《微信本地數(shù)據(jù)庫破解版(含iOS、Android),僅供學(xué)習(xí)研究 [附件下載]》(特別申明:微信的SQLite樣本庫僅供研究和學(xué)習(xí)之外,嚴禁用于商用業(yè)目的,所有權(quán)歸微信所有)。
附錄:更多微信、QQ的文章
[1] QQ、微信團隊原創(chuàng)技術(shù)文章:
《微信團隊分享:微信移動端的全文檢索多音字問題解決方案》
《騰訊技術(shù)分享:Android版手機QQ的緩存監(jiān)控與優(yōu)化實踐》
《微信團隊分享:iOS版微信的高性能通用key-value組件技術(shù)實踐》
《微信團隊分享:iOS版微信是如何防止特殊字符導(dǎo)致的炸群、APP崩潰的?》
《騰訊技術(shù)分享:Android手Q的線程死鎖監(jiān)控系統(tǒng)技術(shù)實踐》
《微信團隊原創(chuàng)分享:iOS版微信的內(nèi)存監(jiān)控系統(tǒng)技術(shù)實踐》
《讓互聯(lián)網(wǎng)更快:新一代QUIC協(xié)議在騰訊的技術(shù)實踐分享》
《iOS后臺喚醒實戰(zhàn):微信收款到賬語音提醒技術(shù)總結(jié)》
《騰訊技術(shù)分享:社交網(wǎng)絡(luò)圖片的帶寬壓縮技術(shù)演進之路》
《微信團隊分享:視頻圖像的超分辨率技術(shù)原理和應(yīng)用場景》
《微信團隊分享:微信每日億次實時音視頻聊天背后的技術(shù)解密》
《QQ音樂團隊分享:Android中的圖片壓縮技術(shù)詳解(上篇)》
《QQ音樂團隊分享:Android中的圖片壓縮技術(shù)詳解(下篇)》
《騰訊團隊分享:手機QQ中的人臉識別酷炫動畫效果實現(xiàn)詳解》
《騰訊團隊分享 :一次手Q聊天界面中圖片顯示bug的追蹤過程分享》
《微信團隊分享:微信Android版小視頻編碼填過的那些坑》
《微信手機端的本地數(shù)據(jù)全文檢索優(yōu)化之路》
《企業(yè)微信客戶端中組織架構(gòu)數(shù)據(jù)的同步更新方案優(yōu)化實戰(zhàn)》
《微信團隊披露:微信界面卡死超級bug“15。。。。”的來龍去脈》
《QQ 18年:解密8億月活的QQ后臺服務(wù)接口隔離技術(shù)》
《月活8.89億的超級IM微信是如何進行Android端兼容測試的》
《以手機QQ為例探討移動端IM中的“輕應(yīng)用”》
《一篇文章get微信開源移動端數(shù)據(jù)庫組件WCDB的一切!》
《微信客戶端團隊負責(zé)人技術(shù)訪談:如何著手客戶端性能監(jiān)控和優(yōu)化》
《微信后臺基于時間序的海量數(shù)據(jù)冷熱分級架構(gòu)設(shè)計實踐》
《微信團隊原創(chuàng)分享:Android版微信的臃腫之困與模塊化實踐之路》
《微信后臺團隊:微信后臺異步消息隊列的優(yōu)化升級實踐分享》
《微信團隊原創(chuàng)分享:微信客戶端SQLite數(shù)據(jù)庫損壞修復(fù)實踐》
《騰訊原創(chuàng)分享(一):如何大幅提升移動網(wǎng)絡(luò)下手機QQ的圖片傳輸速度和成功率》
《騰訊原創(chuàng)分享(二):如何大幅壓縮移動網(wǎng)絡(luò)下APP的流量消耗(下篇)》
《騰訊原創(chuàng)分享(二):如何大幅壓縮移動網(wǎng)絡(luò)下APP的流量消耗(上篇)》
《微信Mars:微信內(nèi)部正在使用的網(wǎng)絡(luò)層封裝庫,即將開源》
《如約而至:微信自用的移動端IM網(wǎng)絡(luò)層跨平臺組件庫Mars已正式開源》
《開源libco庫:單機千萬連接、支撐微信8億用戶的后臺框架基石 [源碼下載]》
《微信新一代通信安全解決方案:基于TLS1.3的MMTLS詳解》
《微信團隊原創(chuàng)分享:Android版微信后臺保活實戰(zhàn)分享(進程保活篇)》
《微信團隊原創(chuàng)分享:Android版微信后臺保活實戰(zhàn)分享(網(wǎng)絡(luò)保活篇)》
《Android版微信從300KB到30MB的技術(shù)演進(PPT講稿) [附件下載]》
《微信團隊原創(chuàng)分享:Android版微信從300KB到30MB的技術(shù)演進》
《微信技術(shù)總監(jiān)談架構(gòu):微信之道——大道至簡(演講全文)》
《微信技術(shù)總監(jiān)談架構(gòu):微信之道——大道至簡(PPT講稿) [附件下載]》
《如何解讀《微信技術(shù)總監(jiān)談架構(gòu):微信之道——大道至簡》》
《微信海量用戶背后的后臺系統(tǒng)存儲架構(gòu)(視頻+PPT) [附件下載]》
《微信異步化改造實踐:8億月活、單機千萬連接背后的后臺解決方案》
《微信朋友圈海量技術(shù)之道PPT [附件下載]》
《微信對網(wǎng)絡(luò)影響的技術(shù)試驗及分析(論文全文)》
《一份微信后臺技術(shù)架構(gòu)的總結(jié)性筆記》
《架構(gòu)之道:3個程序員成就微信朋友圈日均10億發(fā)布量[有視頻]》
《快速裂變:見證微信強大后臺架構(gòu)從0到1的演進歷程(一)》
《快速裂變:見證微信強大后臺架構(gòu)從0到1的演進歷程(二)》
《微信團隊原創(chuàng)分享:Android內(nèi)存泄漏監(jiān)控和優(yōu)化技巧總結(jié)》
《全面總結(jié)iOS版微信升級iOS9遇到的各種“坑”》
《微信團隊原創(chuàng)資源混淆工具:讓你的APK立減1M》
《微信團隊原創(chuàng)Android資源混淆工具:AndResGuard [有源碼]》
《Android版微信安裝包“減肥”實戰(zhàn)記錄》
《iOS版微信安裝包“減肥”實戰(zhàn)記錄》
《移動端IM實踐:iOS版微信界面卡頓監(jiān)測方案》
《微信“紅包照片”背后的技術(shù)難題》
《移動端IM實踐:iOS版微信小視頻功能技術(shù)方案實錄》
《移動端IM實踐:Android版微信如何大幅提升交互性能(一)》
《移動端IM實踐:Android版微信如何大幅提升交互性能(二)》
《移動端IM實踐:實現(xiàn)Android版微信的智能心跳機制》
《移動端IM實踐:WhatsApp、Line、微信的心跳策略分析》
《移動端IM實踐:谷歌消息推送服務(wù)(GCM)研究(來自微信)》
《移動端IM實踐:iOS版微信的多設(shè)備字體適配方案探討》
《信鴿團隊原創(chuàng):一起走過 iOS10 上消息推送(APNS)的坑》
《騰訊信鴿技術(shù)分享:百億級實時消息推送的實戰(zhàn)經(jīng)驗》
>> 更多同類文章 ……
[2] 有關(guān)QQ、微信的技術(shù)故事:
《技術(shù)往事:微信估值已超5千億,雷軍曾有機會收編張小龍及其Foxmail》
《QQ和微信兇猛成長的背后:騰訊網(wǎng)絡(luò)基礎(chǔ)架構(gòu)的這些年》
《閑話即時通訊:騰訊的成長史本質(zhì)就是一部QQ成長史》
《2017微信數(shù)據(jù)報告:日活躍用戶達9億、日發(fā)消息380億條》
《騰訊開發(fā)微信花了多少錢?技術(shù)難度真這么大?難在哪?》
《技術(shù)往事:創(chuàng)業(yè)初期的騰訊——16年前的冬天,誰動了馬化騰的代碼》
《技術(shù)往事:史上最全QQ圖標(biāo)變遷過程,追尋IM巨人的演進歷史》
《技術(shù)往事:“QQ群”和“微信紅包”是怎么來的?》
《開發(fā)往事:深度講述2010到2015,微信一路風(fēng)雨的背后》
《開發(fā)往事:微信千年不變的那張閃屏圖片的由來》
《開發(fā)往事:記錄微信3.0版背后的故事(距微信1.0發(fā)布9個月時)》
《一個微信實習(xí)生自述:我眼中的微信開發(fā)團隊》
《首次揭秘:QQ實時視頻聊天背后的神秘組織》
>> 更多同類文章 ……
(本文同步發(fā)布于:http://www.52im.net/thread-1545-1-1.html)