rust 實現字典樹

何爲字典樹

字典樹又名前綴樹，是一種多叉樹。常用於路由查找、相同前綴的單詞查詢等場景。如果使用包含 26 個英文字母組成的語料庫來構建字典樹，那樹的每一個節點就表示一個字母，從根節點到葉節點的路徑則組成一個單詞。(根節點到中間節點也可能組成一個單詞，因此需要使用額外的標記)

上圖中綠色背景便是單詞 "rust" 在字典樹中的表示。

Trie 樹相較於哈希表，其優點如下：

可以快速檢索單詞是否存在，並且時間複雜度只有 O(m)，m 爲單詞的長度。哈希表在容量巨大哈希衝突嚴重時，複雜度可能增加到 O(log2(n))
Trie 樹在存儲具有相同前綴的單詞時，可以減少存儲開銷，使用更少的空間，例如單詞 "ru" 和 "rust" 共享前綴
Trie 樹可以快速找出具有同一前綴的所有單詞，而哈希表則比較喫力

實現字典樹

抽象出 Trie 結構體，並且使用 root 指向根節點。節點抽象爲 Node 結構體，並且擁有 mark 標記和 childs 子節點列表。

#[derive(Default, Debug)]

struct Trie {

    root: Box<Node>, // 字典樹的根節點

}

#[derive(Default, Debug)]

struct Node {

    mark: bool,                      // 標識字段：用於標識是否從根節點到此節點組成一個單詞

    childs: [Option<Box<Node>>; 26], //26個英文字母，只需要26個槽位

}

插入邏輯爲：

將單詞切分爲單個字符，遍歷每一個字符。從根節點開始查詢，如果找到了字符對應的節點，則直接返回；否則創建新節點。定位子節點方式爲當前字符減去字母'a'的 ASCII 碼值，表示 childs 數組的下標，該下標中存儲的節點便是當前字符應該去的子節點。重複上述過程，直到遍歷完整個單詞中的字符。將最後節點的 mark 設置爲 true，表示從根節點到此節點的路徑是一個完整的單詞。

/// 向字典樹插入單詞

fn insert(&mut self, word: &str) {

    let mut current_node = &mut self.root;

    //逐個字符插入

    for c in word.as_bytes() {

        // 字母在當前的childs的索引

        let index = (c - b'a') as usize;

        let child = &mut current_node.childs[index];

        // 如果child存在則插入，否則新建

        current_node = child.get_or_insert_with(Box::<Node>::default);

    }

    // 將current_node的mark標記爲true，表示從根節點到此節點組成一個單詞

    current_node.mark = true;

}

查詢邏輯爲：

從字典樹中檢索單詞 (或某個前綴) 就簡單了，同樣將單詞切分爲單個的字符，遍歷每一個字符，直到匹配到某個節點爲止。如果沒有匹配到則返回 None，表示字典樹中不存在這個單詞；否則返回最後一個字符所在的 Node，Node 中的 mark 標記如果爲 true，表示是一個完整的單詞。

fn contains(&self, word: &str) -> bool {

    self.word_node(word).map_or(false, |node| node.mark)

}

fn start_with(&self, prifix: &str) -> bool {

    self.word_node(prifix).is_some()

}

fn word_node(&self, word: &str) -> Option<&Node> {

    let mut current_node = &self.root;

    for c in word.as_bytes() {

        let index = (c - b'a') as usize;

        match &current_node.childs[index] {

            None => return None,

            Some(node) => current_node = node,

        }

    }

    Some(&current_node)

}

下面是測試用例：

fn main() {

    let mut trie = Trie::new();

    trie.insert("rust");

    trie.insert("hug");

    trie.insert("hello");

    trie.insert("hugrust");

    println!("hello in Trie:{}", trie.contains("hello"));

    println!("huga in Trie:{}", trie.contains("huga"));

    println!("Trie start with hella:{}", trie.start_with("hella"));

    println!("Trie start with rust:{}", trie.start_with("rust"));

}

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/HXsGou8EV8oCDHBZFAbJSg

何爲字典樹

實現字典樹

猜你喜歡