2016年2月28日 星期日

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

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

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

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

還記得這張圖嗎?這是$S="abcd"$時預處理出來的樹
信不信,我可以把這張圖從$11$個節點縮到只剩$5$個節點,並且沒有讓圖喪失任何功能!
想知道怎麼做嗎?答案在這裡:
雖然這樣圖就不是一棵樹了
不過,還是可以依照上一篇講的方式走
舉個例子,子字串$"abc"$、$"bc"$、$"c"$都會走到$3$ (每個節點下面的那些字串集合就是會走到這個點的字串集合)
可以發現
$"a"$的所有後綴都會走到$1$
$"ab"$的所有後綴都會走到$2$
$"abc"$的所有後綴都會走到$3$
$"abcd"$的所有後綴都會走到$4$

那我們就來嘗試讓這個圖保有這個性質
讓$i$代表$S_{1\sim i}$的所有後綴!($S_{1\sim i}$代表$S$的前$i$個字母組成的字串)

那麼要怎麼讓程式知道要這樣建圖呢?

我們先將字母一個一個加進去,看看圖會怎麼長
加入邊$'a'$,讓路徑$"a"$會走到新節點$1$,這時$1$代表了$"a"$:
加入邊$'b'$,讓路徑$"ab"$會走到新節點$2$,這時$2$代表了$"ab"$ (因為是從$1$走過來的,因此代表了$"a"$再加一個$'b'$):
$2$還差一個$"b"$就能代表$"ab"$的所有後綴了
為了讓$2$代表$"ab"$的所有後綴,我們必須再讓路徑$"b"$連到$2$:
加入邊$'c'$,讓路徑$"abc"$會走到新節點$3$,這時$3$代表了$"abc"$和$"bc"$ (因為是從$2$走過來的,因此代表了$"ab"$和$"b"$再加一個$'c'$):
$3$還差一個$"c"$就能代表$"abc"$的所有後綴了
為了讓$3$代表$"abc"$的所有後綴,我們必須再讓路徑$"c"$連到$3$:
加入邊$'d'$,讓路徑$"abcd"$會走到新節點$4$,這時$4$代表了$"abcd"$、$"bcd"$和$"cd"$ (因為是從$3$走過來的,因此代表了$"abc"$、$"bc"$和$"c"$再加一個$'d'$):
$4$還差一個$"d"$就能代表$"abcd"$的所有後綴了
為了讓$4$代表$"abcd"$的所有後綴,我們必須再讓路徑$"d"$連到$4$:
就這麼簡單,我們建完了$"abcd"$的圖!

但是,畢竟$"abcd"$是相對簡單的字串 (每個字母只有出現一次)
下一篇將討論$"abaab"$怎麼建圖!

沒有留言:

張貼留言

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