問(wèn)題背景搜索關(guān)鍵字智能提示是一個(gè)搜索應(yīng)用的標(biāo)配，主要作用是避免用戶輸入錯(cuò)誤的搜索詞，并將用戶引導(dǎo)到相應(yīng)的關(guān)鍵詞上，以提升用戶搜索體驗(yàn)。美團(tuán)CRM系統(tǒng)中存在數(shù)以百萬(wàn)計(jì)的商家，為了讓用戶快速查找到目標(biāo)商家

問(wèn)題背景搜索關(guān)鍵字智能提示是一個(gè)搜索應(yīng)用的標(biāo)配，主要作用是避免用戶輸入錯(cuò)誤的搜索詞，并將用戶引導(dǎo)到相應(yīng)的關(guān)鍵詞上，以提升用戶搜索體驗(yàn)。

美團(tuán)CRM系統(tǒng)中存在數(shù)以百萬(wàn)計(jì)的商家，為了讓用戶快速查找到目標(biāo)商家，我們基于solrcloud實(shí)現(xiàn)了商家搜索模塊。用戶在查找商家時(shí)主要輸入商戶名、商戶地址進(jìn)行搜索，為了提升用戶的搜索體驗(yàn)和輸入效率，本文實(shí)現(xiàn)了一種基于solr前綴匹配查詢關(guān)鍵字智能提示(Suggestion)實(shí)現(xiàn)。

需求分析1.支持前綴匹配原則在搜索框中輸入海底”，搜索框下面會(huì)以海底為前綴，展示海底撈”、海底撈火鍋”、海底世界”等等搜索詞；輸入萬(wàn)達(dá)”，會(huì)提示萬(wàn)達(dá)影城”、萬(wàn)達(dá)廣場(chǎng)”、萬(wàn)達(dá)百貨”等搜索詞。2.同時(shí)支持漢字、拼音輸入由于中文的特點(diǎn)，如果搜索自動(dòng)提示可以支持拼音的話會(huì)給用戶帶來(lái)更大的方便，免得切換輸入法。比如，輸入haidi”提示的關(guān)鍵字和輸入海底”提示的一樣，輸入wanda”與輸入萬(wàn)達(dá)”提示的關(guān)鍵字一樣。3.支持多音字輸入提示比如輸入chongqing”或者zhongqing”都能提示出重慶火鍋”、重慶烤魚”、重慶小天鵝”。4.支持拼音縮寫輸入對(duì)于較長(zhǎng)關(guān)鍵字，為了提高輸入效率，有必要提供拼音縮寫輸入。比如輸入hd”應(yīng)該能提示出haidi”相似的關(guān)鍵字，輸入wd”也一樣能提示出萬(wàn)達(dá)”關(guān)鍵字?；谟脩舻臍v史搜索行為，按照關(guān)鍵字熱度進(jìn)行排序?yàn)榱颂峁﹕uggest關(guān)鍵字的準(zhǔn)確度，最終查詢結(jié)果，根據(jù)用戶查詢關(guān)鍵字的頻率進(jìn)行排序，如輸入[重慶,chongqing,cq,zhongqing,zq] —> [重慶火鍋”(f1),重慶烤魚”(f2),重慶小天鵝”(f3)，…]，查詢頻率f1 > f2 > f3。

解決方案1.關(guān)鍵字收集當(dāng)用戶輸入一個(gè)前綴時(shí)，碰到提示的候選詞很多的時(shí)候，如何取舍，哪些展示在前面，哪些展示在后面？這就是一個(gè)搜索熱度的問(wèn)題。用戶在使用搜索引擎查找商家時(shí)，會(huì)輸入大量的關(guān)鍵字，每一次輸入就是對(duì)關(guān)鍵字的一次投票，那么關(guān)鍵字被輸入的次數(shù)越多，它對(duì)應(yīng)的查詢就比較熱門，所以需要把查詢的關(guān)鍵字記錄下來(lái)，并且統(tǒng)計(jì)出每個(gè)關(guān)鍵字的頻率，方便提示結(jié)果按照頻率排序。搜索引擎會(huì)通過(guò)日志文件把用戶每次檢索使用的所有檢索串都記錄下來(lái)，每個(gè)查詢串的長(zhǎng)度為1-255字節(jié)。2.漢字轉(zhuǎn)拼音用戶輸入的關(guān)鍵字可能是漢字、數(shù)字，英文，拼音，特殊字符等等，由于需要實(shí)現(xiàn)拼音提示，我們需要把漢字轉(zhuǎn)換成拼音，java中考慮使用pinyin4j組件實(shí)現(xiàn)轉(zhuǎn)換。3.拼音縮寫提取考慮到需要支持拼音縮寫，漢字轉(zhuǎn)換拼音的過(guò)程中，順便提取出拼音縮寫，如chongqing”,"zhongqing"--->"cq",”zq”。4.多音字全排列要支持多音字提示，對(duì)查詢串轉(zhuǎn)換成拼音后，需要實(shí)現(xiàn)一個(gè)全排列組合，字符串多音字全排列算法如下：

Java Code復(fù)制內(nèi)容到剪貼板 publicstaticListgetPermutationSentence(List>termArrays,intstart){ if(CollectionUtils.isEmpty(termArrays)) returnCollections.emptyList(); intsize=termArrays.size(); if(start<0||start>=size){ returnCollections.emptyList(); } if(start==size-1){ returntermArrays.get(start); } List<String>strings=termArrays.get(start); List<String>permutationSentences=getPermutationSentence(termArrays,start+1); if(CollectionUtils.isEmpty(strings)){ returnpermutationSentences; } if(CollectionUtils.isEmpty(permutationSentences)){ returnstrings; } List<String>result=newArrayList<String>(); for(Stringpre:strings){ for(Stringsuffix:permutationSentences){ result.add(pre+suffix); } } returnresult; }

索引與前綴查詢方案一 Trie樹 + TopK算法Trie樹即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希表高。Trie是一顆存儲(chǔ)多個(gè)字符串的樹。相鄰節(jié)點(diǎn)間的邊代表一個(gè)字符，這樣樹的每條分支代表一則子串，而樹的葉節(jié)點(diǎn)則代表完整的字符串。和普通樹不同的地方是，相同的字符串前綴共享同一條分支。例如，給出一組單詞inn, int, at, age, adv, ant, 我們可以得到下面的Trie：

從上圖可知，當(dāng)用戶輸入前綴i的時(shí)候，搜索框可能會(huì)展示以i為前綴的in”，inn”，”int"等關(guān)鍵詞，再當(dāng)用戶輸入前綴a的時(shí)候，搜索框里面可能會(huì)提示以a為前綴的ate”等關(guān)鍵詞。如此，實(shí)現(xiàn)搜索引擎智能提示suggestion的第一個(gè)步驟便清晰了，即用trie樹存儲(chǔ)大量字符串，當(dāng)前綴固定時(shí)，存儲(chǔ)相對(duì)來(lái)說(shuō)比較熱的后綴。

TopK算法用于解決統(tǒng)計(jì)熱詞的問(wèn)題。解決TopK問(wèn)題主要有兩種策略：hashMap統(tǒng)計(jì)+排序、堆排序hashmap統(tǒng)計(jì): 先對(duì)這批海量數(shù)據(jù)預(yù)處理。具體方法是：維護(hù)一個(gè)Key為Query字串，Value為該Query出現(xiàn)次數(shù)的HashTable，即hash_map(Query，Value)，每次讀取一個(gè)Query，如果該字串不在Table中，那么加入該字串，并且將Value值設(shè)為1；如果該字串在Table中，那么將該字串的計(jì)數(shù)加一即可，最終在O(N)的時(shí)間復(fù)雜度內(nèi)用Hash表完成了統(tǒng)計(jì)。堆排序：借助堆這個(gè)數(shù)據(jù)結(jié)構(gòu)，找出Top K，時(shí)間復(fù)雜度為N‘logK。即借助堆結(jié)構(gòu)，我們可以在log量級(jí)的時(shí)間內(nèi)查找和調(diào)整/移動(dòng)。因此，維護(hù)一個(gè)K(該題目中是10)大小的小根堆，然后遍歷300萬(wàn)的Query，分別和根元素進(jìn)行對(duì)比。所以，我們最終的時(shí)間復(fù)雜度是：O（N） + N' * O（logK），（N為1000萬(wàn)，N’為300萬(wàn)）。

該方案存在的問(wèn)題是：

建索引和查詢的時(shí)候都要把漢字轉(zhuǎn)換成拼音，查詢完成后還得把拼音轉(zhuǎn)換成漢字顯示，且需要考慮數(shù)字和特殊字符。需要維護(hù)拼音、縮寫兩棵Trie樹。

方案二 Solr自帶Suggest智能提示Solr作為一個(gè)應(yīng)用廣泛的搜索引擎系統(tǒng)，它內(nèi)置了智能提示功能，叫做Suggest模塊。該模塊可選擇基于提示詞文本做智能提示，還支持通過(guò)針對(duì)索引的某個(gè)字段建立索引詞庫(kù)做智能提示。 (詳見(jiàn)solr的wiki頁(yè)面http://wiki.apache.org/solr/Suggester)

該方案存在的問(wèn)題是：

返回的結(jié)果是基于索引中字段的詞頻進(jìn)行排序，不是用戶搜索關(guān)鍵字的頻率，因此不能將一些熱門關(guān)鍵字排在前面。拼音提示，多音字，縮寫還是要另外加索引字段。

方案三 Solrcloud建立單獨(dú)的collection,利用solr前綴查詢實(shí)現(xiàn)如前所述，以上兩個(gè)方案在實(shí)施起來(lái)都存在一些問(wèn)題，Trie樹+TopK算法，在處理漢字suggest時(shí)不是很優(yōu)雅，且需要維護(hù)兩棵Trie樹，實(shí)施起來(lái)比較復(fù)雜；Solr自帶的suggest智能提示組件存在問(wèn)題是使用freq排序算法，返回的結(jié)果完全基于索引中字符的出現(xiàn)次數(shù)，沒(méi)有兼顧用戶搜索詞語(yǔ)的頻率，因此無(wú)法將一些熱門詞排在更靠前的位置。于是，我們繼續(xù)尋找一種解決這個(gè)問(wèn)題更加優(yōu)雅的方案。

至此，我們考慮專門為關(guān)鍵字建立一個(gè)索引collection，利用solr前綴查詢實(shí)現(xiàn)。solr中的copyField能很好解決我們同時(shí)索引多個(gè)字段(漢字、pinyin, abbre)的需求，且field的multiValued屬性設(shè)置為true時(shí)能解決同一個(gè)關(guān)鍵字的多音字組合問(wèn)題。配置如下：

schema.xml:

XML/HTML Code復(fù)制內(nèi)容到剪貼板 <fieldname="kw"type="string"indexed="true"stored="true"/> <fieldname="pinyin"type="string"indexed="true"stored="false"multiValued="true"/> <fieldname="abbre"type="string"indexed="true"stored="false"multiValued="true"/> <fieldname="kwfreq"type="int"indexed="true"stored="true"/> <fieldname="_version_"type="long"indexed="true"stored="true"/> <fieldname="suggest"type="suggest_text"indexed="true"stored="false"multiValued="true"/>

------------------multiValued表示字段是多值的-------------------------------------

XML/HTML Code復(fù)制內(nèi)容到剪貼板 <uniqueKey>kw</uniqueKey> <defaultSearchField>suggest</defaultSearchField>

說(shuō)明：kw為原始關(guān)鍵字pinyin和abbre的multiValued=true,在使用solrj建此索引時(shí)，定義成集合類型即可：如關(guān)鍵字重慶”的pinyin字段為{chongqing,zhongqing}, abbre字段為{cq, zq}kwfreq為用戶搜索關(guān)鍵的頻率，用于查詢的時(shí)候排序

-------------------------------------------------------

XML/HTML Code復(fù)制內(nèi)容到剪貼板 <copyFieldsource="kw"dest="suggest"/> <copyFieldsource="pinyin"dest="suggest"/> <copyFieldsource="abbre"dest="suggest"/>

------------------suggest_text----------------------------------

XML/HTML Code復(fù)制內(nèi)容到剪貼板 <fieldTypename="suggest_text"class="solr.TextField"positionIncrementGap="100"autoGeneratePhraseQueries="true"> <analyzertype="index"> <tokenizerclass="solr.KeywordTokenizerFactory"/> <filterclass="solr.SynonymFilterFactory" synonyms="synonyms.txt" ignoreCase="true" expand="true"/> <filterclass="solr.StopFilterFactory" ignoreCase="true" words="stopwords.txt" enablePositionIncrements="true"/> <filterclass="solr.LowerCaseFilterFactory"/> <filterclass="solr.KeywordMarkerFilterFactory"protected="protwords.txt"/> </analyzer> <analyzertype="query"> <tokenizerclass="solr.KeywordTokenizerFactory"/> <filterclass="solr.StopFilterFactory" ignoreCase="true" words="stopwords.txt" enablePositionIncrements="true"/> <filterclass="solr.LowerCaseFilterFactory"/> <filterclass="solr.KeywordMarkerFilterFactory"protected="protwords.txt"/> </analyzer> </fieldType>

KeywordTokenizerFactory：這個(gè)分詞器不進(jìn)行任何分詞！整個(gè)字符流變?yōu)閱蝹€(gè)詞元。String域類型也有類似的效果，但是它不能配置文本分析的其它處理組件，比如大小寫轉(zhuǎn)換。任何用于排序和大部分Faceting功能的索引域，這個(gè)索引域只有能一個(gè)原始域值中的一個(gè)詞元。

前綴查詢構(gòu)造:

Java Code復(fù)制內(nèi)容到剪貼板 privateSolrQuerygetSuggestQuery(Stringprefix,Integerlimit){ SolrQuerysolrQuery=newSolrQuery(); StringBuildersb=newStringBuilder(); sb.append(suggest:").append(prefix).append("*"); solrQuery.setQuery(sb.toString()); solrQuery.addField("kw"); solrQuery.addField("kwfreq"); solrQuery.addSort("kwfreq",SolrQuery.ORDER.desc); solrQuery.setStart(0); solrQuery.setRows(limit); returnsolrQuery; }

效果如下圖所示：