字典樹的實現和介紹

cheukyin 發布于2019-07-01 12:42 / 567人閱讀

摘要：優化老代碼的時候，用到了字典樹。我用寫了一個字典樹。因為是多叉樹結構，可能這兩個單詞，，需要一個結束的標識位。但是應該有相關的文本搜索算法和字典樹相結合。如果字典樹更新不頻繁，比如地名，字典樹是可以化，保存到中。

優化老代碼的時候，用到了字典樹。我用Java寫了一個字典樹。分享一下。

先說一下常見的引用場景，單詞匹配，統計（敏感詞檢測，單詞檢測），還有輸入提示等等。

下面是代碼了
node節點代碼

public class Node{
    private List nodeList = new ArrayList<>();
    private char word; //這里保存的一個字符
    private int isEnd = 0; //這里是一個結束標識

    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節點重點就是保存的char和isEnd這個兩個屬性，這里我保存的是字符串，其實可以保存成utf8的編碼，防止一些編碼問題。
因為是多叉樹結構，可能這兩個單詞 sad，saddy，需要一個結束的標識位。

添加節點代碼

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

這一段需要注意的一點是，我是用了List這個數據結構，這個地方可以優化為Map結構，Hash表的時間復雜度是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]) {
                //單詞處于結尾，和有標志位，則直接返回
                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){
    //記錄頭節點
    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]) {
            //搜索文本就不要判斷單詞是否處于結尾了，查到直接就返回結果
                if( nodeList.get(j).getIsEnd() == 1){
                    return true;
                }
                nodeList = nodeList.get(j).getNodeList();
                break;
            }
            //當節點沒有子節點，并且程序運行到此，將nodeList復位到頭節點
            if(j == 0){
                nodeList = head;
            }
        }
    }
    return false;
}

處理敏感詞部分，或者相似功能應該做分詞的處理。如果不做分詞處理的，會出現錯誤，比如瑪麗露A。往后再推一個單詞。
我這里是一個字一個字去進行順序查找的。但是應該有相關的文本搜索算法和字典樹相結合。可以提高效率。

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

如果還哪里寫錯了，或者有什么更好的優化建議，歡迎討論。

GPU云服務器云服務器 java菜單樹的實現 c語言樹的深度和節點 j2ee 數據字典實現介紹騰訊云服務器注冊和配置流程

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/31298.html

字典樹的實現和介紹

摘要：優化老代碼的時候，用到了字典樹。我用寫了一個字典樹。因為是多叉樹結構，可能這兩個單詞，，需要一個結束的標識位。但是應該有相關的文本搜索算法和字典樹相結合。如果字典樹更新不頻繁，比如地名，字典樹是可以化，保存到中。優化老代碼的時候，用到了字典樹。我用Java寫了一個字典樹。分享一下。先說一下常見的引用場景，單詞匹配，統計（敏感詞檢測，單詞檢測），還有輸入提示等等。下面是代碼了nod...

EddieChan 2019-08-16 16:56 評論0 收藏0
簡單字典樹實現

摘要：查找操作查詢指定單詞是否在字典樹中。將單詞標記為當前單詞，將根節點標記為當前節點，執行操作當前單詞為空，那么返回，即字典樹中存在該單詞。字典樹的簡單實現插入操作查找操作刪除操作具體實現放在上，可以在這里找到。原文地址字典樹介紹我們經常會在網上輸入一些單詞，一般情況下，當我們輸入幾個字母時，輸入框中會自動彈出以這些字母開頭的單詞供我們選擇，用戶體驗非常好。不過這種自動提示功能到底...

MonoLog 2019-07-31 11:32 評論0 收藏0
大展身手的字典樹

摘要：原文地址在簡單字典樹的實現一文中，我們以單詞輸入自動提示為引子，簡單介紹了字典樹的實現。前綴匹配本文講述前綴匹配的字典樹實現方案。在簡單字典樹的實現一文中，我們已經實現了字典樹的基本操作，這里只需要再加上一個前綴匹配方法即可。原文地址在簡單字典樹(Trie)的實現一文中，我們以單詞輸入自動提示為引子，簡單介紹了字典樹的實現。那么，字典樹到底可以用于哪些場合呢？前綴匹配：給定字典...

Anchorer 2019-07-24 17:36 評論0 收藏0
最小生成樹原理及Kruskal算法的js實現

摘要：生成樹和最小生成樹的概念設圖連通，則生成樹包含圖中的所有節點，及條邊的連通圖，一個圖的生成樹可以有多顆最小生成樹最小權重生成樹，在生成樹的概念上加一個限制條件，即生成樹的所有邊的權值總和最小的樹，最小生成樹也可以有多顆求解最小生成樹的通用 1. 生成樹和最小生成樹的概念設圖G(V,E)連通，則生成樹：包含圖G(V,E)中的所有節點，及|V|-1條邊的連通圖，一個圖的生成樹可以有多顆最...

scq000 2019-08-21 18:30 評論0 收藏0
一種字典樹結構的高效實現

摘要：另一種高效實現下面介紹另一種實現，它將字典樹用數組存儲起來，不僅壓縮了數組，而且不降低查找效率。這就是雙數組字典樹。字典樹的心得體會常見的字典樹實現方法 class Node{ uint node ; uint[] next; }; 或者類似如下結構 class Node{ uint node; map n...

kycool 2019-08-14 17:44 評論0 收藏0