Algoritmi di String Matching

The String Matching problem is a fundamental operation in theoretical computer science and its practical applications, such as text search, bioinformatics, and cybersecurity. This research analyzes and compares the main String Matching techniques, dividing them into four categories: exact matching, regular expression-based matching, approximate matching, and sampled matching. Exact String Matching focuses on searching for a pattern in a text without errors, analyzing classical algorithms such as Naive Matching, Knuth-Morris-Pratt (KMP), Boyer-Moore, and Rabin-Karp. Another relevant technique is the use of Finite State Automata, which model the problem as a deterministic automation to improve search efficiency. Regular Expression String Matching extends the classical model, allowing the search for more complex patterns. The Thompson and Glushkov constructions are analyzed, which convert a regular expression into an NFA (Nondeterministic Finite Automaton). Additionally, automaton simulation is discussed, enabling matching by managing sets of active states or converting an NFA into a DFA to optimize the search process. Approximate String Matching deals with error-tolerant searching, which is essential in fields such as text recognition and bioinformatics. Algorithms analyzed include Naive Approximate Matching, a modified version of naïve matching that allows a maximum number of errors; Levenshtein (Wagner-Fischer), which uses dynamic programming to compute edit distance by considering insertions, deletions, and substitutions; Bitap (Shift-Or), which exploits bitwise operations for fast searching on short patterns; and Ukkonen’s algorithm, which uses finite state automata to optimize edit distance computation in large texts. These algorithms enable finding matches even in the presence of mutations, insertions, or deletions, improving search performance in noisy data. Finally, Sampled String Matching is explored, a hybrid approach that combines indexing techniques with classical algorithms to improve search efficiency in large texts. Methods such as Character Distance Sampling (CDS) and Character Context Sampling (CCS) are discussed, which reduce the number of necessary verifications through the use of pivots and compact data structures. This analysis provides insights into the advantages and limitations of each method, offering a clear overview of String Matching techniques and their applications in various contexts.

Il problema dello String Matching è un’operazione fondamentale nell’informatica teorica e nelle sue applicazioni pratiche, come la ricerca testuale, la bioinformatica e la sicurezza informatica. Questa ricerca analizza e confronta le principali tecniche di String Matching, suddividendole in quattro categorie: esatto, con espressioni regolari, approssimato e basato su sampling. Lo String Matching Esatto si concentra sulla ricerca di un pattern in un testo senza errori, analizzando algoritmi classici come il Matching ingenuo, Knuth-Morris-Pratt (KMP), Boyer-Moore e Rabin-Karp. Un’altra tecnica rilevante è l’uso di automi a stati finiti, che consente di modellare il problema come un’automazione deterministica per migliorare l’efficienza della ricerca. Lo String Matching con Espressioni Regolari estende il modello classico, permettendo la ricerca di pattern più complessi. Vengono analizzate le costruzioni di Thompson e Glushkov, che convertono un’espressione regolare in un NFA (Automa a Stati Finiti Non Deterministico). Inoltre, viene trattata la simulazione degli automi, che permette di eseguire il matching tramite la gestione di insiemi di stati attivi o la conversione in un DFA per ottimizzare la ricerca. Lo String Matching Approssimato affronta la ricerca con tolleranza agli errori, essenziale in ambiti come il riconoscimento testuale e la bioinformatica. Vengono analizzati algoritmi come il Matching ingenuo approssimato, una versione modificata del matching ingenuo che consente un numero massimo di errori; Levenshtein (Wagner-Fischer), che utilizza la programmazione dinamica per calcolare la distanza di edit considerando inserzioni, cancellazioni e sostituzioni; Bitap (Shift-Or), che sfrutta operazioni bitwise per una ricerca veloce su pattern corti; e Ukkonen, basato su automi a stati finiti per ottimizzare il calcolo della distanza di edit nei testi di grandi dimensioni. Questi algoritmi permettono di individuare corrispondenze anche in presenza di mutazioni, inserzioni o cancellazioni, migliorando la ricerca. Infine, viene esplorato il Sampled String Matching, un approccio ibrido che combina tecniche di indicizzazione con algoritmi classici per migliorare l’efficienza della ricerca in testi di grandi dimensioni. Vengono discussi metodi come il Character Distance Sampling (CDS) e il Character Context Sampling (CCS), che riducono il numero di verifiche necessarie attraverso l’uso di pivot e strutture dati compatte. Questa analisi permette di comprendere i vantaggi e le limitazioni di ciascun metodo, fornendo un quadro chiaro delle tecniche di String Matching e delle loro applicazioni nei diversi contesti.