Python中的模式匹配

這個問題可能更接近圖像處理中的模式匹配。Python中的模式匹配

有什麼辦法可以得到一個成本函數值，應用於不同的列表，這將返回列表間的鄰近度？例如，

a = [4, 7, 9] 
b = [5, 8, 10] 
c = [2, 3]

現在的成本函數值，可以是2元組，（A，B）應大於（A，C）和（B，C）。這可能是一個巨大的計算任務，因爲可以有更多數量的列表，並且所有的排列組合都會打破問題的複雜性。所以只有一組2元組才能工作。

編輯：列表名稱指示操作的類型，其中的元素是相應操作發生的時間。我想要做的是提出一組具有相似發生模式的動作。由於兩個動作不能同時發生，因此它是列表內和列表間距離的組合。

在此先感謝！

來源

2012-08-15 RLOA

比較兩個字符串或列表，你可以使用Levenshtein distance（從here Python實現）：

def levenshtein(s1, s2): 
    l1 = len(s1) 
    l2 = len(s2) 
    matrix = [range(l1 + 1)] * (l2 + 1) 
    for zz in range(l2 + 1): 
     matrix[zz] = range(zz,zz + l1 + 1) 
    for zz in range(0,l2): 
     for sz in range(0,l1): 
      if s1[sz] == s2[zz]: 
       matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, 
             matrix[zz][sz+1] + 1, 
             matrix[zz][sz]) 
      else: 
       matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, 
             matrix[zz][sz+1] + 1, 
             matrix[zz][sz] + 1) 
    return matrix[l2][l1]

使用您的列表：

>>> a = [4, 7, 9] 
>>> b = [5, 8, 10] 
>>> c = [2, 3] 
>>> levenshtein(a,b) 
3 
>>> levenshtein(b,c) 
3 
>>> levenshtein(a,c) 
3

編輯：與添加的解釋在評論中，您可以使用set而不是列表。由於集合中的每個元素都是唯一的，因此再次添加現有元素是無操作的。你可以使用這個集合的isdisjoint方法檢查兩個集不包含相同的元素，或intersection方法，看看他們有哪些元素是共同的：

In [1]: a = {1,3,5} 

In [2]: a.add(3) 

In [3]: a 
Out[3]: set([1, 3, 5]) 

In [4]: a.add(4) 

In [5]: a 
Out[5]: set([1, 3, 4, 5]) 

In [6]: b = {2,3,7} 
In [7]: a.isdisjoint(b) 
Out[7]: False 

In [8]: a.intersection(b) 
Out[8]: set([3])

注：此語法創建組至少需要Python 2.7。

來源

2012-08-15 08:25:45

謝謝羅蘭！雖然代碼可能沒有直接用處，但是感謝大家向我介紹Levenshtein距離的想法。 – RLOA 2012-08-15 11:15:59

你在問一個非常困難的問題。在不允許尺寸改變的情況下，您可以使用幾種距離測量（Euclidean，Manhattan等，請參閱另請參閱部分了解更多信息）。你需要的那個取決於你認爲無論這些列表代表的是什麼，接近度的一個好的度量。

不知道你想用這些列表做什麼，沒有人可以定義一個好的答案，更不用說如何有效地計算它。

來源

2012-08-15 08:37:29

邁克爾，我明白你的意思。基本上，這些列表指示了動作的類型，其中的元素是相應動作發生的時間。我想要做的是提出一組具有相似發生模式的動作。但是不能同時發生兩個動作，因此它是列表內和列表間距離的組合。 – RLOA 2012-08-15 11:18:05

@RLOA：你應該真的編輯這個評論到你的問題。 – 2012-08-15 11:31:01

完成。希望它不會讓人困惑。 – RLOA 2012-08-15 13:02:12

鑑於您給予Michael的澄清的答案，您應該查看「Dynamic Time Warping」。

我還沒有使用http://mlpy.sourceforge.net/，但它的blurb說它提供了DTW。（可能是一個打擊螺母的錘子;取決於你的使用情況。）

來源

2012-08-15 11:56:49

感謝您的回覆並鏈接到mlpy，Dan！事實上，「翹曲」不應該適用於我的情況。時間距離也用於匹配模式。我正在尋找mlpy的其他機會。 – RLOA 2012-08-15 16:00:32

Python中的模式匹配

回答

相關問題