Newsgroup: it.scienza.informatica
Titolo: Compressione dati (sequenze di proteine)

Salve,
premetto che non mi sono mai interessato di compressione dei dati.
Mi domando se esiste un "semplice" e "veloce" algoritmo per comprimere
stringhe che rappresentano sequenze di proteine tipo:
MPRAPRCRAVRSLLRSHYREVLPLATFVRRLGPQGWRLVQRGDPAAFRALVAQCLVCVPWDARPPPAAPS
FRQVSCLKELVARVLQRLCERGAKNVLAFGFALLDGARGGPPEAFTTSVRSYLPNTVTDALRGSGAWGLL
LRRVGDDVLVHLLARCALFVLVAPSCAYQVCGPPLYQLGAATQARPPPHASGPRRRLGCERAWNHSVREA
...
Grazie
 Raffaello

Dalla mia enorme conoscenza .... ahahahha
mi viene in mente il Huffman Code, che è come un alg di compressione ZIP,
basato sulle ricorrenze del carattere mi pare.
Da una rappresetazione binaria a lunghezza variabile a seconda della
ricorrenza di un
carattere in un file ad esempio.
Mi ricordo di avergli dato in pasto la divina commedia, i promessi sposi e
la bibbia una volta
per fare un esperimento :)
CMQ datevi alla Intelligenza Artificiale lameroni!!!! Possibile che nessuno
ne sia attratto!!!
L A ME R Z!!!!!



,
Raffaello Galli ha scritto: 

Un algoritmo molto semplice potrebbe essere quello di rappresentare
ogni simbolo con il piu` piccolo insieme di bit sufficiente, in questo
caso, se le lettere sono 26 allora sono sufficienti 5 bit. In
alternativa per qualcosa di leggermente piu` complesso ma sempre
veloce ti consiglio l'algoritmo di Huffman (che trovi facilmente in
rete).
Maurizio
-- 
The last thing one knows in constructing a work is what to put first.
                -- Blaise Pascal

  Raffaello
ciao, Gino

 ha
scritto:

Le sequenze di dati che contengono caratteri alfabetici sono le sequenze che
si prestano meglio ad essere compresse. In generale qualsiasi sequenza di un
insieme finito di simboli e' semplicemente compressibile, purche' i simboli
non siano in numero elevato (26 nel caso dell'alfabeto).
All'universita' studiai un semplice algoritmo di compressione basato sullo
studio statistico della frequenza dei simboli (Compressione di Huffman).
Vediti il sito
http://www.dia.unisa.it/~ads/TesineAsd2/
trovato con google e Huffman
http://www.dia.unisa.it/~ads/TesineAsd2/huff/index.html
Pietro
--------------------------------
Inviato via 
http://usenet.libero.it

Come tutto il testo e a maggior raggione il testo con molte ripetizioni
(Se non sbaglio la sequenza è data da un set limitato di letrtere) è
possibile comprimere i "dati".
Gli algoritmi sono tanti alla base c'è l'idea di creare una associazione
che "faccia nmantenere costante" il valore dell'espressione:
probabilità di trovare la lettera * (lunghezza della stringa di bit per
codificare la letrtera)
In modo da risparmiare bit per lettere più ricorrenti, ma ciò implica sprecare più
spazio per quelle meno ricorrenti.
Gli algoritmi non fanno altro che creare queste associazioni fra sequenze
di bit e lettere in modo ottimale.
Spero diessere stato chiaro nella semplicità della mia esposizione, Mario.

 ha scritto nel messaggio
news:Pine.OSF.4.31.03011...@harry.molgen.mpg.de...

non vorrei dire una stupidaggine, ma se ben ricordo la compressione dati
sfrutta la ridondanza dell'informazione e la possibilità di poter
classificare le stringhe in tipiche ed atipiche.
le stringhe sopra mi sembrano, a prima vista, abbastanza compresse (un
risultato teorico dice che quanto più un file e random tanto minore diventa
la possibilità di comprimerlo).
se anche nelle sequenze di proteine si trova una certa regolarità e si
riescono a distinguere delle sottostringhe che appaiono più frequentemente
si può anche pensare di comprimerle.
ciao
ferdy

 wrote in message
news:Pine.OSF.4.31.03011...@harry.molgen.mpg.de...

Manca un dato importante che avevi scritto in un altro newsgroup.
Ci avevi detto che il numero di aminoacidi possibili (i quali sono
codificati in lettere maiuscole e formano la sequenza di proteine) e' di 20.
Per cui non penso sia possibile una compressione con meno di 5bits.
Maurus

 Per cui non penso sia possibile una compressione con meno di 5bits.
dipende dalla ricorrenza:
se ho A che ricorre il 99,99% 
B,C,D,E che ricorrono il 0,0025%
posso associare
A=1
B=01
C=001
D=0001
E=00001
e avrò una maggiore compressione 

 e avrò una maggiore compressione
Ok, ho capito quello che intendevi dire anche in un tuo altro post.
Ma per curiosita', c'e' una regola generale affinche' questo tipo di
associazione sia veramente efficace?
Il tuo era un caso limite ok, ma in casi piu' generici dove per esempio sai
che A ricorre il 20% B il 15, C il 10, D il 5 ed E il 10 % e tutti gli altri
sono equiprobabili come fai le associazioni?
O ancora se sono tutti equiprobabili penso che non puoi scendere a meno di 5
bits giusto?
Maurus

 sono equiprobabili come fai le associazioni?
L' algoritmo di huffman ti dice come farle, e ti da la compressione migliore nel
caso hai deciso di codificare le singole lettere.
Però potresti decidere di codificare le coppie di lettere ed ottenere una
compressione maggiore, perchè magari certe coppie non si verificano mai. Oppure
potresti codificare le terne di lettere, oppure pattern più complessi, per
esempio coppie di lettere distanziate tra loro. Le possibilità sono infinite.
In generale vale il principio che quanto più conosci della sequenza e tanto
maggiore è la compressione che puoi ottenere, perchè quello che già conosci non
lo devi codificare. Il sapere che certi simboli si presentano con maggiore
probabilità di altri è un caso particolare di questo principio.

@ <snip> esiste un "semplice" e "veloce" algoritmo per comprimere<snip>
Se cerchi un qualcosa semplice e veloce nell'implementarlo, potresti
usare i sorgenti di tools come gzip o info-zip, poco piu' di un
cut&paste per il tuo scopo.
Se invece intendi semplice e veloce per quanto riguarda la
complessita' nel capirlo e nella sua esecuzione, allora valgono tutte
le risposte date dai colleghi.
-- 
Real email address hasn't .nntp

 bits giusto?
Shannon disse che la H(S) sommatoria da i=1 a n di p con i * log base i di
1/ p con i descrive la media dell'informazione prodotta dalla sorgente..
chiamasi anke kuesta sommatoria ENTROPIA della sorgente :)
massimizzata per p di i = 1/n  cioe' kuando tutti i simboli sono
equiprobabili si ha H=log base 2 di n
by3z Pulz
(a ke kosa porta cercare di preparare un esame di compressione di testi in 3
giorni:D )

 equiprobabili si ha H=log base 2 di n
By3z
Pulz