Comprimi e Cerca: Il Segreto per Ricerche Testuali Super Veloci ed Eco-Friendly!

Ciao a tutti! Oggi voglio parlarvi di qualcosa che mi affascina da morire e che, scommetto, cambierà il modo in cui pensate alla ricerca nei testi digitali. Parliamo di come la compressione dei dati, quella cosa che usiamo per risparmiare spazio, possa in realtà rendere le nostre ricerche non solo più veloci, ma anche incredibilmente più efficienti dal punto di vista energetico. Sembra un controsenso, vero? Comprimere per andare più veloci e consumare meno? Eppure è proprio così!

Il Problema: Oceani di Testo da Esplorare

Viviamo in un’era digitale dove la quantità di testo generata ogni giorno è sbalorditiva. Pensate alle email, ai documenti, agli articoli web, ai libri digitali… un mare magnum di informazioni. Trovare quello che ci serve in questo oceano può essere un’impresa, specialmente quando abbiamo a che fare con collezioni di dati enormi. Tradizionalmente, per cercare una parola o una frase, i sistemi dovevano leggere tutto il testo “in chiaro” (non compresso) oppure, se il testo era compresso per risparmiare spazio, dovevano prima decomprimerlo. Entrambe le opzioni possono essere lente e, come vedremo, dispendiose in termini di energia.

La Svolta: La Compressione Basata su Parole

Negli ultimi vent’anni, una vera rivoluzione è arrivata con la compressione basata su parole. Invece di comprimere carattere per carattere (come fa il classico Huffman sui singoli caratteri, che però non comprime granché), questi metodi trattano intere parole come simboli unici. Immaginate di sostituire la parola “compressione” ogni volta che appare con un codice molto più corto. Questo porta a rapporti di compressione fantastici (spesso riducendo il testo al 25-35% della dimensione originale!) ma, cosa ancora più importante, apre la porta a tecniche di ricerca innovative.

Tecniche come Huffword, Plain Huffman (PH), Tagged Huffman (TH) ed End-Tagged Dense Code (ETDC) sono state sviluppate proprio per questo. In particolare, TH ed ETDC usano un trucco geniale: codificano le parole usando sequenze di byte (non bit singoli), il che velocizza enormemente la decompressione. Ma la vera magia sta nel fatto che permettono di cercare direttamente nel file compresso!

Ricerca Diretta nel Compresso: Come Funziona?

Il Sacro Graal è il cosiddetto “compressed pattern matching”: cercare un pattern (una parola, una frase) senza dover decomprimere tutto prima. Con tecniche come TH ed ETDC, questo diventa non solo possibile, ma addirittura più veloce della ricerca sul testo originale. Come?

Questi metodi (specialmente ETDC e TH) sono progettati per essere “auto-sincronizzanti”. Significa che, anche se inizi a leggere da un punto casuale del file compresso, puoi rapidamente capire dove inizia e finisce un codeword (la rappresentazione compressa di una parola). Inoltre, hanno proprietà (come l’essere “suffix-free” per TH) che permettono di usare algoritmi di ricerca super-efficienti, come il mitico algoritmo di Horspool (una variante del Boyer-Moore).

L’algoritmo di Horspool è furbo: invece di confrontare il pattern carattere per carattere, guarda l’ultimo carattere della finestra di ricerca nel testo e decide di quanto “saltare” in avanti. Se il carattere non corrisponde o non è proprio presente nel pattern, può fare salti belli lunghi, risparmiando un sacco di confronti. Applicato al testo compresso con TH o ETDC (dove i “caratteri” sono i byte dei codeword), questo approccio diventa fulmineo, a volte fino a 8 volte più veloce della ricerca sul testo non compresso!

Non Solo Veloce, Ma Anche “Green”!

Finora abbiamo parlato di velocità e spazio. Ma c’è un altro aspetto cruciale, sempre più importante oggi: l’efficienza energetica. I data center che ospitano tutti questi dati consumano quantità enormi di energia. Si stima che entro il 2025 verranno creati 463 Exabyte di nuovi dati *ogni giorno*! Gestire e cercare in questi dati ha un costo energetico non indifferente.

Ecco la scoperta sorprendente che abbiamo fatto e che voglio condividere con voi: cercare nel testo compresso (con i metodi giusti) consuma molta meno energia! Intuitivamente, si potrebbe pensare che il risparmio derivi solo dal minor tempo di esecuzione (meno tempo acceso = meno energia). Ed è vero, questo è un fattore importante. Ma abbiamo scoperto qualcosa di più inaspettato.

Mettiamo Alla Prova: Gli Esperimenti

Per verificare questa ipotesi, abbiamo messo su un bel po’ di esperimenti. Abbiamo preso una grossa collezione di testi (circa 1 GB, un mix di news, documenti, ecc.), l’abbiamo compressa usando ETDC, TH e PH, e poi abbiamo lanciato ricerche di parole. Abbiamo cercato parole di diversa lunghezza e frequenza.

Per misurare l’energia, abbiamo usato due metodi:

• Un dispositivo hardware dedicato (parte del framework FEETINGS) che misura il consumo reale dell’intero computer (DUT – Device Under Test).
• Il tool software `perf` di Linux, che stima il consumo energetico basandosi sui contatori interni del processore (Intel RAPL).

Abbiamo confrontato le ricerche sul testo compresso (usando Horspool per ETDC/TH e un metodo basato sulla decompressione simulata per PH) con le ricerche fatte usando Horspool sul testo originale non compresso (che chiameremo PLAIN).

I Risultati: Compressione Batte Testo in Chiaro (Anche in Bolletta!)

I risultati sono stati netti e, per certi versi, sbalorditivi:

• Velocità: Come previsto, le ricerche con Horspool su ETDC e TH sono state le più veloci, battendo nettamente sia la ricerca su PH sia quella su testo PLAIN (da 1.5 a oltre 3 volte più veloci di PLAIN, a seconda dei pattern).
• Energia: Qui arriva il bello! Le ricerche su ETDC e TH hanno richiesto dal 30% al 70% di energia in meno rispetto alla ricerca su testo PLAIN. Un risparmio enorme!
• Potenza: La sorpresa più grande è stata questa: le ricerche su testo compresso non solo finivano prima, ma richiedevano anche meno potenza istantanea dal processore (circa 8-10% in meno rispetto a PLAIN). Come mai? Analizzando i contatori interni della CPU (`perf`), abbiamo visto che le ricerche su testo compresso causano molte meno “branch mispredictions” (errori di previsione del processore su quale istruzione eseguire dopo un bivio) e accedono meno alla cache L1 e alla memoria principale (LLC). Meno errori e meno accessi si traducono in un lavoro più “fluido” per la CPU e, quindi, minor consumo istantaneo.

La ricerca su PH, invece, si è dimostrata più lenta e più energivora delle altre basate su compressione, e spesso anche peggio della ricerca su testo PLAIN, confermando che l’algoritmo di ricerca fa una differenza enorme.

Ottimizzare l’Ottimizzabile: I Trucchi di Horspool

Non contenti, abbiamo provato a “spremere” ancora di più l’algoritmo di Horspool applicato a ETDC. Abbiamo sperimentato piccole modifiche al codice:

• Skip-check-end: Aggiungere il pattern alla fine del testo per evitare un controllo a ogni ciclo.
• Skip-loop: Saltare avanti finché l’ultimo carattere non matcha, prima di iniziare il confronto all’indietro.
• Puntatori vs Array: Usare la sintassi dei puntatori in C invece degli array per accedere ai dati.
• Buffer di Lettura: Leggere tutto il file in memoria in una volta sola vs leggerlo a blocchi.

I risultati? Interessantissimi! Ad esempio, il trucco `skip-loop` riduce drasticamente il numero di istruzioni eseguite, ma… aumenta il tempo di esecuzione e il consumo energetico! Perché? Causa un’impennata delle branch mispredictions, che costringono la CPU a “disfare” lavoro speculativo, sprecando tempo ed energia. Alla fine, abbiamo scoperto che usare `skip-check-end` e la sintassi a puntatori, leggendo tutto il file in un colpo solo (se la memoria lo permette), dà il miglior compromesso tra velocità ed efficienza energetica, risparmiando un ulteriore 5-10% di energia rispetto a una versione base di Horspool su ETDC.

Conclusioni: Comprimere Conviene Davvero (Sotto Tutti i Punti di Vista!)

Quindi, cosa ci portiamo a casa da tutto questo? Che la compressione testuale basata su parole, in particolare con tecniche come ETDC e TH che supportano ricerche veloci come Horspool, non è solo un modo per risparmiare spazio. È una strategia potentissima per accelerare le ricerche e, contemporaneamente, ridurre drasticamente il consumo energetico.

In un mondo sempre più affamato di dati e attento all’impatto ambientale, poter cercare in modo efficiente diventa fondamentale. E la compressione, un po’ a sorpresa, si rivela una delle chiavi per farlo. La prossima volta che vedrete un file compresso, non pensate solo allo spazio risparmiato, ma anche alla potenziale velocità ed efficienza nascosta al suo interno!

Stiamo già pensando ai prossimi passi, come estendere questi studi ad altri tipi di compressione (magari dinamica, che non richiede due passate) e valutare l’impatto energetico complessivo quando si usano indici invertiti insieme al testo compresso. Il campo è fertile e le scoperte sono dietro l’angolo!

Fonte: Springer