有路徑與儲存字詞是兩回事
定義 7.1.1
(Trie、終止標記與標準形式)
Trie 在大小為 的有序有限字母表上儲存有限字串集合。根代表空前綴;每條邊標記一個字元,從根到節點的路徑拼出其前綴。節點可以標記為終止,表示對應字串本身在集合中。沒有終止標記的非根路徑表示某個已儲存字串的前綴,而非已儲存字詞。根是例外:即使集合為空,它仍存在。
當 trie 的非根節點恰好是集合 中字串的非空前綴(因此每個非根節點都是至少一個已儲存字串的前綴),而且節點為終止,當且僅當其字串屬於 時,稱這個 trie 對 是標準的。
下述插入及剪枝維持標準形式。本課討論集合而非多重集合:重複插入不增加次數。若允許空字串,它以根的終止標記表示。
概念視角組合
按共用前綴計算節點數
把已儲存的字串按字典序排成 ,並令 。 中長度大於 的每個前綴,都不是任何較前字串的前綴,所以
其中 lcp 是最長共同前綴的長度。對 in、inn、tea、ten、to,各項為 ,共 個非根節點。共用前綴恰好省去了共同前綴的長度。
插入、查找與列舉
插入時從根依次沿字元前進,缺少子節點便建立,最後把終點標為終止。精確成員查詢沿路徑前進,只有終點存在且標為終止才回答是。缺邊證明不存在;到達非終止節點表示精確字詞不在集合中。非根節點仍是某個已儲存字詞的前綴;即使集合為空,根也可以存在。插入空字串只標記根。
前綴查詢先沿前綴前進;若路徑不存在,便沒有已儲存字詞帶此開頭。否則遍歷其子樹,在每個終止節點輸出字串;若前綴節點本身終止,也要輸出該前綴。先輸出節點,再按字母次序訪問子節點,便得到字典序。這是列舉:找到前綴節點本身不是輸出全部答案的成本。
跟蹤與共用前綴
例題 7.1.2
(建立含共用前綴的 trie)
向空 trie 插入 to、tea、ten、in、inn。表示出的前綴包括空前綴和
包括根共有九個節點。終止節點恰是插入的五個字詞;te 非終止,而 in 是終止節點,同時有通往 inn 的子節點。列舉前綴 te 時先輸出 tea,再輸出 ten。
反例模式
前綴節點也可以是字詞
若刪除 in 時移除其整個節點和子樹,也會破壞 inn。只清除 in 的終止標記便移除該精確字詞,同時保留較長字詞。因此刪除後能到達節點,仍不足以判定精確成員關係。
常見錯誤
(把到達的節點當作已儲存字詞)
在跟蹤用的 trie 中,路徑 te 存在,所以路徑一走完便回答「是」的查詢會出錯。但 te 並非終止,集合並不包含它。成員判定既需要完整的路徑,也需要終止標記。
不損害其他字詞的刪除
對存在的字串,沿路徑找到終點並清除終止標記。然後向根回走:只在目前非根節點沒有子節點且非終止時移除它;任一條件不成立便停止。若字串不存在,保持 trie 不變。即使根變成未標記葉節點,也絕不移除根。
定理 7.1.3
(插入、查詢與刪除維持標準形式)
設某個 trie 對有限字串集合 是標準的, 為一個字串。插入 得到對 標準的 trie。成員測試回答「是」,當且僅當 。按上述方式刪除 :若 ,trie 不變;否則得到對 標準的 trie。
證明
(刪除之後哪些節點仍然需要)
插入只為 缺少的前綴加入節點,而 的每個前綴都是 中某個成員的前綴。它把終點標為終止,其餘不變。由標準形式, 的路徑存在且終點為終止,當且僅當 ,這就給出成員測試。
對於刪除,設 ,並設 是 的路徑上的節點, 為根, 是 的節點。清除 的標記後,終止節點恰是 的成員。若非根節點的前綴是 中某個成員的前綴,便稱它為需要的。不在 的路徑上的節點,是 中某個異於 的成員的前綴,所以是需要的;只有 可能不需要。
迴圈從 向上走。它只在節點當下非終止且沒有子節點時才移除它。這種節點是不需要的:若 的某個成員延伸其前綴,便會迫使更長前綴的節點存在,也就是有子節點,而曾被移除的子節點本身都是不需要的。迴圈在第一個終止或有子節點的節點停止。終止節點是 的成員,所以是需要的。仍然存在的子節點是需要的:不在 的路徑上的子節點,是異於 的成員的前綴; 的子節點真延伸 ,所以是異於 的成員的前綴;若迴圈停在 (),它在路徑上的子節點 已被移除,所以剩下的子節點都不在路徑上。每種情況中,停止處的節點都是需要的。需要的節點的每個祖先,都是同一成員的前綴,所以全都是需要的,不會被移除。
因此剪枝後的 trie 恰好含有 中成員的各個前綴所對應的節點,終止標記也恰好位於這些成員。若 ,則路徑不存在,或其節點不是終止,因此不作任何改動。
證明透視
為何迴圈需要兩個停止條件
兩個停止條件各自保護不同的東西。終止標記保護在此節點結束的字詞;子節點保護經過此節點的更長字詞。單靠任何一個都不夠。取 並刪除 tom:節點 m 被移除,而 to 隨即成為沒有子節點的葉節點。若迴圈只檢查「沒有子節點」,便會刪去 to,丟失一個已儲存字詞。若迴圈只檢查「非終止」,則會刪去更長字詞的前綴節點,這正是上面反例所示的失敗。
論證在第一個需要的節點完結。它上面的所有節點都是該節點字串的前綴,所以祖先不需要另外檢查。因此迴圈可以在第一次失敗時停止,無須查看路徑其餘部分。
例題 7.1.4
(從跟蹤用的 trie 刪除)
在例子中,刪除 tea 會清除其標記,只剪去最後的 a 節點:te 仍通往 ten,所以保留。若改刪 in,只清除其標記而不剪去任何節點,因為 inn 仍存在。刪除空字串時,如根已標記則清除它,但絕不刪除根或其他字詞。
例題 7.1.5
(邊界情況:不存在的字詞、最後一個字詞與空字串)
從跟蹤用的 trie 刪除 tex,找不到邊 x,所以字串不存在,沒有任何改動。刪除 te 同樣不改動:其節點存在,但並非終止,所以 te 不是成員。
現在設 。刪除 a 會清除標記。節點 a 非終止且沒有子節點,所以被剪去。迴圈到達根便停止,根保持不動:這就是空集合的 trie。
最後設 ,所以根為終止,並有子節點 a。刪除 只清除根的標記,其他不變,而 a 仍是成員。
成本取決於表示法
命題 7.1.6
(使用子槽位陣列時的成本)
設每個節點有 個子槽位的陣列,可按字元常數時間索引。精確查詢長度為 的字串需 時間。插入及刪除需 時間;若把 視為固定常數,便成為 。若子樹遍歷訪問 個節點並輸出共 個字元,找到長度 的前綴並按字母次序列舉需 。對所有 個節點,此表示使用 個子槽位。
證明
(計算訪問的節點數與掃描的槽位數)
查詢至多沿 條邊前進,訪問至多 個節點,每個花費常數時間。插入至多建立 個節點,初始化每個節點的 個子槽位花費 。刪除先向下走至多 個節點,再向上走;每次「沒有子節點」的檢驗掃描 個槽位,每次移除花費 ,合共 。列舉時,找到前綴節點花費 ,每個被訪問的節點掃描子槽位花費 ,合共 ,寫出輸出花費 。儲存空間是每個節點 個槽位。
稀疏映射可節省槽位,但查找及有序遍歷成本取決於具體映射。
常見錯誤
(只按前綴計算列舉成本)
找到前綴節點需 ,但答案可能是其下的整棵子樹。成本 包括被訪問的節點數 與輸出 。前綴雖短而子樹很大時,即使前綴路徑便宜,列舉仍然昂貴。
習題與解答
快速檢查
(前綴與字詞。例子中的 te 是精確成員嗎?)
檢查終止標記,而不只是路徑。
解答 · 答案
不是。其節點存在,但未標為終止。
快速檢查
(刪除。刪除 tea 後,ten 和 to 哪些仍存在?)
各條路徑經過哪些節點?
解答 · 答案
兩者都在;其路徑都不經被移除的最後 a 節點。
快速檢查
(根。空字串如何儲存?)
只有根代表空前綴。
解答 · 答案
把根標為終止;不論空字串是否成員,根都存在。
快速檢查
(輸出成本。為何只找到前綴節點不足以界定列舉成本?)
想一想找到前綴節點之後還要做甚麼。
解答 · 答案
算法仍可能訪問許多後代,而且必須輸出匹配字詞的字元。