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

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

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

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

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

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

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

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

添加節(jié)點代碼

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

這一段需要注意的一點是，我是用了List這個數(shù)據(jù)結(jié)構(gòu)，這個地方可以優(yōu)化為Map結(jié)構(gòu)，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]) {
                //單詞處于結(jié)尾，和有標志位，則直接返回
                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é)點
    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;
            }
            //當節(jié)點沒有子節(jié)點，并且程序運行到此，將nodeList復位到頭節(jié)點
            if(j == 0){
                nodeList = head;
            }
        }
    }
    return false;
}

處理敏感詞部分，或者相似功能應該做分詞的處理。如果不做分詞處理的，會出現(xiàn)錯誤，比如瑪麗露A。往后再推一個單詞。
我這里是一個字一個字去進行順序查找的。但是應該有相關的文本搜索算法和字典樹相結(jié)合?？梢蕴岣咝省?/p>

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

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

GPU云服務器云服務器 java菜單樹的實現(xiàn) c語言樹的深度和節(jié)點 j2ee 數(shù)據(jù)字典實現(xiàn) 介紹騰訊云服務器注冊和配置流程

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/74276.html

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

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

cheukyin 2019-07-01 12:42 評論0 收藏0
簡單字典樹實現(xiàn)

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

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

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

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

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

scq000 2019-08-21 18:30 評論0 收藏0
一種字典樹結(jié)構(gòu)的高效實現(xiàn)

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

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