L’algoritmo di Knuth-Morris-Pratt

Lasciamo per un attimo in sospeso il discorso sulla compressione per trattare un argomento altrettanto interessante: la ricerca in un testo. Detto in modo più formale ci interessa di conoscere se un pattern P occorre in un testo T.

Per fare questo possiamo considerare le stringhe come array di caratteri P[0]P[1]…P[m] e T[0]T[1]…T[n], ovviamente con con n>m. L’algoritmo cosiddetto a forza bruta (brute-force o naive) è molto semplice e consiste nel provare tutte le possibili soluzioni. Si scorre quindi tutto il testo e si prova a fare match del pattern. Tutto ciò ha complessità O(nm) in quanto si risolve banalmente in due cicli annidati.

Tale approccio, sebbene apparentemente inefficiente, risulta ragionevole in caso pattern piccoli (< 10 caratteri). Il problema principale di tale algoritmo è che non sfrutta l’informazione del pattern; se ad esempio ci troviamo ad un mismatch possiamo in alcuni casi ricominciare ad effettuare confronti ripartendo da una posizione P[i] con i > 0. Per farlo creiamo una tabella che ci dice di quanto possiamo avanzare senza perdere occorrenze basandoci sul prefisso più lungo del pattern che sia anche un suo suffisso: il bordo. In pratica quando abbiamo un mismatch abbiamo già confrontato parte del pattern con il testo e questa tecnica ci permette di usare quei confronti senza rifarli di nuovo.

Huffman Coding

Come da richiesta proseguiamo con un classico della compressione, la codifica di Huffman. Tale algoritmo rientra in quelli statistici e si basa sul concetto di assegnare codewords più corte ai simboli più frequenti. Per farlo parte da una distribuzione di probabilità per i vari simboli dell’alfabeto e da questa crea un albero binario prefix-free (in pratica non esiste una codeword che sia prefisso di un’altra in modo da evitare ambiguità in decodifica).

Run-Length Encoding

Questo è il primo di una serie di articoli (forse, se ne avrò voglia e tempo) inerenti alla compressione dei dati. La cosa verrà trattata nel modo più pragmatico possibile riducendo all’osso i simbolini matematici.

Per iniziare ho scelto una forma di codifica senza perdita usata generalmente nei fax (insieme ad altra “roba” che vedremo in seguito). L’idea alla base è molto semplice: sequenze di dati contigue ripetute vengono trasformate in una coppia (simbolo, #occorrenze). Ad esempio la stringa aaabbccccc sarà rappresentata da (a,3)(b,2)(c,5). Tra i formati basati su questo principio ricordiamo PackBits di Apple, introdotta con il MacPaint ed usata a volte nei file tiff. Vediamone ora una semplice implementazione in Python.