javascript實作多字元查詢之AC算法

首先簡要介紹一下AC自動機：Aho-Corasick automation，該算法在1975年産生于貝爾實驗室，是著名的多模比對算法之一。一個常見的例子就是給出n個單詞，再給出一段包含m個字元的文章，讓你找出有多少個單詞在文章裡出現過。要搞懂AC自動機，先得有模式樹（字典樹）Trie和KMP模式比對算法的基礎知識。KMP算法是單模式串的字元比對算法，AC自動機是多模式串的字元比對算法。

一、原理

AC自動機算法詳解 》》 https://www.cnblogs.com/cmmdc/p/7337611.html

二、JavaScript代碼

//javascript實作字典樹trie，簡單的實作下
class TrieNode {
    constructor(value){
        this.value = value; //value為單個字元
        this.num=1;
        this.deep=0;//根節點預設0
        this.son=[];
        this.isEnd=false;
    }
    findNode(value){
        for(let i=0;i<this.son.length;i++){
            const node=this.son[i]
            if(node.value == value){
                return node;
            }
        }
        return null;
    }
}
class Trie {
    constructor(){
        this.root=new TrieNode(null);
        this.size=1;//一開始的時候隻有根節點這一個節點
    }
    insert(str){
        let node=this.root;
        for(let c of str){
            let snode = node.findNode(c);
            if(snode==null){
                snode=new TrieNode(c)
                snode.deep=node.deep+1;
                node.son.push(snode);
            }else{
                snode.num++;//有N個字元串經過它
            }
            node=snode;

        }
        //如果目前的node已經是一個word，則不需要添加
        if (!node.isEnd) {
            this.size++;
            node.isEnd = true;
        }
    }
    has(str){
        let node=this.root;
        for(let c of str){
            const snode=node.findNode(c)
            if(snode){
                node=snode;
            }else{
                return false;
            }
        }
        return node.isEnd;
    }
}
//建構字典樹失敗指針
function build_ac_automation(root){
    root.fail=null;
    const queue=[root]
    let i=0;
    while(i<queue.length){
        const temp=queue[i];
        for(let j=0;j<temp.son.length;j++){
            const node=temp.son[j]
            if(temp===root){
                node.fail=root;
            }else{
                node.fail=temp.fail.findNode(node.value)||root;
            }
            queue.push(node);
        }
        i++
    }
}
//ac算法多字元查詢
function acSearch(arr,str) {
    //生成字典樹
    const tr=new Trie()
    arr.forEach(function (item) {
        tr.insert(item)
    })
    //構造字典樹的失敗指針
    build_ac_automation(tr.root)
    let node=tr.root;

    const data=[];
    for(let i=0;i<str.length;i++){

        let cnode=node.findNode(str[i])
        //比對不到字元，進入失敗比對，
        while(!cnode&&node!==tr.root){
            node=node.fail;

            cnode=node.findNode(str[i])
        }
        if(cnode){
            node=cnode;
        }
        if(node.isEnd){
            data.push({
                start:i+1-node.deep,
                len:node.deep,
                str:str.substr(i+1-node.deep,node.deep),
                num:node.num,
            })
        }
    }
    return data;
}

//test
const result=acSearch(['she','shr','her','her'],'sher');
console.log(result);

/**
 * [ { start: 0, len: 3, str: 'she', num: 1 },
 { start: 1, len: 3, str: 'her', num: 2 } ]
 */
           

　　

　　

　　

轉載于:https://www.cnblogs.com/caoke/p/10895032.html