• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆 - 6, 文章 - 0, 評(píng)論 - 24, 引用 - 0
            數(shù)據(jù)加載中……

            Trie—單詞查找樹

             

            Trie—單詞查找樹

            l  簡(jiǎn)介

            Trie又稱單詞查找樹、前綴樹,是一種哈希樹的變種。應(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)過的字符連接起來,為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。

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

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

            n  查詢快。對(duì)于長度為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適用于“最長前綴匹配”。

            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  查找字符串

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

            n  刪除字符串

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

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

            l  代碼

            trie.h


            l  參考資料

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

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

            posted on 2009-03-27 23:51 yuyang7 閱讀(5299) 評(píng)論(5)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)

            評(píng)論

            # re: Trie—單詞查找樹  回復(fù)  更多評(píng)論   

            好,不錯(cuò),呵呵
            2009-03-28 15:55 | 中國福利彩票

            # re: Trie—單詞查找樹  回復(fù)  更多評(píng)論   

            如果想在磁盤上存儲(chǔ)Trie可以嘛?也許用數(shù)組實(shí)現(xiàn)?
            比如說詞典的應(yīng)用。用只讀的Trie存儲(chǔ)詞典索引,每個(gè)節(jié)點(diǎn)保存數(shù)據(jù)文件的文件偏移量。要求可以直接從磁盤上用file mapping使用詞典索引。
            2009-03-28 22:27 | lxu

            # re: Trie—單詞查找樹  回復(fù)  更多評(píng)論   

            @lxu
            嗯,構(gòu)造雙數(shù)組trie (Double-Array Trie)。
            2009-03-28 23:26 | yuyang7

            # re: Trie—單詞查找樹  回復(fù)  更多評(píng)論   

            謝謝,學(xué)到東西了。
            不過覺得博主的代碼可以優(yōu)化下,重復(fù)代碼的地方太多。

            比如說insert的C風(fēng)格部分,我覺得可以改成,

            void insert(const char* str)
            {
            int size = strlen(str);
            insert<char*>(str, str + size);
            }
            ====================================
            這樣子可以減少重復(fù)代碼的部分,而且也方便以后修改嘛。

            另外,貌似memset(child, 0, sizeof(child))應(yīng)該改成memset(child, 0, size * sizeof(child))
            2009-03-31 00:04 | 黃宇

            # re: Trie—單詞查找樹[未登錄]  回復(fù)  更多評(píng)論   

            同意樓上的第一點(diǎn)意見,實(shí)際上我是先實(shí)現(xiàn)了針對(duì)C風(fēng)格字符串的函數(shù),后來覺得有需要對(duì)一段區(qū)間內(nèi)的字符進(jìn)行查找,才添加了針對(duì)迭代器的函數(shù),造成了代碼冗余.
            第二點(diǎn)意見我并不認(rèn)同,可能樓上理解偏差了.可能樓上是想說 memset(child, 0, size * sizeof(tree_node<size>*)  的吧.
            2009-03-31 11:32 | yuyang7

            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            99久久精品国产一区二区| 久久精品国产亚洲av麻豆小说 | 热综合一本伊人久久精品| 久久久久久久久久久精品尤物 | 国产精品va久久久久久久| 国产一区二区久久久| 精品久久久久中文字幕日本| 国产精品日韩深夜福利久久| 久久精品国产亚洲αv忘忧草| 色综合久久88色综合天天| 国产精品亚洲综合久久| 国产L精品国产亚洲区久久| 伊人久久精品无码二区麻豆| 丰满少妇人妻久久久久久4| 亚洲国产一成人久久精品 | 久久免费小视频| 亚洲人成电影网站久久| 久久综合久久综合九色| 久久精品国产亚洲AV香蕉| 91精品国产高清久久久久久91| 狠狠色婷婷久久综合频道日韩| 国产高清美女一级a毛片久久w| 久久综合综合久久综合| 亚洲а∨天堂久久精品| 国产成人精品久久亚洲高清不卡 | 亚洲精品无码久久久久AV麻豆| 国产亚洲欧美成人久久片| 国产激情久久久久久熟女老人| 精品99久久aaa一级毛片| 久久精品国产久精国产思思| 亚洲欧美日韩精品久久亚洲区| 超级碰久久免费公开视频| 国产亚洲欧美精品久久久| 久久精品国产亚洲av麻豆图片| 老司机午夜网站国内精品久久久久久久久| 97久久超碰成人精品网站| 亚洲va久久久噜噜噜久久天堂| 2019久久久高清456| 人妻中文久久久久| 精品久久人人做人人爽综合| 麻豆精品久久精品色综合|