Возвращает индексы подматрицы в массиве

Question

Я использую 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_b в массиве may_a.

На выходе мне нужно получить индексы вхождений.

out_index=[2,7] 

Может кто-то пожалуйста, предложить, как получить out_index?

Answer 1

EDIT Следующий код действительно позволяет выполнить проверку на основе свертке равенства. Он отображает 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]) 

Answer 2

Я не уверен, обеспечивает ли 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. 

Answer 3

Это должно также работать с другими, что булева данных:

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

Answer 4

более симпатичное подход, который не может выполнить хорошо, но работает для любого DTYPE, является использование 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 «s, при сравнении его с may_b временный массив (a - b + 1) * b создается, что может быть проблемой ш с большими a s и b s.

Answer 5

Это очень похоже на string search problem. Если вы хотите, чтобы избежать реализации одного из этих алгоритмов строки поиска, вы могли бы злоупотреблять питонов встроенные в строку поиска, которая очень быстро, делая что-то вроде:

# 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 на этот шаг.

Вы также можете использовать regular expression module вместо цикла, чтобы выполнить поиск по строкам.