字典樹的實(shí)現(xiàn)和介紹

EddieChan 發(fā)布于2019-08-16 16:56 / 2554人閱讀

摘要：優(yōu)化老代碼的時(shí)候，用到了字典樹。我用寫了一個(gè)字典樹。因?yàn)槭嵌嗖鏄浣Y(jié)構(gòu)，可能這兩個(gè)單詞，，需要一個(gè)結(jié)束的標(biāo)識(shí)位。但是應(yīng)該有相關(guān)的文本搜索算法和字典樹相結(jié)合。如果字典樹更新不頻繁，比如地名，字典樹是可以化，保存到中。

優(yōu)化老代碼的時(shí)候，用到了字典樹。我用Java寫了一個(gè)字典樹。分享一下。

先說一下常見的引用場(chǎng)景，單詞匹配，統(tǒng)計(jì)（敏感詞檢測(cè)，單詞檢測(cè)），還有輸入提示等等。

下面是代碼了
node節(jié)點(diǎn)代碼

public class Node{
    private List nodeList = new ArrayList<>();
    private char word; //這里保存的一個(gè)字符
    private int isEnd = 0; //這里是一個(gè)結(jié)束標(biāo)識(shí)

    public Node(char w){
        this.word = w;
    }

    public Node(){ }

    public List getNodeList() {
        return nodeList;
    }

    public void setNodeList(List nodeList) {
        this.nodeList = nodeList;
    }

    public char getWord() {
        return word;
    }

    public void setWord(char word) {
        this.word = word;
    }

    public int getIsEnd() {
        return isEnd;
    }

    public void setIsEnd(int isEnd) {
        this.isEnd = isEnd;
    }
}

Node節(jié)點(diǎn)重點(diǎn)就是保存的char和isEnd這個(gè)兩個(gè)屬性，這里我保存的是字符串，其實(shí)可以保存成utf8的編碼，防止一些編碼問題。
因?yàn)槭嵌嗖鏄浣Y(jié)構(gòu)，可能這兩個(gè)單詞 sad，saddy，需要一個(gè)結(jié)束的標(biāo)識(shí)位。

添加節(jié)點(diǎn)代碼

    public void addNode(List nodeList,char[] word){
        List temp = new ArrayList<>();
        //遍歷單詞
        for (int i=0;i < word.length; i++ ){
            //查看子節(jié)點(diǎn)
            for (int j = nodeList.size(); j >= 0; j--) {
                //有子節(jié)點(diǎn)并且字相同，則更新nodeList并且跳出循環(huán)，檢查下一個(gè)字
                if (j > 0 && nodeList.get(j-1).getWord() == word[i]) {
                    nodeList = nodeList.get(j-1).getNodeList();
                    break;
                //如果子節(jié)點(diǎn)為零，則說明需要添加新節(jié)點(diǎn)    
                }else if(j == 0 ){
                    Node n = new Node(word[i]);
                    //判斷是否達(dá)到單詞結(jié)尾，添加標(biāo)志位
                    if( nodeList.size() == 0 && (i == word.length -1)){
                        n.setIsEnd(1);
                    }
                    temp = n.getNodeList();
                    nodeList.add(n);
                    //nodeList賦值給新節(jié)點(diǎn)，結(jié)束循環(huán)
                    nodeList = temp;
                }
            }
        }
    }

這一段需要注意的一點(diǎn)是，我是用了List這個(gè)數(shù)據(jù)結(jié)構(gòu)，這個(gè)地方可以優(yōu)化為Map結(jié)構(gòu)，Hash表的時(shí)間復(fù)雜度是O(1)。

搜索單詞

public boolean searchNode(List nodeList,char[] word){
    for (int i=0;i < word.length; i++ ){
        for (int j = nodeList.size() - 1; j >= 0; j--) {
            if (nodeList.get(j).getWord() == word[i]) {
                //單詞處于結(jié)尾，和有標(biāo)志位，則直接返回
                if( (i == word.length -1) && nodeList.get(j).getIsEnd() == 1){
                    return true;
                }
                nodeList = nodeList.get(j).getNodeList();
                break;
            }
        }
    }

    return false;
}

搜索文本

  
public boolean searchText(List nodeList,char[] word){
    //記錄頭節(jié)點(diǎn)
    List head = nodeList;
    for (int i=0;i < word.length; i++ ){
        for (int j = nodeList.size() - 1; j >= 0; j--) {
            if (nodeList.get(j).getWord() == word[i]) {
            //搜索文本就不要判斷單詞是否處于結(jié)尾了，查到直接就返回結(jié)果
                if( nodeList.get(j).getIsEnd() == 1){
                    return true;
                }
                nodeList = nodeList.get(j).getNodeList();
                break;
            }
            //當(dāng)節(jié)點(diǎn)沒有子節(jié)點(diǎn)，并且程序運(yùn)行到此，將nodeList復(fù)位到頭節(jié)點(diǎn)
            if(j == 0){
                nodeList = head;
            }
        }
    }
    return false;
}

處理敏感詞部分，或者相似功能應(yīng)該做分詞的處理。如果不做分詞處理的，會(huì)出現(xiàn)錯(cuò)誤，比如瑪麗露A。往后再推一個(gè)單詞。
我這里是一個(gè)字一個(gè)字去進(jìn)行順序查找的。但是應(yīng)該有相關(guān)的文本搜索算法和字典樹相結(jié)合。可以提高效率。

我這里實(shí)現(xiàn)的是O（m*n）上面也提到了可以優(yōu)化到O（n），但是也比之前快了不少了。比如輸入提示，比每一次查詢數(shù)據(jù)庫之類的要快很多。如果字典樹更新不頻繁，比如地名，字典樹是可以json化，保存到Redis中。這樣可以給其他語言去使用，而且比一次性查詢數(shù)據(jù)庫，之后再結(jié)構(gòu)化，也是要快一點(diǎn)的。

如果還哪里寫錯(cuò)了，或者有什么更好的優(yōu)化建議，歡迎討論。