Giovedì 26 Giugno
Andrea Baronchelli
Estrazione di informazione da sequenze di simboli mediante algoritmi di compressione dati
ore 17:30
Università di Roma I

Abstract

Quando si analizza una stringa di caratteri il problema principale e' conoscere, e quindi estrarre, l'informazione che vi e' contenuta. In questo intervento illustrero' alcuni metodi di estrazione di informazione basati sull'utilizzo dell'algoritmo di compressione LZ77. Questo zipper comprime una stringa leggendola in modo sequenziale e sostituendo ciascuna serie di caratteri ripetuti con un puntatore alla precedente occorrenza di quella serie. Detto dizionario di una sequenza l'insieme delle stringhe sostituite da LZ77, presentero' uno studio statistico dei dizionari di diverse sequenze (random, testi letterari, DNA). Dopo aver definito i cosiddetti testi artificiali a partire dai dizionari, mostrero' poi come, confrontando testi artificiali, si possano identificare le proprieta' di un testo (l'argomento, la lingua, l'autore) o costruire alberi linguistici e filogenetici piu' accuratamente di quando si confrontino le sequenze originali.