1、 Thesis for National Training Team of China, IOI2009淺析字母樹在信息學競賽中的應用浙江省紹興市第一中學董華星二八年十二月Huaxing DONG Shaoxing One Senior High School in Zhejiang Province 12 of 21目錄 摘要3 關鍵字3 前言3 正文41. 預備知識41.1. 試題分析41.2. 結(jié)構簡介52. 字母樹在串的快速檢索中的應用73. 字母樹在“串”排序方面的應用94. 字母樹在減少無效轉(zhuǎn)移方面的應用115. 字母樹在最長公共前綴問題的應用135.1. 串的最長公共前綴問題13

2、5.2. 數(shù)字相關的公共前綴問題146. 拓展思考166.1. 字母樹應用的擴展166.2. 字母樹的局限167. 總結(jié)17 參考文獻17 附錄181. 單詞查找樹182. 感謝. 20 感謝21摘要字母樹（又叫單詞查找樹、Trie 樹，Trie Tree），構造簡單，并能很好地處理和“串”相關的檢索（Retrieva l）問題。本文從此著手，歸納了筆者的學習經(jīng)驗 ， 詳細論述了其在快速查找、排序、優(yōu)化轉(zhuǎn)移等方面的常見應用，并對其擴展做了提示。 關鍵字字母樹 快速檢索 “串”排序 無效轉(zhuǎn)移 最長公共前綴問題 前言當我們走進圖書館的閱覽室尋找書時，會不由自主地根據(jù)書架上的分類標簽尋找自己所喜好的

3、書籍；當打開電腦中的資源管理器時，我們會看到一層一層的目錄結(jié)構。它們的存在，方便了我們生活中的一個重要的問題檢索。 在信息學競賽（ Olympiad in Informatics ，簡稱 OI）的學習過程中，我們也經(jīng)常會遇到關于“檢索”的問題。而通常采用的不借助任何數(shù)據(jù)結(jié)構 （Data Structure）的的枚舉方法，雖然簡單易寫， 但往往存在著效率低下的弊端。那我們?nèi)绾尾拍芡ㄟ^簡單的途徑提高算法中的檢索效率？ 圖一 資源管理器 接下來筆者將淺析并推薦一種數(shù)據(jù)結(jié)構字母樹，借助它我們便能夠很好地處理與“串”相關的檢索問題。 正文1. 預備知識為了更深入地讓讀者了解這種數(shù)據(jù)結(jié)構，本文首先將對其進

4、行一番具體介紹并說明其構造。 1.1. 試題分析例一 單詞查找樹1我們需要將一個確定的單詞列表建出一棵單詞查找樹，滿足 1. 根結(jié)點不包含字母，除根結(jié)點外的每個都僅含一個大寫英文字母； 2. 從根結(jié)點到某一結(jié)點，路徑上經(jīng)過的字母依次連起來所構成的字母序列，稱為該結(jié)點對應的單詞。單詞列表中的每個詞，都是該單詞查找樹某個結(jié)點所對應的單詞； 3. 在滿足上述條件下，該單詞查找樹的結(jié)點數(shù)最少。統(tǒng)計出該單詞查找樹的結(jié)點數(shù)目。 輸入格式若干行單詞，描述單詞列表。輸出格式一個數(shù)字，表示結(jié)點數(shù)目。樣例輸入A AN ASP AS ASCASCII1 第十七屆全國青少年信息學奧林匹克競賽（NOI2000）二試試題

5、 RootABSNAPCSIIICBASBASIC樣例輸出13解析題目對這種數(shù)據(jù)結(jié)構的限制內(nèi)容較多，又要滿足“該單詞查找樹的結(jié)點數(shù)最少”，故貪心即可。即，對于樹中的每個結(jié)點，它的包含相同字母的所有兒子都應當合并在一起。按照以上所有條件模擬出這棵樹，統(tǒng)計一下其結(jié)點個數(shù)即可。 圖二 樣例示意 1.2. 結(jié)構簡介其實，上題所提的這種數(shù)據(jù)結(jié)構便是本文要講的“字母樹”。既然叫做“字母樹”，顧名思義，那一定是一種樹形結(jié)構。而且它還是一棵有根樹（Root ed Tree）。其結(jié)構特點與上題描述及解析基本一致，其中： ROOTionlfyomrpmieaac rtdiocns圖三 字母樹 1. 根節(jié)點不包含任

6、何字母，而除它以外的每個結(jié)點都僅包含一個字母（事實上也可以將一個數(shù)字看成字母來建字母樹）； 2. 從根結(jié)點到某個結(jié)點，路徑上經(jīng)過的字母依次連接起來所構成的字母序列，稱為該結(jié)點對應的單詞。單詞列表中的每個詞，都是該字母樹某個結(jié)點所對應的單詞； 3. 每個結(jié)點的所有兒子包含的字母各不相同。 單詞列表為“inform”、“informer ”、“information”、“informatics ”、“olympic ” 以及“olympiad ”對應的字母樹可以是如圖三所示。例如，保存“informer ” 和“information”時，由于它們的前六個字母是相同的，所以希望它們共享這些字母，而

7、只對剩下的部分進行分開存儲?？梢院苊黠@地發(fā)現(xiàn)，字母樹很好地利用了串的公共前綴，節(jié)約了存儲空間2。 字母樹的插入（Insert）、刪除（ Delete）和查找（Find）都非常簡單，用一個一重循環(huán)即可，即第 i 次循環(huán)找到前 i 個字母所對應的子樹，然后進行相應的操作。實現(xiàn)這棵字母樹，我們用最常見的數(shù)組保存即可，當然也可以開動態(tài)的指針類型。至于結(jié)點對兒子的指向，一般有三種方法： 1. 對每個結(jié)點開一個字母集大小的數(shù)組，對應的下標是兒子所表示的字母，內(nèi)容則是這個兒子對應在大數(shù)組上的位置，即標號； 2. 對每個結(jié)點掛一個鏈表，按一定順序記錄每個兒子是誰； 3. 使用左兒子右兄弟表示法記錄這棵樹。 三

8、種方法，各有千秋。第一種易實現(xiàn)，但實際的空間要求較大；第二種， 較易實現(xiàn)，空間要求相對較小，但比較費時；第三種，空間要求最小，但相對費時且不易寫。但總的來說，幾種實現(xiàn)方式都是比較簡單的，只要在做題時加以合理選擇即可，本文不再贅述。 從以上介紹可以明顯看出，字母樹是一種簡單的數(shù)據(jù)結(jié)構。 2 這里是指字符串中實際出現(xiàn)的字符的保存量，下同 2. 字母樹在串的快速檢索中的應用字母樹能很好地利用串的公共前綴，節(jié)約了存儲空間。既然字母樹存儲東西的代價少了，那么用它來檢索是否應該有著比較高的效率？下面請看例題。 例二 查找生詞給出 N 個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現(xiàn)的順序

9、寫出所有不在熟詞表中的生詞。 輸入格式第一行，一個數(shù)字 N； 接著 N 行，每行一個熟詞表中的單詞； 接著一行，一篇文章。 輸出格式若干行，每行一個生詞。樣例輸入5one dollar hundred thousand itit costs one thousand one hundred and one yuan.樣例輸出costs and yuan解析本題的解法較多。 一種解法是：先將所有熟詞用一個數(shù)組記錄下來。接著枚舉文章中的每個單詞，對于對應的單詞，枚舉熟詞表，檢查它是否已經(jīng)存在，不存在則輸出并且將 它存到熟詞表的末尾。反復操作即可。這種算法最簡單，也是最容易被人接受的 ， 但時間復雜

10、度明顯較大。 另一種解法是：采用哈希（ Hash）3，對于所有的熟詞先建立映射關系。再枚舉文章中的每個單詞，看看是否已經(jīng)被哈希了，沒有則輸出并為其進行哈希。這種做法也比較常見，若哈希函數(shù)設計得比較好且合理解決哈希沖突，時間復雜度接近讀入復雜度。 既然問題是查找一個單詞是否為熟詞，正好符合字母樹的功能，故又得到了一種解法：對于所有熟詞先建出字母樹，對于所有對應單詞為熟詞的結(jié)點進行標記。接著枚舉所有文章中的單詞，去字母樹中查找一下對應的結(jié)點是否標記，沒有標記 則輸出，順便把這個單詞插入到字母樹中并對相應結(jié)點進行標記。這種做法很好利 用了字母樹的特性，我們采用本文之前提到的第一種存儲方式，時間復雜度

11、僅為 讀入復雜度，且常數(shù)較小。 比較上述三種解法，可以發(fā)現(xiàn)：最直接的做法效率很低；使用哈希，雖然時間復雜度可以接近讀入復雜度，但需要借助良好的哈希函數(shù)；而使用字母樹，由于它的各項操作的時間復雜度均較小，總復雜度可以做到讀入復雜度?？梢院苋菀椎匕l(fā)現(xiàn)字母樹在檢索方面的存在著較大優(yōu)勢。 3 可參考IOI2006 國家集訓隊論文Hash 函數(shù)的設計優(yōu)化，作者李羽修 以及 IOI2007 國家集訓隊論文Hash 在信息學競賽中的一類應用，作者楊弋 3. 字母樹在“串”排序方面的應用既然字母樹在檢索方面的有著較大優(yōu)勢，很自然便讓我們想到拿它來實現(xiàn)字典的索引。翻一翻英語字典，可以發(fā)現(xiàn)所有單詞表中的單詞是按字

12、典序排列的， 我們的字母樹是否可以實現(xiàn)“串”的排序呢？答案是肯定的。 例三 感謝給你 N 個互不相同的僅由一個單詞構成的英文名，讓你將它們按字典序從小到大排序輸出。 輸入格式第一行，一個數(shù)字 N； 接著 N 行，每行一個英文名。輸出格式共 N 行，每行一個英文名，描述排序后的結(jié)果。樣例輸入5Reagan Bush Clinton Bush Obama樣例輸出Bush Bush Clinton Obama Reagan解析對于排序問題，解題者一般首先都會想到那些常用的排序算法選擇排序 （Select ion Sort）、冒泡排序（ Bubble Sort）、歸并排序（ Merge Sort）、快

13、速排序 （Quick Sort）4等。如果用歸并排序來排一些比較小的數(shù)字，因為比較兩個數(shù)字大小的時間復雜度是 O(1)的，所以總復雜度是 O(Nlog 2N)。這里，兩個字符串比較大小，直接比的話，最壞復雜度是 O(|S|)的，因此排序的總復雜度變成了O(N|S|log2N)，雖然我們可以用一些方法對其進行優(yōu)化，但是復雜度還是遠遠大于讀入復雜度。 RootBCORulbesiaahngmtaaon n嘗試著用字母樹進行排序，仍舊采用上文提到的第一種存儲方式對所有字符串建樹，這棵樹的每個結(jié)點的所有兒子也就很顯然地按照其字母大小排序。接著對這棵樹進行先序遍歷（又叫前根遍歷等， Preorder T

14、raversal），每次遍歷到一個對應單詞是實際存在的結(jié)點就輸出這個單詞即可。當然，對于字母樹的每個結(jié)點應該記錄一下對應單詞出現(xiàn)了幾次，避免同一個單詞漏輸出的情況發(fā)生。 用這種做法，所有串被讀入與輸出各一次，遍歷整棵樹的代價是樹的結(jié)點數(shù)乘以常數(shù) 26，因此，其總復雜度是線性的。 圖四 樣例解答 到這里，讀者不難驚喜地發(fā)現(xiàn)字母樹不僅可以做到快速索引，還支持了一種特 殊排序算法“串”排序。而我們知道將數(shù)據(jù)有序化后能為我們帶來更高效的 檢索。 Thesis for National Training Team of China, IOI20094 可參考算法藝術與信息學競賽，作者劉汝佳、黃亮 13

15、of 21Huaxing DONGShaoxing One Senior High School in Zhejiang Province Thesis for National Training Team of China, IOI20094. 字母樹在減少無效轉(zhuǎn)移方面的應用字母樹能夠提供快速的索引功能，極大地方便了解題者對單詞的查找，只要充分利用這一點，它還能夠在遞推（Recursion）中一顯身手。 例四 文章給出有 N 個單詞的字典，和一篇長 L 的沒有標點符號的文章。問這文章有多少種解釋方式。 輸入格式第一行，一個數(shù)字 N； 接下來 N 行，每行一個單詞，描述字典內(nèi)容； 接下來若干字

16、符，描述文章。 輸出格式一個數(shù)字，表示所求答案并對 12345679 取模。樣例輸入5ab cb bc ba aabcba樣例輸出2解析采用遞推解決本題。設 Fi為到文章的第 i 個字母結(jié)束的解釋方式數(shù)。每次枚舉接下來的一個單詞的長度 x，若第 i+1 至 i+x 確為字典中的一個單詞，則增加一個遞推為 Fi+x+=Fi。最后答案即為 FL。那么，此題的復雜度主要在于如何確定一個串為一個單詞。 當然，可以采用逐個且逐位比較的判斷方式，但是總時間復雜度明顯較低， Huaxing DONG Shaoxing One Senior High School in Zhejiang Province 1

17、7 of 21為 O(NL2 ) 。 解題者想到“如何確定一個串為一個單詞”實際是一個匹配問題。于是，可 以考慮用 KMP（Knuth Morris Pratt）算法5對每個字典中的單詞預先在文章中找到所有的匹配位置。這樣，算法總復雜度可以寫成 O(NL)或 O(L2)，而且常數(shù)較大。當然也可以考慮用哈希來處理匹配問題，不過復雜度也并未有所改觀。 此時，讀者應當想到，可以用字母樹來確認一個單詞是否存在。先將所有字典 中的單詞建成字母樹，并對字母樹上相應位置進行標記。接著，依照一開始的做法， 每次先枚舉一個位置 i，再枚舉接下來的一個單詞的長度 x，邊枚舉單詞的長度邊在字母樹上進行查找，如果當前

18、結(jié)點對應的單詞是字典中的，則進行相應的轉(zhuǎn)移。此算法的復雜度為 O(LD)，這里的 D 是字母樹的深度。當 N 和 L 同級別時，乍一看最壞復雜度和之前所提的利用 KMP 算法或哈希相當。但是，我們可以意識到，當枚舉單詞長度 x 時，如果在字母樹上已經(jīng)找不到對應結(jié)點，便可退出對單詞的枚舉，即結(jié)束了當前 i 下對轉(zhuǎn)移的枚舉。這樣，在字母樹本身常數(shù)較小的基礎 上，還有效減少了許多冗余操作，使程序速度再次得到大大提高。 由上述例題可以看到，字母樹提供的快速“檢索”，還能夠在一定程度上減 少一些試題采用遞推、動態(tài)規(guī)劃（Dynamic Programming，簡稱 DP）等算法時的無效轉(zhuǎn)移，加快程序運行速

19、度。 5 可參考Matrix67 博客 2006 年 11 月 29 日志 /blog/archives/1155. 字母樹在最長公共前綴問題的應用本文前面重點論述的是字母樹在檢索方面的功能，但這功能的由來實質(zhì)是利用了它對串的公共前綴的處理。提到“公共前綴”以及“檢索”，讀者不難想到 一個經(jīng)典問題，即串的最長公共前綴（Longest Common Prefix，簡稱 LCP）問題 。字母樹也能夠很好處理該問題。 5.1. 串的最長公共前綴問題例五 串的最長公共前綴給出 N 個小寫英文字母串，以及 Q 個詢問，即詢問某兩個串的最長公共前綴的長度是多少。

20、 輸入格式第一行，兩個數(shù)字 N 和 Q； 接下來 N 行，每行一個字母串； 接下來 Q 行，每行一個兩個數(shù)字，表示對這兩個編號的串進行詢問輸出格式Q 行，每行是對應問題的答案。樣例輸入2 2abc abd 1 11 2樣例輸出32解析本題有多種解法，比如可以用 New LCP6、后綴樹（Suffix Tree）7等。現(xiàn) 6 可參考IOI2006 國家集訓隊作業(yè)New LCP（ 原創(chuàng)），作者陳啟峰 7 可參考IOI2003 國家集訓隊論文尋找最大重復子串，作者林希德 Thesis for National Training Team of China, IOI2009在大致介紹一下字母樹的做法。

21、 同樣，首先對所有的串建立其對應的字母樹。此時發(fā)現(xiàn)，對于兩個串的最長公共前綴的長度即它們所在結(jié)點的公共祖先個數(shù)，于是，問題就轉(zhuǎn)化為了離線（Offline）的最近公共祖先（Least Common Ancestor，簡稱 LCA）問題。 而最近公共祖先問題同樣是一個經(jīng)典問題，可以用下面幾種方法： 1. 利用并查集（Disjoint Set）8 采用經(jīng)典的 Tarjan 算法； 2. 求出字母樹的歐拉序列（Euler Sequence ）后，就可以轉(zhuǎn)為經(jīng)典的最小值查詢（Range Minimum Query，簡稱 RMQ）9問題了； 3. 對于字母樹上的每個結(jié)點，遞推求出其所有向上 2k 后的祖先

22、。查找兩個點的最近公共祖先就可以通過它們同時快速地向上跳躍盡可能大的距離得到了。 5.2. 數(shù)字相關的公共前綴問題通過上述的介紹，可以發(fā)現(xiàn)字母樹可以在最長公共前綴和最近公共祖先之間起到橋梁作用。而對于字符串，研究公共前綴就可以得到上述問題，那對于數(shù)字研究公共前綴是怎么一回事呢？下面再來看一個例題。 例六 近似問題兩個實數(shù)都保留小數(shù)點后相同位數(shù) k 后，兩數(shù)一致，則 k 稱為它們的公共精度。這里，k 不超過兩數(shù)的小數(shù)位數(shù)的最小值。其中，最大的 k 叫做它們的最長公共精度?，F(xiàn)在，有 N 個不足 1 的非負實數(shù)，讓你求出一個數(shù)字 x，使得這個數(shù)和所有數(shù)字的最長公共精度之和最大。 輸入格式第一行，一個

23、整數(shù) N； 接著 N 行，每行一個小數(shù)。 8 可參考算法藝術與信息學競賽，作者劉汝佳、黃亮 9 可參考IOI2007 國家集訓隊論文RMQ 與 LCA 問題，作者郭華陽 Huaxing DONG Shaoxing One Senior High School in Zhejiang Province 21 of 21輸出格式任意一個滿足要求的 x。樣例輸入40.3150.310.3140.3樣例輸出0.315解析本題中的保留小數(shù)是直接保留，并不需要四舍五入，這就為我們的解題帶來了方便。將每個數(shù)字的小數(shù)部分作為一個字符串，用這些串建起一棵字母樹。一個很顯然的結(jié)論是，最后的答案一定是這棵樹上某個結(jié)

24、點對應的單詞。在建樹的時候順便統(tǒng)計出以每個結(jié)點對應單詞為前綴的字符串個數(shù) v。而以某個單詞為我們所求的 x 的最長公共精度和，就是這個單詞經(jīng)過的每個結(jié)點的對應的 v 之和。因此，最后只要遍歷整棵樹，更新一下答案即可。時間復雜度也僅是讀入復雜度。 而對于本題，若采用別的解法，并不能夠簡單快捷并且高效的得到解決。 上題對小數(shù)部分的保留是直接保留。對于保留方式是需要進行四舍五入 的10 ，本文不再介紹，但也是可以使用字母樹進行求解的。這將作為思考留給讀者。 10 POJ 2007 年 11 月月賽第一題 /JudgeOnline/problem?id=3464

25、6. 拓展思考6.1. 字母樹應用的擴展上一節(jié)內(nèi)容的最后一段中說到“字母樹的相關的直接應用”。讀者一定會 想， 既然是“直接”，那一定還有“間接”。不錯，字母樹的應用還遠遠沒有結(jié)束。 在例四的解析中，我們提到“ 如何確定一個串為一個單詞實際是一個匹配問題”。這里，“匹配”就很容易讓我們想到 KMP 算法，而字母樹也可以通過其過硬的檢索功能處理該問題。如果把這兩者結(jié)合起來，會得到什么？相信不少讀者已經(jīng)知道，那就是功能更加強大的一種新的數(shù)據(jù)結(jié)構 AC 自動機（Aho-Corasick Pattern Matching Machine）11。 本文對 AC 自動機不再介紹，讀者可以參看 2006 年

26、國家集訓隊成員王赟 （My Accept Is Going On，即 Maigo ）的論文。 6.2. 字母樹的局限宋代戴復古的寄興中便出有成語“金無足赤，人無完人”。字母樹雖 然存在諸多優(yōu)點，但還是有其一定局限。 由于字母樹所解決的題目，串對應的字符集一般較小，因此由字符集大小帶來的各常數(shù)時間和空間復雜度，我們在實踐中一般將其忽略。 因其良好的時間復雜度和空間復雜度是建立在字符集較小的前提下的。雖然，字母樹的時間和空間復雜度隨著其實現(xiàn)方式可以進行一定的轉(zhuǎn)化，但是，針對處理的字符集較大并且要求的時間復雜度也較優(yōu)的題目它一般不能適用。 所以，我們解題在選用字母樹前，應當對題目中數(shù)據(jù)范圍和時間限制

27、加以一定分析。而這一步也是我們做任何題目所需要的。 11 可參考IOI2006 國家集訓隊論文Trie 圖的構建、活用與改進（第三版），作者王赟 7. 總結(jié)字母樹是一種好懂、好想、好寫、好用的數(shù)據(jù)結(jié)構。它合理利用串的公共前綴來節(jié)約內(nèi)存，在“檢索”方面存在著很大優(yōu)勢。 而字母樹的所有應用都圍繞著其特點展基本的查找外，還能進行字符串的排序，減少遞推、動態(tài)規(guī)劃等算法中的無效轉(zhuǎn)移并達到加速的目的，并且它也在“最長公共前綴”這一經(jīng)典問題的解決中占有一席之地，而本文未作介紹的 基于字母樹的 AC 自動機有著更強大的應用?？梢园l(fā)現(xiàn)，字母樹是一種簡單并且全能的數(shù)據(jù)結(jié)構，而它的這些應用都與它的“檢索”功能密切相

28、關。當然，不是所有題目都能使用字母樹，這需要我們對題目進行仔細分析并合理選擇。 字母樹，簡單，但堪稱經(jīng)典。當做到和關于“檢索”的題時，請讀者不妨考慮一下，字母樹能否為解題帶來便利。也許，讀者就能夠從中獲得更多的喜悅。 參考文獻1 劉汝佳、黃亮 算法藝術與信息學競賽 M 北京：清華大學 2 楊弋 Hash 在信息學競賽中的一類應用 A IOI2007 國家集訓隊論文 C 中國計算機學會 3 Thomas H.Cormen 等 算法導論 M 北械工業(yè) 4 KMP 算法詳解 EB/OL /blog/archives/115 ， 2006-11-295 郭華陽 RMQ 與 LCA 問題 A IOI2007 國家集訓隊論文 C 中國計算機學會 6 金