elasticsearch[五]：深入探索ES搜索引擎的自動(dòng)補(bǔ)全與拼寫(xiě)糾錯(cuò)：如何實(shí)現(xiàn)高效智能的搜索體驗(yàn)
前一章講了搜索中的拼寫(xiě)糾錯(cuò)功能，里面一個(gè)很重要的概念就是萊文斯坦距離。這章會(huì)講解搜索中提升用戶體驗(yàn)的另一項(xiàng)功能 - [自動(dòng)補(bǔ)全]。本章直接介紹 ES 中的實(shí)現(xiàn)方式以及真正的搜索引擎對(duì)自動(dòng)補(bǔ)全功能的優(yōu)化。
![elasticsearch[五]：深入探索ES搜索引擎的自動(dòng)補(bǔ)全與拼寫(xiě)糾錯(cuò)：如何實(shí)現(xiàn)高效智能的搜索體驗(yàn),Elastic search,搜索引擎,elasticsearch,mybatis,自然語(yǔ)言處理,大數(shù)據(jù),ES,人工智能](https://imgs.yssmx.com/Uploads/2024/01/821021-1.png)
大家對(duì)上面的這個(gè)應(yīng)該都不陌生，搜索引擎會(huì)根據(jù)你輸入的關(guān)鍵字進(jìn)行一些提示，這樣用戶只需要輸入部分內(nèi)容就可以進(jìn)行選擇了。尤其在移動(dòng)端會(huì)比較方便。淘寶、京東的搜索也有類(lèi)似的功能，只不過(guò)行業(yè)不同，提示出來(lái)的內(nèi)容也不同罷了。
1、Lucene 中的搜索建議
1.1 使用步驟：
- 導(dǎo)入 lucene-suggest 組件
- 指定聯(lián)想數(shù)據(jù)來(lái)源，lucene suggest 提供了幾個(gè) InputIteratior 的默認(rèn)實(shí)現(xiàn)，也可以自定義實(shí)現(xiàn)
- BufferedInputIterator：對(duì)二進(jìn)制類(lèi)型的輸入進(jìn)行輪詢(xún)；
- DocumentInputIterator：從索引中被 store 的 field 中輪詢(xún)；
- FileIterator：從文件中每次讀出單行的數(shù)據(jù)輪詢(xún)，以 \ t 進(jìn)行間隔（且 \ t 的個(gè)數(shù)最多為 2 個(gè)）；
- HighFrequencyIterator：從索引中被 store 的 field 輪詢(xún)，忽略長(zhǎng)度小于設(shè)定值的文本；
- InputIteratorWrapper：遍歷 BytesRefIterator 并且返回的內(nèi)容不包含 payload 且 weight 均為 1；
- SortedInputIterator：二進(jìn)制類(lèi)型的輸入輪詢(xún)且按照指定的 comparator 算法進(jìn)行排序；
InputIteratior 中幾個(gè)方法的作用：
weight():此方法設(shè)置某個(gè)term的權(quán)重，設(shè)置的越高suggest的優(yōu)先級(jí)越高；
payload():每個(gè)suggestion對(duì)應(yīng)的元數(shù)據(jù)的二進(jìn)制表示，我們?cè)趥鬏攲?duì)象的時(shí)候需要轉(zhuǎn)換對(duì)象或?qū)ο蟮哪硞€(gè)屬性為BytesRef類(lèi)型，相應(yīng)的suggester調(diào)用lookup的時(shí)候會(huì)返回payloads信息；
hasPayload()：判斷iterator是否有payloads；
contexts():獲取某個(gè)term的contexts,用來(lái)過(guò)濾suggest的內(nèi)容，如果suggest的列表為空，返回null
hasContexts():獲取iterator是否有contexts;
- 建立 suggest 索引：suggester.build(new InputIteratorWrapper{});// 根據(jù) InputIterator 的具體實(shí)現(xiàn)決定數(shù)據(jù)源以及創(chuàng)建索引的規(guī)則
- 索引建立完畢即可在索引上進(jìn)行查詢(xún)，輸入模糊的字符，Lucene suggest 的內(nèi)部算法會(huì)根據(jù)索引的建立規(guī)則提出 suggest 查詢(xún)的內(nèi)容。suggester.lookup(name, contexts, 2, true, false);
1.2.Lucene suggest 核心實(shí)現(xiàn)一覽
Lucene 使用 AnalyzingInfixSuggester 類(lèi)中的 lookup 方法去聯(lián)想數(shù)據(jù)來(lái)源進(jìn)行查詢(xún)，其實(shí)就是一個(gè)普通的 search，所以我們的關(guān)鍵是要維護(hù)好這個(gè)聯(lián)想數(shù)據(jù)來(lái)源，各行各業(yè)都應(yīng)該有自己?jiǎn)为?dú)的語(yǔ)料庫(kù)。
2 Elastic Search 中的搜索優(yōu)化策略
應(yīng)該從這幾個(gè)方面入手：怎么優(yōu)化 Suggest 詞庫(kù)、提升 Suggest 詞準(zhǔn)確率、怎么提高響應(yīng)速度
2.1.Suggest 詞庫(kù)獲取
- 冷啟動(dòng)可以從內(nèi)容中提取熱詞數(shù)據(jù)來(lái)解決，或者人工設(shè)置
- 挖掘搜索日志：
- 挖掘近 1 個(gè)月搜索日志，按照每天獨(dú)立 IP 進(jìn)行統(tǒng)計(jì)頻次，即每個(gè) IP 用戶天搜索同一關(guān)鍵詞多次只記一次，用 IP 過(guò)濾也有其局限性，偽 IP，動(dòng)態(tài) IP，局域網(wǎng)共享同一公網(wǎng) IP，都會(huì)影響到基于 IP 來(lái)判斷用戶的準(zhǔn)確性，你也可以使用 sessionId 或者 userId 來(lái)判斷
- 統(tǒng)計(jì)后搜索詞頻次之后，抽取搜索頻次 > 100（自定閾值）的詞，同時(shí)對(duì)日志數(shù)據(jù)進(jìn)行清洗，過(guò)濾去除大于 10 個(gè)字（去除太長(zhǎng)的長(zhǎng)尾詞），單字和符號(hào)內(nèi)容
- 定時(shí)更新 suggest 詞庫(kù)中。
- 搜索日志里面包含大量 誤輸入詞：
- 需要在 suggest 詞庫(kù)里面去掉誤輸入詞，對(duì)于搜索頻次高的詞，可以挖掘其對(duì)應(yīng)的正確詞，通過(guò)同義詞進(jìn)行查詢(xún)改寫(xiě)。
- 誤輸入詞同義詞挖掘可以通過(guò)挖掘搜索 session 序列，使用 word2vec 訓(xùn)練來(lái)獲取誤輸入詞的同義詞，通過(guò)分詞器同義詞設(shè)置，對(duì)誤輸入詞進(jìn)行查詢(xún)改寫(xiě)。
2.2. 提升 Suggest 詞準(zhǔn)確率
- 使用 fuzzy 模糊查詢(xún)：基于編輯距離算法來(lái)匹配文檔。編輯距離的計(jì)算基于我們提供的查詢(xún)?cè)~條和被搜索文檔。
- 排序：從搜索日志挖掘的 Suggest 詞，可以根據(jù)搜索詞的搜索頻次作為熱度來(lái)設(shè)置 weight，Suggest 會(huì)根據(jù) weight 來(lái)排序。
2.3. 提升響應(yīng)速度
當(dāng)使用 completion suggester 的時(shí)候， 不是用于完成 類(lèi)似于 " 關(guān)鍵詞 " 這樣的模糊匹配場(chǎng)景，而是用于完成關(guān)鍵詞前綴匹配的。 對(duì)于漢字的處理，無(wú)需使用 ik/ HanLP 一類(lèi)的分詞器，直接使用 keyword analyzer，配合去除一些不需要的 stop word 即可。
代碼參考：
LinkedHashSet<String> returnSet = new LinkedHashSet<>();
Client client = elasticsearchTemplate.getClient();
SuggestRequestBuilder suggestRequestBuilder = client.prepareSuggest(elasticsearchTemplate.getPersistentEntityFor(SuggestEntity.class).getIndexName());
//全拼前綴匹配
CompletionSuggestionBuilder fullPinyinSuggest = new CompletionSuggestionBuilder("full_pinyin_suggest")
.field("full_pinyin").text(input).size(10);
//漢字前綴匹配
CompletionSuggestionBuilder suggestText = new CompletionSuggestionBuilder("suggestText")
.field("suggestText").text(input).size(size);
//拼音搜字母前綴匹配
CompletionSuggestionBuilder prefixPinyinSuggest = new CompletionSuggestionBuilder("prefix_pinyin_text")
.field("prefix_pinyin").text(input).size(size);
suggestRequestBuilder = suggestRequestBuilder.addSuggestion(fullPinyinSuggest).addSuggestion(suggestText).addSuggestion(prefixPinyinSuggest);
SuggestResponse suggestResponse = suggestRequestBuilder.execute().actionGet();
Suggest.Suggestion prefixPinyinSuggestion = suggestResponse.getSuggest().getSuggestion("prefix_pinyin_text");
Suggest.Suggestion fullPinyinSuggestion = suggestResponse.getSuggest().getSuggestion("full_pinyin_suggest");
Suggest.Suggestion suggestTextsuggestion = suggestResponse.getSuggest().getSuggestion("suggestText");
List<Suggest.Suggestion.Entry> entries = suggestTextsuggestion.getEntries();
//漢字前綴匹配
for (Suggest.Suggestion.Entry entry : entries) {
List<Suggest.Suggestion.Entry.Option> options = entry.getOptions();
for (Suggest.Suggestion.Entry.Option option : options) {
returnSet.add(option.getText().toString());
}
}
//全拼suggest補(bǔ)充
if (returnSet.size() < 10) {
List<Suggest.Suggestion.Entry> fullPinyinEntries = fullPinyinSuggestion.getEntries();
for (Suggest.Suggestion.Entry entry : fullPinyinEntries) {
List<Suggest.Suggestion.Entry.Option> options = entry.getOptions();
for (Suggest.Suggestion.Entry.Option option : options) {
if (returnSet.size() < 10) {
returnSet.add(option.getText().toString());
}
}
}
}
//首字母拼音suggest補(bǔ)充
if (returnSet.size() == 0) {
List<Suggest.Suggestion.Entry> prefixPinyinEntries = prefixPinyinSuggestion.getEntries();
for (Suggest.Suggestion.Entry entry : prefixPinyinEntries) {
List<Suggest.Suggestion.Entry.Option> options = entry.getOptions();
for (Suggest.Suggestion.Entry.Option option : options) {
returnSet.add(option.getText().toString());
}
}
}
return new ArrayList<>(returnSet);
3.搜索引擎對(duì)搜索提示的優(yōu)化
搜索引擎的優(yōu)化，需要更智能，每個(gè)人輸入相同的關(guān)鍵字，提示出來(lái)的內(nèi)容可能是完全不相同的，這就是所謂的 “千人千面”。這就用到了數(shù)據(jù)分析的知識(shí)，可以根據(jù)用戶一段時(shí)間內(nèi)的搜索歷史，分析用戶的搜索習(xí)慣，結(jié)合語(yǔ)料庫(kù)實(shí)現(xiàn)對(duì)用戶的精準(zhǔn)提示。跟輸入法的提升功能類(lèi)似，會(huì)根據(jù)你過(guò)往的輸入文本進(jìn)行自動(dòng)提示。所以，你付出了隱私，得到的是更大的便捷。這也是沒(méi)有辦法的事情。
- 搜索提示的一點(diǎn)小總結(jié)（重點(diǎn)）
- 需要一個(gè)搜索詞庫(kù) / 語(yǔ)料庫(kù)，各行各業(yè)均應(yīng)該不同
- 對(duì)用戶輸入的關(guān)鍵字進(jìn)行分詞
- 根據(jù)分詞及其他搜索條件去語(yǔ)料庫(kù)中查詢(xún)?nèi)舾蓷l（百度是 10 條）記錄返回
- 為了提升準(zhǔn)確率，通常都是前綴搜索
- 會(huì)根據(jù)萊溫斯坦距離進(jìn)行拼寫(xiě)糾錯(cuò)
4.搜索引擎中的智能提示 API 調(diào)用
如你所見(jiàn)，各大搜索引擎都提供了智能提示的 API 供廣大用戶調(diào)用，如果你司沒(méi)有自研的能力，可以直接 js 中跨域調(diào)用，先把系統(tǒng)跑起來(lái)再說(shuō)，給大家提供主流搜索引擎的調(diào)用地址，包含電商的哦。
4.1. 搜索引擎 JSONP 調(diào)用接口
提示：URL 中的 #content# 為搜索的 關(guān)鍵字
谷歌（Google）
http://suggestqueries.google.com/complete/search?client=youtube&q=#content#&jsonp=window.google.ac.h
callback：window.google.ac.h
window.google.ac.h([“關(guān)鍵字”,[[“關(guān)鍵字”,0],[“關(guān)鍵字 歌詞”,0],[“關(guān)鍵字參數(shù)”,0],[“關(guān)鍵字 lyrics”,0],[“關(guān)鍵字過(guò)濾”,0],[“關(guān)鍵字排名”,0],[“關(guān)鍵字查詢(xún)”,0],[“關(guān)鍵字提取算法”,0],[“關(guān)鍵字規(guī)劃師可通過(guò)以下哪種方式幫助您制作新的搜索網(wǎng)絡(luò)廣告系列”,0],[“關(guān)鍵字優(yōu)化”,0]],{“k”:1,“q”:“uhaB8ZMjzJay-BACee_C0eVdUCA”}])
必應(yīng)（Bing）
http://api.bing.com/qsonhs.aspx?type=cb&q=#content#&cb=window.bing.sug
callback：window.bing.sug
if(typeof window.bing.sug == 'function') window.bing.sug({"AS":{"Query":"關(guān)鍵字","FullResults":0}} /* pageview_candidate */);
百度（Baidu）
http://suggestion.baidu.com/su?wd=#content#&cb=window.baidu.sug
callback：window.baidu.sug
window.baidu.sug({q:"關(guān)鍵字",p:false,s:["關(guān)鍵字搜索排名","關(guān)鍵字怎么優(yōu)化","關(guān)鍵字查詢(xún)工具","關(guān)鍵字推廣","關(guān)鍵詞優(yōu)化","關(guān)鍵詞排名","關(guān)鍵字 英文","關(guān)鍵詞挖掘","關(guān)鍵詞查詢(xún)","關(guān)鍵詞搜索"]});
好搜（So）
https://sug.so.#/suggest?encodein=utf-8&encodeout=utf-8&format=json&word=#content#&callback=window.so.sug
**callback：**window.so.sug
window.so.sug({"query":"關(guān)鍵字","result":[{"word":"關(guān)鍵字查詢(xún)"},{"word":"關(guān)鍵字工具"},{"word":"關(guān)鍵字查詢(xún)工具"},{"word":"關(guān)鍵字挖掘"},{"word":"關(guān)鍵字搜索"},{"word":"關(guān)鍵字英文"},{"word":"關(guān)鍵字是什么"},{"word":"關(guān)鍵字廣告"},{"word":"關(guān)鍵字分析"},{"word":"關(guān)鍵字規(guī)劃師"}],"version":"b","rec":""});
搜狗（Sogou）
https://www.sogou.com/suggnew/ajajjson?type=web&key=#content#
**callback：**window.sogou.sug
window.sogou.sug(["關(guān)鍵字",["關(guān)鍵字查詢(xún)","關(guān)鍵字搜索","關(guān)鍵字優(yōu)化","關(guān)鍵字規(guī)劃師","關(guān)鍵字查詢(xún)lol","關(guān)鍵字是什么意思","關(guān)鍵字搜索工具","關(guān)鍵字廣告圖片","關(guān)鍵字排名查詢(xún)","關(guān)鍵字生成器"],["0;0;0;0","1;0;0;0","2;0;0;0","3;0;0;0","4;0;0;0","5;0;0;0","6;0;0;0","7;0;0;0","8;0;0;0","9;0;0;0"],["","","","","","","","","",""],["0"],"","suglabId_1"],-1);
淘寶（Taobao）
https://suggest.taobao.com/sug?code=utf-8&q=#content#&callback=window.taobao.sug
**callback：**window.taobao.sug
window.taobao.sug({"result":[["關(guān)鍵字推廣","204"],["關(guān)鍵字seo","198"],["關(guān)鍵字 網(wǎng)站","182"],["關(guān)鍵字搜索","119"],["關(guān)鍵字軟件","44"],["關(guān)鍵字首頁(yè)","50"],["關(guān)鍵字收錄","35"],["關(guān)鍵字采集","16"],["關(guān)鍵字采集器","10"],["網(wǎng)站關(guān)鍵字","180"]]})
搜索建議使用方式
以百度為例，API 返回的是 JSONP 數(shù)據(jù)，JSONP 是跨域訪問(wèn)的一種方式。由于服務(wù)器返回的 JavaScript 代碼可以直接引用，通過(guò)回調(diào)函數(shù)的方式就可以間接的獲取服務(wù)器的數(shù)據(jù)。
下面是一個(gè)回調(diào)搜索建議的例子，window.baidu.sug 返回的是一個(gè) json 對(duì)象：
<script type="text/javascript">
window.onload = function() {
//組裝查詢(xún)地址
var sugurl = "http://suggestion.baidu.com/su?wd=#content#&cb=window.baidu.sug";
var content = "關(guān)鍵字";
sugurl = sugurl.replace("#content#", content);
//定義回調(diào)函數(shù)
window.baidu = {
sug: function(json) {
console.log(json)
}
}
//動(dòng)態(tài)添加JS腳本
var script = document.createElement("script");
script.src = sugurl;
document.getElementsByTagName("head")[0].appendChild(script);
}
</script>
控制臺(tái)打印的結(jié)果：如果要將結(jié)果保存在一個(gè)字符串?dāng)?shù)組中，只需要 var arr = json.s 即可。
5.拼寫(xiě)糾錯(cuò)功能的實(shí)現(xiàn)
在使用搜索引擎時(shí)，當(dāng)我們輸入錯(cuò)誤的關(guān)鍵詞時(shí)，當(dāng)然這里的錯(cuò)誤是拼寫(xiě)錯(cuò)誤，搜索引擎的下拉框中仍會(huì)顯示以正確關(guān)鍵詞為前前輟的提示，當(dāng)你直接回車(chē)搜索錯(cuò)誤的關(guān)鍵詞時(shí)，搜索引擎的結(jié)果中仍包括正確關(guān)鍵詞的結(jié)果。你有沒(méi)有想過(guò)它是如何實(shí)現(xiàn)的呢?
![elasticsearch[五]：深入探索ES搜索引擎的自動(dòng)補(bǔ)全與拼寫(xiě)糾錯(cuò)：如何實(shí)現(xiàn)高效智能的搜索體驗(yàn),Elastic search,搜索引擎,elasticsearch,mybatis,自然語(yǔ)言處理,大數(shù)據(jù),ES,人工智能](https://imgs.yssmx.com/Uploads/2024/01/821021-2.png)
這個(gè)的實(shí)現(xiàn)可以有多種方案，常見(jiàn)的方法就是我們前面學(xué)習(xí)過(guò)的最長(zhǎng)公共子序列和今天要講的萊文斯坦距離方式。
最長(zhǎng)公共子序列可以查看我前面的博文程序員的算法課（6）- 最長(zhǎng)公共子序列（LCS）。
這兩種方案都需要跟正確的詞典進(jìn)行對(duì)照，**計(jì)算編輯距離或者最長(zhǎng)公共子序列，將編輯距離最小或子序列最長(zhǎng)的單詞，作為糾正之后的單詞，**返回給用戶。
- 萊文斯坦距離
萊文斯坦距離，又稱(chēng) Levenshtein 距離，是[編輯距離]的一種。指兩個(gè)[字串]之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。允許的編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)[字符]，刪除一個(gè)字符。
如單詞 three，我不小心手誤打成了 ethre，可以看到 ethre 只需要把首字母 e 移動(dòng)到末尾即可變成正確的單詞 three。此時(shí) ethre 相對(duì)于 three 的編輯距離就是 1。
萊文斯坦距離允許增加、刪除、替換字符這三個(gè)編輯操作，最長(zhǎng)公共子串長(zhǎng)度只允許增加、刪除字符這兩個(gè)編輯操作。
萊文斯坦距離和最長(zhǎng)公共子串長(zhǎng)度，從兩個(gè)截然相反的角度，分析字符串的相似程度。萊文斯坦距離的大小，表示兩個(gè)字符串差異的大小；而最長(zhǎng)公共子串的大小，表示兩個(gè)字符串相似程度的大小。
5.1.Lucene 中通過(guò) Suggest 模塊下的 SpellChecker 功能來(lái)實(shí)現(xiàn)拼寫(xiě)糾錯(cuò)。
源碼中，定義了兩個(gè) public 的靜態(tài)成員變量， DEFAULT_ACCURACY 表示默認(rèn)的最小分?jǐn)?shù)，SpellCheck 會(huì)對(duì)字典里的每個(gè)詞與用戶輸入的搜索關(guān)鍵字進(jìn)行一個(gè)相似度打分，默認(rèn)該值是 0.5，相似度分值范圍是 0 到 1 之間，數(shù)字越大表示越相似，小于 0.5 會(huì)認(rèn)為不是同一個(gè)結(jié)果。F_WORD 是對(duì)于字典文件里每一行創(chuàng)建索引時(shí)使用的默認(rèn)域名稱(chēng)，默認(rèn)值為：word。
幾個(gè)重要的 API：
-
**[getAccuracy](http://www.tuicool.com/admin/blogs/)：**accuracy 是精確度的意思，這里表示最小評(píng)分，評(píng)分越大表示與用戶輸入的關(guān)鍵字越相似 - suggestSimilar：這個(gè)方法就是用來(lái)決定哪些 word 會(huì)被判定為比較相似的然后以數(shù)組的形式返回，這是 SpellChecker 的核心；
- setComparator：設(shè)置比較器，既然涉及到相似度問(wèn)題，那肯定有相似度大小問(wèn)題，有大小必然存在比較，有比較必然需要比較器，通過(guò)比較器決定返回的建議詞的順序，因?yàn)橐话阈枰炎钕嚓P(guān)的顯示在最前面，然后依次排序顯示；
- setSpellIndex：設(shè)置拼寫(xiě)檢查索引目錄的
- setStringDistance：設(shè)置編輯距離
看到了 setStringDistance 這個(gè)方法，想都不用想，Lucene 肯定也是使用編輯距離的方式進(jìn)行匹配的。
源碼中還有兩個(gè)私有屬性，分別代表前綴和后綴的權(quán)重，前綴要比后綴大。
private float bStart = 2.0f;
private float bEnd = 1.0f;
幾個(gè)重要的方法：
- formGrams：對(duì)輸入的字符串按指定長(zhǎng)度分割，返回分割后的數(shù)組。
- indexDictionary：將字典文件里的詞進(jìn)行 ngram 操作后得到多個(gè)詞然后分別寫(xiě)入索引。
- suggestSimilar：用來(lái)計(jì)算最后返回的建議詞。有三種建議模式：
- SUGGEST_WHEN_NOT_IN_INDEX：意思就是只有當(dāng)用戶提供的搜索關(guān)鍵字在索引 Term 中不存在我才提供建議，否則我會(huì)認(rèn)為用戶輸入的搜索關(guān)鍵字是正確的不需要提供建議。
- SUGGEST_MORE_POPULAR：表示只返回頻率較高的詞組，用戶輸入的搜索關(guān)鍵字首先需要經(jīng)過(guò) ngram 分割，創(chuàng)建索引的時(shí)候也需要進(jìn)行分詞，如果用戶輸入的詞分割后得到的 word 在索引中出現(xiàn)的頻率比索引中實(shí)際存在的 Term 還要高，那說(shuō)明不需要進(jìn)行拼寫(xiě)建議了。
- SUGGEST_ALWAYS：永遠(yuǎn)進(jìn)行建議，只是返回的建議結(jié)果受 numSug 數(shù)量限制即最多返回幾條拼寫(xiě)建議。
最終返回用戶輸入關(guān)鍵字和索引中當(dāng)前 Term 的相似度，這個(gè)取決于你 Distance 實(shí)現(xiàn)，默認(rèn)實(shí)現(xiàn)是 LevenshteinDistance
（萊文斯坦距離）即計(jì)算編輯距離。采用三個(gè)一維數(shù)組代替了一個(gè)二維數(shù)組，一個(gè)數(shù)組為上一輪計(jì)算的值，一個(gè)數(shù)組保存本輪計(jì)算的值，最后一個(gè)數(shù)組用于交換兩個(gè)數(shù)組的值。核心源碼如下：
package org.apache.lucene.search.spell;
public class LevenshteinDistance implements StringDistance {
@Override
public float getDistance (String target, String other) {
char[] sa;
int n;
int p[]; //上一行計(jì)算的值
int d[]; //當(dāng)前行計(jì)算的值
int _d[]; //用于交換p和d
sa = target.toCharArray();
n = sa.length;
p = new int[n+1];
d = new int[n+1];
final int m = other.length();
if (n == 0 || m == 0) {
if (n == m) {
return 1;
}
else {
return 0;
}
}
int i; // target的索引
int j; // other的索引
char t_j; //other的第j個(gè)字符
int cost;
//初始化，將空字符串轉(zhuǎn)換為長(zhǎng)度為i的target字符串的操作次數(shù)
for (i = 0; i<=n; i++) {
p[i] = i;
}
for (j = 1; j<=m; j++) {
t_j = other.charAt(j-1);
//左方的初始值為將長(zhǎng)度為j的other字符串轉(zhuǎn)換為空字符串的操作次數(shù)
d[0] = j;
//計(jì)算將長(zhǎng)度為i的target字符串轉(zhuǎn)換為長(zhǎng)度為j的other字符串的操作次數(shù)
for (i=1; i<=n; i++) {
cost = sa[i-1]==t_j ? 0 : 1;
//d[i-1]左方、p[i]上方、p[i-1]左上
d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost);
}
//交換p和d，用于下一輪計(jì)算
_d = p;
p = d;
d = _d;
}
//計(jì)算相似度，p中最后一個(gè)元素為L(zhǎng)evensteinDistance
return 1.0f - ((float) p[n] / Math.max(other.length(), sa.length));
}
}
Lucene 還內(nèi)置了另外幾種相似度實(shí)現(xiàn)，都是基于距離計(jì)算的：JaroWinklerDistance、LuceneLevenshteinDistance 和 NGramDistance。
源碼中還有大量同步鎖的使用，跟本次內(nèi)容關(guān)系不大，暫時(shí)先不考慮。
5.2.solr 有 SpellCheckComponent 拼寫(xiě)糾錯(cuò)功能，此外還有依靠文件來(lái)糾錯(cuò)和主索引糾錯(cuò)的方式。
solr 的糾錯(cuò)依賴(lài)于 lucene，主要通過(guò)插件的方式進(jìn)行使用。solr 通過(guò)配置文件的方式指定糾錯(cuò)的規(guī)則，里面一個(gè)非常重要的屬性：
accuracy，這個(gè)值每下降 0.1 就可以糾錯(cuò)一個(gè)字母, 下降 0.2 可以糾錯(cuò)一個(gè)漢字，例如：將其調(diào)整到 0.8 時(shí)可以搜索到數(shù)據(jù)但是僅僅只能出錯(cuò)一個(gè)漢字或者兩個(gè)字母。
5.3.es 糾錯(cuò)
官方公式：https://www.elastic.co/guide/en/elasticsearch/reference/current/search-suggesters-phrase.html
es 中使用 phrase Suggester 來(lái)進(jìn)行拼寫(xiě)糾錯(cuò)。phrase suggester 在 term suggester 之上添加了額外的邏輯以選擇整體更正的 phrase，而不是基于單個(gè)分詞加權(quán)的 ngram 語(yǔ)言模型。在實(shí)際中 phrase suggester 能夠根據(jù)單詞的詞頻等信息作出更好的選擇。
ES 中常用的 4 種 Suggester 類(lèi)型：Term、Phrase、Completion、Context。
- Term suggester 正如其名，只基于 analyze 過(guò)的單個(gè) term 去提供建議，并不會(huì)考慮多個(gè) term 之間的關(guān)系。API 調(diào)用方只需為每個(gè) token 挑選 options 里的詞，組合在一起返回給用戶前端即可。 那么有無(wú)更直接辦法，API 直接給出和用戶輸入文本相似的內(nèi)容？ 答案是有，這就要求助 Phrase Suggester 了。
- Phrase suggester 在 Term suggester 的基礎(chǔ)上，會(huì)考量多個(gè) term 之間的關(guān)系，比如是否同時(shí)出現(xiàn)在索引的原文里，相鄰程度，以及詞頻等等。
- Completion Suggester，它主要針對(duì)的應(yīng)用場(chǎng)景就是 “Auto Completion”。 此場(chǎng)景下用戶每輸入一個(gè)字符的時(shí)候，就需要即時(shí)發(fā)送一次查詢(xún)請(qǐng)求到后端查找匹配項(xiàng)，在用戶輸入速度較高的情況下對(duì)后端響應(yīng)速度要求比較苛刻。因此實(shí)現(xiàn)上它和前面兩個(gè) Suggester 采用了不同的數(shù)據(jù)結(jié)構(gòu)，索引并非通過(guò)倒排來(lái)完成，而是將 analyze 過(guò)的數(shù)據(jù)編碼成 FST 和索引一起存放。對(duì)于一個(gè) open 狀態(tài)的索引，F(xiàn)ST 會(huì)被 ES 整個(gè)裝載到內(nèi)存里的，進(jìn)行前綴查找速度極快。但是 FST 只能用于前綴查找，這也是 Completion Suggester 的局限所在。
- Context Suggester，會(huì)根據(jù)上下文進(jìn)行補(bǔ)全，這種方式補(bǔ)全效果較好，但性能較差，用的人不多。這也是 es 中拼寫(xiě)糾錯(cuò)的高級(jí)用法。
小結(jié)搜索引擎中對(duì)拼寫(xiě)糾錯(cuò)的算法猜想
Google 搜索框的補(bǔ)全 / 糾錯(cuò)功能，如果用 ES 怎么實(shí)現(xiàn)呢？我能想到的一個(gè)的實(shí)現(xiàn)方式:
- 在用戶剛開(kāi)始輸入的過(guò)程中，使用 Completion Suggester 進(jìn)行關(guān)鍵詞前綴匹配，剛開(kāi)始匹配項(xiàng)會(huì)比較多，隨著用戶輸入字符增多，匹配項(xiàng)越來(lái)越少。如果用戶輸入比較精準(zhǔn)，可能 Completion Suggester 的結(jié)果已經(jīng)夠好，用戶已經(jīng)可以看到理想的備選項(xiàng)了。
- 如果 Completion Suggester 已經(jīng)到了零匹配，那么可以猜測(cè)是否用戶有輸入錯(cuò)誤，這時(shí)候可以嘗試一下 Phrase Suggester。
- 如果 Phrase Suggester 沒(méi)有找到任何 option，開(kāi)始嘗試 term Suggester。
精準(zhǔn)程度上 (Precision) 看： Completion > Phrase > term， 而召回率上 (Recall) 則反之。從性能上看，Completion Suggester 是最快的，如果能滿足業(yè)務(wù)需求，只用 Completion Suggester 做前綴匹配是最理想的。 Phrase 和 Term 由于是做倒排索引的搜索，相比較而言性能應(yīng)該要低不少，應(yīng)盡量控制 suggester 用到的索引的數(shù)據(jù)量，最理想的狀況是經(jīng)過(guò)一定時(shí)間預(yù)熱后，索引可以全量 map 到內(nèi)存。
真正的搜索引擎的拼寫(xiě)糾錯(cuò)優(yōu)化，肯定不止我講的這么簡(jiǎn)單，但是萬(wàn)變不離其宗。掌握了核心原理，就是掌握了解決問(wèn)題的方法，剩下就靠你自己的靈活運(yùn)用和實(shí)戰(zhàn)操練了。
參考文章
- https://baike.baidu.com/item/%E8%8E%B1%E6%96%87%E6%96%AF%E5%9D%A6%E8%B7%9D%E7%A6%BB/14448097?fr=aladdin
- https://www.jianshu.com/p/f2cacf1d5d1b
- http://www.chepoo.com/spelling-correction-function-realization.html
- https://blog.csdn.net/qq_25800311/article/details/90665244
- https://blog.csdn.net/yzl_8877/article/details/53375132
- https://blog.csdn.net/sqh201030412/article/details/51038870
- https://blog.csdn.net/github_26672553/article/details/72639396
- https://elasticsearch.cn/article/142
參考文章
- https://www.cnblogs.com/woider/p/5805248.html
- https://blog.csdn.net/m0_37556444/article/details/82734959
- https://www.jianshu.com/p/69d56f9c0576
https://blog.csdn.net/m0_37609579/article/details/101001985文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-821021.html
https://blog.csdn.net/m0_37609579/article/details/101039881?utm_medium=distribute.pc_relevant.none-task-blog-2defaultbaidujs_baidulandingword~default-1-101039881-blog-130149985.235v40pc_relevant_anti_vip&spm=1001.2101.3001.4242.2&utm_relevant_index=4文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-821021.html
到了這里，關(guān)于elasticsearch[五]：深入探索ES搜索引擎的自動(dòng)補(bǔ)全與拼寫(xiě)糾錯(cuò)：如何實(shí)現(xiàn)高效智能的搜索體驗(yàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
