Algoritmo di riconoscimento del modello di matrice

Question

Algoritmo di riconoscimento del modello di matrice

#1 da (1 voti)
#2 da (0 voti)

6

Sto progettando un analizzatore logico e vorrei implementare un algoritmo Matrix. Ho diversi canali ciascuno rappresentato da una riga nella matrice e ogni elemento della colonna sarebbe lo stato, ad esempio:

Channel 1   1 0 0 1 0 1 1 0 1
Channel 2   1 1 0 1 1 0 0 1 1
Channel 3   0 1 0 1 1 0 1 0 0

Vorrei rilevare un pattern all'interno della mia matrice per esempio, rilevare TUTTE le corrispondenze della bitmap all'interno della matrice:

1 0
1 1

Penso che possa essere realizzato testando element by element, ma penso che ci dovrebbe essere un modo migliore di farlo. C'è qualche API Java o un modo per farlo? Se c'è un API ARM ottimizzato per le istruzioni NEON sarebbe bello anche se non obbligatorio.

Saranno circa a matrice 8 di 3 o 2 righe per 20000 colonne circa, la matrice non è fissa, cambia ogni volta che la scansione perché sto ricevendo costantemente i dati. Ho bisogno di elaborarli in 500mS o meno. Sto lavorando su una piattaforma ARM, dual core, 1,2 GHz, 1 Gb RAM, Android 4.1.2

Grazie mille in anticipo.

java algorithms algebraic-data-type

posta Andres 18.12.2012 - 01:36

fonte

2 risposte

0

Non so se ci sia un'API Java per farlo, ma una ricerca di "matching di stringhe bidimensionali" o "matching di pattern bidimensionale" fa apparire un sacco di carte. Ad esempio, la tesi di laurea di Martijn van de Rijdt (PDF) esamina diversi algoritmi e (essendo una tesi piuttosto che un diario carta) è probabilmente più leggibile rispetto ai documenti originali.

risposta data 18.12.2012 - 09:14

fonte

Leggi altre domande sui tag java algorithms algebraic-data-type

Come implementare il link di aggregazione figlio-genitore in C ++? Aggregatore eventi ... non riceve risposta, come determinare il completamento?

score 1 · Accepted Answer

EDIT: dopo aver chiarito un po 'le cose, vedo che stai cercando una specie di cosa diversa a cui stavo pensando prima. Quando la tua matrice cambia per ogni ricerca, creare una sorta di struttura di ricerca in anticipo non ti aiuterà molto - invece probabilmente potresti aver bisogno di una libreria di elaborazione bitmap ottimizzata a basso livello (o scrivere il tuo codice nativo in C, analogo a questo esempio ). Anche allora, c'è ancora il problema che dovrai convertire i dati di input nel formato bitmap utilizzato da quella libreria, ogni volta, per ogni singola ricerca. Quindi sicuramente dovrai fare un ciclo su tutti i bit della tua matrice.

Per questo motivo, dubito che tu possa migliorare molto la semplice ricerca di forza bruta che itera su tutta la matrice e confronta solo i valori con i valori della data sottomatrice.