[linguaggio C] decodifica di un codice prefisso

[misterx]

ho una certa parola che codificata mi genera i seguenti codici di lunghezza variabili:

a:1
r:0100
t:0101
n:0110
i:0111

se compongo una parola del tipo:
0100010101111010101100111

Qual'è la strategia per la sua decodifica ?
Possibile che per ogni bit letto si debba usare una sorta di if(.....) oppure va usato un albero binario ?

ciao

[lupoxxx87]

penso che il modo più comodo, anche se forse non il più corretto, sia sfruttare le operazioni and, or, xor e not sui bit all'interno degli if

[banryu79]

Beh, visto che il codice 'a' è lungo solo 1 bit mentre tutti gli altri codici ('r','t','n','i') sono lunghi 4 bit intanto devi costruirti un parser che legga una stringa di bit in input 1 bit alla volta:
- se il bit letto vale 1 prendi solo quello come token, e lo decodifichi come 'a'
- se il bit letto vale 0 prendi quello più i successivi 3 come token e lo decodifichi, per esempio, con un costrutto switch-case che discrimina i codici 'r', 't', 'n' e 'i'

Non ho capito a cosa dovrebbe servire l'albero binario?

[lefantome]

assolutamente l'albero binario.

Oltretutto sta implementando l'algoritmo di huffman .

l'albero binario serve per la codifica e la decodifica. in pratica ogni codice di una parola è un path dell'albero per giungere alla foglia a cui è associato un carattere

[||ElChE||88]

Non ho capito a cosa dovrebbe servire l'albero binario?
Leggi un bit alla volta e lo usi per muoverti nell'albero binario.
Se arrivi ad una foglia hai trovato il carattere e puoi ripartire dalla radice.
Se non puoi muoverti nella direzione in cui dovresti ed il nodo non ha un carattere associato (in questo esempio un codice che inizia con 00), hai trovato un errore.
http://www.pctunerup.com/up//results/_201004/20100419130058_Untitled.png

[banryu79]

Sono andato a leggermi la codifica di Huffman, grazie della spiegazione :)

[cdimauro]

ho una certa parola che codificata mi genera i seguenti codici di lunghezza variabili:

a:1
r:0100
t:0101
n:0110
i:0111

se compongo una parola del tipo:
0100010101111010101100111

Qual'è la strategia per la sua decodifica ?
Possibile che per ogni bit letto si debba usare una sorta di if(.....) oppure va usato un albero binario ?

ciao
Con quel tipo di codifica non servono if e neppure alberi binari. Si può fare MOLTO più velocemente.

Se non hai fretta pensaci sù, perché può essere molto stimolante.

Se, invece, ti serve la soluzione quanto prima, fammi sapere.

[banryu79]

Con quel tipo di codifica non servono if e neppure alberi binari. Si può fare MOLTO più velocemente.

Se non hai fretta pensaci sù, perché può essere molto stimolante.

Se, invece, ti serve la soluzione quanto prima, fammi sapere.
*edited*

[misterx]

assolutamente l'albero binario.

Oltretutto sta implementando l'algoritmo di huffman .

l'albero binario serve per la codifica e la decodifica. in pratica ogni codice di una parola è un path dell'albero per giungere alla foglia a cui è associato un carattere

ciao,
è esattamente così. Il mio dubbio è che ad esempio, data la seguente sequenza o meglio, frequenza di caratteri:

a:45
f:16
c:13
12:d
9:i
5:o

graficando su carta, ottengo due alberi binari con profondità differenti e quindi 1 solo bit risparmiato; mi chiedo come fa l'algoritmo a non percorrere l'una anzichè l'altra strada: ma forse con la crescita bottom-up viene di conseguenza ?

[clockover]

Con quel tipo di codifica non servono if e neppure alberi binari. Si può fare MOLTO più velocemente.

Se non hai fretta pensaci sù, perché può essere molto stimolante.

Se, invece, ti serve la soluzione quanto prima, fammi sapere.

anche io ho appena letto cos'è la codifica di huffman (a dire il vero gli ho dato uno sguardo veloce)! Ma forse con una funzione ricorsiva si può fare anche abbastanza facilmente! Non mi fucilate se ho detto ca..ate :D :D

[DanieleC88]

Con quel tipo di codifica non servono if e neppure alberi binari. Si può fare MOLTO più velocemente.

Se non hai fretta pensaci sù, perché può essere molto stimolante.

Se, invece, ti serve la soluzione quanto prima, fammi sapere.

DFA?

[banryu79]

DFA?
No, ancora più veloce :O
P.S.: al massimo mandagli un pvt, così non roviniamo la "suspence" di misterx che magari vuol godersi l'indagine ;)

[WarDuck]

No, ancora più veloce :O
P.S.: al massimo mandagli un pvt, così non roviniamo la "suspence" di misterx che magari vuol godersi l'indagine ;)

Circuito integrato? :asd:

Col DFA ed una matrice per le transizioni si può fare, anche se il numero di stati (almeno per come l'ho pensato io) è maggiore di 5 (dato che sono 5 le "sequenze" diverse da riconoscere).

[DanieleC88]

Più che altro è che con un DFA diventa più o meno uguale al caso dell'albero. Anzi, si trasforma in un grafo, ma la visita è analoga. :P

Ora ci rimugino su e vediamo. Mi divertono queste cose. :D

[banryu79]

Circuito integrato? :asd:

Beh, forse non così veloce, però sicuramente più pratico :D

[WarDuck]

Beh, forse non così veloce, però sicuramente più pratico :D

Che io sappia l'automa a stati finiti per le prestazioni che offre è quanto di più semplice possa esserci.

Basta costruire una matrice di transizione e fare un ciclo, anche perché meno di O(n) non ci puoi mettere dato che devi parsare la stringa.

Usando codifiche un po' più banali o cmq sfruttando la struttura stessa si potrebbe risolvere la cosa con operazioni costanti su caratteri ASCII (e non mi sembra sia questo il caso).

Ma considerando che stiamo in C, non mi vengono cose più pratiche in mente... :Prrr:

[banryu79]

Che io sappia l'automa a stati finiti per le prestazioni che offre è quanto di più semplice possa esserci.

Basta costruire una matrice di transizione e fare un ciclo, anche perché meno di O(n) non ci puoi mettere dato che devi parsare la stringa.

Usando codifiche un po' più banali o cmq sfruttando la struttura stessa si potrebbe risolvere la cosa con operazioni costanti su caratteri ASCII (e non mi sembra sia questo il caso).

Ma considerando che stiamo in C, non mi vengono cose più pratiche in mente... :Prrr:
Avevo pensato anche io a un DFA e anche a altro, poi per non voler aspettare, e per non rovinare la suspence a misterx ho scritto queste idee a cdimauro ma lui ha suggerito altro...

[cdimauro]

anche io ho appena letto cos'è la codifica di huffman (a dire il vero gli ho dato uno sguardo veloce)! Ma forse con una funzione ricorsiva si può fare anche abbastanza facilmente! Non mi fucilate se ho detto ca..ate :D :D
No, con la ricorsione si perde troppo tempo.
Basta costruire una matrice di transizione e fare un ciclo, anche perché meno di O(n) non ci puoi mettere dato che devi parsare la stringa.
No, c'è una soluzione O(1) durante la decodifica, a cui si aggiunge una parte di inizializzazione che è O(2 ^ lunghezza massima dei codici).
Con possibilità di ottimizzazione in caso di soluzione "ibrida" (coi codici più lunghi calcolati tramite albero binario di decodifica).

:cool:

[cionci]

Anche la decodifica di Huffman si può fare senza albero, basta crearsi un vettore di struct in cui viene indicato il carattere corrispondente e l'incremento del contatore dei bit.

Ad esempio, nel caso:

a:1
r:010
t:0110
n:01110
i:01111

Si può fare un vettore di 32 elementi così inizializzato:

[0] => (0, 0) (condizione di errore)
....
[7] => (0, 0) (condizione di errore)
[8] => (r, 3)
[11] => (r, 3)
[12] => (t, 4)
[13] => (t, 4)
[14] => (n, 6)
[15] => (i, 5)
[16] => (a, 1)
....
[31] => (a, 1)

Si prendono 5 bit alla volta, ci si indicizza il vettore, si scrive il carattere e si incrementa il contatore dei bit della grandezza corrispondente.

Oooopsss...mi sa che è la stessa cosa di cui parlava Cesare :D

[WarDuck]

No, con la ricorsione si perde troppo tempo.

No, c'è una soluzione O(1) durante la decodifica, a cui si aggiunge una parte di inizializzazione che è O(2 ^ lunghezza massima dei codici).
Con possibilità di ottimizzazione in caso di soluzione "ibrida" (coi codici più lunghi calcolati tramite albero binario di decodifica).

:cool:

Mmm, provo ad abbozzare una soluzione:

Uso un array di caratteri, in questo caso lungo 8, con indici da 0 a 7.

Lo riempo in corrispondenza degli indici in binario (in 1 metto 'a').

4 - 0100 - 'r'
5 - 0101 - 't'
6 - 0110 - 'n'
7 - 0111 - 'i'

Converto la sequenza a blocchi di 4 usando la conversione binario-decimale e ricavando il carattere dall'array precedentemente riempito.

In questo caso prima mi assicuro che la cifra del blocco iniziale sia diverso da 1.

E' solo un abbozzo ghgh.

Edit: azz ho aspettato troppo per postare (volevo elaborare il codice prima), cionci mi ha anticipato, ma vabbè ora vedo bene cosa dice lui :D.

[cdimauro]

Anche la decodifica di Huffman si può fare senza albero, basta crearsi un vettore di struct in cui viene indicato il carattere corrispondente e l'incremento del contatore dei bit.

Ad esempio, nel caso:

a:1
r:010
t:0110
n:01110
i:01111

Si può fare un vettore di 32 elementi così inizializzato:

[0] => (0, 0) (condizione di errore)
....
[7] => (0, 0) (condizione di errore)
[8] => (r, 3)
[11] => (r, 3)
[12] => (t, 4)
[13] => (t, 4)
[14] => (n, 6)
[15] => (i, 5)
[16] => (a, 1)
....
[31] => (a, 1)

Si prendono 5 bit alla volta, ci si indicizza il vettore, si scrive il carattere e si incrementa il contatore dei bit della grandezza corrispondente.

Oooopsss...mi sa che è la stessa cosa di cui parlava Cesare :D
Bravo Riccardo. :)

[||ElChE||88]

Non capisco mica perché dovrebbe essere O(1)?
Alla fine il tempo impiegato dalla decodifica dipende dalle dimensioni della stringa.
O ho capito male?

[cionci]

Non capisco mica perché dovrebbe essere O(1)?
Alla fine il tempo impiegato dalla decodifica dipende dalle dimensioni della stringa.
O ho capito male?
E' O(1) la decodifica del singolo simbolo.

[||ElChE||88]

E' O(1) la decodifica del singolo simbolo.
Ah ok, pensavo intendesse la decodifica della stringa (in effetti mi sembrava un po' improbabile :fagiano:).

[cdimauro]

Pardon, non sono stato chiaro. Come stringa intendevo la stringa di bit necessari a codificare un simbolo.

[WarDuck]

Non ho ben capito perché usi il contatore del bit da leggere, supponendo che in questo caso si raggruppi a 4 a 4.

L'unica differenza la fa 'a' che è codificato col solo bit 1 (ed è l'unico elemento che comincia con 1).

Scrivo il mio pseudo codice:


code[4] = 'r'
code[5] = 't'
code[6] = 'n'
code[7] = 'i'

input = "0100010101111010101100111"

i = 0;
while (i < input.len):
if (input[i] == '0'):
print code[dec(input[i], 4)] // dec prende puntatore e lunghezza per convertire in decimale
i = i + 4
else:
print 'a'
i++


Così facendo esce fuori: "rtiatni".

@cesare: supponendo di avere a disposizione l'hashmap, secondo te si sarebbe potuta saltare la parte di conversione in binario e usare direttamente le parti di stringa interessate?

[cdimauro]

Non ho ben capito perché usi il contatore del bit da leggere, supponendo che in questo caso si raggruppi a 4 a 4.

L'unica differenza la fa 'a' che è codificato col solo bit 1 (ed è l'unico elemento che comincia con 1).

Scrivo il mio pseudo codice:


code[4] = 'r'
code[5] = 't'
code[6] = 'n'
code[7] = 'i'

input = "0100010101111010101100111"

i = 0;
while (i < input.len):
if (input[i] == '0'):
print code[dec(input[i], 4)] // dec prende puntatore e lunghezza per convertire in decimale
i = i + 4
else:
print 'a'
i++


Così facendo esce fuori: "rtiatni".
Il "contatore" di bit serve a sapere di quanti bit è costituito il match del simbolo, visto che la codifica è a lunghezza variabile.

Inoltre in questo modo il suo codice è abbastanza generico, perché non fa particolari assunzioni sul fatto che c'è un simbolo che viene codificato con un solo bit, e tutti gli altri con 4 bit, mentre il tuo sì.

Detto in altri termini, il tuo codice funziona (bene) soltanto con quella particolare distribuzione, per cui cambiandola quasi sicuramente andrà adattato o riscritto, mentre la soluzione di Riccardo è molto generica: se cambia la distribuzione costruisce una nuova LUT, e il codice rimane invariato.

Si dovrebbe cambiare leggermente per distribuzioni che generano codici di Huffman particolarmente lunghi, e qui subentrerebbe la soluzione "ibrida" di cui parlavo prima (metà LUT-based, e l'altra metà usando l'albero binario di ricerca).
@cesare: supponendo di avere a disposizione l'hashmap, secondo te si sarebbe potuta saltare la parte di conversione in binario e usare direttamente le parti di stringa interessate?
No, sarebbe troppo dispendioso. Un carattere occupa 8 bit.

La LUT, invece, è fatta apposta per occupare quanto meno spazio possibile, lavorando direttamente col flusso di bit codificati.

[WarDuck]

Ah ecco, ora ho capito... diciamo che non avevo considerato il caso in cui le lunghezze di codifica sono diverse :p .

Grazie per la risposta.

[DanieleC88]

Ingegnoso... peccato di non esserci arrivato subito. :cry:

:D

[nuovoUtente86]

E' O(1) la decodifica del singolo simbolo.

resto perplesso su questo punto ovvero sul fatto di poter considerare la codifica del singolo simbolo costante. Se è vero che lo è rispetto alla lunghezza del testo codificato, è anche vero che al k-esimo passaggio di decodifica si va ad effettuare una conversione binario-decimale che è proporzionale alla parola più lunga di codifica dei simboli.
Riflessione più che altro generale, piuttosto che riferita al semplice esempio considerato.

[cionci]

resto perplesso su questo punto ovvero sul fatto di poter considerare la codifica del singolo simbolo costante. Se è vero che lo è rispetto alla lunghezza del testo codificato, è anche vero che al k-esimo passaggio di decodifica si va ad effettuare una conversione binario-decimale che è proporzionale alla parola più lunga di codifica dei simboli.
Riflessione più che altro generale, piuttosto che riferita al semplice esempio considerato.
Questo è vero, ma come hai detto rispetto alla lunghezza dell'intero testo è costante. Anche perché può essere stimata con un limite superiore fisso per qualsiasi codifica.

[nuovoUtente86]

Questo è vero, ma come hai detto rispetto alla lunghezza dell'intero testo è costante. Anche perché può essere stimata con un limite superiore fisso per qualsiasi codifica.

Si esatto, conoscendo la codifica a priori, e perdendo di generalità, siamo (rinunciando però al caso migliore) in grado di fissare un numero costante di operazioni (che alla fine saranno assegnamenti, somme e shift) qualsiasi sia il simbolo.Alla fine nell' esempio fatta ci si ritrova a trattare 5 bit con padding al byte per cui non si ha tanto da discutere. La differenza sarebbe da considerare nel caso in cui (mi sembra se ne è parlato già su) si trattassero gli input come stringhe o con codifica multi-byte.

[cionci]

Si esatto, conoscendo la codifica a priori, e perdendo di generalità
In generale...visto che le sequenze non possono essere più lunghe di 256 bit.

[cdimauro]

Le LUT si possono benissimo calcolare in base alla codifica di Huffman dei simboli correntemente utilizzati, quindi mantenendo la genericità dell'algoritmo.

Questo per lunghezze massime fissate (usualmente 8 bit). Per lunghezze maggiori l'approccio ibrido che ho descritto prima copre anche questi casi rendendo, di fatto, l'algoritmo perfettamente generico (e rimanendo in ogni caso molto più efficiente dell'approccio tradizionale, perché i simboli più frequenti sono anche i più corti e, quindi, vengono decodificati in tempo costante usando la LUT).

[nuovoUtente86]

In generale...visto che le sequenze non possono essere più lunghe di 256 bit.

Ma più aumenta la generalità, più aumenta il costo computazionale costante indipendentemente dal simbolo. L' approccio ibrido, di cui si parlava, è allora, effettivamente, il giusto compresso.

[cionci]

Ma più aumenta la generalità, più aumenta il costo computazionale costante indipendentemente dal simbolo. L' approccio ibrido, di cui si parlava, è allora, effettivamente, il giusto compresso.
Questo è poco ma sicuro.

[banryu79]

* edit

[banryu79]

Anche la decodifica di Huffman si può fare senza albero, basta crearsi un vettore di struct in cui viene indicato il carattere corrispondente e l'incremento del contatore dei bit.

Ad esempio, nel caso:

a:1
r:010
t:0110
n:01110
i:01111

Si può fare un vettore di 32 elementi così inizializzato:

[0] => (0, 0) (condizione di errore)
....
[7] => (0, 0) (condizione di errore)
[8] => (r, 3)
[11] => (r, 3)
[12] => (t, 4)
[13] => (t, 4)
[14] => (n, 6)
[15] => (i, 5)
[16] => (a, 1)
....
[31] => (a, 1)

Si prendono 5 bit alla volta, ci si indicizza il vettore, si scrive il carattere e si incrementa il contatore dei bit della grandezza corrispondente.

Ciao, mi piacerebbe capire bene questa logica e dato che non ho dimestichezza ne esperienze pregresse (ne tantomeno studi == sto in brache di tela :D) mi sono preso la briga di tentare di comprendere il meccanismo che hai illustrato "in modo empirico".

Ecco il mio tentativo:

Codifica (Cionci):
simbolo -> cod binario (cod decimale)
a -> 1 (1)
r -> 010 (2)
t -> 0110 (6)
n -> 01110 (14)
i -> 01111 (15)

Vettore di 32 struct [simbolo/lunghezza] (la lunghezza serve a incrementare un contatore di bit)
[00] [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15]
err. err. err. err. err. err. err. err. r,3. r,3. r,3. r,3. t,4. t,4. n,5. i,5.

[16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31]
a,1. a,1. a,1. a,1. a,1. a,1. a,1. a,1. a,1. a,1. a,1. a,1. a,1. a,1. a,1. a,1.

Esempio input: "ratti"
----------------------
01010110011001111, inputLength==17

parsing (step length of 5 bit):
1. [[01010]]110011001111 -> 01010 = 10 -> (r, 3) -> indexCounter==3
2. 010[[10110]]011001111 -> 10110 = 22 -> (a, 1) -> indexCounter==4
3. 0101[[01100]]11001111 -> 01100 = 12 -> (t, 4) -> indexCounter==8
4. 01010110[[01100]]1111 -> 01100 = 12 -> (t, 4) -> indexCounter==12
5. 010101100110[[01111]] -> 01111 = 15 -> (i, 5) -> indexCounter==17==inputLength

La cosa torna, ho capito che il "passo" di decodifica lungo 5 bit viene determinato dalla lunghezza della più lunga stringa di codifica (in questo caso simboli 'i' e 'n').

Non capisco però come viene inizializzato il vettore di lookup (posizione del tal simbolo, valore di incremento del contatore dei bit associato al simbolo): lo spiegheresti?
Grazie in anticipo :)

[||ElChE||88]

a -> 1 (1)
r -> 010 (2)
t -> 0110 (6)
n -> 01110 (14)
i -> 01111 (15)
Non è giusto, stai leggendo dalla parte sbagliata.
r -> 01000 (8)
t -> 01100 (12)
n -> 01110 (14)
i -> 01111 (15)
a -> 10000 (16)
Ora i numeri combaciano con gli indici del vettore di lookup.

[cionci]

a -> 1 (1)
r -> 010 (2)
t -> 0110 (6)
n -> 01110 (14)
i -> 01111 (15)
Aveva solo stampato il valore della codifica ;) La tabella stampata è giusta.

a:1XXXX
r:010XX
t:0110X
n:01110
i:01111
Nota che la scelta della codifica per ogni simbolo è stata fatta oculatamente. Cioè non esistono simboli che abbiano la parte senza le X corrispondente a quella di un altro simbolo. Questo è d'obbligo perché altrimenti non sarebbe possibile distinguere i simboli l'uno dall'altro.

I bit con la X sono bit di cui non conosciamo il valore (possono essere parte della codifica di qualsiasi altro simbolo), di conseguenza dobbiamo inserire la lettera corrispondente alla codifica in qualsiasi indice della tabella che abbia la parte senza X identica alla codifica del simbolo:
a:1XXXX da 10000 a 11111
r:010XX da 01000 a 01011
t:0110X da 01100 a 01101
n:01110
i:01111

[banryu79]

@cionci
@||ElChE||88
Grazie mille, adesso le cose tornano :)



a:1XXXX
r:010XX
t:0110X
n:01110
i:01111

Nota che la scelta della codifica per ogni simbolo è stata fatta oculatamente. Cioè non esistono simboli che abbiano la parte senza le X corrispondente a quella di un altro simbolo. Questo è d'obbligo perché altrimenti non sarebbe possibile distinguere i simboli l'uno dall'altro.

Quindi la codifica presentata da misterx nel post #1 (http://www.hwupgrade.it/forum/showpost.php?p=31675065&postcount=1) non va bene (è ambigua per questo sistema?)

a: 1XXX
r: 0100
t: 0101
n: 0110
i: 0111

[cionci]

Per "parte" intendevo tutta la parte...
Cioè non puoò esistere una cosa del genere:
a:010XX
b:0101X

[cdimauro]

Ma più aumenta la generalità, più aumenta il costo computazionale costante indipendentemente dal simbolo. L' approccio ibrido, di cui si parlava, è allora, effettivamente, il giusto compresso.
Aggiungo che, nell'approccio ibrido, quando la lunghezza del match è pari a 0, la LUT del simbolo può "puntare" al ramo già attraversato (corrisponde agli 8 bit già "consumati" impiegando la LUT), e da lì proseguire con la classica ricerca binaria.

In questo modo anche per i simboli più lunghi (ma meno frequenti) c'è sempre un guadagno grazie all'impiego della LUT, perché 8 passi vengono "saltati".

[nuovoUtente86]

Aggiungo che, nell'approccio ibrido, quando la lunghezza del match è pari a 0, la LUT del simbolo può "puntare" al ramo già attraversato (corrisponde agli 8 bit già "consumati" impiegando la LUT), e da lì proseguire con la classica ricerca binaria.

In questo modo anche per i simboli più lunghi (ma meno frequenti) c'è sempre un guadagno grazie all'impiego della LUT, perché 8 passi vengono "saltati".

Puoi, cortesemante, fare un esempio. Francamente non riesco a seguire la tua idea.

[cionci]

Puoi, cortesemante, fare un esempio. Francamente non riesco a seguire la tua idea.
Ad esempio, supponi che al massimo tu voglia mappare 8 bit sulla tabella.
Fai una struttura di questo tipo:
struct entry
{
unsigned char c;
unsigned int lenght;
btree * t;
};

Considera tutti i caratteri aventi codifica di lunghezza maggiore di 8 bit... Basta raggruppare in un albero binario tutte le codifiche che hanno i primi 8 bit uguali ;)
Se lenght==9 allora si scorre l'albero fino a trovare il carattere corrispondente alla codifica sfruttando i bit successivi ai primi 8.

[banryu79]

Per "parte" intendevo tutta la parte...
Cioè non puoò esistere una cosa del genere:
a:010XX
b:0101X
Many thanks :mano:
(grazie per la vostra disponibilità nello spiegare le cose)

Ora mi torna:

Codifica (misterx):
simbolo -> cod binario (cod decimale)
a -> 1 (1) 1XXX.... da 1000(8) a 1111(15)
r -> 0100 (4) 0100....
t -> 0101 (5) 0101....
n -> 0110 (6) 0110....
i -> 0111 (7) 0111....

stepLength=4.

Vettore di 16 struct [simbolo/lunghezza] (la lunghezza serve a incrementare un contatore di bit)
[00] [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15]
err. err. err. err. r,4. t,4. n,4. i,4. a,1. a,1. a,1. a,1. a,1. a,1. a,1. a,1.

Esempio input: "ratti"
----------------------
0100 1 0101 0101 0111, inputLength==17

parsing (step length of 4 bit):
1. [[0100]]1010101010111 -> 0100 = 4 -> (r, 4) -> indexCounter==4
2. 0100[[1010]]101010111 -> 1010 = 10 -> (a, 1) -> indexCounter==5
3. 01001[[0101]]01010111 -> 0101 = 5 -> (t, 4) -> indexCounter==9
4. 010010101[[0101]]0111 -> 0101 = 5 -> (t, 4) -> indexCounter==13
5. 0100101010101[[0111]] -> 0111 = 7 -> (i, 4) -> indexCounter==17==inputLength


@EDIT:
Ho notato che l'alfabeto dei simboli nel tuo esempio e in quello di misterx è il medesimo Sigma = {r,t,n,i,a}
Ma mentre nel tuo esempio usiamo 32 bit per la LUT, in questo di misterx ne usiamo 16 (perchè nel tuo esempio, per via della codifica scelta, il codice/codici possibili del simbolo 'a' convertito in decimale vale da 16 a 32).
Dunque una scelta occulata della codifica permette di risparmiare spazio per la LUT.

[marco.r]

E' O(1) la decodifica del singolo simbolo.

In realta' la complessita' asintotica non varia, perche' se considero finito il numero massimo di bit allora entrambi i casi sono O(1), mentre se lo considero potenzialmente illimitato allora entrambi sono O(n).
E' comunque vero che la differenza pratica e' notevole dato che il fattore (costante) di differenza e' dato dal fatto che l'algoritmo naive esegue un numero di controlli maggiore di un fattore 8/16/32 (a seconda della dimensione degli interi usati per la tabella).

[cionci]

Ma mentre nel tuo esempio usiamo 32 bit per la LUT, in questo di misterx ne usiamo 16 (perchè nel tuo esempio, per via della codifica scelta, il codice/codici possibili del simbolo 'a' convertito in decimale vale da 16 a 32).
Dunque una scelta occulata della codifica permette di risparmiare spazio per la LUT.
Certo, ma dipende dalle motivazioni che ti portano alla scelta. In Huffman si usano le frequenze dei vari simboli per generare le codifiche. A simbolo meno frequente corrisponde una codifica più lunga.
La codifica che avevo scelto io era solo per creare un esempio un po' più esplicativo.

[nuovoUtente86]

Many thanks :mano:
(grazie per la vostra disponibilità nello spiegare le cose)

Ora mi torna:

Codifica (misterx):
simbolo -> cod binario (cod decimale)
a -> 1 (1) 1XXX.... da 1000(8) a 1111(15)
r -> 0100 (4) 0100....
t -> 0101 (5) 0101....
n -> 0110 (6) 0110....
i -> 0111 (7) 0111....

stepLength=4.

Vettore di 16 struct [simbolo/lunghezza] (la lunghezza serve a incrementare un contatore di bit)
[00] [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15]
err. err. err. err. r,4. t,4. n,4. i,4. a,1. a,1. a,1. a,1. a,1. a,1. a,1. a,1.

Esempio input: "ratti"
----------------------
0100 1 0101 0101 0111, inputLength==17

parsing (step length of 4 bit):
1. [[0100]]1010101010111 -> 0100 = 4 -> (r, 4) -> indexCounter==4
2. 0100[[1010]]101010111 -> 1010 = 10 -> (a, 1) -> indexCounter==5
3. 01001[[0101]]01010111 -> 0101 = 5 -> (t, 4) -> indexCounter==9
4. 010010101[[0101]]0111 -> 0101 = 5 -> (t, 4) -> indexCounter==13
5. 0100101010101[[0111]] -> 0111 = 7 -> (i, 4) -> indexCounter==17==inputLength


@EDIT:
Ho notato che l'alfabeto dei simboli nel tuo esempio e in quello di misterx è il medesimo Sigma = {r,t,n,i,a}
Ma mentre nel tuo esempio usiamo 32 bit per la LUT, in questo di misterx ne usiamo 16 (perchè nel tuo esempio, per via della codifica scelta, il codice/codici possibili del simbolo 'a' convertito in decimale vale da 16 a 32).
Dunque una scelta occulata della codifica permette di risparmiare spazio per la LUT.

In realtà 32 sono i possibili valori codificabili e quindi indicizzabili in decimale, per cui bastano 5 bit (che poi corrispondo alla massima parola di codifica).

[nuovoUtente86]

Forse è interessante considerare la complessità nei vari casi.
Nel caso andiamo a scansionare linearmente tutto il testo da decodificare, avremmo, indipendentemente dalle occorrenze dei simboli, un costo proporzionale alla lunghezza dell' input.
Con l' utilizzo della lista associativa, ad ogni passo, consideriamo :
-il costo di conversione, per ora abbiamo detto costante
-il costo di indicizzazione, sempre costante.
Nel caso peggiore (un testo composto unicamente dal simbolo minimale) abbiamo un costo pari a 2*n, quindi ancora lineare.
Nel caso migliore (testo composto dal simbolo a codifica più lunga) avremmo un costo di 2*(n/w) dove w è la word di codifica massima. Qui il costo è sublineare, ma resta vantaggioso fintanto che, come già detto, possiamo considerare il passo di conversione costante.

[misterx]

per il numero di occorrenze mi sono avvalso di un semplice array inizializzato con 255 elementi in quanto sto considerando solo i caratteri ASCII. Il carattere letto in input come intero lo uso come indice dell'array e vado quindi ad incrementarne il suo contenuto.


int occorrenze[255];
occorrenze[carattere letto]++;


Così facendo credo che la complessità del mio algoritmo sia dell'ordine di O(1) vero ?

ciao

[cionci]

E' O(N) con N il numero dei caratteri.
Comunque il fatto che tu ti fermi a 255 non è dovuto alla codifica ASCII, è dovuto al fatto che stai usando un byte ;)

[nuovoUtente86]

per il numero di occorrenze mi sono avvalso di un semplice array inizializzato con 255 elementi in quanto sto considerando solo i caratteri ASCII. Il carattere letto in input come intero lo uso come indice dell'array e vado quindi ad incrementarne il suo contenuto.


int occorrenze[255];
occorrenze[carattere letto]++;


Così facendo credo che la complessità del mio algoritmo sia dell'ordine di O(1) vero ?

ciao

come scritto sopra:

Nel caso andiamo a scansionare linearmente tutto il testo da decodificare, avremmo, indipendentemente dalle occorrenze dei simboli, un costo proporzionale alla lunghezza dell' input.

[misterx]

E' O(N) con N il numero dei caratteri.
Comunque il fatto che tu ti fermi a 255 non è dovuto alla codifica ASCII, è dovuto al fatto che stai usando un byte ;)

ciao,
ho scritto ASCII per sottolineare che mi stavo occupando di testi scritti; comunque grazie

ciao