Il miglior metodo per la corrispondenza dei modelli sulla stringa binaria?

Question

Il miglior metodo per la corrispondenza dei modelli sulla stringa binaria?

#1 da (4 voti)

3

Ho bisogno di cercare una lunga stringa di dati di stringa binaria (un paio di megabyte di cifre binarie) per i modelli di cifre binarie. Ci sono circa 100 000 modelli diversi da cercare. Ciascuno è un massimo di 10 bit / pattern di lunghezza del carattere di 1 e 0. Ho quindi bisogno di visualizzare il modello più comune di tutti questi.

I dati binari vengono inviati in tempo reale a una sorta di file di testo o database. È essenzialmente un grande blocco di cifre binarie che ho bisogno di cercare un paio di migliaia di modelli diversi nel modo più veloce possibile. Ogni nuova cifra in entrata lo fa in circa 10 secondi di tempo uno dopo l'altro.

Quindi, ad esempio, potrebbe esserci la seguente stringa:

10101110000110001011011111000101011010111101110100000011011101010101010111011100101010101011000101110011011111110001010010000110101011100000110011100101001010011001011010110101101010001010101010100010101010010100101001010101010111010101010010100101010011101010101010101001001010110101

e ho bisogno di trovare quello che è il più comune tra questi 100.000 pattern, come 0001100111 , 0110011011 , 1100011 e così via.

Qual è il modo migliore per farlo sui dati in tempo reale che vengono inseriti in un file di testo? Non ha davvero bisogno di essere esattamente in tempo reale, ma preferirei che fosse il più realistico possibile. D'altronde, è piuttosto una questione di console diritta, in modo da renderla il più libera possibile, ma posso adattarmi in quanto non ha nemmeno bisogno di essere terminale.

Ho circa 1 anno di esperienza di programmazione in Bash. Un semplice script bash sarebbe abbastanza veloce per 100.000 di tali pattern? Ma tutte quelle migliaia di schemi mi fanno temere che solo una semplice soluzione di script bash potrebbe essere un po 'troppo lenta e obsoleta. O SQL può essere davvero più veloce di un semplice script di bash? Ho sentito parlare di algoritmi di corrispondenza binaria, ma non so davvero cosa siano e sembra un po 'fuori dal mio campionato al momento, tuttavia sono disposto a scendere a fondo se è davvero il modo più efficace. Qual'è il miglior modo per farlo ?

algorithms binary search pattern-matching

posta user289944 03.12.2017 - 00:00

fonte

1 risposta

Leggi altre domande sui tag algorithms binary search pattern-matching

Il rallentamento dei commit è necessariamente indicativo del debito in codice? Costruire un solido vocabolario quando si lavora in un dominio specifico

score 4 · Answer 1

Istruzione dei problemi riformulati

Hai un enorme% binario% di co_de e dovrai scansionarlo per un set di migliaia di bit content . Il problema principale è che i pattern di bit possono verificarsi ovunque nel contenuto e non solo all'inizio di un byte.

Soluzione algoritmica

Diciamo che ogni modello ha un id, un offset di bit iniziale 0, una lunghezza di bit ed è definito in una sequenza di byte allineati sul bit più significativo del primo byte. La sequenza di byte deve essere abbastanza lunga da contenere altri 7 bit (ad esempio patterns dove i punti rappresentano bit inutilizzati nei byte di modello che verranno impostati su 0 e tratteggiare una modifica di byte).

Costruite per ogni schema le 7 derivate ottenute spostando i bit di tutti i pattern di un offset da 1 a 7 (ad esempio 110110..-........ , .110110.-........ , ..110110-........ , ecc ...), e memorizza tutti e 7 di essi e il modello originale in una mappatura ...11011-0....... nell'id del modello.
Per ogni elemento map :
1. Per ogni offset di byte di map , in modo che la lunghezza del contenuto rimanente sia sufficientemente lunga rispetto alla lunghezza content dei byte del modello:
  1. Crea una copia dei byte di contenuto n e imposta i primi bit di offset della copia su 0. Imposta anche% last% di ultimi bit su 0.
  2. confronta la copia alterata con il pattern, byte per byte. Se ogni byte è uguale, aumentare il conteggio per il modello mappato.
Ordina i modelli diminuendo il numero di pattern

Questo algoritmo sarà molto veloce perché il passo 5 viene eseguito per confronto di byte, come per le stringhe. Il passaggio 4 è veloce, poiché si basa su due operazioni binarie AND sulla copia.