忽若流星

Trie—單詞查找樹(shù)

l  簡(jiǎn)介

Trie，又稱單詞查找樹(shù)、前綴樹(shù)，是一種哈希樹(shù)的變種。應(yīng)用于字符串的統(tǒng)計(jì)與排序，經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。

含有單詞“tea”“tree”“A”“ZSU”的一棵Trie。

l  性質(zhì)

n  根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外的每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。

n  從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。

n  每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。

l  優(yōu)點(diǎn)

n  查詢快。對(duì)于長(zhǎng)度為m的鍵值，最壞情況下只需花費(fèi)O(m)的時(shí)間；而BST最壞情況下需要O(m log n)的時(shí)間。

n  當(dāng)存儲(chǔ)大量字符串時(shí)，Trie耗費(fèi)的空間較少。因?yàn)殒I值并非顯式存儲(chǔ)的，而是與其他鍵值共享子串。

n  Trie適用于“最長(zhǎng)前綴匹配”。

l  操作

n  初始化或清空

遍歷Trie，刪除所有節(jié)點(diǎn)，只保留根節(jié)點(diǎn)。

n  插入字符串

1.     設(shè)置當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)，設(shè)置當(dāng)前字符為插入字符串中的首個(gè)字符；

2.     在當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)上搜索當(dāng)前字符，若存在，則將當(dāng)前節(jié)點(diǎn)設(shè)為值為當(dāng)前字符的子節(jié)點(diǎn)；否則新建一個(gè)值為當(dāng)前字符的子節(jié)點(diǎn)，并將當(dāng)前結(jié)點(diǎn)設(shè)置為新創(chuàng)建的節(jié)點(diǎn)。.

3.     將當(dāng)前字符設(shè)置為串中的下個(gè)字符，若當(dāng)前字符為0，則結(jié)束；否則轉(zhuǎn)2.

n  查找字符串

搜索過(guò)程與插入操作類似，當(dāng)字符找不到匹配時(shí)返回假；若全部字符都存在匹配，判斷最終停留的節(jié)點(diǎn)是否為樹(shù)葉，若是，則返回真，否則返回假。

n  刪除字符串

首先查找該字符串，邊查詢邊將經(jīng)過(guò)的節(jié)點(diǎn)壓棧，若找不到，則返回假；否則依次判斷棧頂節(jié)點(diǎn)是否為樹(shù)葉，若是則刪除該節(jié)點(diǎn)，否則返回真。

l 實(shí)現(xiàn)
對(duì)于字符表大小為S的字符串集，需建立一個(gè)S叉樹(shù)來(lái)代表這些字符串的集合。

l  代碼

trie.h
/**//** 版權(quán)所有 (C) 2009 喻揚(yáng) 中山大學(xué)
/* 本程序只作學(xué)習(xí)用途，未經(jīng)許可，不得用于任何商業(yè)目的。
*/
#include <string.h>

/**//* trie的節(jié)點(diǎn)類型 */
template <int Size> //Size為字符表的大小
struct trie_node {
    /**//* 數(shù)據(jù)成員 */
    bool terminable; //當(dāng)前節(jié)點(diǎn)是否可以作為字符串的結(jié)尾
    int node; //子節(jié)點(diǎn)的個(gè)數(shù)
    trie_node *child[Size]; //指向子節(jié)點(diǎn)指針

    /**//* 構(gòu)造函數(shù) */
    trie_node() : terminable(false), node(0) { memset(child, 0, sizeof(child)); }
};

/**//* trie */
template <int Size, typename Index> //Size為字符表的大小，Index為字符表的哈希函數(shù)
class trie {
public:
    /**//* 定義類型別名 */
    typedef trie_node<Size> node_type;
    typedef trie_node<Size>* link_type;

    /**//* 構(gòu)造函數(shù) */
    trie(Index i = Index()) : index(i) {}

    /**//* 析構(gòu)函數(shù) */
    ~trie() { clear(); }

    /**//* 清空 */
    void clear() {
        clear_node(root);
        for (int i = 0; i < Size; ++i) root.child[i] = 0;
    }

    /**//* 插入字符串 */
    template <typename Iterator>
    void insert(Iterator begin, Iterator end) {
        link_type cur = &root; //當(dāng)前節(jié)點(diǎn)設(shè)置為根節(jié)點(diǎn)
        for (; begin != end; ++begin) {
            if (!cur->child[index[*begin]]) { //若當(dāng)前字符找不到匹配，則新建節(jié)點(diǎn)
                cur->child[index[*begin]] = new node_type;
                ++cur->node; //當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)加一
            }
            cur = cur->child[index[*begin]]; //將當(dāng)前節(jié)點(diǎn)設(shè)置為當(dāng)前字符對(duì)應(yīng)的子節(jié)點(diǎn)
        }
        cur->terminable = true; //設(shè)置存放最后一個(gè)字符的節(jié)點(diǎn)的可終止標(biāo)志為真
    }

    /**//* 插入字符串，針對(duì)C風(fēng)格字符串的重載版本 */
    void insert(const char *str) { insert(str, str + strlen(str)); }

    /**//* 查找字符串，算法和插入類似 */
    template <typename Iterator>
    bool find(Iterator begin, Iterator end) {
        link_type cur = &root;
        for (; begin != end; ++begin) {
            if (!cur->child[index[*begin]]) return false;
            cur = cur->child[index[*begin]];
        }
        return cur->terminable;
    }

    /**//* 查找字符串，針對(duì)C風(fēng)格字符串的重載版本 */
    bool find(const char *str) { return find(str, str + strlen(str)); }

    /**//* 刪除字符串 */
    template <typename Iterator>
    bool erase(Iterator begin, Iterator end) {
        bool result; //用于存放搜索結(jié)果
        erase_node(begin, end, root, result);
        return result;
    }

    /**//* 刪除字符串，針對(duì)C風(fēng)格字符串的重載版本 */
    bool erase(char *str) {    return erase(str, str + strlen(str)); }

    /**//* 按字典序遍歷單詞樹(shù) */
    template <typename Functor>
    void traverse(Functor &execute = Functor()) {
        visit_node(root, execute);
    }

private:
    /**//* 訪問(wèn)某結(jié)點(diǎn)及其子結(jié)點(diǎn) */
    template <typename Functor>
    void visit_node(node_type cur, Functor &execute) {
        execute(cur);
        for (int i = 0; i < Size; ++i) {
            if (cur.child[i] == 0) continue;
            visit_node(*cur.child[i], execute);
        }
    }
    /**//* 清除某個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn) */
    void clear_node(node_type cur) {
        for (int i = 0; i < Size; ++i) {
            if (cur.child[i] == 0) continue;
            clear_node(*cur.child[i]);
            delete cur.child[i];
            cur.child[i] = 0;
            if (--cur.node == 0) break;
        }
    }

    /**//* 邊搜索邊刪除冗余節(jié)點(diǎn)
       返回值用于向其父節(jié)點(diǎn)聲明是否該刪除該節(jié)點(diǎn) */
    template <typename Iterator>
    bool erase_node(Iterator begin, Iterator end, node_type &cur, bool &result) {
        if (begin == end) { //當(dāng)?shù)竭_(dá)字符串結(jié)尾：遞歸的終止條件
            result = cur.terminable; //如果當(dāng)前節(jié)點(diǎn)可以作為終止字符，那么結(jié)果為真
            cur.terminable = false; //設(shè)置該節(jié)點(diǎn)為不可作為終止字符，即刪除該字符串
            return cur.node == 0; //若該節(jié)點(diǎn)為樹(shù)葉，那么通知其父節(jié)點(diǎn)刪除它
        }
        if (cur.child[index[*begin]] == 0) return result = false; //當(dāng)無(wú)法匹配當(dāng)前字符時(shí)，將結(jié)果設(shè)為假并返回假，
                                                                  //即通知其父節(jié)點(diǎn)不要?jiǎng)h除它
        else if (erase_node(++begin--, end, *(cur.child[index[*begin]]), result)) { //判斷是否應(yīng)該刪除該子節(jié)點(diǎn)
            delete cur.child[index[*begin]]; //刪除該子節(jié)點(diǎn)
            cur.child[index[*begin]] = 0; //子節(jié)點(diǎn)數(shù)減一
            if (--cur.node == 0 && cur.terminable == false) return true; //若當(dāng)前節(jié)點(diǎn)為樹(shù)葉，那么通知其父節(jié)點(diǎn)刪除它
        }
        return false; //其他情況都返回假
    }

    /**//* 根節(jié)點(diǎn) */
    node_type root;

    /**//* 將字符轉(zhuǎn)換為索引的轉(zhuǎn)換表或函數(shù)對(duì)象 */
    Index index;
};

l  參考資料