您现在的位置： Linux教程網 >> UnixLinux > >> Linux編程 >> Linux編程

字典樹(Trie樹)實現與應用

閱讀目錄

一、概述
二、構建過程
三、簡單應用
四、參考資料

一、概述

　　1、基本概念

　　字典樹，又稱為單詞查找樹，Tire數，是一種樹形結構，它是一種哈希樹的變種。

　　2、基本性質

根節點不包含字符，除根節點外的每一個子節點都包含一個字符
從根節點到某一節點。路徑上經過的字符連接起來，就是該節點對應的字符串
每個節點的所有子節點包含的字符都不相同

　　3、應用場景

　　典型應用是用於統計，排序和保存大量的字符串(不僅限於字符串)，經常被搜索引擎系統用於文本詞頻統計。

　　4、優點

　　利用字符串的公共前綴來減少查詢時間，最大限度的減少無謂的字符串比較，查詢效率比哈希樹高。

二、構建過程

　　1、字典樹節點定義

class TrieNode // 字典樹節點
    {
        private int num;// 有多少單詞通過這個節點,即由根至該節點組成的字符串模式出現的次數
        private TrieNode[] son;// 所有的兒子節點
        private boolean isEnd;// 是不是最後一個節點
        private char val;// 節點的值

        TrieNode()
        {
            num = 1;
            son = new TrieNode[SIZE];
            isEnd = false;
        }
    }

　　2、字典樹構造函數

    Trie() // 初始化字典樹
    {
        root = new TrieNode();
    }

　　3、建立字典樹

// 建立字典樹
    public void insert(String str) // 在字典樹中插入一個單詞
    {
        if (str == null || str.length() == 0)
        {
            return;
        }
        TrieNode node = root;
        char[] letters = str.toCharArray();//將目標單詞轉換為字符數組
        for (int i = 0, len = str.length(); i < len; i++)
        {
            int pos = letters[i] - 'a';
            if (node.son[pos] == null)  //如果當前節點的兒子節點中沒有該字符，則構建一個TrieNode並復值該字符
            {
                node.son[pos] = new TrieNode();
                node.son[pos].val = letters[i];
            } 
            else   //如果已經存在，則將由根至該兒子節點組成的字符串模式出現的次數+1
            {
                node.son[pos].num++;
            }
            node = node.son[pos];
        }
        node.isEnd = true;
    }

　　4、在字典樹中查找是否完全匹配一個指定的字符串

    // 在字典樹中查找一個完全匹配的單詞.
    public boolean has(String str)
    {
        if(str==null||str.length()==0)
        {
            return false;
        }
        TrieNode node=root;
        char[]letters=str.toCharArray();
        for(int i=0,len=str.length(); i<len; i++)
        {
            int pos=letters[i]-'a';
            if(node.son[pos]!=null)
            {
                node=node.son[pos];
            }
            else
            {
                return false;
            }
        }
        //走到這一步，表明可能完全匹配，也可能部分匹配，如果最後一個字符節點為末端節點，則是完全匹配，否則是部分匹配
        return node.isEnd;
    }

　　5、前序遍歷字典樹

　　// 前序遍歷字典樹.
    public void preTraverse(TrieNode node)
    {
        if(node!=null)
        {
            System.out.print(node.val+"-");
            for(TrieNode child:node.son)
            {
                preTraverse(child);
            }
        }
    }

　　6、計算單詞前綴的數量

　　// 計算單詞前綴的數量
    public int countPrefix(String prefix)
    {
        if(prefix==null||prefix.length()==0)
        {
            return-1;
        }
        TrieNode node=root;
        char[]letters=prefix.toCharArray();
        for(int i=0,len=prefix.length(); i<len; i++)
        {
            int pos=letters[i]-'a';
            if(node.son[pos]==null)
            {
                return 0;
            }
            else
            {
                node=node.son[pos];
            }
        }
        return node.num;
    }

　　完整代碼：

package com.xj.test;

public class Trie
{
    private int SIZE = 26;
    private TrieNode root;// 字典樹的根

    class TrieNode // 字典樹節點
    {
        private int num;// 有多少單詞通過這個節點,即由根至該節點組成的字符串模式出現的次數
        private TrieNode[] son;// 所有的兒子節點
        private boolean isEnd;// 是不是最後一個節點
        private char val;// 節點的值

        TrieNode()
        {
            num = 1;
            son = new TrieNode[SIZE];
            isEnd = false;
        }
    }
    Trie() // 初始化字典樹
    {
        root = new TrieNode();
    }
    

    // 建立字典樹
    public void insert(String str) // 在字典樹中插入一個單詞
    {
        if (str == null || str.length() == 0)
        {
            return;
        }
        TrieNode node = root;
        char[] letters = str.toCharArray();//將目標單詞轉換為字符數組
        for (int i = 0, len = str.length(); i < len; i++)
        {
            int pos = letters[i] - 'a';
            if (node.son[pos] == null)  //如果當前節點的兒子節點中沒有該字符，則構建一個TrieNode並復值該字符
            {
                node.son[pos] = new TrieNode();
                node.son[pos].val = letters[i];
            } 
            else   //如果已經存在，則將由根至該兒子節點組成的字符串模式出現的次數+1
            {
                node.son[pos].num++;
            }
            node = node.son[pos];
        }
        node.isEnd = true;
    }

    // 計算單詞前綴的數量
    public int countPrefix(String prefix)
    {
        if(prefix==null||prefix.length()==0)
        {
            return-1;
        }
        TrieNode node=root;
        char[]letters=prefix.toCharArray();
        for(int i=0,len=prefix.length(); i<len; i++)
        {
            int pos=letters[i]-'a';
            if(node.son[pos]==null)
            {
                return 0;
            }
            else
            {
                node=node.son[pos];
            }
        }
        return node.num;
    }

    // 打印指定前綴的單詞
    public String hasPrefix(String prefix)
    {
        if (prefix == null || prefix.length() == 0)
        {
            return null;
        }
        TrieNode node = root;
        char[] letters = prefix.toCharArray();
        for (int i = 0, len = prefix.length(); i < len; i++)
        {
            int pos = letters[i] - 'a';
            if (node.son[pos] == null)
            {
                return null;
            }
            else
            {
                node = node.son[pos];
            }
        }
        preTraverse(node, prefix);
        return null;
    }

    // 遍歷經過此節點的單詞.
    public void preTraverse(TrieNode node, String prefix)
    {
        if (!node.isEnd)
        {
            for (TrieNode child : node.son)
            {
                if (child != null)
                {
                    preTraverse(child, prefix + child.val);
                }
            }
            return;
        }
        System.out.println(prefix);
    }

    // 在字典樹中查找一個完全匹配的單詞.
    public boolean has(String str)
    {
        if(str==null||str.length()==0)
        {
            return false;
        }
        TrieNode node=root;
        char[]letters=str.toCharArray();
        for(int i=0,len=str.length(); i<len; i++)
        {
            int pos=letters[i]-'a';
            if(node.son[pos]!=null)
            {
                node=node.son[pos];
            }
            else
            {
                return false;
            }
        }
        //走到這一步，表明可能完全匹配，可能部分匹配，如果最後一個字符節點為末端節點，則是完全匹配，否則是部分匹配
        return node.isEnd;
    }

    // 前序遍歷字典樹.
    public void preTraverse(TrieNode node)
    {
        if(node!=null)
        {
            System.out.print(node.val+"-");
            for(TrieNode child:node.son)
            {
                preTraverse(child);
            }
        }
    }

    public TrieNode getRoot()
    {
        return this.root;
    }

    public static void main(String[]args)
    {
        Trie tree=new Trie();
        String[]strs= {"banana","band","bee","absolute","acm",};
        String[]prefix= {"ba","b","band","abc",};
        for(String str:strs)
        {
            tree.insert(str);
        }
        System.out.println(tree.has("abc"));
        tree.preTraverse(tree.getRoot());
        System.out.println();
        //tree.printAllWords();
        for(String pre:prefix)
        {
            int num=tree.countPrefix(pre);
            System.out.println(pre+"數量:"+num);
        }
    }
}

　　執行結果截圖：

三、簡單應用

　　下面講一個簡單的應用，問題是這樣的：

　　現在有一個英文字典(每個單詞都是由小寫的a-z組成)，單詞量很大，而且還有很多重復的單詞。

　　此外，我們還有一些Document，每個Document包含一些英語單詞。下面是問題：

　　(問題1)請你選擇合適的數據結構，將所有的英文單詞生成一個字典Dictionary？

　　(問題2)給定一個單詞，判斷這個單詞是否在字典Dictionary中，如果在單詞庫中，輸出這個單詞出現總共出現的次數，否則輸出NO？

package com.xj.test;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Trie
{
    private int SIZE = 26;
    private TrieNode root;// 字典樹的根

    class TrieNode // 字典樹節點
    {
        private int num;// 有多少單詞通過這個節點,即由根至該節點組成的字符串模式出現的次數
        private TrieNode[] son;// 所有的兒子節點
        private boolean isEnd;// 是不是最後一個節點
        private char val;// 節點的值

        TrieNode()
        {
            num = 1;
            son = new TrieNode[SIZE];
            isEnd = false;
        }
    }
    Trie() // 初始化字典樹
    {
        root = new TrieNode();
    }
    

    // 建立字典樹
    public void insert(String str) // 在字典樹中插入一個單詞
    {
        if (str == null || str.length() == 0)
        {
            return;
        }
        TrieNode node = root;
        char[] letters = str.toCharArray();//將目標單詞轉換為字符數組
        for (int i = 0, len = str.length(); i < len; i++)
        {
            int pos = letters[i] - 'a';
            if (node.son[pos] == null)  //如果當前節點的兒子節點中沒有該字符，則構建一個TrieNode並復值該字符
            {
                node.son[pos] = new TrieNode();
                node.son[pos].val = letters[i];
            } 
            else   //如果已經存在，則將由根至該兒子節點組成的字符串模式出現的次數+1
            {
                node.son[pos].num++;
            }
            node = node.son[pos];
        }
        node.isEnd = true;
    }

    // 計算單詞前綴的數量
    public int countPrefix(String prefix)
    {
        if(prefix==null||prefix.length()==0)
        {
            return-1;
        }
        TrieNode node=root;
        char[]letters=prefix.toCharArray();
        for(int i=0,len=prefix.length(); i<len; i++)
        {
            int pos=letters[i]-'a';
            if(node.son[pos]==null)
            {
                return 0;
            }
            else
            {
                node=node.son[pos];
            }
        }
        return node.num;
    }

    // 打印指定前綴的單詞
    public String hasPrefix(String prefix)
    {
        if (prefix == null || prefix.length() == 0)
        {
            return null;
        }
        TrieNode node = root;
        char[] letters = prefix.toCharArray();
        for (int i = 0, len = prefix.length(); i < len; i++)
        {
            int pos = letters[i] - 'a';
            if (node.son[pos] == null)
            {
                return null;
            }
            else
            {
                node = node.son[pos];
            }
        }
        preTraverse(node, prefix);
        return null;
    }

    // 遍歷經過此節點的單詞.
    public void preTraverse(TrieNode node, String prefix)
    {
        if (!node.isEnd)
        {
            for (TrieNode child : node.son)
            {
                if (child != null)
                {
                    preTraverse(child, prefix + child.val);
                }
            }
            return;
        }
        System.out.println(prefix);
    }

    // 在字典樹中查找一個完全匹配的單詞.
    public boolean has(String str)
    {
        if(str==null||str.length()==0)
        {
            return false;
        }
        TrieNode node=root;
        char[]letters=str.toCharArray();
        for(int i=0,len=str.length(); i<len; i++)
        {
            int pos=letters[i]-'a';
            if(node.son[pos]!=null)
            {
                node=node.son[pos];
            }
            else
            {
                return false;
            }
        }
        //走到這一步，表明可能完全匹配，可能部分匹配，如果最後一個字符節點為末端節點，則是完全匹配，否則是部分匹配
        return node.isEnd;
    }

    // 前序遍歷字典樹.
    public void preTraverse(TrieNode node)
    {
        if(node!=null)
        {
            System.out.print(node.val+"-");
            for(TrieNode child:node.son)
            {
                preTraverse(child);
            }
        }
    }
    public TrieNode getRoot()
    {
        return this.root;
    }
    public static void main(String[]args) throws IOException
    {
        Trie tree=new Trie();
        String[] dictionaryData= {"hello","student","computer","sorry","acm","people","experienced","who","reminds","everyday","almost"};
        //構建字典
        for(String str:dictionaryData)
        {
            tree.insert(str);
        }
        String filePath="C:\\Users\\Administrator\\Desktop\\sourceFile.txt";
        File file=new File(filePath);
        if(file.isFile() && file.exists())
        { 
            InputStreamReader read = new InputStreamReader(new FileInputStream(file));
            BufferedReader bufferedReader = new BufferedReader(read);
            String lineTxt = null;
            Map<String,Integer> countMap=new HashMap<String,Integer>();
            while((lineTxt = bufferedReader.readLine())!= null)
            {
                if(tree.has(lineTxt))
                {
                    if(countMap.containsKey(lineTxt))
                    {
                        countMap.put(lineTxt, countMap.get(lineTxt)+1);
                    }
                    else
                    {
                        countMap.put(lineTxt, 1);
                    }
                }
                else
                {
                    System.out.println(lineTxt+"不在字典中！");
                }
            }
            for(String s:countMap.keySet())
            {
                System.out.println(s+"出現的次數"+countMap.get(s));
            }
            read.close();
        }
    }   
    
}

　　其中text文件內容為：

　　程序執行結果為：

上一篇文章： Java中的BitSet學習筆記
下一篇文章： Java NIO中的讀和寫

Linux編程

Python中的字典應用實例

Python 字典內置方法get應用

Android應用實現多語言切換

使用雙緩沖技術實現Android畫板應用

應用Python快速實現系統原型

Python字典數組排序實現

一個通用的Trie樹，標准C++實現

如何使用HTML5實現拍照上傳應用

相關文章

應用LoadRunner實現對Linux系統的監視

ethtool 在 Linux 中的實現框架和應用

iptables實現應用層的包過濾

Qt下應用QTcpServer與QTcpSocket實現Tcp控制

大-小頂混合堆的實現與應用(a min-max heap)

Java實戰應用:MyBatis實現單表的增刪改

Android照片牆應用實現，再多的圖片也不怕崩潰

Android 游戲之場景的實現以及拓展應用照片浏覽器

用Animation動畫實現Android應用的歡迎界面

Android應用自動更新功能的實現

【linux基礎】22、iptables layer7 實現七層應用過濾

利用Docker輕松實現雲原生應用

Linux編程

SHELL編程

PERL編程