logo标签列表

返回数组中子数组的索引

pythonarraysnumpy
8

我使用Python和numpy。

我有一个numpy数组may_a:

may_a = numpy.array([False, True, False, True, True, False, True, False, True, True, False])

我有一个NumPy数组may_b：

may_b = numpy.array([False,True,True,False])

我需要在数组may_a中找到数组may_b。

输出结果需要包含出现的索引。

out_index=[2,7]

请问有人可以建议一下，我该如何获得out_index？

你是不是想说 out_index=[2,6]？ - Konfle Dolex
1
@Konfle Dolex，out_index=[2,7] - Olga
@Olga 啊。我误读了你的问题。 - Konfle Dolex
@Robin，不，这是寻找最佳决策。 - Olga
5个回答
5

编辑 以下代码可以执行基于卷积的相等性检查。它将True映射为1，将False映射为-1。它还反转了b，这对其正常工作是必需的：

def search(a, b) :
    return np.where(np.round(fftconvolve(a * 2 - 1, (b * 2 - 1)[::-1],
                                         mode='valid') - len(b)) == 0)[0]

我已经检查了大量随机输入，发现与as_strided方法给出的输出相同。我也比较了两者的时间效率，当搜索令牌大约为256项时，卷积方法才开始节省时间。

虽然看起来有点过度，但对于布尔数据，您可以使用（滥用？）卷积：

In [8]: np.where(np.convolve(may_a, may_b.astype(int),
   ...:                      mode='valid') == may_b.sum())[0]
Out[8]: array([2, 7])

对于较大的数据集，使用scipy.signal.fftconvolve可能会更快：

In [13]: np.where(scipy.signal.fftconvolve(may_a, may_b,
   ....:                                   mode='valid') == may_b.sum())[0]
Out[13]: array([2, 7])

然而，您必须小心，因为输出现在是浮点数，四舍五入可能会破坏等式检查：

In [14]: scipy.signal.fftconvolve(may_a, may_b, mode='valid')
Out[14]: array([ 1.,  1.,  2.,  1.,  1.,  1.,  1.,  2.])

因此，你最好选择类似这样的东西：
In [15]: np.where(np.round(scipy.signal.fftconvolve(may_a, may_b, mode='valid') -
   ....:                   may_b.sum()) == 0)[0]
Out[15]: array([2, 7])
1
使用这个卷积，你将匹配任何形如[*, True, True, *]的东西，其中 * 是通配符。 - Bi Rico
1
@BiRico 哎呀，你说得完全正确！也许有挽救这个方法的机会，可以将“True”和“False”映射到一些整数值上，可能是“+1”和“-1”。 - Jaime
@Jaime `>>> may_a = np.array([True,True,True,True])
out_ind = np.where(np.convolve(may_a, may_b.astype(int),mode='valid') == may_b.sum())[0] out_ind -> array([0])` 这是不正确的。
 - Olga
1
@Olga 是的，这就是 BiRico 所说的。但我在答案顶部编辑的方法很好用：out_ind = np.where(np.convolve(may_a * 2 - 1, (may_b * 2 - 1)[::-1], mode='valid') == len(may_b)) - Jaime
@Jaime 如果数组是二维的呢？may_a = np.array([[0,1,2],[2,3,1],[3,4,5],[3,3,3]]); may_b = np.array([[3,3,3],[2,3,1]]); 这种方法失败了。 - machen
5

一种更酷的方法是使用as_strided，虽然性能可能不如其他方法，但适用于任何数据类型：

In [2]: from numpy.lib.stride_tricks import as_strided

In [3]: may_a = numpy.array([False, True, False, True, True, False,
   ...:                      True, False, True, True, False])

In [4]: may_b = numpy.array([False,True,True,False])

In [5]: a = len(may_a)

In [6]: b = len(may_b)

In [7]: a_view = as_strided(may_a, shape=(a - b + 1, b),
   ...:                     strides=(may_a.dtype.itemsize,) * 2)

In [8]: a_view
Out[8]: 
array([[False,  True, False,  True],
       [ True, False,  True,  True],
       [False,  True,  True, False],
       [ True,  True, False,  True],
       [ True, False,  True, False],
       [False,  True, False,  True],
       [ True, False,  True,  True],
       [False,  True,  True, False]], dtype=bool)

In [9]: numpy.where(numpy.all(a_view == may_b, axis=1))[0]
Out[9]: array([2, 7])

请注意，即使a_view是may_a数据的一个视图，在与may_b进行比较时，也会创建临时数组(a - b + 1) * b，对于大的a和b可能会有问题。

4
或许你喜欢指出一些小细节……使用 .strides[0] 而非 .itemsize 更加不容易出错，因为在数组之前进行了切片的情况下。 - seberg
3
这看起来非常类似于string search problem。如果您想避免实现这些字符串搜索算法之一，您可以滥用Python内置的字符串搜索，这非常快，例如：
# I've added [True, True, True] at the end.
may_a = numpy.array([False, True, False, True, True, False, True, False, True, True, False, True, True, True])
may_b = numpy.array([False,True,True,False])

may_a_str = may_a.tostring()
may_b_str = may_b.tostring()

idx = may_a_str.find(may_b_str)
out_index = []
while idx >= 0:
    out_index.append(idx)
    idx = may_a_str.find(may_b_str, idx+1)

这对于布尔数组应该可以正常工作。如果您想将此方法用于另一种数组类型，则需要确保两个数组的步幅匹配，并将 out_index 除以该步幅。
您也可以使用 正则表达式模块 而不是循环来进行字符串搜索。
2
这也适用于其他布尔数据类型：
In [1]: import numpy as np

In [2]: a = np.array([False, True, False, True, True, False, True, False, True, True, False])

In [3]: b = np.array([False,True,True,False])

In [4]: def get_indices(a, b):
   ...:     window = len(b)
   ...:     shape = a.shape[:-1] + (a.shape[-1] - window + 1, window)
   ...:     strides = a.strides + (a.strides[-1],)
   ...:     w = np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)
   ...:     return np.where(np.all(np.equal(w,b),1) == True)[0]

In [5]: get_indices(a,b)
Out[5]: array([2, 7])
我改变了一个数组a。 >>> a=np.array([False,False]) >>> b=np.array([False,True,True,False]) >>> get_indices(a,b) >>> Out: ValueError: negative dimensions are not allowed - Olga
1
@Olga -- 是的，shape 将会是 (-1, 4)，你可以添加 if len(a) < len(b): return np.array([]) 来防止这种情况，因为在这种情况下 b 不可能是 a 的子数组。 - root
1

我不确定numpy是否提供了这样的函数。如果没有，这里有一个解决方案：

import numpy

def searchListIndexs(array, target):
    ret = []
    iLimit = len(array)-len(target)+1
    jLimit = len(target)
    for i in range(iLimit):
        for j in range(jLimit):
            if array[i+j] != target[j]:
                break
        else:
            ret.append(i)
    return ret


may_a = numpy.array([False, True, False, True, True, False, True, False, True, True, False])
may_b = numpy.array([False,True,True,False])
out_index = searchListIndexs(may_a, may_b)
print out_index #If you are using Python 3, then use print(out_index) instead.
是的。:( 这是这种方法的局限性。 - Konfle Dolex
顺便说一句，我猜这没有比这更快的算法了。我猜测需要遍历整个数组，因为在这种情况下无法进行排序。 - Konfle Dolex
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接