Return the indexes of a sub-array in an array

Question

I use Python with numpy.

I have a numpy array may_a:

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

I have a numpy array may_b:

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

I need to find array may_b in array may_a.

In the output I need to get indexes of occurrences.

out_index=[2,7]

Can someone please suggest, how do I get out_index?

Answer 1

EDIT The following code does allow to perform a convolution based check of equality. It maps True to 1 and False to -1. It also reverses b, which is needed for it to work properly:

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

I have checked that it gives the same output as the as_strided method for a variety of random inputs, which it does. I have also timed both approached, and convolution only starts paying off with largish search tokens of around 256 items.

---

It seems like a little overkill, but with boolean data you can use (abuse?) convolution:

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

For larger datasets it may be faster to go with 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])

You have to be careful though, because the output now is floating point, and rounding may spoil the equality check:

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

So you may be better off with something along the lines of:

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])