2016年2月28日 星期日

後綴自動機 (SAM) 圖文教學 (五)

請先參考後綴自動機 (SAM) 圖文教學 (四)

(Copyright:圖片轉載請註明來源網址,感謝~)

我們已經在紙上演練了這麼多次,該來看看這個很視覺化的東西要怎麼用程式來實作了吧?

首先是節點儲存問題
回顧定義,每個節點都代表了一個字串的一堆後綴所組成的字串集合
例如這張$S="abbbb"$圖:(還記得$S$是甚麼嗎?趕快到這裡複習一下吧~)

可以發現節點$7$代表了$"abbbb"$、$"bbbb"$、$"bbb"$、$"bb"$、$"b"$這些字串,也就是$"abbbb"$的所有後綴組成的字串集合
可是又不能很貪心地只儲存長度最長的$"abbbb"$,因為這些字串還有黑色和綠色之分,是會影響下一次加入新字母時的行為的......

咦?真的是這樣嗎?

可以發現,$7$的綠色邊指向$8$,而$8$所代表的字串集合 (分別是$"bbb"$、$"bb"$和$"b"$) 恰好就是$7$的所有綠色字串!
廢話,不然要綠色邊的作用是啥?(該不會真的忘記綠色邊是幹嘛的吧?請從這裡找到它的定義吧~)
不用另外存$7$所代表的每個字串的顏色了
因此,對於$7$這個節點,我們真的只要儲存長度最長的$"abbbb"$就好了!

可是這樣每個節點還是需要$O(\left|S\right|)$的空間來儲存QQ

仔細觀察一下,如果我們只知道圖的形狀和每條邊代表的字母,能不能推出任意節點代表的字串集合中最長的那一個字串 (因為其他的字串枚舉後綴就出來了) 呢?
其實,如果真的需要這些資訊的話,我們只要把$0$、$1$、$2$、$3$、$5$、$7$特別標記起來
然後對於每個節點$u$,存下其代表的字串集合中最長字串的長度 (稱作$max\_len[u]$吧) 就好了

這樣一來
假如我要知道$5$代表的最長字串長怎樣:
因為$5$被特別標記起來了,因此可以直接知道答案是$S$的前$max\_len[5]=4$個字母組成的字串 (求得$"abbb"$)
假如我要知道$8$代表的最長字串長怎樣:
隨便挑一條「指向$8$」的綠色邊「反向」走到另一個節點$u$,遞迴得到$u$的答案為$s$ (如果走到$5$,$s="abbb"$;如果走到$7$,$s="abbbb"$),那麼$8$代表的最長字串就是$s$的後$max\_len[8]=3$個字母組成的字串了 (求得$"bbb"$)

所以每個節點只要存兩個資訊就好:有沒有被特別標記、其代表的字串集合中最長字串的長度!

現在,我們儲存「點」的空間複雜度已經可以降到$O(\left|S\right|)$了
那麼,儲存「邊」的空間複雜度呢?

最主要的節點儲存問題已經解決了,還是趕快來寫code比較重要吧 (好啦其實是因為用程式流程來講會比較好解釋)

下一篇將說明用程式實作$SAM$的方式 (其實這張圖就是後綴自動機 ($SAM$) 啦,沒有很困難的對吧(?) )

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原