2016年2月28日 星期日

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

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

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

說明:
用兩個「$"$」框起來的東西是字串
用兩個「$'$」框起來的東西是字元 (在這裡等價於單純的英文字母)
「路徑$"abcd"$」代表字串$"abcd"$在圖上會走過的一條路徑
「字串集合」代表很多字串 (?)

$"abaab"$的圖要怎麼建呢?
我們可以照著上一篇的思路,一個字母一個字母慢慢加

依序加入邊$'a'$和邊$'b'$的過程和上一篇一模模一樣樣,若已經忘記了可以翻回去回顧一下呦~
依序加完邊$'a'$和邊$'b'$時圖會長這樣:
加入$'a'$,讓路徑$"aba"$會走到新節點$3$,這時$3$代表了$"aba"$和$"ba"$ (因為是從$2$走過來的,因此代表了$"ab"$和$"b"$再加一個$′a′$):
$3$還差一個$"a"$就能代表$"aba"$的所有後綴了
為了讓$3$代表$"aba"$的所有後綴,我們必須再讓路徑$"a"$連到$3$
可是問題來了,路徑$"a"$已經存在了,會走到$1$!
怎麼辦呢?
沒關係,我們先製造一種特殊的邊,這條邊可以把連向的點代表的字串集合全部加到連出的那點!
不過為了杜絕濫用行為 (?),每個點最多只能連出一條這種特殊的邊
這種特殊的邊就畫成綠色的吧,而因為這條邊被加入的字串集合也寫成綠色
從$3$到$1$連一條這種綠色的邊,圖就會變這樣:
加入邊$'a'$,讓路徑$"abaa"$會走到新節點$4$,這時$4$代表了$"abaa"$和$"baa"$ (因為是從$3$走過來的,因此代表了$"aba"$和$"ba"$再加一個′a′)
注意,$3$代表的字串集合裡面,$"a"$是綠色的,代表路徑$"a"$不是真的走到$3$,因此當然也不能直接藉由加一條邊$'a'$讓路徑$"aa"$走到$4$
所以,$4$目前只有代表$"abaa"$和$"baa"$:
$4$還差$"aa"$和$"a"$就能代表$"abaa"$的所有後綴了
我們先讓路徑$"aa"$連到$4$
這時$4$代表了$"abaa"$、$"baa"$和$"aa"$ (因為是從$3$和$1$走過來的,因此代表了$"aba"$、$"ba"$和$"a"$再加一個$′a′$)
現在圖長這樣:
一樣的問題又出現了,路徑$"a"$已經存在了,會走到$1$!
套用一樣的老方法,從$4$到$1$連一條綠色的邊:
加入$'b'$,讓路徑$"abaab"$會走到新節點$5$,這時$5$代表了$"abaab"$、$"baab"$和$"aab"$ (因為是從$4$走過來的,因此代表了$"abaa"$、$"baa"$和$"aa"$再加一個$′b′$)
注意,$4$代表的字串集合裡面,$"a"$是綠色的,代表路徑$"a"$不是真的走到$4$,因此當然也不能直接藉由加一條邊$'b'$讓路徑$"ab"$走到$5$
所以,$5$目前只有代表$"abaab"$、$"baab"$和$"aab"$:
一樣的問題又出現了,代表$"ab"$的路徑已經存在了,會走到$2$!
一樣,套用老方法,從$5$到$2$連一條綠色的邊:
於是,$"ab"$和$"b"$都被加進了$5$代表的字串集合裡面
現在$5$已經代表了$"abaab"$的所有後綴!
就這麼簡單,我們建完了$"abaab"$的圖!

為了確定你的理解是對的,請自己動手畫出$"aaaa"$的圖
它應該長這個樣子:
有趣的是,在後面再加一個$'b'$之後,會變成這個樣子:
可以觀察到一個有趣的現象:
不同於之前的節點們,$5$代表的字串集合全部都變成黑色的了!

如果還躍躍欲試,可以挑戰看看畫出$"abcaba"$的圖
它應該長這個樣子:


但是,真的每次都可以只用綠色的邊就能搞定嗎?
好像沒辦法耶

下一篇將討論$"abbbb"$怎麼建圖!

沒有留言:

張貼留言

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