算法合集之trie圖的構(gòu)建、活用與改進(jìn)-資料下載頁
2024-10-16 20:29本頁面
【正文】 ntest 【 樣例輸出 】 1 10 【 注意 】 樣例中 “ 第一次出現(xiàn) ”的不良單詞是 Problem而不是rob， 雖然 rob比 Problem先結(jié)束 。 【 時間限制 】 1s。 【 內(nèi)存限制 】 5000KB。 Trie圖的改進(jìn)（例 5分析） ? 乍一看 ， 這道題與例 1不是一模一樣的嗎 ？ 其實不然 。 與例 1相比 ， 這道題的字符集大得多 ， 如果直接建 trie圖 ， 從每個結(jié)點出發(fā)要建 253條邊 ，而結(jié)點數(shù)最多為 100000， 嚴(yán)重超內(nèi)存 。 試想一下 ， 如果要做一個漢字的多模式匹配系統(tǒng) ， 豈不是要從每個結(jié)點出發(fā)建幾千幾萬條邊呢 ？ 所以 ，為解決此問題 ， trie圖的改進(jìn)勢在必行 。 Trie圖的改進(jìn)（例 5分析） ? 我們看到，在本題中，算法的瓶頸在于從每個結(jié)點出發(fā)的邊數(shù)。那么我們自然會想到：一定要存儲所有的邊嗎？答案是否定的。 Trie樹中的邊自然是要存儲的，但新建的邊則不必存儲。如果不存儲新建的邊，那么如何實現(xiàn)狀態(tài)間的轉(zhuǎn)移呢？我們用一個函數(shù) child(x,c)來獲得結(jié)點 x的 c孩子。函數(shù)內(nèi)部的程序其實完全是按照加邊的原則編寫的：如果 x本來就有 c孩子，那么就返回這個孩子；如果 x沒有 c孩子，根據(jù)加邊的原則，函數(shù)應(yīng)該返回 x的后綴結(jié)點的 c孩子，也就是令 x為它的后綴結(jié)點，重新執(zhí)行函數(shù)。如果 x變成了根結(jié)點仍然沒有 c孩子，同樣根據(jù)加邊的原則，函數(shù)的返回值就應(yīng)該是根結(jié)點本身。 Trie圖的改進(jìn)（時間復(fù)雜度分析） ? 經(jīng)過這樣的處理，算法的空間復(fù)雜度由 O(L1a)降到了O(L1)，對于本題來說是足夠低的了。但是，由于 child函數(shù)的執(zhí)行時間的不確定性，我們對算法的時間復(fù)雜度產(chǎn)生了疑問。其實，算法的時間復(fù)雜度為 O(L1+L2)，數(shù)量級并沒有受到影響，只是增加了一點常數(shù)系數(shù)。為什么呢？顯然，在調(diào)用 child(x,c)的時候，只有當(dāng) x沒有 c孩子，需要重復(fù)執(zhí)行 child函數(shù)時運行時間才會增加。我們分別討論增加的這點時間對建圖過程和文本檢查過程所需時間的影響： Trie圖的改進(jìn)（時間復(fù)雜度分析） ? 建圖過程：由于我們并不存儲一個結(jié)點的所有孩子指針，所以建圖的過程其實就是求每個結(jié)點的危險性及后綴結(jié)點的過程。若 b是 trie樹中 a結(jié)點的一個孩子，那么 b的后綴結(jié)點的深度至多比 a的后綴結(jié)點大 1。如果把 trie樹中某條路徑上的結(jié)點的后綴結(jié)點的深度排成一個數(shù)列，那么相鄰兩項中，后一項減一項的差一定小于等于 1。當(dāng)后一項減前一項的差小于 1時， child函數(shù)就會被重復(fù)執(zhí)行。但是，child函數(shù)回溯的次數(shù)不會超過 trie樹的深度，所以建圖過程的時間復(fù)雜度為 O(L1)。 ? 文本檢查過程：把這個過程看成是一個光標(biāo)在安全圖中漫游的過程。因為光標(biāo)如果往下走，它只能走 1步，所以若把光標(biāo)經(jīng)過的位置的深度也排成一個數(shù)列，這個數(shù)列與上一段提到的數(shù)列具有相同的性質(zhì)：增長是緩慢的。同理，文本檢查過程的時間復(fù)雜度為 O(L2)。 Trie圖的改進(jìn)（時間復(fù)雜度分析） ? 綜上所述，改進(jìn)后的 trie圖的時間復(fù)雜度為O(L1+L2)。無論從時間復(fù)雜度上看還是從空間復(fù)雜度上看，改進(jìn)后的算法都明顯優(yōu)于改進(jìn)前。第二部分中的 《 字謎 》 一題到此也得到了圓滿解決。其實，改進(jìn)后的算法已經(jīng)就是用于多模式串匹配的改進(jìn) KMP算法了。 Trie圖的改進(jìn)（小結(jié)） 對于什么樣的題目需要用改進(jìn)的 trie圖，在此作一下總結(jié)： ? 純粹的多模式匹配問題（如例 5）：當(dāng)題目中的字符集大小有限且較小時，不必用改進(jìn)的 trie圖，因為內(nèi)存夠用，若進(jìn)行改進(jìn)，增加的常數(shù)系數(shù)可能反而大于字符集的大小 a。如果字符集較大甚至無限（漢字的多模式匹配系統(tǒng)的字符集幾乎可以認(rèn)為是無限的），就必須使用改進(jìn)的 trie圖。 ? 用到圖中每一條邊的題目（如例 4）：一般用未改進(jìn)的 trie圖。在內(nèi)存十分緊張的情況下，可以采用改進(jìn)的trie圖，用時間換空間，但這樣做時間復(fù)雜度仍為O(L1a+L2)，且常數(shù)系數(shù)較未改進(jìn)時大。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1