Algoritmi per ricerca pattern simili

di damien il
7 risposte
Pochi posts
Iscritto da
ago, 2021
Messaggi
12
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

  • Super Famoso
    Iscritto da
    apr, 2013
    Messaggi
    6267
    La domanda e' troppo generica.
    Comunque la bioinformatica ha sviluppato diversi algoritmi per la ricerca di sottostringhe nel DNA che supporta piccole variazioni.
  • Pochi posts
    Iscritto da
    ago, 2021
    Messaggi
    12
    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.
  • Super Famoso
    Iscritto da
    nov, 2011
    Messaggi
    21917
    Non è una questione affatto semplice.
    Per curiosità, di cosa si tratta, senza scendere nei dettagli?
  • Pochi posts
    Iscritto da
    ago, 2021
    Messaggi
    12
    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..
  • Pochi posts
    Iscritto da
    ago, 2021
    Messaggi
    12
    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..
  • Pochi posts
    Iscritto da
    set, 2020
    Messaggi
    23
    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.
  • Pochi posts
    Iscritto da
    feb, 2021
    Messaggi
    2
    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