
使用較少的 RAM
|
311
確切的記憶體行為取決於你的資料結構。通常,由於從字串的開始到結尾具有多條路
徑,DAWG 無法將值指定給鍵,但這裡所顯示的版本能夠接受值的對映。trie 也能夠接
受值的對映。某些結構必須在一開始被建構,而其他結構能夠隨時被更新。
這些結構中有一些的強處在於它們提供
共同前綴搜尋
(
common prefix search
);亦即,
你能夠要求共用你所提供之前綴的全部單詞。以我們的 4 個單詞為例,搜尋
“
ta
”
的結果
會是
“
tap
”
與
“
taps
”
。更且,因為是透過圖形結構(graph structure)被發掘的,這些結
果的擷取非常快速。例如,如果你正在處理 DNA,使用 trie 壓縮數百萬個短字串可能是
降低 RAM 使用量的有效率方式。
圖 11-2 Trie 與 DAWG 結構(Chkno 繪製,
http://bit.ly/Trie_and_DAWG
,CC BY-SA 3.0)
在後續幾個小節裡,我們會更仔細地檢視 DAWG、trie,以及它們的使用狀況。
DAWG(directed acyclic word graph,有向非循環字圖)
DAWG(
https://github.com/kmike/DAWG
)( MIT 授權)試圖有效率地表示具有共同前綴
與後綴的字串。
在範例 11-13 中,你看到非常簡單的 DAWG 設置。對這個實作來說,DAWG 在建構之
後不能被修改;它讀取迭代器,建構自己一次。無法在建構之後作更新可能不適用於
你的使用案例,若是如此,你可能需要改用 ...