Re: [問題] 二維的字串比對問題
看板Prob_Solve (計算數學 Problem Solving)作者pause2 (好大的陽光)時間18年前 (2006/07/07 12:12)推噓2(2推 0噓 0→)留言2則, 2人參與討論串3/9 (看更多)
※ 引述《windows2k (KERORO軍曹)》之銘言：
: 傳統的一維比對, 給定一個字串 text 和一個 pattern
: 要看看pattern是否有在 text出現過
: 對於這種問題, 已經有很多解決方案, 如 BM, KMP之類的演算法
: 那如果變成二維的情況該怎麼轉化成一維
: 如
: abc bc
: bcd 中要找出 cd 這個pattern
: cde
: 可以找到
: abc abc
: bcd 和 bcd
: cde cde
: 兩組解
: 該怎麼把二維的問題轉成一維來做?
你所提的應該是所謂的 "multiple pattern matching" 的問題
比較著名的有 Aho-Corasick, Wu-Manber等algorithm
我簡述一下 Aho-Corasick algorithm 的作法
它是把多個 pattern 建成 finite-state-machine，
以你提的例子，有個initial state 0，吃到 b 進到 state 1
state 1 吃到 c 進到 state2 , state2為一個final state~ 表示中了pattern "bc"
以此類推~
然後把input text一個個的放入 state-machine裡run
則對每個text，在 O(len(text)) 內，知道有沒有中哪個pattern~
search時間與pattern的多寡無關，只與text長度有關
關於 pattern-matching 的問題，還有很多的演算法，可以查查~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.168.174.44
※ 編輯: pause2 來自: 218.168.174.44 (07/07 12:21)
推
07/07 12:39, , 1F
07/07 12:39, 1F
推
07/07 12:49, , 2F
07/07 12:49, 2F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
