js實現(xiàn)敏感詞過濾算法及實現(xiàn)邏輯
最近弄了一個用戶發(fā)表評論的功能,用戶上傳了評論,再文章下可以看到自己的評論,但作為社會主義接班人,踐行社會主義核心價值觀,所以給評論敏感詞過濾的功能不可少,在網(wǎng)上找了資料,發(fā)現(xiàn)已經(jīng)有非常成熟的解決方案。 常用的方案用這么兩種
1.全文搜索,逐個匹配。這種聽起來就不夠高大上,在數(shù)據(jù)量大的情況下,會有效率問題,文末有比較
2.DFA算法-確定有限狀態(tài)自動機 附上百科鏈接確定有限狀態(tài)自動機
DFA算法介紹
DFA是一種計算模型,數(shù)據(jù)源是一個有限個集合,通過當(dāng)前狀態(tài)和事件來確定下一個狀態(tài),即 狀態(tài)+事件=下一狀態(tài),由此逐步構(gòu)建一個有向圖,其中的節(jié)點就是狀態(tài),所以在DFA算法中只有查找和判斷,沒有復(fù)雜的計算,從而提高算法效率
參考文章 Java實現(xiàn)敏感詞過濾
實現(xiàn)邏輯
構(gòu)造數(shù)據(jù)結(jié)構(gòu)
將敏感詞轉(zhuǎn)換成樹結(jié)構(gòu),舉例敏感詞有著這么幾個 ['日本鬼子','日本人','日本男人'] ,那么數(shù)據(jù)結(jié)構(gòu)如下(圖片引用參考文章)
每個文字是一個節(jié)點,連續(xù)的節(jié)點組成一個詞, 日本人 對應(yīng)的就是中間的那條鏈,我們可以使用對象或者map來構(gòu)建樹,這里的栗子采用 map 構(gòu)建節(jié)點,每個節(jié)點中有個狀態(tài)標(biāo)識,用來表示當(dāng)前節(jié)點是不是最后一個,每條鏈路必須要有個終點節(jié)點,先來看下構(gòu)建節(jié)點的流程圖
判斷邏輯
先從文本的第一個字開始檢查,比如 你我是日本鬼子 ,第一個字 你 ,在樹的第一層找不到這個節(jié)點,那么繼續(xù)找第二個字,到了 日 的時候,第一層節(jié)點找到了,那么接著下一層節(jié)點中查找 本 ,同時判斷這個節(jié)點是不是結(jié)尾節(jié)點,若是結(jié)尾節(jié)點,則匹配成功了,反之繼續(xù)匹配
代碼實現(xiàn)
####構(gòu)造數(shù)據(jù)結(jié)構(gòu)
/** * @description * 構(gòu)造敏感詞map * @private * @returns */ private makeSensitiveMap(sensitiveWordList) { // 構(gòu)造根節(jié)點 const result = new Map(); for (const word of sensitiveWordList) { let map = result; for (let i = 0; i < word.length; i++) { // 依次獲取字 const char = word.charAt(i); // 判斷是否存在 if (map.get(char)) { // 獲取下一層節(jié)點 map = map.get(char); } else { // 將當(dāng)前節(jié)點設(shè)置為非結(jié)尾節(jié)點 if (map.get('laster') === true) { map.set('laster', false); } const item = new Map(); // 新增節(jié)點默認(rèn)為結(jié)尾節(jié)點 item.set('laster', true); map.set(char, item); map = map.get(char); } } } return result; }
最終map結(jié)構(gòu)如下
查找敏感詞
/** * @description * 檢查敏感詞是否存在 * @private * @param {any} txt * @param {any} index * @returns */ private checkSensitiveWord(sensitiveMap, txt, index) { let currentMap = sensitiveMap; let flag = false; let wordNum = 0;//記錄過濾 let sensitiveWord = ''; //記錄過濾出來的敏感詞 for (let i = index; i < txt.length; i++) { const word = txt.charAt(i); currentMap = currentMap.get(word); if (currentMap) { wordNum++; sensitiveWord += word; if (currentMap.get('laster') === true) { // 表示已到詞的結(jié)尾 flag = true; break; } } else { break; } } // 兩字成詞 if (wordNum < 2) { flag = false; } return { flag, sensitiveWord }; } /** * @description * 判斷文本中是否存在敏感詞 * @param {any} txt * @returns */ public filterSensitiveWord(txt, sensitiveMap) { let matchResult = { flag: false, sensitiveWord: '' }; // 過濾掉除了中文、英文、數(shù)字之外的 const txtTrim = txt.replace(/[^\u4e00-\u9fa5\u0030-\u0039\u0061-\u007a\u0041-\u005a]+/g, ''); for (let i = 0; i < txtTrim.length; i++) { matchResult = checkSensitiveWord(sensitiveMap, txtTrim, i); if (matchResult.flag) { console.log(`sensitiveWord:${matchResult.sensitiveWord}`); break; } } return matchResult; }
效率
為了看出DFA的效率,我做了個簡單的小測試,測試的文本長度為5095個漢字,敏感詞詞庫中有2000個敏感詞,比較的算法分別為 DFA算法 和 String原生對象提供的 indexOf API做比較
// 簡單的字符串匹配-indexOf ensitiveWords.forEach((word) => { if (ss.indexOf(word) !== -1) { console.log(word) } })
分別將兩個算法執(zhí)行100次,得到如下結(jié)果
可直觀看出, DFA 的平均耗時是在1ms左右,最大為5ms; indexOf 方式的平均耗時在9ms左右,最大為14ms,所以DFA效率上還是非常明顯有優(yōu)勢的。
總結(jié)
以上所述是小編給大家介紹的js實現(xiàn)敏感詞過濾算法及實現(xiàn)邏輯,希望對大家有所幫助,如果大家有任何疑問請給我留言,小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持!
相關(guān)文章
Echarts實現(xiàn)暫無數(shù)據(jù)的三種方法
本文將介紹如何使用Echarts實現(xiàn)暫無數(shù)據(jù)的三種方法,詳細(xì)講解這三種方法的實現(xiàn)步驟和效果展示,幫助讀者更好地理解如何在Echarts中處理暫無數(shù)據(jù)的情況2023-08-08使用OpenLayers3 添加地圖鼠標(biāo)右鍵菜單
這篇文章主要介紹了使用OpenLayers3 添加地圖鼠標(biāo)右鍵菜單的相關(guān)資料,需要的朋友可以參考下2015-12-12在Webpack中用url-loader處理圖片和字體的問題
這篇文章主要介紹了在Webpack中用url-loader處理圖片和字體的問題及解決方法,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-04-04