Die Indizes eines Sub-Arrays in einem Array zurückgeben

Question

Ich benutze Python mit numpy.

Ich habe eine numpy Array may_a:

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

Ich habe eine numpy Array may_b:

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

Ich brauche may_a Array may_b in Reihe zu finden.

In der Ausgabe muss ich Indizes der Vorkommen erhalten.

out_index=[2,7] 

Kann jemand bitte vorschlagen, wie bekomme ich out_index?

Answer 1

EDIT Der folgende Code eine Faltung basierte Prüfung der Gleichheit auszuführen erlaubt. Es bildet True bis 1 und False bis -1 ab. Es kehrt auch b, die benötigt wird, um richtig zu funktionieren:

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

Ich habe überprüft, dass sie die gleiche Ausgabe wie die as_strided Verfahren für eine Vielzahl von zufälligen Eingänge gibt, die es tut. Ich habe auch beide zeitlich angefahren, und Convolution fängt erst an, mit größeren Suchmarkern von rund 256 Items zu bezahlen.

---

Es scheint wie ein wenig Overkill, aber mit booleschen Daten, die Sie verwenden können (Missbrauch?Faltung):

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

Für größere Datenmengen kann es schneller gehen mit 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]) 

Sie müssen aber vorsichtig sein, denn der Ausgang jetzt Punkt schwimmt, und Rundung kann die Gleichheit verderben Check:

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

So können Sie mit etwas entlang der Linien von besser dran:

Answer 2

Ich bin nicht sicher, ob numpy eine Funktion dafür bereitstellen. Wenn dies nicht der Fall, hier ist eine Lösung:

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

Dies sollte auch mit anderen, dass boolean Daten arbeiten:

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

Ein viel cooler Ansatz, der eine gut nicht durchführen kann, die aber für jeden dtype arbeitet, ist die Verwendung 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]) 

Sie müssen aber vorsichtig sein, denn obwohl a_view eine Ansicht von may_a ‚s Daten vorhanden sind, wenn sie mit may_b ein temporäres Array von (a - b + 1) * b Vergleich geschaffen, die w ein Problem sein kann, ith large a s und b s.

Answer 5

Dies sieht einem string search problem sehr ähnlich. Wenn Sie vermeiden möchten, man diese Zeichenfolge Suchalgorithmen Implementierung, könnten Sie Pythons in String-Suche gebaut missbrauchen, die sehr schnell ist, um so etwas wie tun:

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

Dies sollte für Boolesche Arrays funktionieren. Wenn Sie diesen Ansatz für einen anderen Array-Typ verwenden möchten, müssen Sie sicherstellen, dass die Schritte der beiden Arrays übereinstimmen und out_index um diesen Schritt teilen.

Sie könnten auch die regular expression module anstelle der Schleife verwenden, um die String-Suche zu tun.