Re: 跟大家分享一個悲劇

看板C_and_CPP作者 (眠月)時間18年前 (2006/03/23 02:49), 編輯推噓5(504)
留言9則, 6人參與, 最新討論串2/2 (看更多)
補充一下 suffix tree 的說明好了 大部分人應該是沒看過這東西 他是一種 tree(廢話) 根據輸入的字串來建立一個 suffix tree 這個 tree 的每個分支都代表這個字串的一個 suffix suffix 就是詞尾,後置修飾 舉例來說 programmer 這個單字,er 就是他的一個 suffix,因為 programmer graprogrammer 的 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

03/23 05:37, , 1F
yoco大解說的很詳細呀 收錄精華~:)
03/23 05:37, 1F

03/23 08:46, , 2F
推+1
03/23 08:46, 2F

03/23 09:47, , 3F
我覺得 suffix tree 的 constant 還蠻高的
03/23 09:47, 3F

03/23 09:48, , 4F
寫起程式來要用的力氣也不小...
03/23 09:48, 4F

03/23 09:49, , 5F
如果不是有太特別的用途 有很多 average performance 很好的
03/23 09:49, 5F

03/23 09:50, , 6F
會好寫很多...
03/23 09:50, 6F

03/23 10:09, , 7F
同意,如果不是太閒的人千萬不要寫.. 寫心酸的..
03/23 10:09, 7F

03/23 22:27, , 8F
謝謝詳細解說...
03/23 22:27, 8F

11/12 21:20, , 9F
喔喔喔喔!!終於找到畫樹的中文解說了!!千找萬找Ptt就有!吼!
11/12 21:20, 9F
文章代碼(AID): #148Pmcyb (C_and_CPP)
文章代碼(AID): #148Pmcyb (C_and_CPP)