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中的模式匹配

回答

相关问题