詳解Java中字典樹(Trie樹)的圖解與實現

Posted on by

簡介

Trie又稱為前綴樹或字典樹，是一種有序樹，它是一種專門用來處理串匹配的數據結構，用來解決一組字符中快速查找某個字符串的問題。Google搜索的關鍵字提示功能相信大傢都不陌生，我們在輸入框中進行搜索的時候，會下拉出一系列候選關鍵詞。

image-20220511111955847

上面這個關鍵詞提示功能，底層最基本的原理就是我們今天說的數據結構：Trie樹

我們先看看Tire樹長什麼樣子，以單純的單詞匹配為例，首先它是一棵多叉樹結構，根節點是一個空字符，樹中節點分為普通節點和結尾節點（如圖中紅色節點）。結尾節點表示加上前面前綴，可以稱為一個單詞，如圖中hi，him。

image-20220511113614538

工作過程

Tire樹與之前串匹配最大的不同點是，之前我們都是單模式串，查看主串中是否有與模式串匹配的子串，操作過程也是用模式串去與主串進行比較。而Tire樹是多模式串，我們先將模式串提前構建成Tire樹，然後查看主串是否匹配模式串，且更適用於類似如上關鍵詞提示的前綴匹配。接下來我們自己通過實現一個簡易的關鍵詞提示功能來講解Tire樹。

數據結構

一個value存儲當前節點值，用一個26大小的數組存儲當前節點的孩子節點，這是一個簡單但是可能產生浪費的方法，可以采用有序存入采用二分法查找，或者采用hash表，跳表進行優化。一個標志當前節點是否可作為尾節點。

/**
     * Trie樹節點
     * 假設我們隻做26個小寫字母下的匹配
     */
    public static class Node{
        //當前節點值
        private char value;
        //當前節點的孩子節點
        private Node[] childNode;
        //標志當前節點是否是某單詞結尾
        private boolean isTail;
        public Node(char value) {
            this.value = value;
        }
    }

初始化

初始化一個僅有root節點的Tire樹，root節點值為'/0'。

Node root;
public void init() {
        root = new Node('\0');
        root.childNode = new Node[26];
}

構建字典樹

將需要加入的模式串加入Tire樹，遍歷當前字符串字符，從Tire樹根節點開始查找當前字符，如果字符已經存在不需要處理，並且從這個字符節點出發，查看下一個字符是否存在，如果當前節點不存Tire樹，才需要插入當前字符，當插入最後一個字符時需要標志當前字符節點為尾節點。

image-20220511222429713

/**
     * 將當前串插入字典樹
     * @param chars
     */
    public void insertStr(char[] chars) {
        //首先判斷首字符是否已經在字典樹中，然後判斷第二字符，依次往下進行判斷，找到第一個不存在的字符進行插入孩節點
        Node p = root;
        //表明當前處理到瞭第幾個字符
        int chIndex = 0;
        while (chIndex < chars.length) {
            while (chIndex < chars.length && null != p) {
                Node[] children = p.childNode;
                boolean find = false;
                for (Node child : children) {
                    if (null == child) {continue;}
                    if (child.value == chars[chIndex]) {
                        //當前字符已經存在，不需要再進行存儲
                        //從當前節點出發，存儲下一個字符
                        p = child;
                        ++ chIndex;
                        find = true;
                        break;
                    }
                }
                if (Boolean.TRUE.equals(find)) {
                    //在孩子中找到瞭 不用再次存儲
                    break;
                }
                //如果把孩子節點都找遍瞭，還沒有找到這個字符，直接將這個字符加入當前節點的孩子節點
                Node node = new Node(chars[chIndex]);
                node.childNode = new Node[26];
                children[chars[chIndex] - 'a'] = node;
                p = node;
                ++ chIndex;
            }
        }
        //字符串中字符全部進入tire樹中後，將最後一個字符所在節點標志為結尾節點
        p.isTail = true;
    }

應用

匹配有效單詞

遍歷字符串，從根節點出發，查看字符是否存在，隻要存在不存在的情況，直接返回false，如果每個字符都存在，判斷最後一個字符是否為結尾節點，如果不是，到這裡還不是一個有效單詞，返回false，否則，返回true。

 /**
     * 查看當前字符串是否可以在trie中找到
     * @param str 主串
     * @return true/false
     */
    public boolean isMatch(String str) {
        //從root開始進行匹配，隻要有一個找不到即為匹配失敗
        char[] chars = str.toCharArray();
        int chIndex = 0;
        Node p = root;
        while (null != p) {
            Node[] children = p.childNode;
            boolean flag = false;
            for (Node child : children) {
                if (null == child) {continue;}
                if (child.value == chars[chIndex]) {
                    flag = true;
                    p = child;
                    ++ chIndex;
                    //當比較最後一個字符的時候，這個字符需要是結尾字符才能完全匹配
                    if (chIndex == chars.length && p.isTail) {
                        return true;
                    }
                    break;
                }
            }
            if (Boolean.FALSE.equals(flag)) {
                return false;
            }
        }
        return false;
    }

測試樣例

public static void main(String[] args) {
        //he, him, lot, a
        //初始化Tire樹
        Trie trie = new Trie();
        trie.init();
        //構建Tire樹，隻有以下單詞才是有效單詞
        trie.insertStr("he".toCharArray());
        trie.insertStr("him".toCharArray());
        trie.insertStr("lot".toCharArray());
        trie.insertStr("a".toCharArray());
        //匹配字符串是否為有效單詞
        System.out.println(trie.isMatch("lot"));
        System.out.println(trie.isMatch("lit"));

    }

運行結果

image-20220511223308571

關鍵詞提示

根據輸入的關鍵詞前綴，匹配所有可能出現的關鍵詞。首先遍歷字符串，從節點出發，隻要有一個找不到，直接返回null，直至找到最後一個字符對應的節點，從該節點出發找到所有尾節點。

 /**
     * 找到所有以str為前綴的字符串
     * @param str 前綴串
     * @return 所有以str為前綴的單詞
     */
    public List<String> findStrPrefix(String str) {
        //根據str首先找到str最後一個字符，然後從這個字符出發，找到所有字符串
        List<String> result = new ArrayList<>();
        char[] chars = str.toCharArray();
        //分成兩步走
        //1。找到str最後一個自字符在字典樹中的node
        //2。從該node出發，找到所有的結尾node，即為以str為前綴的字符串
        int chIndex = 0;
        Node p = root;
        while (null != p && chIndex < chars.length) {
            Node[] children = p.childNode;
            boolean flag = false;
            for (Node child : children) {
                if (null == child) {continue;}
                if (child.value == chars[chIndex]) {
                    //已經找到
                    p = child;
                    flag = true;
                    ++ chIndex;
                    break;
                }
            }
            //如果沒有找到，直接返回空
            if (Boolean.FALSE.equals(flag)) {
                return null;
            }
        }
        //找到瞭最後一個節點
        //深度優先遍歷，查找所有尾節點
        this.dfs(p, new StringBuilder(str), result);
        return result;
    }

    public void dfs(Node p, StringBuilder str, List<String> result) {
        Node[] children = p.childNode;
        for (Node child : children) {
            if (null == child) {
                continue;
            }
            str.append(child.value);
            if (child.isTail) {
                result.add(str.toString());
            }
            //再遞歸查當前節點的孩子節點
            dfs(child, str, result);
            //需要將剛剛set進去的節點刪除，否則影響當前節點的下一個孩子節點
            //舉個例子，h的孩子節點有e，i，當e放進去之後不拿出來，在遍歷到i的時候，就會形成hei
            str.setLength(str.length() - 1);
        }
    }

測試樣例

public static void main(String[] args) {
        //he, him, lot, a
        //初始化Tire樹
        Trie trie = new Trie();
        trie.init();
        //構建Tire樹，隻有以下單詞才是有效單詞
        trie.insertStr("he".toCharArray());
        trie.insertStr("him".toCharArray());
        trie.insertStr("lot".toCharArray());
        trie.insertStr("a".toCharArray());
        //匹配字符串是否為有效單詞
        List<String> strings = trie.findStrPrefix("h");
    }

運行結果

總結

到這裡Trie樹就講完瞭，主要就是聚合前綴，通過樹的特性，按照鏈路進行訪問，同時標志尾節點，標志到當前節點是一個完整的字符串。

以上就是詳解Java中字典樹(Trie樹)的圖解與實現的詳細內容，更多關於Java字典樹的資料請關註LevelAH其它相關文章！

推薦閱讀：