2016年2月28日 星期日

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

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

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

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

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

依序加入邊$'a'$、邊$'b'$的過程和上上篇一模模模一樣樣樣,若已經忘記了可以翻回去回顧一下噢~
依序加完邊$'a'$、邊$'b'$時圖會長這樣:
加入邊$′b′$,讓路徑$"abb"$會走到新節點$3$,這時$3$代表了$"abb"$和$"bb"$ (因為是從$2$走過來的,因此代表了$"ab"$和$"b"$再加一個$′b′$):
$3$還差一個$"b"$就可以代表$"abb"$的所有後綴了
一樣的問題又來了,路徑$"b"$已經存在了,會連到$2$!
套用一樣的老方法,從$3$到$2$連一條綠色的邊:
額......好像出錯惹......
$2$代表的字串集合中有些不是$"abb"$的後綴啊QQ
既然我們需要一個代表$"b"$的節點,那就自己創造一個吧!
方法是從$2$分離出一個符合需求的點!

建立一個新節點$4$代表$"b"$
可是這樣就把$"b"$從$2$代表的字串集合搶走了
沒關係,從$2$到$4$連一條綠色邊,把丟掉的$"b"$加回來就沒事了
路徑$"bb"$之前是從$2$走到$3$的,現在要讓它改由從$4$走到$3$
像以前的$2$一樣,$4$要連邊$'b'$到$3$
現在,所有點代表的字串集合已經全部恢復原狀
除此之外,我們還多了一個代表$"b"$的點$4$!
這樣一來,我們就可以從$3$連一條綠色邊到$4$了
耶!
加入邊$′b′$,讓路徑$"abbb"$會走到新節點$5$,這時$5$代表了$"abbb"$和$"bbb"$ (因為是從$3$走過來的,因此代表了$"abb"$和$"bb"$再加一個$′b′$):
$3$還差$"bb"$和$"b"$就可以代表$"abbb"$的所有後綴了
一樣的問題又來了,路徑$"bb"$已經存在了,會連到$3$!
套用一樣的老方法,從$5$到$3$連一條綠色的邊
然後一樣又因為$3$代表的字串集合中有些不是$"abbb"$的後綴而出錯
一樣又要把需要的點從$3$分離出來
建立一個新節點$6$代表$"bb"$和$"b"$
可是這樣就把$"bb"$從$3$代表的字串集合搶走了
沒關係,從$3$連出的綠色邊改成連到$6$,就可以把丟掉的$"bb"$加回來了
路徑$"bbb"$之前是從$3$走到$5$的,現在要讓它改由從$6$走到$5$
像以前的$3$一樣,$6$要連邊$'b'$到$5$
現在,所有點代表的字串集合已經全部恢復原狀
除此之外,我們還多了一個代表$"bb"$和$"b"$的點$6$!
這樣一來,我們就可以從$5$連一條綠色邊到$6$了
耶!
接下來就只附過程圖了 (一樣的概念),打字好累Orz





於是,我們就把$"abbbb"$的圖建出來了!

為了確定你的理解是對的,請自己動手畫出$"abacc"$的圖
它應該長這個樣子:
如果還躍躍欲試,可以挑戰看看畫出$"abccba"$的圖
經過這一連串的過程:

最後應該長這個樣子XD:

但是,真的每次都可以只用綠邊和分離一個點就搞定嗎?
恭喜!答案是Yes (如果想知道為甚麼,請繼續看下去吧~)

咦?剛剛的建圖過程好像還滿有道理的
可是......知道了要怎麼用紙筆畫出任意字串的這種圖
你真的知道要怎麼用程式來儲存圖上的所有資訊嗎?

下一篇將教你如何有效的將圖上各種資訊儲存好!

沒有留言:

張貼留言

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