快捷導(dǎo)航

詳解Java前綴樹Trie的原理及代碼實現(xiàn)

更新時間：2022年11月18日 08:56:58 作者：劉Java

Trie又被稱為前綴樹、字典樹。Trie利用字符串的公共前綴來高效地存儲和檢索字符串?dāng)?shù)據(jù)集中的關(guān)鍵詞，最大限度地減少無謂的字符串比較，其核心思想是用空間換時間。本文主要介紹了Trie的原理及實現(xiàn)，感興趣的可以了解一下

Trie的概念

Trie（發(fā)音類似 “try”）又被稱為前綴樹、字典樹。Trie利用字符串的公共前綴來高效地存儲和檢索字符串?dāng)?shù)據(jù)集中的關(guān)鍵詞，最大限度地減少無謂的字符串比較，其核心思想是用空間換時間。

Trie樹可被用來實現(xiàn)字符串查詢、前綴查詢、詞頻統(tǒng)計、自動拼寫、補完檢查等等功能。

Trie樹的三個性質(zhì)：

根節(jié)點不包含字符，除根節(jié)點外每一個節(jié)點都只包含一個字符。
從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。
每個節(jié)點的所有子節(jié)點包含的字符都不相同。

Trie的實現(xiàn)

Trie是一顆非典型的多叉樹形結(jié)構(gòu)，多叉樹是因為一個節(jié)點可以有多個字節(jié)點，而非典型在于節(jié)點中沒有專門的字段直接保存此節(jié)點的值，而是通過一個數(shù)組或者map保存了當(dāng)前節(jié)點的所有下層子節(jié)點的值，也正是因此，根節(jié)點不表示任何字符。

基本結(jié)構(gòu)

最簡單的前綴樹的結(jié)構(gòu)如下：

內(nèi)部包含一個哈希表next，存儲著子節(jié)點的值到對應(yīng)的節(jié)點的映射關(guān)系。
還有一個布爾值isEnd，用來標(biāo)識該節(jié)點是否是一個字符串的結(jié)束。
調(diào)用無參構(gòu)造器將會初始化這兩個屬性。

實際上，還可以包含其他的屬性以實現(xiàn)特定的功能，例如加入count表示以當(dāng)前單詞結(jié)尾的單詞數(shù)量，加入prefix表示以該處節(jié)點之前的字符串為前綴的單詞數(shù)量。

另外，對于下層子節(jié)點的存儲，如果字符串僅包含小寫字母，或者固定范圍的字符，那么我們可以使用定長（例如26）的數(shù)組來表示next，這樣省去了hash操作的開銷，但同樣可能造成空間的浪費。

class Trie {
    /**
* 經(jīng)過該節(jié)點的字符串的下層節(jié)點
*/
    Map<Character, Trie> next;
    /**
* 該節(jié)點是否是一個字符串的結(jié)束
*/
    boolean isEnd;

    public Trie() {
        this.next = new HashMap<>();
        this.isEnd = false;
    }

}

構(gòu)建Trie

通過調(diào)用構(gòu)造器初始化一個Trie的根節(jié)點，通過insert操作向前綴樹中插入關(guān)鍵詞字符串（模式串）。

可以看到其實現(xiàn)的方法比較簡單：將字符串轉(zhuǎn)換為char數(shù)組，順序遍歷char數(shù)組的每個字符，然后從根節(jié)點開始判斷該節(jié)點的下層子節(jié)點映射next：

如果不包含此字符，那么加入一個新子節(jié)點進(jìn)去，值對應(yīng)著當(dāng)前字符。然后使用該子節(jié)點，進(jìn)入下一次循環(huán)判斷下一個字符。
如果包含此字符或者新插入了節(jié)點，那么當(dāng)前字符獲取對應(yīng)的子節(jié)點，進(jìn)入下一次循環(huán)判斷下一個字符。

循環(huán)完畢，我們完成了當(dāng)前字符串的Trie構(gòu)建，那么還需要將最后一個節(jié)點的isEnd改為true，表示該節(jié)點是一個字符串的結(jié)束。

public void insert(String word) {
    //初始默認(rèn)為根節(jié)點，根節(jié)點不包含任何字符
    Trie cur = this;
    //遍歷該字符串的字符數(shù)組
    for (char c : word.toCharArray()) {
        //如果該節(jié)點的下層不包含此字符，那么加入一個新節(jié)點進(jìn)去
        if (!cur.next.containsKey(c)) {
            cur.next.put(c, new Trie());
        }
        //查找下一層節(jié)點
        cur = cur.next.get(c);
    }
    //遍歷字符串完畢，最后的節(jié)點isEnd置為true，表示一個字符串的結(jié)束
    cur.isEnd = true;
}

查找字符串

基于Trie結(jié)構(gòu)可以查找字符串、匹配前綴、查找出現(xiàn)次數(shù)等等，這里我們給出查找字符串和查找前綴的方法。

比較簡單，我們從字典樹的根開始，查找前綴：

如果子節(jié)點存在。沿著指針移動到子節(jié)點，繼續(xù)搜索下一個字符。
如果子節(jié)點不存在。說明字典樹中不包含該前綴，返回空指針。

可以看到查找字符串相比于匹配前綴，僅僅是多了一個最下層子節(jié)點是否是一個字符串的結(jié)束的判斷而已。

/**
 * 查找字符串
 */
public boolean search(String word) {
    Trie end = searchPrefix(word);
    return end != null && end.isEnd;
}

/**
 * 匹配前綴
 */
public boolean startsWith(String prefix) {
    return searchPrefix(prefix) != null;
}

private Trie searchPrefix(String prefix) {
    //初始默認(rèn)為根節(jié)點，根節(jié)點不包含任何字符
    Trie cur = this;
    //遍歷該字符串的字符數(shù)組
    for (char c : prefix.toCharArray()) {
        //如果該節(jié)點的下層不包含此字符，那么直接返回null
        if (!cur.next.containsKey(c)) {
            return null;
        }
        //查找下一層節(jié)點
        cur = cur.next.get(c);
    }
    return cur;
}

Trie的總結(jié)

假設(shè)我們加入了she、he、his、her這四個字符串，那么Trie的結(jié)構(gòu)如下，其中紅色節(jié)點表示其屬于某個字符串的尾部節(jié)點。

Trie時間復(fù)雜度：初始化為O(1)，每次操作為O(N)，N為插入或查找的字符串的長度。

Trie空間復(fù)雜度：O(N)，N表示Trie結(jié)點數(shù)量，或者說所有插入字符串的長度之和（減去相同前綴長度）。如果是采用定長數(shù)組表示next，那么空間復(fù)雜度為O(N*M)，M表示字符集的大小，即數(shù)組長度。

可以看到，使用Trie的數(shù)據(jù)結(jié)構(gòu)使得插入、查詢?nèi)~、查詢前綴的時間復(fù)雜度與已插入的單詞數(shù)目和長度無關(guān)，這是它的一個優(yōu)點。

但是，Trie又名前綴樹，因為它只能基于前綴匹配實現(xiàn)某些功能。另一些功能，例如判斷一段字符串中是否包含某些關(guān)鍵詞，不需要前綴匹配，此時就無法使用Trie了。

相關(guān)題目如下：208. 實現(xiàn) Trie (前綴樹)

完整實現(xiàn)如下：

class Trie {
    /**
     * 經(jīng)過該節(jié)點的字符串的下層節(jié)點
     */
    Map<Character, Trie> next;
    /**
     * 該節(jié)點是否是一個字符串的結(jié)束
     */
    boolean isEnd;

    public Trie() {
        this.next = new HashMap<>();
        this.isEnd = false;
    }

    public void insert(String word) {
        //初始默認(rèn)為根節(jié)點，根節(jié)點不包含任何字符
        Trie cur = this;
        //遍歷該字符串的字符數(shù)組
        for (char c : word.toCharArray()) {
            //如果該節(jié)點的下層不包含此字符，那么加入一個新節(jié)點進(jìn)去
            if (!cur.next.containsKey(c)) {
                cur.next.put(c, new Trie());
            }
            //查找下一層節(jié)點
            cur = cur.next.get(c);
        }
        //遍歷字符串完畢，最后的節(jié)點isEnd置為true，表示一個字符串的結(jié)束
        cur.isEnd = true;
    }

    /**
     * 查找字符串
     */
    public boolean search(String word) {
        Trie end = searchPrefix(word);
        return end != null && end.isEnd;
    }

    /**
     * 匹配前綴
     */
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        //初始默認(rèn)為根節(jié)點，根節(jié)點不包含任何字符
        Trie cur = this;
        //遍歷該字符串的字符數(shù)組
        for (char c : prefix.toCharArray()) {
            //如果該節(jié)點的下層不包含此字符，那么直接返回null
            if (!cur.next.containsKey(c)) {
                return null;
            }
            //查找下一層節(jié)點
            cur = cur.next.get(c);
        }
        return cur;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("你是xxl嗎？");
    }
}

以上就是詳解Java前綴樹Trie的原理及代碼實現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于Java前綴樹Trie的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: