在NumPy数组中搜索序列

Question

假设我有以下数组：

 array([2, 0, 0, 1, 0, 1, 0, 0])

我怎么在那里我有值序列发生指数：[0,0]？因此，在这种情况下的预期输出为：[1,2,6,7]。

编辑：

1）请注意，这[0,0]只是一个序列。可能是[0,0,0]或[4,6,8,9]或[5,2,0]，仅此而已。

2）如果将我的数组修改为：array([2, 0, 0, 0, 0, 1, 0, 1, 0, 0])，则具有相同序列的预期结果[0,0]将是[1,2,3,4,8,9]。

我正在寻找一些NumPy快捷方式。

Answer 1

嗯，这基本上是template-matching problem图像处理中经常出现的问题。这篇文章中列出了两种方法：基于纯NumPy和基于OpenCV（cv2）。

方法1：
使用NumPy，可以2D在输入数组的整个长度上创建一组滑动索引。因此，每一行都是元素的滑动窗口。接下来，将每一行与输入序列匹配，这将带来broadcasting矢量化解决方案。我们寻找所有True表明完美匹配的行，因此它们将是匹配的起始索引。最后，使用这些索引，创建一个扩展到序列长度的索引范围，以提供所需的输出。实施将是-

def search_sequence_numpy(arr,seq):
    """ Find sequence in an array using NumPy only.

    Parameters
    ----------    
    arr    : input 1D array
    seq    : input 1D array

    Output
    ------    
    Output : 1D Array of indices in the input array that satisfy the 
    matching of input sequence in the input array.
    In case of no match, an empty list is returned.
    """

    # Store sizes of input array and sequence
    Na, Nseq = arr.size, seq.size

    # Range of sequence
    r_seq = np.arange(Nseq)

    # Create a 2D array of sliding indices across the entire length of input array.
    # Match up with the input sequence & get the matching starting indices.
    M = (arr[np.arange(Na-Nseq+1)[:,None] + r_seq] == seq).all(1)

    # Get the range of those indices as final output
    if M.any() >0:
        return np.where(np.convolve(M,np.ones((Nseq),dtype=int))>0)[0]
    else:
        return []         # No match found

方法2： 使用OpenCV（cv2），我们有一个内置函数template- matching：cv2.matchTemplate。使用此，我们将具有起始匹配索引。其余步骤将与以前的方法相同。这是使用的实现cv2：

from cv2 import matchTemplate as cv2m

def search_sequence_cv2(arr,seq):
    """ Find sequence in an array using cv2.
    """

    # Run a template match with input sequence as the template across
    # the entire length of the input array and get scores.
    S = cv2m(arr.astype('uint8'),seq.astype('uint8'),cv2.TM_SQDIFF)

    # Now, with floating point array cases, the matching scores might not be 
    # exactly zeros, but would be very small numbers as compared to others.
    # So, for that use a very small to be used to threshold the scorees 
    # against and decide for matches.
    thresh = 1e-5 # Would depend on elements in seq. So, be careful setting this.

    # Find the matching indices
    idx = np.where(S.ravel() < thresh)[0]

    # Get the range of those indices as final output
    if len(idx)>0:
        return np.unique((idx[:,None] + np.arange(seq.size)).ravel())
    else:
        return []         # No match found

样品运行

In [512]: arr = np.array([2, 0, 0, 0, 0, 1, 0, 1, 0, 0])

In [513]: seq = np.array([0,0])

In [514]: search_sequence_numpy(arr,seq)
Out[514]: array([1, 2, 3, 4, 8, 9])

In [515]: search_sequence_cv2(arr,seq)
Out[515]: array([1, 2, 3, 4, 8, 9])

运行时测试

In [477]: arr = np.random.randint(0,9,(100000))
     ...: seq = np.array([3,6,8,4])
     ...:

In [478]: np.allclose(search_sequence_numpy(arr,seq),search_sequence_cv2(arr,seq))
Out[478]: True

In [479]: %timeit search_sequence_numpy(arr,seq)
100 loops, best of 3: 11.8 ms per loop

In [480]: %timeit search_sequence_cv2(arr,seq)
10 loops, best of 3: 20.6 ms per loop

似乎基于Pure NumPy的是最安全，最快的！