成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

簡(jiǎn)單字典樹(shù)實(shí)現(xiàn)

MonoLog / 869人閱讀

摘要：查找操作查詢指定單詞是否在字典樹(shù)中。將單詞標(biāo)記為當(dāng)前單詞，將根節(jié)點(diǎn)標(biāo)記為當(dāng)前節(jié)點(diǎn)，執(zhí)行操作當(dāng)前單詞為空，那么返回，即字典樹(shù)中存在該單詞。字典樹(shù)的簡(jiǎn)單實(shí)現(xiàn)插入操作查找操作刪除操作具體實(shí)現(xiàn)放在上，可以在這里找到。

原文地址

字典樹(shù)介紹

我們經(jīng)常會(huì)在網(wǎng)上輸入一些單詞，一般情況下，當(dāng)我們輸入幾個(gè)字母時(shí)，輸入框中會(huì)自動(dòng)彈出以這些字母開(kāi)頭的單詞供我們選擇，用戶體驗(yàn)非常好。

不過(guò)這種自動(dòng)提示功能到底是怎么實(shí)現(xiàn)的呢？這就要用到我們的前綴樹(shù)了，前綴樹(shù)也叫字典樹(shù)、Trie樹(shù)。假如我們有一個(gè)簡(jiǎn)單的字典，里面包含以下幾個(gè)單詞：apps apple cook cookie cold，那么可以構(gòu)建以下樹(shù)：


圖1. 簡(jiǎn)單的字典樹(shù)

當(dāng)我們輸入a時(shí)，程序會(huì)遍歷a的子樹(shù)，找出所有的單詞，這里就是apps和apple了。繼續(xù)輸入ppl，那么只用遍歷appl下面的子樹(shù)，然后即得到apple。同理，輸入co時(shí)，會(huì)遍歷o下面的子樹(shù)，取得單詞cook, cookie, cold。這里的單詞不一定都在葉節(jié)點(diǎn)上，像上例中的cook就是在其中一個(gè)子節(jié)點(diǎn)上。

從上面的圖中，我們可以總結(jié)出字典樹(shù)的一些特征來(lái)：

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

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

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

字典樹(shù)的基本操作

字典樹(shù)有三個(gè)基本操作：插入，查找，刪除：

插入操作：向字典樹(shù)中插入某個(gè)單詞。將單詞標(biāo)記為當(dāng)前單詞，將根節(jié)點(diǎn)標(biāo)記為當(dāng)前節(jié)點(diǎn)，執(zhí)行操作1：

當(dāng)前單詞為空，將當(dāng)前節(jié)點(diǎn)標(biāo)記為單詞位置，終止操作；否則取出當(dāng)前單詞的首字符記為X，遍歷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)：如果X存在于子節(jié)點(diǎn)N，將剩余字符標(biāo)記為當(dāng)前單詞，將N標(biāo)記為當(dāng)前節(jié)點(diǎn)，重復(fù)操作1，如果X不存在于當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)中，那么進(jìn)入操作2。

取出當(dāng)前單詞的首字符記為X，新建一個(gè)節(jié)點(diǎn)M存儲(chǔ)X，M的父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。剩余字符串記為當(dāng)前單詞，如果當(dāng)前單詞為空，將M標(biāo)記為單詞位置，終止操作；否則，將M標(biāo)記為當(dāng)前節(jié)點(diǎn)，重復(fù)操作2。

查找操作：查詢指定單詞是否在字典樹(shù)中。將單詞標(biāo)記為當(dāng)前單詞，將根節(jié)點(diǎn)標(biāo)記為當(dāng)前節(jié)點(diǎn)，執(zhí)行操作1：

當(dāng)前單詞為空，那么返回true，即字典樹(shù)中存在該單詞。否則，取出當(dāng)前單詞的首字符，標(biāo)記為X，遍歷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)，如果X存在于子節(jié)點(diǎn)N中，將N標(biāo)記為當(dāng)前節(jié)點(diǎn)，將剩余字符串標(biāo)記為當(dāng)前單詞，重復(fù)操作1；如果X不存在于子節(jié)點(diǎn)中，返回false，即字典樹(shù)中不存在該單詞。

刪除操作：刪除字典樹(shù)中的某個(gè)單詞。將單詞標(biāo)記為當(dāng)前單詞，將根節(jié)點(diǎn)標(biāo)記為當(dāng)前節(jié)點(diǎn)，執(zhí)行操作1：

當(dāng)前單詞為空，如果當(dāng)前節(jié)點(diǎn)不為葉子節(jié)點(diǎn)，那么取消標(biāo)記當(dāng)前節(jié)點(diǎn)為單詞位置，當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，刪除該葉子節(jié)點(diǎn)即可，然后終止操作。當(dāng)前單詞不為空，取出當(dāng)前單詞的首字符記為X，遍歷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)：如果X存在于當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)N上，將N標(biāo)記為當(dāng)前節(jié)點(diǎn)，將剩余字符串記為當(dāng)前單詞，重復(fù)過(guò)程1；否則刪除失敗，即單詞不在字典樹(shù)上，終止操作。

字典樹(shù)的簡(jiǎn)單實(shí)現(xiàn)

插入操作：

def insert(word):
    current_word = word
    current_node = root
    insert_operation_1(current_word, current_node)

def insert_operation_1(current_word, current_node):
    if current_word not empty:
        X = current_word[0]

        if X in current_node.child:
            current_word = current_word[1:]
            current_node = child_node
            insert_operation_1(current_word, current_node)
        else:
            insert_operation_2(current_word, current_node)

    else:
        mark current_node insert_node 

def insert_operation_2(current_word, current_node):
    X = current_word[0]
    M.value = x
    M.father = current_node
    current_node.child = M

    current_word = current_word[1:]
    if current_word not empty:
        current_node = M
        insert_operation_2(current_word, current_node)

    else:
        mark M insert_node

查找操作：

def find(word):
    current_word = word
    current_node = root
    return find_opration(current_word, current_node)

def find_opration(current_word, current_node):
    if current_word not empty:
        X = current_word[0]
        if X in current_node.child_node:
            current_word = current_word[1:]
            current_node = child_node
            if current_word not empty:
                return find_opration(current_word, current_node)
            else:
                return current_node.isword
        else:
            return false
    else:
        return true

刪除操作：

def delete(word):
    current_word = word
    current_node = root
    return delete_operation(current_word, current_node)

def delete_operation(current_word, current_node):
    if current_word not empty:
        X = current_word[0]
        if X in current_node.child_node:
            current_word = current_word[1:]
            current_node = child_node
            is_deleted = delete_operation(current_word, current_node)
        else:
            return false
    else:
        if current_node have child_node:
            mark current_node no_word_node
        else:
            delete current_node
        return true

具體實(shí)現(xiàn)放在gist上，可以在這里找到。

參考

6天通吃樹(shù)結(jié)構(gòu)—— 第五天 Trie樹(shù)
從Trie樹(shù)（字典樹(shù)）談到后綴樹(shù)
數(shù)據(jù)結(jié)構(gòu)之Trie樹(shù)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/45284.html

相關(guān)文章

  • 大展身手的字典樹(shù)

    摘要：原文地址在簡(jiǎn)單字典樹(shù)的實(shí)現(xiàn)一文中，我們以單詞輸入自動(dòng)提示為引子，簡(jiǎn)單介紹了字典樹(shù)的實(shí)現(xiàn)。前綴匹配本文講述前綴匹配的字典樹(shù)實(shí)現(xiàn)方案。在簡(jiǎn)單字典樹(shù)的實(shí)現(xiàn)一文中，我們已經(jīng)實(shí)現(xiàn)了字典樹(shù)的基本操作，這里只需要再加上一個(gè)前綴匹配方法即可。 原文地址 在簡(jiǎn)單字典樹(shù)(Trie)的實(shí)現(xiàn)一文中，我們以單詞輸入自動(dòng)提示為引子，簡(jiǎn)單介紹了字典樹(shù)的實(shí)現(xiàn)。那么，字典樹(shù)到底可以用于哪些場(chǎng)合呢？ 前綴匹配：給定字典...

    Anchorer 評(píng)論0 收藏0

  • Trie樹(shù) php 實(shí)現(xiàn)敏感詞過(guò)濾

    摘要：在樹(shù)中，每個(gè)節(jié)點(diǎn)表示一個(gè)狀態(tài)，每條邊表示一個(gè)字符，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)經(jīng)過(guò)的邊即表示一個(gè)詞條。查找一個(gè)詞條最多耗費(fèi)的時(shí)間只受詞條長(zhǎng)度影響，因此的查找性能是很高的，跟哈希算法的性能相當(dāng)。 Last-Modified: 2019年5月10日15:25:35 參考文章 c++ 使用map實(shí)現(xiàn)Trie樹(shù) 關(guān)鍵詞過(guò)濾擴(kuò)展，用于檢查一段文本中是否出現(xiàn)敏感詞，基于Double-Array Trie...

    王笑朝 評(píng)論0 收藏0

  • 一種字典樹(shù)結(jié)構(gòu)的高效實(shí)現(xiàn)

    摘要：另一種高效實(shí)現(xiàn)下面介紹另一種實(shí)現(xiàn)，它將字典樹(shù)用數(shù)組存儲(chǔ)起來(lái)，不僅壓縮了數(shù)組，而且不降低查找效率。這就是雙數(shù)組字典樹(shù)。 字典樹(shù)的心得體會(huì) 常見(jiàn)的字典樹(shù)實(shí)現(xiàn)方法 class Node{ uint node ; uint[] next; }; 或者類似如下結(jié)構(gòu) class Node{ uint node; map n...

    kycool 評(píng)論0 收藏0

  • 準(zhǔn)備下次編程面試前你應(yīng)該知道的數(shù)據(jù)結(jié)構(gòu)

    摘要：以下內(nèi)容編譯自他的這篇準(zhǔn)備下次編程面試前你應(yīng)該知道的數(shù)據(jù)結(jié)構(gòu)瑞典計(jì)算機(jī)科學(xué)家在年寫(xiě)了一本書(shū)，叫作算法數(shù)據(jù)結(jié)構(gòu)程序。 國(guó)外 IT 教育學(xué)院 Educative.io 創(chuàng)始人 Fahim ul Haq 寫(xiě)過(guò)一篇過(guò)萬(wàn)贊的文章《The top data structures you should know for your next coding interview》,總結(jié)了程序員面試中需要掌...

    desdik 評(píng)論0 收藏0

  • 準(zhǔn)備下次編程面試前你應(yīng)該知道的數(shù)據(jù)結(jié)構(gòu)

    摘要：以下內(nèi)容編譯自他的這篇準(zhǔn)備下次編程面試前你應(yīng)該知道的數(shù)據(jù)結(jié)構(gòu)瑞典計(jì)算機(jī)科學(xué)家在年寫(xiě)了一本書(shū)，叫作算法數(shù)據(jù)結(jié)構(gòu)程序。 國(guó)外 IT 教育學(xué)院 Educative.io 創(chuàng)始人 Fahim ul Haq 寫(xiě)過(guò)一篇過(guò)萬(wàn)贊的文章《The top data structures you should know for your next coding interview》,總結(jié)了程序員面試中需要掌...

    chadLi 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<