首页 > 代码库 > JavaScript 上万关键字瞬间匹配——借助Hash表快速匹配算法
JavaScript 上万关键字瞬间匹配——借助Hash表快速匹配算法
来源:
http://www.cnblogs.com/index-html/archive/2013/04/17/js_keyword_match.html
http://www.etherdream.com/funnyscript/Keyword/Keyword.html
适用于多关键字、大文本匹配,若关键字只有一个,则只是最朴素的字符串匹配(逐个匹配),没显示作用。
var treeSearch = { makeTree: function(strKeys) { "use strict"; var tblCur = {}, tblRoot, key, str_key, Length, j, i ; tblRoot = tblCur; for ( j = strKeys.length - 1; j >= 0; j -= 1) { str_key = strKeys[j]; Length = str_key.length; for ( i = 0; i < Length; i += 1) { key = str_key.charAt(i); if (tblCur.hasOwnProperty(key)) { //生成子节点 tblCur = tblCur[key]; } else { tblCur = tblCur[key] = {}; } } tblCur.end = true; //最后一个关键字没有分割符 tblCur = tblRoot; } return tblRoot; }, search: function(content, tblRoot) { "use strict"; var tblCur, p_star = 0, n = content.length, p_end, match, //是否找到匹配 match_key, match_str, arrMatch = [], //存储结果 arrLength = 0 //arrMatch的长度索引 ; while (p_star < n) { tblCur = tblRoot; //回溯至根部 p_end = p_star; match_str = ""; match = false; do { match_key = content.charAt(p_end); if (!(tblCur = tblCur[match_key])) { //本次匹配结束 p_star += 1; break; }else{ match_str += match_key; } p_end += 1; if (tblCur.end === true) //是否匹配到尾部 //找到匹配关键字 { match = true; } } while (true); if (match === true) { //最大匹配 arrMatch[arrLength] = { //增强可读性 key: match_str, begin: p_star - 1, end: p_end }; arrLength += 1; p_star = p_end; } } return arrMatch; }};
function test(strContent, strKeys) { var arrMatch, tblRoot = treeSearch.makeTree(strKeys), t = new Date(); arrMatch = treeSearch.search(strContent, tblRoot); console.log("time is: " + (new Date() - t) + "mm"); console.log(arrMatch);}var s = (function() { var Things = [‘ ‘, ‘\n‘, ‘A‘, ‘B‘, ‘C‘, ‘D‘, ‘E‘, ‘F‘, ‘G‘, ‘H‘, ‘I‘, ‘J‘, ‘K‘, ‘L‘, ‘M‘, ‘N‘, ‘O‘, ‘Q‘, ‘R‘, ‘S‘, ‘T‘, ‘U‘, ‘V‘, ‘W‘, ‘X‘, ‘Y‘, ‘Z‘, ‘a‘, ‘b‘, ‘c‘, ‘d‘, ‘e‘, ‘f‘, ‘g‘, ‘h‘, ‘i‘, ‘j‘, ‘k‘, ‘l‘, ‘m‘, ‘n‘, ‘o‘, ‘q‘, ‘r‘, ‘s‘, ‘t‘, ‘u‘, ‘v‘, ‘w‘, ‘x‘, ‘y‘, ‘z‘]; var s = ""; for (var i = 1000000; i >= 0; i--) { s += Things[parseInt(Math.random() * Things.length) % Things.length] }; return s;})()test(s, ["abc", "efge", "fun", "tree"]);
JavaScript 上万关键字瞬间匹配——借助Hash表快速匹配算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。