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