122
Conclusioni
Molte applicazioni, soprattutto quelle realizzate nell’ambito dell’infrastruttura di Internet, devono trattare e gestire enormi database di espressioni regolari, poiché per realizzare determinati compiti sfruttano la potenza del formalismo conciso, e allo stesso tempo espressivo, che le espressioni regolari offrono.
Infatti, basti pensare al filtering, alla classificazione, al routing dei documenti XML e al BGP routing che vengono eseguiti proprio attraverso l’utilizzo di linguaggi basati sulle espressioni regolari. Il problema che si presenta in questo tipo di applicazioni è conosciuto con il nome di RE-retrieval, ovvero recupero di insiemi di espressioni regolari che soddisfano una determinata query string in ingresso all’applicazione. Per risolvere tale problema occorrono strutture dati efficienti che siano in grado di memorizzare oggetti che sono proprio rappresentati da espressioni regolari. Il compito di proporre una nuova struttura dati che memorizza espressioni è alquanto sfidante poiché le espressioni regolari possono rappresentare anche insiemi infiniti di stringhe.
In questa tesi abbiamo proposto un nuovo metodo per indicizzare insiemi di espressioni regolari. In particolare, abbiamo fornito un approccio geometrico
123
basato sulla ricerca in intervalli di stringhe, memorizzati nella struttura dati indice Interval Tree estesa al caso delle stringhe.
La soluzione proposta, studiata con l’intento di trovare un buon compromesso tra semplicità ed efficienza, consiste nell’approssimare una generica espressione regolare attraverso un intervallo di stringhe. Come estremi di un generico intervallo abbiamo considerato la stringa lessicograficamente più piccola (estremo sinistro) e la stringa lessicograficamente più grande (estremo destro) del linguaggio definito dall’espressione regolare presa in considerazione. Abbiamo constatato che non sempre è possibile determinare gli estremi che delimitano un intervallo e questo accade quando in una espressione è presente la stella di Kleene. Per tale motivo abbiamo introdotto alcune nozioni che ci hanno permesso di determinare, seppure in modo approssimato, gli estremi di un intervallo rappresentante una generica espressione caratterizzata dalla presenza della stella di Kleene.
Il metodo proposto in questa tesi, sperimentato sul data set reale di pattern utilizzati per interrogare il database PROSITE, si è rivelato, analizzando i dati ottenuti dalla sperimentazione, efficiente, poiché, come si può notare anche dai grafici esposti nel capitolo 6, per una generica query string in ingresso non si esaminano mai tutti gli intervalli di stringhe che approssimano le espressioni facenti parte dell’intero data set. Quindi, il metodo proposto è molto conveniente rispetto alla scansione sequenziale e dal punto di vista della complessità risulta essere più semplice di quello proposto in [21] (RE-tree), che è invece abbastanza complesso da gestire, soprattutto per quanto riguarda gli algoritmi di mantenimento della struttura, che non sono per nulla semplici. Infatti, la semplicità del metodo che noi proponiamo è da apprezzare perché la ricerca in intervalli è più efficiente da realizzare e comporta una migliore ingegnerizzazione degli algoritmi utilizzati in applicazioni in cui il tempo di risposta è cruciale. La gestione di una struttura dati come il RE-tree in questo tipo di applicazioni potrebbe comportare dei tempi elevati di risposta.
124
In ogni caso, come ulteriore lavoro futuro, sarebbe interessante confrontare la performance della struttura dati RE-tree, considerando però la memorizzazione di data set reali e non sintetici di espressioni regolari, con la performance ottenuta utilizzando il metodo proposto in questa tesi.
Inoltre, risulterebbe molto interessante sperimentare l’applicazione del metodo che proponiamo ad applicazioni realizzate nell’ambito delle reti e che sfruttano linguaggi le cui specifiche richiedono il trattamento di espressioni regolari (ad esempio nel caso del BGP routing).
