Suche eine Sequenz in einem NumPy Array

Question

Lassen Sie uns sagen, dass ich die folgende Array:

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

Wie kann ich die Indizes bekommen, wo ich Auftreten Folge von Werten haben: [0,0]? Die erwartete Ausgabe für einen solchen Fall wäre also: [1,2,6,7].

Edit:

1) Bitte beachten Sie, dass [0,0] nur eine Sequenz ist. Es könnte [0,0,0] oder [4,6,8,9] oder [5,2,0], einfach alles sein.

2) Wenn mein Array geändert wurde zu: array([2, 0, 0, 0, 0, 1, 0, 1, 0, 0]), wäre das erwartete Ergebnis mit der gleichen Sequenz [0,0][1,2,3,4,8,9].

Ich bin auf der Suche nach einer NumPy-Verknüpfung.

Answer 1

Nun erfüllen sollte, ist dies im Grunde ein template-matching problem das kommt in der Bildverarbeitung sehr oft vor. In diesem Beitrag sind zwei Ansätze aufgeführt: Pure NumPy basiert und OpenCV (cv2) basiert.

Ansatz # 1: Mit NumPy kann man ein 2D Array gleitender Indizes über die gesamte Länge des Eingangsarrays erstellen. Somit wäre jede Reihe ein gleitendes Fenster von Elementen. Ordnen Sie als nächstes jede Zeile der Eingabesequenz zu, die broadcasting für eine vektorisierte Lösung enthält. Wir suchen nach allen True Zeilen, die anzeigen, dass diejenigen diejenigen sind, die die perfekten Übereinstimmungen sind, und als solche wären die Startindizes der Spiele. Unter Verwendung dieser Indizes erstellen Sie schließlich eine Reihe von Indizes, die sich bis zur Länge der Sequenz erstrecken, um die gewünschte Ausgabe zu erhalten. Die Umsetzung wäre -

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, 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 2D array of sliding indices across 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 

Ansatz # 2: Mit OpenCV (cv2), haben wir eine integrierte Funktion für template-matching: cv2.matchTemplate. Damit hätten wir die passenden Startindizes. Der Rest der Schritte wäre der gleiche wie für den vorherigen Ansatz. Hier ist die Umsetzung mit 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 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 

---

Probelauf

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

Runtime Test

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 

scheint, wie die reine NumPy Basis ist die sicherste und schnellste t!

Answer 2

Hier ist eine Möglichkeit, es mit einem forloop zu tun

def find_seq(a_list, val): 

    seqs = [] 
    for i, item in enumerate(a_list[:-1]): 
     if item == val and a_list[i + 1] == val: 
      #or you could append a tuple: seqs.append((i, i+1)) 
      seqs.append(i) 
      seqs.append(i + 1) 
    return seqs 

print(find_seq([2, 0, 0, 1, 0, 1, 0, 0], 0)) 

Ergebnis:

[1, 2, 6, 7] 

Answer 3

Ich denke, dass dies Ihre Anforderungen

def search(seq, lst): 
    ls, ll = len(seq), len(lst) 
    r = range(ls) 
    res = [] 
    i = 0 
    while i<ll-ls: 
     if lst[i:i+ls]!=seq: 
      i = i+1 
     else: 
      res = res + [i+j for j in r] # concatenate list of indices and new indices 
      i = i+ls      # advance index after the match 
    return res