<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    posts - 134,comments - 22,trackbacks - 0
     簡介

    Trie又稱單詞查找樹、前綴樹,是 簡介

    Trie又稱單詞查找樹、前綴樹,是一種哈希樹的變種。應用于字符串的統計與排序,經常被搜索引擎系統用于文本詞頻統計。

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

    性質

    根節點不包含字符,除根節點外的每一個節點都只包含一個字符。

    從根節點到某一節點,路徑上經過的字符連接起來,為該節點對應的字符串。

    每個節點的所有子節點包含的字符都不相同。

    優點

    查詢快。對于長度為m的鍵值,最壞情況下只需花費O(m)的時間;而BST最壞情況下需要O(m log n)的時間。

    當存儲大量字符串時,Trie耗費的空間較少。因為鍵值并非顯式存儲的,而是與其他鍵值共享子串。

    Trie適用于“最長前綴匹配”。

    操作

    初始化或清空

    遍歷Trie,刪除所有節點,只保留根節點。

    插入字符串

    1.     設置當前節點根節點,設置當前字符為插入字符串中的首個字符;

    2.     當前節點的子節點上搜索當前字符,若存在,則將當前節點設為值為當前字符的子節點;否則新建一個值為當前字符的子節點,并將當前結點設置為新創建的節點。.

    3.     當前字符設置為串中的下個字符,若當前字符0,則結束;否則轉2.

    查找字符串

    搜索過程與插入操作類似,當字符找不到匹配時返回假;若全部字符都存在匹配,判斷最終停留的節點是否為樹葉,若是,則返回真,否則返回假。

    刪除字符串

    首先查找該字符串,邊查詢邊將經過的節點壓棧,若找不到,則返回假;否則依次判斷棧頂節點是否為樹葉,若是則刪除該節點,否則返回真。

    實現
    對于字符表大小為S的字符串集,需建立一個S叉樹來代表這些字符串的集合。

    l  代碼


    /** 版權所有 (C) 2009 喻揚 中山大學
    /* 本程序只作學習用途,未經許可,不得用于任何商業目的。
    */

    #include <string.h>

    /* trie的節點類型 */
    template <int Size> //Size為字符表的大小
    struct trie_node {
        
    /* 數據成員 */
        
    bool terminable; //當前節點是否可以作為字符串的結尾
        int node; //子節點的個數
        trie_node *child[Size]; //指向子節點指針

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

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

        
    /* 構造函數 */
        trie(Index i 
    = Index()) : index(i) {}

        
    /* 析構函數 */
        
    ~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; //當前節點設置為根節點
            for (; begin != end; ++begin) {
                
    if (!cur->child[index[*begin]]) //若當前字符找不到匹配,則新建節點
                    cur->child[index[*begin]] = new node_type;
                    
    ++cur->node; //當前節點的子節點數加一
                }

                cur 
    = cur->child[index[*begin]]; //將當前節點設置為當前字符對應的子節點
            }

            cur
    ->terminable = true//設置存放最后一個字符的節點的可終止標志為真
        }


        
    /* 插入字符串,針對C風格字符串的重載版本 */
        
    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;
        }


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

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


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

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


    private:
        
    /* 訪問某結點及其子結點 */
        template 
    <typename Functor>
        
    void visit_node(node_type cur, Functor &execute) {
            execute(cur);
            
    for (int i = 0; i < Size; ++i) {
                
    if (cur.child[i] == 0continue;
                visit_node(
    *cur.child[i], execute);
            }

        }

        
    /* 清除某個節點的所有子節點 */
        
    void clear_node(node_type cur) {
            
    for (int i = 0; i < Size; ++i) {
                
    if (cur.child[i] == 0continue;
                clear_node(
    *cur.child[i]);
                delete cur.child[i];
                cur.child[i] 
    = 0;
                
    if (--cur.node == 0break;
            }

        }


        
    /* 邊搜索邊刪除冗余節點
           返回值用于向其父節點聲明是否該刪除該節點 
    */

        template 
    <typename Iterator>
        
    bool erase_node(Iterator begin, Iterator end, node_type &cur, bool &result) {
            
    if (begin == end) //當到達字符串結尾:遞歸的終止條件
                result = cur.terminable; //如果當前節點可以作為終止字符,那么結果為真
                cur.terminable = false//設置該節點為不可作為終止字符,即刪除該字符串
                return cur.node == 0//若該節點為樹葉,那么通知其父節點刪除它
            }

            
    if (cur.child[index[*begin]] == 0return result = false//當無法匹配當前字符時,將結果設為假并返回假,
                                                                      
    //即通知其父節點不要刪除它
            else if (erase_node(++begin--, end, *(cur.child[index[*begin]]), result)) //判斷是否應該刪除該子節點
                delete cur.child[index[*begin]]; //刪除該子節點
                cur.child[index[*begin]] = 0//子節點數減一
                if (--cur.node == 0 && cur.terminable == falsereturn true//若當前節點為樹葉,那么通知其父節點刪除它
            }

            
    return false//其他情況都返回假
        }


        
    /* 根節點 */
        node_type root;

        
    /* 將字符轉換為索引的轉換表或函數對象 */
        Index index;
    }
    ;


    l  參考資料

    英文維基 http://en.wikipedia.org/wiki/Trie

    中文維基 http://zh.wikipedia.org/w/index.php?title=Trie&variant=zh-cn

    一種哈希樹的變種。應用于字符串的統計與排序,經常被搜索引擎系統用于文本詞頻統計。

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

    性質

    根節點不包含字符,除根節點外的每一個節點都只包含一個字符。

    從根節點到某一節點,路徑上經過的字符連接起來,為該節點對應的字符串。

    每個節點的所有子節點包含的字符都不相同。

    優點

    查詢快。對于長度為m的鍵值,最壞情況下只需花費O(m)的時間;而BST最壞情況下需要O(m log n)的時間。

    當存儲大量字符串時,Trie耗費的空間較少。因為鍵值并非顯式存儲的,而是與其他鍵值共享子串。

    Trie適用于“最長前綴匹配”。

    操作

    初始化或清空

    遍歷Trie,刪除所有節點,只保留根節點。

    插入字符串

    1.     設置當前節點根節點,設置當前字符為插入字符串中的首個字符;

    2.     當前節點的子節點上搜索當前字符,若存在,則將當前節點設為值為當前字符的子節點;否則新建一個值為當前字符的子節點,并將當前結點設置為新創建的節點。.

    3.     當前字符設置為串中的下個字符,若當前字符0,則結束;否則轉2.

    查找字符串

    搜索過程與插入操作類似,當字符找不到匹配時返回假;若全部字符都存在匹配,判斷最終停留的節點是否為樹葉,若是,則返回真,否則返回假。

    刪除字符串

    首先查找該字符串,邊查詢邊將經過的節點壓棧,若找不到,則返回假;否則依次判斷棧頂節點是否為樹葉,若是則刪除該節點,否則返回真。

    實現
    對于字符表大小為S的字符串集,需建立一個S叉樹來代表這些字符串的集合。

    l  代碼


    /** 版權所有 (C) 2009 喻揚 中山大學
    /* 本程序只作學習用途,未經許可,不得用于任何商業目的。
    */

    #include <string.h>

    /* trie的節點類型 */
    template <int Size> //Size為字符表的大小
    struct trie_node {
        
    /* 數據成員 */
        
    bool terminable; //當前節點是否可以作為字符串的結尾
        int node; //子節點的個數
        trie_node *child[Size]; //指向子節點指針

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

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

        
    /* 構造函數 */
        trie(Index i 
    = Index()) : index(i) {}

        
    /* 析構函數 */
        
    ~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; //當前節點設置為根節點
            for (; begin != end; ++begin) {
                
    if (!cur->child[index[*begin]]) //若當前字符找不到匹配,則新建節點
                    cur->child[index[*begin]] = new node_type;
                    
    ++cur->node; //當前節點的子節點數加一
                }

                cur 
    = cur->child[index[*begin]]; //將當前節點設置為當前字符對應的子節點
            }

            cur
    ->terminable = true//設置存放最后一個字符的節點的可終止標志為真
        }


        
    /* 插入字符串,針對C風格字符串的重載版本 */
        
    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;
        }


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

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


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

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


    private:
        
    /* 訪問某結點及其子結點 */
        template 
    <typename Functor>
        
    void visit_node(node_type cur, Functor &execute) {
            execute(cur);
            
    for (int i = 0; i < Size; ++i) {
                
    if (cur.child[i] == 0continue;
                visit_node(
    *cur.child[i], execute);
            }

        }

        
    /* 清除某個節點的所有子節點 */
        
    void clear_node(node_type cur) {
            
    for (int i = 0; i < Size; ++i) {
                
    if (cur.child[i] == 0continue;
                clear_node(
    *cur.child[i]);
                delete cur.child[i];
                cur.child[i] 
    = 0;
                
    if (--cur.node == 0break;
            }

        }


        
    /* 邊搜索邊刪除冗余節點
           返回值用于向其父節點聲明是否該刪除該節點 
    */

        template 
    <typename Iterator>
        
    bool erase_node(Iterator begin, Iterator end, node_type &cur, bool &result) {
            
    if (begin == end) //當到達字符串結尾:遞歸的終止條件
                result = cur.terminable; //如果當前節點可以作為終止字符,那么結果為真
                cur.terminable = false//設置該節點為不可作為終止字符,即刪除該字符串
                return cur.node == 0//若該節點為樹葉,那么通知其父節點刪除它
            }

            
    if (cur.child[index[*begin]] == 0return result = false//當無法匹配當前字符時,將結果設為假并返回假,
                                                                      
    //即通知其父節點不要刪除它
            else if (erase_node(++begin--, end, *(cur.child[index[*begin]]), result)) //判斷是否應該刪除該子節點
                delete cur.child[index[*begin]]; //刪除該子節點
                cur.child[index[*begin]] = 0//子節點數減一
                if (--cur.node == 0 && cur.terminable == falsereturn true//若當前節點為樹葉,那么通知其父節點刪除它
            }

            
    return false//其他情況都返回假
        }


        
    /* 根節點 */
        node_type root;

        
    /* 將字符轉換為索引的轉換表或函數對象 */
        Index index;
    }
    ;


    l  參考資料

    英文維基 http://en.wikipedia.org/wiki/Trie

    中文維基 http://zh.wikipedia.org/w/index.php?title=Trie&variant=zh-cn

    posted on 2010-05-02 11:35 何克勤 閱讀(1040) 評論(0)  編輯  收藏 所屬分類: Algorithm and Data Structure
    主站蜘蛛池模板: 国产午夜亚洲不卡| 亚美影视免费在线观看| 亚洲成人精品久久| 免费在线观看黄网| 日韩精品无码区免费专区 | 日韩在线天堂免费观看| 三年片在线观看免费大全电影| 免费国产草莓视频在线观看黄| 亚洲日本va在线观看| 无码乱人伦一区二区亚洲一| 亚洲人午夜射精精品日韩| 免费观看一级毛片| 18勿入网站免费永久| 久久一区二区三区免费播放| 中文字幕乱码系列免费| www在线观看播放免费视频日本| 老司机亚洲精品影院在线观看| 亚洲情A成黄在线观看动漫软件 | 在线看片免费人成视久网| 韩日电影在线播放免费版| 黄色毛片视频免费| 男男gvh肉在线观看免费| 亚洲乱妇熟女爽到高潮的片 | 成人黄色免费网址| 99在线免费观看视频| 污视频在线观看免费| 免费视频一区二区| 久久免费公开视频| 99精品视频免费观看| 日本免费大黄在线观看| 91精品免费不卡在线观看| 99re在线视频免费观看| 99re热精品视频国产免费| 精品免费久久久久久久| 日韩精品免费一级视频| 免费三级毛片电影片| 女人18毛片水真多免费播放 | 人妻免费久久久久久久了| 日韩在线视频线视频免费网站| 一道本不卡免费视频| 久久国产免费直播|