Entropia di un file
Ciao a tutti,
devo scrivere un programma che sia in grado di stimare la probabilità di ogni simbolo di un file e che valuti l'entropia del file.
So che l'entropia rappresenta il numero minimo di bits necessari per rappresentare un simbolo della sorgente di informazione.
Chiamo $P_{i}^{m}$ la probabilità dell'$i$-esimo simbolo del file dove $m$ rappresenta la lunghezza dei simboli.
Queste probabilità possono essere stimate numericamente guardando le rispettive frequenze.
A partire poi dalle frequenze, posso calcolare l'entropia di ordine $m$.
Quindi ciò che dovrei fare è scrivere un programma che sia in grado di stimare l'entropia di ordine $m$ di un file testuale, per valori di $m<=16 bit$.
Bene, non so da che parte iniziare.
La mia idea è:
devo scrivere un programma che sia in grado di stimare la probabilità di ogni simbolo di un file e che valuti l'entropia del file.
So che l'entropia rappresenta il numero minimo di bits necessari per rappresentare un simbolo della sorgente di informazione.
Chiamo $P_{i}^{m}$ la probabilità dell'$i$-esimo simbolo del file dove $m$ rappresenta la lunghezza dei simboli.
Queste probabilità possono essere stimate numericamente guardando le rispettive frequenze.
A partire poi dalle frequenze, posso calcolare l'entropia di ordine $m$.
Quindi ciò che dovrei fare è scrivere un programma che sia in grado di stimare l'entropia di ordine $m$ di un file testuale, per valori di $m<=16 bit$.
Bene, non so da che parte iniziare.
La mia idea è:
- creo un programma (es. Java) che legge in input un file testuale[/list:u:zxedxeyg]
- considero per esempio $m=2$ e i simboli alfanumerici $A...Z$ e $0...9$. Ora dovrei trovare la frequenza nel testo di ogni coppia possibile fra questi simboli[/list:u:zxedxeyg]
- dalla frequenza calcolo l'entropia.[/list:u:zxedxeyg]
E' più o meno corretto?
Ma questo è il caso semplice, poi le cose si complicano che considero anche caratteri speciali come punto interrogativo, virgole, ecc e valori di $m < 2$ e $m>2$.
Sono molto confuso, avrei bisogno di una mano...
(Non chiedo la soluzione, il codice, ma dei consigli per aiutarmi a sviluppare meglio l'idea che c'è sotto).
Grazie mille
Risposte
Io credo che il problema ti chieda esclusivamente di calcolarti l'entropia usando la classica formula
\[ - \sum_{s \in \Sigma} P(s)\,\log_2 P(s). \]
dove \(\Sigma\) è il tuo alfabeto di simboli (singoli byte nel file di testo) e la probabilità sia stata calcolata in qualche modo. Non credo sia richiesto il calcolo di ordine maggiore di uno, ma a dire il vero non vedo alcun problema nell'implementarli. È sufficiente considerare come simboli del tuo alfabeto sequenze di caratteri invece che singoli caratteri. Che cosa non ti è chiaro?
\[ - \sum_{s \in \Sigma} P(s)\,\log_2 P(s). \]
dove \(\Sigma\) è il tuo alfabeto di simboli (singoli byte nel file di testo) e la probabilità sia stata calcolata in qualche modo. Non credo sia richiesto il calcolo di ordine maggiore di uno, ma a dire il vero non vedo alcun problema nell'implementarli. È sufficiente considerare come simboli del tuo alfabeto sequenze di caratteri invece che singoli caratteri. Che cosa non ti è chiaro?
Non mi è chiaro come faccio in Java a considerare un file come sequenza di bit, sequenza di bit, o più, in generale, sequenza di m bit...
Puoi per esempio dare una occhiata qui (pagina trovata con una veloce ricerca con Google..). Tendenzialmente leggi i byte di un file e non i singoli bit.. Di fatto sono pochissimi i file in cui i simboli presi in considerazione non siano multipli di bytes per cui lavorerei con byte e basta. Ma se proprio vuoi lavorare con i bit è sufficiente leggere i singoli bit dai byte. Non credo ci sia un modo più comodo: non è qualcosa che si fa spesso.
Si infatti leggo il file come flusso di byte, il problema è proprio suddividere il byte in sequenze di m bits..
Secondo me ti stai complicando la vita. Non credo che l'esercizio ti chieda di lavorare su sequenze di m bit generiche.. Ti consiglio di chiedere chiarimenti.
Purtroppo si invece, per sequenze di 8 bit è facile, per gli altri casi no e non so come fare..
Ma hai chiesto al professore? Per la maggior parte dei file (file compressi esclusi) non ha alcun senso considerare simboli che non siano multipli di un byte. In ogni caso devi usare operazioni bitwise per estrarre i singoli bit. Il modo più semplice è quello di estrarre un bit per volta. Se devi estrarre il bit k dal file consideri il byte k/8 e il resto ti dirà quale bit estrarre. Dopodiché calcoli il resto k%m e vai inserire il bit in quella posizione del simbolo. Probabilmente è più comodo fare un ciclo di simboli e calcolati k piuttosto che considerare direttamente k ma il discorso rimane più o meno lo stesso.
Grazie per l'aiuto, si ho chiesto. Provero' a fare come dici sperando di riuscirci
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo