Newsgroup: it.comp.lang.c++
Titolo: Comprimere stringhe

Salve a tutti,
vorrei comprimere delle stringhe, generalmente corte (tipo messaggi
chat: qualche decina di caratteri, qualche centinaio al massimo).
Potrei usare la libreria zlib... o c'e' qualcosa di piu' mirato a
questo scopo, che magari e' piu' semplice e con prestazioni migliori?
Thx,
Pleg

 questo scopo, che magari e' piu' semplice e con prestazioni migliori?
Ci sono un fottio di algoritmi di compressione, librerie di compressione
etc. Ognuno ha il suo compromesso compressione/prestazioni.
In particolare io la compressione non andrei a farla a livello di
messaggio ma a livello di canale, ammesso che la cosa sia utile.
-- 
-riko


La maggior parte degli algoritmi di compressione efficaci per il testo
sono basati su codifiche a codice prefisso come quelle di Huffman, e
hanno bisogno di costruirsi un dizionario da accodare/mettere in
intestazione al file. Per messaggi così corti, l'overhead della
compressioneprobabilmente eccede il peso del messaggio in chiaro.
O concateni un testo più lungo, e poi comprimi il tutto, o lasci
perdere.
Io comunque mi trovo bene con bzip2: 
http://www.bzip.org/
Ciao,
Matteo

 compressione probabilmente eccede il peso del messaggio in chiaro.
E' quello che temevo, grazie della conferma!
Pleg

 messaggio ma a livello di canale, ammesso che la cosa sia utile.
Che cosa significa a "livello di canale"?
Thx,
Pleg

 > compressione probabilmente eccede il peso del messaggio in chiaro.
Pero': se ad es. usassi la codifica Huffman con tabella dei simboli
fissata a priori e conosciuta ad entrambi (dovrebbe essere
ragionevole, se la tari sulla lingua desiderata), non hai piu'
quell'overhead e dovresti guadagnarci abbastanza, no?
Pleg

 compressioneprobabilmente eccede il peso del messaggio in chiaro.
S�, a meno che non mantieni fisso il dizionario, e trasmetti solo i dati 
compressi. In tal caso elimini l'overhead e velocizzi anche la compressione.
E.

 Che cosa significa a "livello di canale"?
Cosa non capisci?
-- 
-riko

 chat: qualche decina di caratteri, qualche centinaio al massimo).
Puoi valutare di costruire un tuo sistema di compressione basato sulla 
natura dei testi che verranno scritti.
In linea di principio si tratta comunque di ridurre al minimo il numero 
di BIT necessari per codificare un messaggio di testo composto dai 
simboli ussati con la frequenza maggiore, avendo comunque a 
disposizione un codice o piu' speciali necessari per cambiare il 
sistema di compressione in presenza di simboli meno probabili.
Esempio stupidissimo : codifichi tutto a 6 bit (significa comprimere al 
25% massimo) lettere, numeri e segni di interpunzione e lasci un paio 
di codici liberi per indicare che stai passando dal minuscolo/minuscolo 
oppure che vuoi usare un carattere non compresso etc.
Altro esempio usi solo 4 bit (50% di compressione massimo) considerando 
che secondo questo diagramma
http://www.fondazionegiulietti.it/downloads/c01p0508.pdf
Le lettere piu' usate per piu' dell 1,5% sono solo 16.
Puoi usare quindi la lettera Z come codice speciale aggiungendo al 
fondo un paio di bit per avere in totale 3 zone ulteriori di codifica.
In altri termini quando trovi un z potrebbe essere cosi' codificata :
111100 e' una z.
111101 e' uno spazio
111010 segue una delle altre 10 lettere + 6 codici per caratteri di 
interpunzione piu' usati
111011 segue un codice ascii esteso
Questa idea sicuramente e' da ottimizzare ragionando bene sulla natura 
dei messaggi ma e' solo per dare un esempio di come potresti procedere.

[cut]
E' quello che dicevamo io e ?manu* : una codifica Huffman a dizionario
fisso.
Pleg

 fisso.
E allora? E' vietato fornire un esempio concreto o ti da fastidio?