La ricerca di un team di Unict, con numerose ricadute nel campi dell’informatica, ha ricevuto un riconoscimento al recente Symposium on Experimental Algorithms di Vienna
Il problema dello string-matching, o corrispondenza tra stringhe, trova efficacia in un grande insieme di applicazioni nei diversi campi della ricerca.
La problematica consiste nel trovare tutte le occorrenze di una parola o di una sequenza di caratteri (la "stringa modello") all'interno di un testo più lungo (la "stringa di ricerca"). In altre parole, si tratta di determinare dove e quante volte una specifica sequenza di caratteri appare in un documento più grande.
In sintesi si tratta di una pietra miliare dell'informatica, con applicazioni che vanno dalla ricerca web alla medicina, dall'educazione alla sicurezza informatica. La sua importanza, infatti, risiede nella capacità di estrarre rapidamente informazioni rilevanti da enormi quantità di dati, migliorando la nostra capacità di comprendere e interagire con il mondo digitale.
Nonostante sembri un problema semplice, il string matching può essere estremamente complesso, soprattutto quando si tratta di testi molto grandi o quando si cercano stringhe con variazioni e errori. Diversi algoritmi sono stati sviluppati per affrontare queste sfide, ottimizzando la velocità e l'efficienza delle ricerche.
Pertanto il problema dello string matching rappresenta di fondamentale importanza nel campo della ricerca di oggi e del futuro.
E proprio nei giorni scorsi un team “targato” Unict – grazie al lavoro intitolato Efficient Exact Online String Matching Through Linked Weak Factors - ha ricevuto un importante riconoscimento alla conferenza Symposium on Experimental Algorithms 2024 che si è tenuta a Vienna nei giorni scorsi.
Il lavoro – realizzato da Simone Faro del Dipartimento di Matematica e Informatica dell'Università di Catania, da Mattew Palmer della British Computer Society e da Stefano Scafiti, recentemente nominato dottore di ricerca in Informatica nell’ateneo catanese - si è classificato come best ranked paper e ha ottenuto una menzione speciale da parte del Program Chair, il prof. Leo Liberti, direttore di ricerca del Centre national de la recherche scientifique (CNRS) in Francia.
In foto da sinistra Simone Faro, Mattew Palmer e Leo Liberti
“Il premio riconosce il nostro impegno nella ricerca e nello sviluppo di un algoritmo innovativo per la risoluzione del problema dello string matching esatto che risulta allo stato attuale il più efficiente tra quelli attualmente esistenti in letteratura”, spiega il prof. Simone Faro.
“Soprattutto perché la nostra ricerca è stata premiata dalla SEA, una conferenza di rilevanza internazionale che attira contributi dalla comunità dell'informatica, dalla ricerca operativa/programmazione matematica e da altre comunità scientifiche, focalizzandosi sul ruolo della sperimentazione e delle tecniche di ingegneria degli algoritmi nel design e nella valutazione di algoritmi e strutture dati”, precisa il ricercatore dell’ateneo catanese.
“La nostra scoperta potrebbe avere notevoli ricadute nei settori dell’informatica, ma anche della bioinformatica, analisi dei testi e sicurezza informatica e altri settori – aggiunge -. Da anni mi dedico allo studio del text processing e ho pubblicato in questi anni una survey che analizza in dettaglio il problema dello string matching e le sue soluzioni”.
In merito alle sue applicazioni, lo string matching è cruciale per molte applicazioni quotidiane e settori diversi.
Basti pensare ai motori di ricerca. Ogni volta che digitiamo una parola su un motore di ricerca, questo utilizza algoritmi di string matching per trovare e mostrare i risultati più pertinenti in una frazione di secondo. Questo permette di navigare tra miliardi di pagine web e ottenere informazioni utili in modo rapido ed efficiente.
Nel campo della genetica, il confronto di sequenze di DNA è essenziale per identificare geni, trovare mutazioni o comprendere le relazioni evolutive tra diverse specie. Gli algoritmi di string matching aiutano gli scienziati a confrontare lunghe sequenze di nucleotidi, accelerando la ricerca e la diagnosi medica.
E ancora nei settori dell'educazione e della pubblicazione, il rilevamento del plagio è un'attività fondamentale. Software specializzati utilizzano tecniche di string matching per confrontare documenti e identificare somiglianze sospette, garantendo l'integrità accademica e intellettuale.
Gli algoritmi di string matching sono utilizzati anche nel campo della sicurezza informatica per individuare malware e attività sospette analizzando grandi volumi di dati di rete e confrontando sequenze di codice con modelli conosciuti di minacce.