Problema con il teorema di Shannon

[Darèios89]

Avrei bisogno di un' altro piccolo favore, con la matematica non sono mai stato forte, ho dei problemi nell' applicazione del teorema di Shannon, per stabilire il numero di bit necessario affinchè la codifica di Huffman si possa fare senza perdita di informazioni.

Presa la stringa:

"Viva le donne!"

Dovrei calcolare il numero minimo di bit necessari alla codifica ottimale.
Ora secondo il teorema il numero è dato da [tex]NE[/tex] dove [tex]E[/tex] è l' entropia, allora ho calcolato:

[tex]14*[8(-\frac{1}{14}\log_2(\frac{1}{14}))-2*(\frac{1}{7}\log_2(\frac{1}{7}))][/tex]

Ho messo 8 e 2 a moltiplicare perchè ho molti logaritmi con la stessa frequenza.
Allora praticamente avrei il primo logaritmo che all' incirca farebbe -3, quindi [tex]\frac{3}{14}[/tex] che moltiplicato per 8 fuori dovrebbe essere [tex]\frac{12}{7}[/tex], il secondo logaritmo dovrebbe dare -2 circa, quindi avrei [tex]\frac{4}{7}[/tex]
Alla fine di tutti i conti ottengo 32, ma non va, perchè ho letto che il calcolo corretto dovrebbe essere 41.
Ma dove sbaglio?

Grazie mille come sempre.

[apatriarca]

Verifichiamo un po' i tuo conti. Per prima cosa facciamo una tabella delle frequenze dei vari simboli:
(V, 2), (i, 1), (a, 1), (l, 1), (e, 2), (d, 1), (o, 1), (n, 2), (' ', 2), (!, 1).
Il numero totale di caratteri è 14, ci sono 4 caratteri che compaiono 2 volte e 6 che compaiono 1 volta sola. Per cui dovrebbe venire:
$14*( - 6 * (log_2(1/14))/(14) - 4 * (log_2(1/7))/(7)) ~= 45.3$
Mi viene comunque diverso..

[Rggb1]

'V' maiuscolo e minuscolo non sono differenti? Quindi abbiamo tre caratteri con frequenza 2.

[Darèios89]

Si avevo sbagliato, dei conti.
Ha ragione RggB, però i conti non mi tornano lo stesso, abbiamo 8 caratteri che si ripetono una volta sola, e 3 caratteri che si ripetono due volte, ma il conto finale mi viene:

[tex]14(\frac{12}{7}+\frac{6}{7})[/tex]

E ottengo 36, ma ancora non ci siamo

[hamming_burst]

Di mio non ho mai usato questa funzione con la codifica di Shannon.
Ma per sapere qual è il numero di bit necessari (minimi) per codificare quella stringa, io conosco un altro teorema, legato con l'algoritmo di codifica.

Ho provato a calcolare, ma non ricordo come si tratta la codifica se due lettere hanno frequenza uguale.

Domanda idiots: gli apici non c'entrano con la stringa?

[Darèios89]

Di mio non ho mai usato questa funzione con la codifica di Shannon.

Non esiste, o almeno non l' abbiamo fatta, non è la codifica di Shannon, la codifica è una generica codifica LOSSLESS, oppure il teorema può essere usato se si effettua la codifica di Huffman per verificare di avere effettuato una codifica ottimale se il numero di bit dopo la codifica di Huffman è maggiore di poco, o uguale al numero di bit trovati col teorema di Shannon, quindi il mio calcolo deve darmi il numero minimo di bit per una codifica ottimale, sia che si effettui con Huffman o in generale una codifica LOSLESS.
Il problema è che non coincidono i calcoli.
No gli apici non sono inclusi.

P.S. che fastidiosa l' elaborazione delle immagini

[Rggb1]

Ma sei sicuro il risultato sia 41? (E non magari 47?)

[Darèios89]

Si sono sicuro, dovrebbe venire 40.5, insomma 41.

[hamming_burst]

togliendo gli spazi?


PS: per la "codifica di Shannon" non esiste, mi è partita una parola, intendevo che non ho mai usato questa funzione di Shannon con la codifica di Huffman. Ma questa funzione penso venga usata prima di applicare l'algoritmo.
Quella che conosco io, devi prima calcolare l'alfabeto, le frequenze e la codifica, e poi puoi calcolare.