Re: La Scoperta del Titolo della Bibbia
Inviato da Max_Piano il 13/12/2005 22:25:36
Visto che Paolo Marra mi ha invitato a introdurre l'argomento penso sia meglio definire i concetti base della Teoria dell' Informazione.
Se trovate questo post pesante/inutile ignoratelo oppure leggete solo le frasi in grassetto, chiedete se non vi è chiaro qualcosa, al limite tenetelo come appendice...ma non prendetevela con me, ok ?
Allora comincio!
Il pioniere di questa disciplina sulla quale è basato il mondo in cui viviamo (computer, TV, radio, telefono, cellulari, DVD, ecc…) è stato Claude Elwood Shannon (morto 4 anni fa all’età di 86 anni).
Per primo ha ipotizzato e dimostrato che qualsiasi sorgente discreta non può portare una quantità di informazione infinita ed è riuscito a calcolarla (anche se sarebbe riduttivo ricordarlo solo per questo).
L’informazione va qui intesa in senso matematico e statistico, non filosofico : quindi non c’è un modo oggettivo per dire se la Divina Commedia sia più o meno interessante della Gazzetta dello Sport.
Immaginate di avere una sorgente di informazione che emette una serie di simboli da un alfabeto.
Citazione:
Un altro esempio potrebbe essere un sistema di allarme antincendio in cui normalmente il segnale è su “off”; quando scoppia un incendio il segnale va a “on” e suona l’allarme.
In pratica è come avere una sorgente con due soli simboli (on/off).
Una sorgente così si dice binaria.
Essendo l’incendio poco probabile è naturale associare il segnale “on” ad una maggior informazione o detto altrimenti il simbolo “on” porta un’alta quantità di informazione.
In generale diciamo che minore è la probabilità associata ad un simbolo e maggiore è la sua quantità di informazione.
Riallacciandomi a quello detto da Paolo Marra appare ovvio che 2 sia il numero minimo di simboli perché se ne avessi uno solo la sua incertezza e quindi la sua informazione sarebbe nulla.
Viceversa non c’è un limite al numero di simboli che è possibile usare, anzi è possibile dimostrare che se il numero di simboli è più alto l’efficienza di codifica migliora.
L’informazione per un certo simbolo la possiamo anche misurare !
I = log 1/p = - log p
Dove p è la probabilità di emissione (da 0 a 1) del simbolo considerato e log è il logaritmo.
E’ una definizione come un’altra però è quella più semplice e che al tempo stesso verifica alcune proprietà necessarie.
Per esempio se il simbolo è certo (cioè p=1) la sua informazione è nulla mentre se il simbolo è poco probabile (p~0) la sua informazione tende ad infinito (log 1 = 0 mentre log 0 = - #INF ).
Mediando le singole quantità di informazione di tutti i simboli emessi dalla sorgente abbiamo la cosiddetta entropia; l’entropia è in pratica la quantità di informazione media che distingue la sorgente.
H = p1 * I1 + p2 * I2 +… + pn * In
Le singole quantità le abbiamo pesate per le singole probabilità.
Solitamente si usa il logaritmo in base 2 quindi H si misura in bit.
Si può dimostrare che una sorgente ha una quantità di informazione massima quando tutti i simboli sono equiprobabili cioè quando i simboli sono emessi in modo casuale.
Potrebbe stupire a prima vista!
In realtà così non è se ricordiamo che l’informazione va intesa come una misura dell’incertezza e nulla è più incerto di un qualcosa che è casuale.
In tal caso abbiamo semplicemente H = log M
dove M è il numero di simboli
Per esempio una sorgente che emette simboli ASCII (0,1,…255) equiprobabili avrà una entropia pari a 8 bit (essendo log 256 = 8)
In effetti dire che una sorgente di 256 simboli equiprobabili ha una quantità di informazione pari a 8 bit per simbolo sembra quasi una cosa ovvia ma in realtà se i simboli non sono casuali questo valore sarà inferiore.
Un significato importante dell’entropia è che rappresenta anche il numero di bit necessari per codificare una sorgente.
Visto che l’entropia non può superare il valore massimo scritto prima significa anche che è possibile in qualche modo comprimere la sorgente usando un numero medio di bit per simbolo inferiore.
Per esempio gli algoritmi della famiglia Lempel-Ziv sono alla base di sistemi famosi di compressione come i programmi/librerie zip, rar, zlib o formati immagine (lossless) come le gif.
Il fatto che sia possibile comprimere un file (ad esempio di testo) dipende proprio dal fatto che la quantità di informazione presente nella sorgente è inferiore a quella massima che si ha solo nel caso di simboli equiprobabili.
Il fatto che esista una correlazione tra i simboli crea una sorta di rindondanza che rende una parte dei dati superflua.
Calcolata l’entropia non possiamo pensare di codificare la sorgente con un numero di bit per simbolo inferiore (valore medio).
Le tecniche usate per comprimere sono molte e non è possibile affrontarle qui comunque vi basti sapere che si basano sulla creazione di opportuni codici a lunghezza variabile da associare ai vari simboli.
Se simboli più probabili hanno codici più corti e viceversa simboli meno probabili hanno codici più lunghi è facile immaginare come in media si risparmino dei bit (naturalmente poi ci serve un “dizionario” per la decodifica)
Per codice intendiamo ad esempio la sequenza 1/0 che identifica un carattere (ad esempio un carattere ASCII è rappresentato da codici di 8 bit)
Un esempio immediato…
In italiano il simbolo “u” dopo due simboli “q” successivi non porta informazione perché è sempre certo (es: la parola "soqquadro"). In questo caso potremmo anche non trasmettere la “u” !
Anche il fatto che l’ultima lettera di ogni parola è quasi sempre una vocale tende a rendere tali simboli più certi quindi a ridurre l’entropia totale della sorgente.
Accenno solo al fatto che nulla vieta di raggruppare più simboli insieme considerando quindi un nuovo alfabeto
Ad esempio invece di 21 simboli a,b,c,…z
Potremmo considerare un alfabeto di 21x21 = 441 simboli dati dalle coppie aa,ab,ac,…rt,sa,…zz
Questo aumenta l’efficienza di compressione di cui però l’entropia rappresenta il limite.
Direi di fermarci qui, per ora
Se trovate questo post pesante/inutile ignoratelo oppure leggete solo le frasi in grassetto, chiedete se non vi è chiaro qualcosa, al limite tenetelo come appendice...ma non prendetevela con me, ok ?
Allora comincio!
Il pioniere di questa disciplina sulla quale è basato il mondo in cui viviamo (computer, TV, radio, telefono, cellulari, DVD, ecc…) è stato Claude Elwood Shannon (morto 4 anni fa all’età di 86 anni).
Per primo ha ipotizzato e dimostrato che qualsiasi sorgente discreta non può portare una quantità di informazione infinita ed è riuscito a calcolarla (anche se sarebbe riduttivo ricordarlo solo per questo).
L’informazione va qui intesa in senso matematico e statistico, non filosofico : quindi non c’è un modo oggettivo per dire se la Divina Commedia sia più o meno interessante della Gazzetta dello Sport.
Immaginate di avere una sorgente di informazione che emette una serie di simboli da un alfabeto.
Citazione:
Esempio:
Leggere il testo di un libro in cui avete una successione di caratteri presi da un alfabeto (es: a,b,c,…,z)
Man mano che leggete lettera per lettera è come avere una sorgente che emette dei simboli.
Non tutti i simboli compaiono con la stessa frequenza : per esempio la "a" è molto più probabile della "q"
Un altro esempio potrebbe essere un sistema di allarme antincendio in cui normalmente il segnale è su “off”; quando scoppia un incendio il segnale va a “on” e suona l’allarme.
In pratica è come avere una sorgente con due soli simboli (on/off).
Una sorgente così si dice binaria.
Essendo l’incendio poco probabile è naturale associare il segnale “on” ad una maggior informazione o detto altrimenti il simbolo “on” porta un’alta quantità di informazione.
In generale diciamo che minore è la probabilità associata ad un simbolo e maggiore è la sua quantità di informazione.
Riallacciandomi a quello detto da Paolo Marra appare ovvio che 2 sia il numero minimo di simboli perché se ne avessi uno solo la sua incertezza e quindi la sua informazione sarebbe nulla.
Viceversa non c’è un limite al numero di simboli che è possibile usare, anzi è possibile dimostrare che se il numero di simboli è più alto l’efficienza di codifica migliora.
L’informazione per un certo simbolo la possiamo anche misurare !
I = log 1/p = - log p
Dove p è la probabilità di emissione (da 0 a 1) del simbolo considerato e log è il logaritmo.
E’ una definizione come un’altra però è quella più semplice e che al tempo stesso verifica alcune proprietà necessarie.
Per esempio se il simbolo è certo (cioè p=1) la sua informazione è nulla mentre se il simbolo è poco probabile (p~0) la sua informazione tende ad infinito (log 1 = 0 mentre log 0 = - #INF ).
Mediando le singole quantità di informazione di tutti i simboli emessi dalla sorgente abbiamo la cosiddetta entropia; l’entropia è in pratica la quantità di informazione media che distingue la sorgente.
H = p1 * I1 + p2 * I2 +… + pn * In
Le singole quantità le abbiamo pesate per le singole probabilità.
Solitamente si usa il logaritmo in base 2 quindi H si misura in bit.
Si può dimostrare che una sorgente ha una quantità di informazione massima quando tutti i simboli sono equiprobabili cioè quando i simboli sono emessi in modo casuale.
Potrebbe stupire a prima vista!
In realtà così non è se ricordiamo che l’informazione va intesa come una misura dell’incertezza e nulla è più incerto di un qualcosa che è casuale.
In tal caso abbiamo semplicemente H = log M
dove M è il numero di simboli
Per esempio una sorgente che emette simboli ASCII (0,1,…255) equiprobabili avrà una entropia pari a 8 bit (essendo log 256 = 8)
In effetti dire che una sorgente di 256 simboli equiprobabili ha una quantità di informazione pari a 8 bit per simbolo sembra quasi una cosa ovvia ma in realtà se i simboli non sono casuali questo valore sarà inferiore.
Un significato importante dell’entropia è che rappresenta anche il numero di bit necessari per codificare una sorgente.
Visto che l’entropia non può superare il valore massimo scritto prima significa anche che è possibile in qualche modo comprimere la sorgente usando un numero medio di bit per simbolo inferiore.
Per esempio gli algoritmi della famiglia Lempel-Ziv sono alla base di sistemi famosi di compressione come i programmi/librerie zip, rar, zlib o formati immagine (lossless) come le gif.
Il fatto che sia possibile comprimere un file (ad esempio di testo) dipende proprio dal fatto che la quantità di informazione presente nella sorgente è inferiore a quella massima che si ha solo nel caso di simboli equiprobabili.
Il fatto che esista una correlazione tra i simboli crea una sorta di rindondanza che rende una parte dei dati superflua.
Calcolata l’entropia non possiamo pensare di codificare la sorgente con un numero di bit per simbolo inferiore (valore medio).
Le tecniche usate per comprimere sono molte e non è possibile affrontarle qui comunque vi basti sapere che si basano sulla creazione di opportuni codici a lunghezza variabile da associare ai vari simboli.
Se simboli più probabili hanno codici più corti e viceversa simboli meno probabili hanno codici più lunghi è facile immaginare come in media si risparmino dei bit (naturalmente poi ci serve un “dizionario” per la decodifica)
Per codice intendiamo ad esempio la sequenza 1/0 che identifica un carattere (ad esempio un carattere ASCII è rappresentato da codici di 8 bit)
Un esempio immediato…
In italiano il simbolo “u” dopo due simboli “q” successivi non porta informazione perché è sempre certo (es: la parola "soqquadro"). In questo caso potremmo anche non trasmettere la “u” !
Anche il fatto che l’ultima lettera di ogni parola è quasi sempre una vocale tende a rendere tali simboli più certi quindi a ridurre l’entropia totale della sorgente.
Accenno solo al fatto che nulla vieta di raggruppare più simboli insieme considerando quindi un nuovo alfabeto
Ad esempio invece di 21 simboli a,b,c,…z
Potremmo considerare un alfabeto di 21x21 = 441 simboli dati dalle coppie aa,ab,ac,…rt,sa,…zz
Questo aumenta l’efficienza di compressione di cui però l’entropia rappresenta il limite.
Direi di fermarci qui, per ora
Messaggio orinale: https://old.luogocomune.net/site/newbb/viewtopic.php?forum=47&topic_id=426&post_id=3944