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.

Ubuntu: creare divx da Dvd in 4 click

Cari pidduisti non preoccupatevi, questo non diventerà un blog pieno di anomini articoli tecnici sull’ultima release di KDE. La casa del piddu è di un’altra categoria. Ho notato però che rete manca un tutorial su come rippare un dvd e trasformarlo in divx. Ho abbandonato i vecchi sistemi microzozz (diciamocelo, Linux fa molto più figo) e per lavorare su video & co. viaggio in genere su Mac. Ieri sera però non avevo voglia di tirare fuori il portatile, dunque ho cercato di sfruttare il mio vecchio e caro desktop con Ubuntu (Dapper Drake) on board. [No Ragazzo Strambo, non ho voglia di aggiornare la distro].

Meno chiacchiere e passiamo ai fatti.

Robin Hood: rubare ai poveri per dare a chi? [Reprise]

Il giorno dopo è sempre quello della riflessione. Siamo andati dai carramba per la denuncia di rito, e abbiamo avuto il piacere di scambiare due chiacchiere mentre attendevamo il nostro turno. Prima è arrivata la signora Ada Lovelace, che ci ha raccontato per filo e per segno lo scippo che aveva appena subito in via Derna. Una volta finito di raccontare, ha ricominciato dall’inizio con la stessa storia, ma più approfondita. Prima che iniziasse per la terza l’abbiamo fatta passare avanti. E’ arrivata quindi una bella ragazza pisana, anche lei con un furto da denunciare. Dopo un paio di battute, su cui spicca:

–Siete pisani?–
–Se dio vole, no.–

L’avvenente tipa ci ha scambiato per siciliani, nonostante nessuno di noi abbia detto bedda madre.

Parlando coi carramba, abbiamo capito che ormai anche qui questo genere di visite è prassi. Forse dovremmo fermarci un attimo e capire cosa stia succedendo, il “dalli allo zingaro!” serve a poco o niente. Meno ancora può essere utile una soluzione “flambé”, tipo quelle proposte da qualche acuto lettore nel precedente post. A proposito, mi scuso per aver segnalato quel lettore al filtro anti-spam akismet, ma purtroppo ho una cronica allergia ai fascisti.

La conclusione a cui giungono tutti quando si commentano questi fatti di cronaca è: quelle sono persone che non hanno niente da perdere. Per questo si arrischiano ad arrampicarsi su per le grondaie in cerca di soldi non propriamente guadagnati. La sfida da vincere sta proprio qui, mettere meno gente possibile nelle condizioni di non aver niente da perdere. Una battaglia per ora più che persa, non a caso la nostra società sta implodendo: finite le scorte economiche accumulate dalle famiglie, anche i giovani saranno sulla strada. In questi ultimi 15 anni siamo stati governati dal capitalismo, ora finalmente abbiamo la dimostrazione che era un cavallo perdente. E pensare che c’era chi lo diceva già dal 1848.

Robin Hood: rubare ai poveri per dare a chi?

Da non crederci. Tornare a casa dopo aver fatto la spesa, andare al bagno a lavarsi le mani e trovare la finestra del bagno spaccata. Ma raccontiamola meglio.

Verso le ore 18:20 i pidduisti si recano all’Eurospin per rimpinguare le esigue scorte alimentari di casapiddu. Tornati alle 19:16, i fab four (in realtà three più bacciamerda) iniziano a mettere a posto le varie buste di roba ed iniziano bellamente a preparare la cena. Rambo decide che forse è meglio lavarsi le mani prima di toccare del cibo, e si avvia al bagno. Lì la scioccante sorpresa.

il vetro del bagno di casapiddu

Pezzi di vetro (non quelli di De Gregori) sparsi per tutto il bagno (che tra l’altro Rambo stesso aveva pulito la settimana scorsa).

Levi Montalcini disco pub

Seratona di quelle indimenticabili. Dopo la parentesi giornalistico-lavorativa, con la combriccola s’era deciso per andare a vedere i Killer Queen, official tribute band italiana di Brian May e soci. Non saranno i veri queen, ma suonano veramente da paura. Invece che si fa che non si fa, si finisce al cantiere 21, guidati con maestria dal re della movida perugina, aka il barista capo del Fashion Coffee.

Il locale in questione è sito in località Santa sabina, periferia radicale ed estrema di Perugia. Lontano dal centro storico ormai infestato da Erasmus ed assassini. Anzi, colgo l’occasione per rompere il mio silenzio sul delitto di Perugia:

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.

La casa delle povertà

Brava gente, quella di Casapiddu. Povera, ma onesta e umile. La sera, quando arriva l’ora di cena i pidduisti si ritrovano intorno al loro tavolo sgangherato, e contemplano stancamente la desolazione. Un pasto frugale, giusto per ricordare allo stomaco cosa sia un carboidrato. Una mozzarella forse scaduta (l’indomani sapranno la verità) da dividere in quattro, pane raffermo acquistato impegnando il braccialetto, ultimo ricordo delle famiglie lontane.

Il ragazzo strambo trova ristoro nelle uova rimaste, Jiimbo cuoce su di una padella gli scarti delle cene dell’ultimo mese: mezza salsiccia, della carta stagnola e uno stecchino sfibrato.

Perugia da sniffare

Continua il nostro scovare video di studenti perugini in giro per la rete. Anche qui siamo in presenza di gente che ormai ha i neuroni a fine carriera. Il vecchio retaggio figlio della cultura pop, secondo cui sotto l’effetto di alcool o droghe si “crea” meglio, è definitivamente tramontato. Spero che qualcuno faccia qualcosa.

Perugia da bere

A perugia non si parla d’altro in questi giorni. La movida perugina ha subito un brutto scossone con l’omicidio della povera Meredith, finalmente tutti si sono accorti di come ormai il centro sia un pullulare di ubriachi, drogati e deviati. Basta girare un po’ su youtube per fugare ogni dubbio, forse è il caso di fermarci a riflettere.