[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]

Originariamente inviato da banryu79

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.

[banryu79]

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

[cdimauro]

Originariamente inviato da 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

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]

Originariamente inviato da cdimauro

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]

Originariamente inviato da 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

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]

Originariamente inviato da cdimauro

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

[DanieleC88]

Originariamente inviato da cdimauro

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]

Originariamente inviato da DanieleC88

DFA?

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

[WarDuck]

Originariamente inviato da banryu79

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

Circuito integrato?

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.

[banryu79]

Originariamente inviato da WarDuck

Circuito integrato?

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

[WarDuck]

Originariamente inviato da banryu79

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

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...

[banryu79]

Originariamente inviato da WarDuck

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...

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]

Originariamente inviato da clockover

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

No, con la ricorsione si perde troppo tempo.

Originariamente inviato da WarDuck

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).

[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

[WarDuck]

Originariamente inviato da cdimauro

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).

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 .