Algoritmi per ricerca pattern simili

di il
7 risposte

Algoritmi per ricerca pattern simili

Buongiorno,
Ho la necessità di realizzare un software che "scovi" alcuni pattern binari all'interno di file da circa 10MB; attualmente con boyermoore riesco a trovarli abbastanza velocemente; il problema è che spesso vi sono delle varianti a queste stringhe binarie, che non vengono quindi identificate; Qualcuno ha qualche dritta?

7 Risposte

  • Re: Algoritmi per ricerca pattern simili

    La domanda e' troppo generica.
    Comunque la bioinformatica ha sviluppato diversi algoritmi per la ricerca di sottostringhe nel DNA che supporta piccole variazioni.
  • Re: Algoritmi per ricerca pattern simili

    Cerco di descrivere meglio il problema:
    attualmete l'operatore carica il file binario in oggetto in un'applicazione che visualizza in un grafico a linee tutti i valori dei bytes che contiene, quindi osserva il grafico in cerca di determinate "forme" assunte dallo stesso, e ne annota la posizione per segnalarle al reparto successivo. Purtroppo questo richiede una formazione molto lunga,in quanto il riconoscimento o meno del pattern è dato in gran parte dalla perizia e dall'esperienza dell'operatore. Ora dispongo di un archivio dei pattern più ricorrenti, che viene usato sia per un confronto visivo, sia dal prototipo di applicazione che sto cercando di sviluppare, che però utilizzando un algoritmo di ricerca stringhe esatta, non rileva le eventuali varianti.
  • Re: Algoritmi per ricerca pattern simili

    Non è una questione affatto semplice.
    Per curiosità, di cosa si tratta, senza scendere nei dettagli?
  • Re: Algoritmi per ricerca pattern simili

    Già, ho dato un occhio anche a ML.net e altri sistemi di machine learning, ma non sono riuscito a capire se possono fare al caso mio, gli esempi che ho visto sono usati per catalogazioni o previsioni, non ricerche..
  • Re: Algoritmi per ricerca pattern simili

    Update: Sono riuscito utilizzando un algoritmo di ricerca che usa la metrica. No so spiegarmi meglio, è una cosa che ho trovato e per le quali non ho proprio le competenze, ma funziona..
  • Re: Algoritmi per ricerca pattern simili

    Puoi provare con la distanza di levenshtein.

    Puoi modificare l'algoritmo base in modo che tenga conto di una determinata soglia di differenza.

    Per inciso, l'algoritmo calcola la differenza fra stringhe e può tornarti utile in aggiunta ad ulteriori strumenti come le sottostringhe ed eventualmente le espressioni regolari.
  • Re: Algoritmi per ricerca pattern simili

    La sparo li, si potrebbe utilizzare una cross-correlazione?
    Un secolo fa, quando ero studente, ricordo di un esempio che permetteva di scovare una sequenza di bit in un segnale avente NSR 60dB, cioè il rumore 1000 volte più ampio del segnale, proprio grazie alla x-corr.
    Si faceva in MATLAB con le funzioni built-in.
Devi accedere o registrarti per scrivere nel forum
7 risposte