Newsgroup: it.comp.java
Titolo: compressione huffman...

Dove posso trovare un algoritmo in java che faccia la compressione di huffman 
lavorando semplicemente con delle stringhe? Che ne so, con metodi tipo
public static String getCompString(String stringaOriginale)
public static String getDecompString(String stringaCompressa)
tnx!
-- 
by \ \/ /\/
PerezDeQueya80 on AzzurraNET.org

 tnx!
La parte di codifica e decodifica di huffmann io l'ho fatta per stream di
short, ed infondo è una cosa abbastanza semplice e facilmente adattabile.
La codifica che ho scritto però non è adattiva, il che vuol dire che se vuoi
ottenre una codifica huffmann conveniente sui tuoi dati tu devi avere delle
informazioni statistiche su di essi; in base a tali informazioni devi
stabilire una tabella di codici e usare quella per la compressione...
Se vuoi posso mandarti il codice: è integrato in una applicazione quindi
devi rimettere insieme qualche pezzo sparso qua e là, ma credimi quando ti
dico che è davvero semplice.
Fammi sapere
Ciao
Giacomo

 Giacomo
Ciao


 dico che è davvero semplice.
Mi intrufolo, la questione mi interessa, se potessi inviare il codice te ne
sarei grato, eventualmente
qualche link o documento a cui fare riferimento in modo diretto senza
perdermi nei meandri di Google.
Ciao
Pow
--
----------------------------------------------------
Ama il tuo mestiere con passione
E' il significato della tua vita
Auguste Rodin (1840-1917)
 "Not everything that  counts can be
 counted, and not everything that can
be counted counts".
Albert Einstein
"Hunt for the Engineer and the Engineer will hunt you."
Hellraiser5 Pinhead

 costruito stringa per stringa...
Che io sappia la cosa non è detto che sia così. In linea generale per
effettuare una codifica huffmann, come sai, devi stabilire un vocabolario;
tale vocabolario però deve essere noto al decodificatore, quindi deve essere
incluso nei dati compressi, a meno che non nè esista uno di default. Quale
delle due implementazioni è conveninete usare dipende, oltre che da
considerazioni di "usabilità", dal rapporto tra quanto è oneroso trasmettere
un vocabolario "ad hoc" e quanto l'uso di questo vocabolario migliora le
prestazione dell'algoritmo. Due esempi estremi possono ben illustrare
l'idea:
- Se ha insiemi di dati piccoli ma tutti con una statistica simile (per
esempio piccoli periodi di testo scritti in intaliano corrente), ti conviene
usare un vocabolario standard: se tu usassi un vocabolario "ad hoc" per ogni
stream avresti prestazioni dell'algoritmo solo poco migliori (per ipotesi la
statistica del singolo insieme è simile a quella media di tutti gli
insiemi), ma l'inclusione del vocabolario rappresenterebbe una grossa fetta
di dati nello stream compresso (quindi evitandotelo riduci di molto la
dimensione dello stream)
- Se hai insiemi molto grandi e con statistiche molto diverse, ti conviene
un vocabolario ad hoc: se ne usassi uno standard, il risparmio della "non
inclusione" sarebbe percentualmente trascurabile (l'insieme di dati è grande
per ipotesi, quindi sarà "grande" anche l'insieme dei dati compressi), ma le
prestazioni dell'algoritmo decadrebbero sensibilmente adattandosi poco il
vocabolario standard alla statistica specifica di quel set di dati
Addirittura ci sono implementazioni "adattative" dell'algoritmo adatte per
insiemi di dati che hanno una statistica stabile solo "localmente": ogni
tanto (quando le prestazioni decadono troppo, immagino) l'algoritmo
ricalcola il vocabolario ottimale, lo include nei dati e comincia ad usare
quello...
La valutazione di quale metodo utilizzare può essere molto delicata: non so
con che tipo di dati hai a che fare, e la mia esperienza in merito è
comunque abbastanza limitata, ma se vuoi possiamo parlarne...
Ciao
Giacomo

 
Ciao


 quello...
Non so se era l'algoritmo di huffman ma ricordo un metodo che prevede di 
partire da una statistica vuota (cioe' tutti i simboli ugualmente 
probabili) per codificare il primo simbolo.
Ad ogni simbolo codificato la statistica viene aggiornata (aggiornando 
di conseguenza il vocabolario) prima di codificare il simbolo successivo.
Questo fa si che il vocabolario non debba essere trasmesso a chi 
effettua la decodifica in quanto e' in grando di ricostruirlo dal 
messaggio codificato: per il primo simbolo si utilizza la statistica 
vuota e poi si aggiorna in base al simbolo decodificato.
E' passato molto tempo e quindi potrei sbagliarmi. Qualcuno ne sa di piu'?
Andrea

Si, in effetti hai ragione, anch'io ho sentito parlare di qualcosa del
genere: rimane però il fatto che per stream corti la statistica fatta sul
singolo insieme potrebbe essere insufficiente...
Ciao
Giacomo