Re: [問題] pattern比對的問題

看板Python作者yauhh (喲)時間11年前 (2014/10/14 01:27)推噓1(1推 0噓 0→)

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

※ 引述《liataian (T-PANY FOREVER)》之銘言： : 大家好, 有一個問題讓我百思不得其解, 想上來請教一下板友的想法 : 假設我現在有一個list = ['AB','B','AC','CD','E'] : 我想要對list中的元素train一個有關前後順序的pattern : 以上例來說, 每次train出的pattern如下(在[]中的字母是有順序的, 在{}中則無): : 'AB' 跟 'B' 比對後train出一個pattern1 : [A,B] (得知A在B前面) : pattern1 跟 'AC' 比對後再train出一個pattern2 : [A,{B,C}] (得知A也在C前面) : pattern2 跟 'CD' 比對後再train出一個pattern3 : [A,{B,[C,D]}] (得知A也在D前面, : 且C在D前面) : pattern3 跟 'E' 比對後再train出一個pattern4 : {[A,{B,[C,D]}],E} : 最後我可以知道的結果就是: "A一定在B,C,D前面, C一定在D前面" : 其他可能還不知道先後順序的部分先不管(因為這個list之後會再加入更多item去train) : 想請教板友有什麼工具可以達成我要的目的嗎? : 或是板友有什麼想法可以提供嗎? : 感覺自己描述得不太好, 如果有不清楚還請見諒@@ : 謝謝基本的工具是一些演算法。第一步，做字典排序。用意是盡可能由前往後，不需要回溯太多種情況。例如，以下四個字串經過字典排序之後，是以下四個字串的順序。 a de b de c c e 第二步，要用 maximal common sequence 演算法。 ade 和 bde 做 MCS 之後，分別會分解為 [a,de,empty] 和 [b,de,empty] ， de 是共有的部分。而前後為差異的部分。差異的部分合併，並且保持先後順序，就合併為 [{a,b},de] 。再往後算，就應該是要對現有的結構的每一項， a, b, de 等等，個別算有沒有 MCS ，如果有，就表示在 [{a,b},de] 中可以拉一條分歧線出來。如果下一項進來都沒有 MCS ，就是對現有的 graph 來說完全獨立的東西。用這種方法一直算，就會是這樣： MCS(ade, bde) => [{a,b},de,{empty,empty}] => [{a,b},de] MCS([{a,b},de], c) => {[{a,b},de],c} MCS({[{a,b},de],c}, ce) => {[{a,b},{d,c},e,{empty,empty}], [{empty,empty},c,{empty,e}]} => {[{a,b},{d,c},e],ce} 不過這樣出現重疊的路線 ce 了，就需要加一個去除重複的步驟。我覺得，去除重複的基礎，應該是你所提的 pattern1 的產生，因為 B 對於 AB 來說可以融合，所以 B 消失了。這個基礎式子是以下幾條規則： {ab,b} => MCS(ab,b) => [{a,empty},b,{empty,empty}] => ab {a,b} => MCS(a,b) => {a,b} {empty,a} => a {a,empty} => a {empty,empty} => [] 所以當 {[{a,b},{d,c},e],ce} 出現時，要做 MCS([{a,b},{d,c},e], ce) ，意思就是在設計 MCS 函數時，要想到該怎麼處理各種 graph 結構。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.159.130 ※ 文章網址: http://www.ptt.cc/bbs/Python/M.1413221250.A.882.html