String matching is a fundamental problem in computer science, with a myriad of direct applications into several distinct areas of computing, including information retrieval, data compression, bioinformatics, natual language processing, linguistics and network security. It consists in finding all the occurrences of a pattern x of length m in a text y of length n, both drawn from a common alphabet Σ of size σ. The problem has attracted researchers’ interest over the years, inspiring solutions of particular practical and theoretical interest. Among them, those based on automata deserve a special mention, since they have always led to the design of flexible and efficient algorithms.

Quello dello string matching è un problema fondamentale nell'informatica, con una miriade di problemi di applicazioni dirette in diverse aree distinte dell’informatica, comprese i sistemi di gestione e compressione dei dati, la bioinformatica, l'elaborazione del linguaggio naturale, la linguistica e la sicurezza delle reti. Consiste nel trovare tutte le occorrenze di un pattern x di lunghezza m in un testo y di lunghezza n, entrambi tratti da un alfabeto comune Σ di dimensione σ. Il problema ha attirato negli anni l'interesse dei ricercatori, ispirando soluzioni di particolare interesse pratico e teorico. Tra questi, quelli basati sugli automi meritano una menzione speciale, poiché hanno sempre portato alla progettazione di strutture flessibili e algoritmi efficienti.

Rappresentazioni compatte dell'automa suffisso per lo string matching

SCAFITI, STEFANO
2024

Abstract

String matching is a fundamental problem in computer science, with a myriad of direct applications into several distinct areas of computing, including information retrieval, data compression, bioinformatics, natual language processing, linguistics and network security. It consists in finding all the occurrences of a pattern x of length m in a text y of length n, both drawn from a common alphabet Σ of size σ. The problem has attracted researchers’ interest over the years, inspiring solutions of particular practical and theoretical interest. Among them, those based on automata deserve a special mention, since they have always led to the design of flexible and efficient algorithms.
12-feb-2024
Italiano
Quello dello string matching è un problema fondamentale nell'informatica, con una miriade di problemi di applicazioni dirette in diverse aree distinte dell’informatica, comprese i sistemi di gestione e compressione dei dati, la bioinformatica, l'elaborazione del linguaggio naturale, la linguistica e la sicurezza delle reti. Consiste nel trovare tutte le occorrenze di un pattern x di lunghezza m in un testo y di lunghezza n, entrambi tratti da un alfabeto comune Σ di dimensione σ. Il problema ha attirato negli anni l'interesse dei ricercatori, ispirando soluzioni di particolare interesse pratico e teorico. Tra questi, quelli basati sugli automi meritano una menzione speciale, poiché hanno sempre portato alla progettazione di strutture flessibili e algoritmi efficienti.
FARO, SIMONE
Università degli studi di Catania
Catania
File in questo prodotto:
File Dimensione Formato  
Phd_Thesis_latest.pdf

accesso aperto

Dimensione 1.13 MB
Formato Adobe PDF
1.13 MB Adobe PDF Visualizza/Apri

I documenti in UNITESI sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14242/77380
Il codice NBN di questa tesi è URN:NBN:IT:UNICT-77380