Re: 跟大家分享一個悲劇

看板C_and_CPP (C/C++)作者yoco315 (眠月)時間18年前 (2006/03/23 02:49)推噓5(5推 0噓 4→)

留言9則, 6人參與討論串2/2 (看更多)

補充一下 suffix tree 的說明好了大部分人應該是沒看過這東西他是一種 tree（廢話）根據輸入的字串來建立一個 suffix tree 這個 tree 的每個分支都代表這個字串的一個 suffix suffix 就是詞尾，後置修飾舉例來說 programmer 這個單字，er 就是他的一個 suffix，因為 programmer gra 則不是 programmer 的 suffix 一個長度 n 的字串有 n 個 suffix 以字串 cocoa 來說他的五個 suffix 分別是 cocoa ocoa coa oa a suffix tree 就是根據一個字串的 suffix 建立的 tree 例如上面那個 cocoa 可以表示成 root ├ a // a ├ co │ ├ a // coa │ └ coa // cocoa └ o ├ a // oa └ coa // ocoa suffix tree 可以提供我們 pattern matching 的功能例如我們如果要尋找 cocoa 裡面有沒有 oco 這個子字串只要沿著 suffix tree 從 root 慢慢往下走就可以時間複雜度是子字串的長度，相當不錯！傳統 pattern matching 在長度 n 的母字串搜索長度 m 的子字串時間複雜度分別有 O(mn), O(n), O(n/m) 不過 worst case 也是 O(mn) 等演算法如果利用 suffix tree 來搜索子字串，每次只需要付出 O(m) 的成本，當你需要在一個超大母字串裡面搜索很多種子字串的時候，例如你想知道一個檔案裡面是不是含有病毒，就可以把這個檔案建成 suffix tree，然後把你已經知道的數千種病毒特徵拿下去比對，（當然這個例子簡化了很多）這種時候 suffix tree 就很合用。建立 suffix tree 最差的方法當然就是暴力法，你第一次取出整個字串，放到 tree 裡面去，從 root 開始比對，如果都一樣就繼續往下走，如果遇到不一樣的字元，那就可以分支，並且完成這次插入，第二次取出後面 n-1，然後比對跟分支，第三次取出後面 n-2... .... 總共 n 次，時間複雜度 O(n^2) 天哪！O(n^2)！那根本就很慢阿！不過好險 suffix tree 存在 O(n) 的建構法，很複雜，不太容易用 BBS 說明 XD 幸好網路上有很詳細的教學 http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm http://wwwmayr.in.tum.de/konferenzen/Ferienakademie99/maass/applet.html suffix tree 除了 pattern matching 以外還有很多其他的用途像是資料壓縮，Longest common squence，或是其他點點點點現在大家都知道 suffix tree 是幹什麼吃的了考慮下面這個字串 aj;fej$@#afFap,k3258akaqehhvlleqhf 很亂，對，這表示每次我在加入一個新的 suffix 到 tree 裡面的時候都會因為 char squence 的不同，比沒兩個字元就很快分支，然後完成插入但是如果我的字串長這樣 1234567812345678123456781234567812345678123456781234567812345678 瞎子已經看出來他每八個字元循環一次了當然我插入前面八個 suffix 的時候還沒有問題問題是當我要插入第九個的時候，他會跟第一個一直 match，一直 match，都無法分支一直到最後最後把整個字串都跑完了，才發現不同（一個是字元結束，一個是1）這就是為什麼循環的字串會讓整個程式的速度突然 down 下來要不是靈光一閃我可能永遠以為我的程式有錯 T_T -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.129.180