Codice di sorgente a prefisso?!

[Gremo]

Caio a tutti scrivo qui perché non riesco a trovare una sezione più adatta , anche se sono certo che nessuno risponderà .

In ogni caso ho un dizionario delle parole di codice così fatto, semplice semplice:

W = {0, 001, 101, 11}

Nella Teoria dell'Informazione un codice si dice univocamente decodificabile se è a prefisso, ossia (cito testualmente) se nessuna parola di codice è prefisso di ogni altra parola di codice (si, la scelta del termine è stata un pò infelice, occorreva chiamarlo non-a-prefisso...ma tant'è).

Nell'esempio W sembra non essere a prefisso, poiché evidentemente la parola 0 è prefisso della parola 001. Ma il metodo di Sardinas-Patterson dimostra il contrario.

Dove sbaglio? E mi è confermato dal fatto che un ipotetico decodificatore mostrerebbe del ritardo, esempietto:

- Arriva 0 -> non posso decidere se si tratta di 'a' o è l'inizio di 'b'
- (RITARDO)
- Arriva di nuovo 0 -> non posso decidere se è 'aa' oppure l'inizio di 'b' (RITARDO).
  Se arriva 1 allora ho terminato la prima parola.
- Arriva 0 | 1 -> posso finalmente decidere:
  se è zero, allora ho 'aa' e continuo, altrimenti ho 'b' e continuo.

Segue quindi che W presenta ritardo, non è istantaneo e quindi neanche a prefisso...

[tuccio`]

se è prefisso, è univocamente decodificabile.. in generale non vale l'implicazione inversa, ma in casi particolari (come il tuo) sì.. non capisco il punto, e neanche cosa intendi per "ritardo" finché puoi leggere usando una finestra di dimensione costante (3 nel tuo caso) non credo si possa parlare di ritardo

[lock cmpxchg8b %ebx]

Prova a dare un occhiata a questo thread (i post "interessanti" sono quelli di cionci e cdimauro).

[Gremo]

Originariamente inviato da tuccio`

se è prefisso, è univocamente decodificabile.. in generale non vale l'implicazione inversa, ma in casi particolari (come il tuo) sì..non capisco il punto

Dici che nel mio caso si...ma il mio non è a prefisso, o sbaglio?

Originariamente inviato da tuccio`

e neanche cosa intendi per "ritardo" finché puoi leggere usando una finestra di dimensione costante (3 nel tuo caso) non credo si possa parlare di ritardo

Ritardo nella decodifica, perchè non puoi sapere all'arrivo dello 0 iniziale, di quale parola si tratti...tu cosa intendi per finestra di dimensione costante? Questo codice è B-LV...quindi a lunghezza variabile!

[tuccio`]

Originariamente inviato da Gremo

Dici che nel mio caso si...ma il mio non è a prefisso, o sbaglio?

certo, non è a prefisso.. quello che dico è che se è prefisso, è decodificabile in modo univoco, ma se è decodificabile in modo univoco non è detto che sia a prefisso.. quindi ci sono codici (come quello che hai postato) che sono decodificabili in modo univoco anche se non sono codici prefisso

Originariamente inviato da Gremo

Ritardo nella decodifica, perchè non puoi sapere all'arrivo dello 0 iniziale, di quale parola si tratti...tu cosa intendi per finestra di dimensione costante? Questo codice è B-LV...quindi a lunghezza variabile!

intendo dire che se la parola di codice più lunga è di 3 bit, al massimo dovrai leggere 3 bit per decodificare (quindi per decodificare devi mantenere una "finestra" di lunghezza 3 sulla stringa che sposti avanti man mano che decodifichi), e la decodifica, fissato un codice, rimane lineare rispetto alla lunghezza della stringa (sempre che il tuo problema sia la complessità della decodifica)..

[Gremo]

Originariamente inviato da Antonio23

è condizione sufficiente ma non necessaria

L'essere u.d. è necessaria ma non sufficiente, il contrario di quello che dici tu. Ossia per un codice, l'essere u.d. è una proprietà che deve essere necessariamente presente se il codice è a prefisso, ma da sola non è sufficiente a garantirne quest'ultima.

Sostanzialmente:
u.d. -> a-prefisso o non-a-prefisso
prefisso -> u.d

Baglio? In ogni caso, W è o non è a prefisso?

Altro esempietto, questa volta provate a rispondere: 0, 2, 03, 011, 104, 341, 11234 è a prefisso?

[Gremo]

Originariamente inviato da tuccio`

certo, non è a prefisso.. quello che dico è che se è prefisso, è decodificabile in modo univoco, ma se è decodificabile in modo univoco non è detto che sia a prefisso.. quindi ci sono codici (come quello che hai postato) che sono decodificabili in modo univoco anche se non sono codici prefisso
intendo dire che se la parola di codice più lunga è di 3 bit, al massimo dovrai leggere 3 bit per decodificare (quindi per decodificare devi mantenere una "finestra" di lunghezza 3 sulla stringa che sposti avanti man mano che decodifichi), e la decodifica, fissato un codice, rimane lineare rispetto alla lunghezza della stringa (sempre che il tuo problema sia la complessità della decodifica)..

Ok grazie, è chiara la prima parte ma la seconda non molto...cmq a questo punto credo che ci sia un errore nel libro, guarda l'esempio che ho postato sopra...

[Gremo]

Ok visto che sono abbastanza esaurito, è venerdì sera e sto studiando, mi sono preso la briga di scannerizzare un attimo la pagina del libro che parla della sequenza: 0, 2, 03, 011, 104, 341, 11234. Ditemi come fa a essere a prefisso... (è sicuramente u.d.):

[tuccio`]

il tuo libro dice che W2 è univocamente decodificabile, ma non è scritto da nessuna parte che è a prefisso (e infatti non lo è).. dice che W3 è un codice prefisso

[Gremo]

Originariamente inviato da tuccio`

il tuo libro dice che W2 è univocamente decodificabile, ma non è scritto da nessuna parte che è a prefisso (e infatti non lo è).. dice che W3 è un codice prefisso

La parola x è un prefisso della parola y se y = x z: informalmente, x è un prefisso di y se la parola y comincia con la parola x. Un codice prefisso, come spiegato nel testo, è un codice in cui nessuna parola è prefisso di un’altra.

W3 = 0, 2, 03, 011, 104, 341, 11234: posto x = 0, sia ha che 03 = x 3, e inoltre 011 = x 11. Sono diventato stupido?

[tuccio`]

non l'avevo nemmeno guardato W3, visto che parlavi di W2.. non saprei che dirti, sembrerebbe sbagliato anche a me, ma non è che sia un grande esperto di queste cose.. ti tocca aspettare qualcun altro

[wingman87]

Originariamente inviato da Gremo

Ma il teorema cosa dice?

[Gremo]

Originariamente inviato da wingman87

Ma il teorema cosa dice?

In questa pagina, viene usato il metodo di Sardinas-Patterson per capire se un codice è u.d. oppure no... se in una di quelle colonne R1...RN (R0 è il codice in sè) vedi qualche parola presente in R0, allora non è u.d., viceversa lo è. Inoltre, se l'ultimo insieme RN finisce con l'insieme vuoto, il codice è a prefisso.

Secondo te W3 è a prefisso oppure no?!

Originariamente inviato da Antonio23

eh? l'essere a prefisso è condizione sufficiente per l'essere univocamente decodificabile, ma non necessaria, ovvero non vale l'implicazione inversa, ed il tuo codice all'inizio lo dimostra...

Stiamo parlando adesso del codice W3... grazie a voi ho capito che W2 può anche non essere a prefisso (e infatti non lo è..)

[wingman87]

Originariamente inviato da Gremo

In questa pagina, viene usato il metodo di Sardinas-Patterson per capire se un codice è u.d. oppure no... se in una di quelle colonne R1...RN (R0 è il codice in sè) vedi qualche parola presente in R0, allora non è u.d., viceversa lo è. Inoltre, se l'ultimo insieme RN finisce con l'insieme vuoto, il codice è a prefisso.

Ma le colonne come si costruiscono?

Originariamente inviato da Gremo

Secondo te W3 è a prefisso oppure no?!

Secondo la definizione che conosco io, che poi è anche quella che hai ripetuto qualche post fa, no.

[Gremo]

Originariamente inviato da wingman87

Ma le colonne come si costruiscono?

Detto semplice semplice:
1) Poni R0 = W

R0 = {10, 010, 1, 1110}

2) Crei R1 facendo tutte le possibili coppie di parole di R0, e se qualche parola è prefisso di un'altra, ne prendi il suffisso. Poiché 1 è prefisso di 10, prendi 0. E poiché 1 lo è anche di 1110, prendi 110. R1 diventa:

R1 = {0, 110}

3) Continui creando RN verificando che qualche elmento di R0 sia prefisso di qualche elemento di RN-1 (e viceversa). In questo caso R2 quindi è creato confrontando R0/R1. Nell'esempio 1 è sempre prefisso di 110, quindi prendi 10. R2 diventa:

R2 = {10}

E questo è l'ultimo insieme. Poiché R2 contiene 10 e 10 è parola di W, il codice non è a prefisso.

Originariamente inviato da wingman87

Secondo la definizione che conosco io, che poi è anche quella che hai ripetuto qualche post fa, no.

C'è qualcosa che sbaglio, dubito che il libro sia in torto. Anche perché seguendo il procedimento di sopra, il codice W3 del libro termina con l'insieme vuoto...se così è sicuramente a prefisso, il libro sbaglierebbe anche in quello.

[wingman87]

Mi sono documentato su wikipedia:
http://en.wikipedia.org/wiki/Sardina...rson_algorithm
http://en.wikipedia.org/wiki/Prefix_code
Evidentemente nel tuo libro c'è un errore, ma bello grosso.
Sto tentando di immaginare come possa l'autore aver sbagliato così...
Forse l'autore intende qualcos'altro per codice a prefisso (ma immagino che tu la definizione l'abbia presa da quel libro).
Il problema è la frase in alto:

Si osservi che se l'ultimo insieme che si costruisce è vuoto, allora il codice è anche a prefisso.

Semmai se il primo che si costruisce è vuoto... Forse l'autore si è confuso e dopo dando per giusto quello che aveva scritto sopra ha aggiunto la frase sotto:

ciò garantisce che si tratta di codice a prefisso.

Anzi, riflettendoci meglio credo che l'errore sia meno grave, mi spiego: è innegabile che il codice W3 ha una caratteristica che il codice W2 non ha, infatti se prendi uno stream continuo di parole dell'insieme W3 puoi decodificarle in modo "continuo", nel senso che hai la certezza che la decodifica possa proseguire senza intoppi, anche se a volte con del ritardo (come spiegavi qualche post sopra), invece nel caso di W2 c'è almeno una sequenza di caratteri che se ripetuti non permettono di decidere come decodificare la stringa finché la ripetizione non termina.
Esempio:
0011111111111...
Ricordando che W2={0,001,101,11}
finché la sequenza di 1 non termina non possiamo sapere se 001 è la parola 001 oppure la concatenazione di due 0 e 11

Credo quindi che l'autore volesse sottolineare questa caratteristica ma si è confuso ed ha usato un termine errato. Personalmente non so come è definita questa caratteristica.

PS: come vedi ho cambiato opinione nel corso del messaggio, ho preferito comunque lasciare anche la prima parte, così è possibile ripercorrere completamente il mio pensiero.

[Gremo]

Originariamente inviato da wingman87

Mi sono documentato su wikipedia:
http://en.wikipedia.org/wiki/Sardina...rson_algorithm
http://en.wikipedia.org/wiki/Prefix_code
Evidentemente nel tuo libro c'è un errore, ma bello grosso.
Sto tentando di immaginare come possa l'autore aver sbagliato così...
Forse l'autore intende qualcos'altro per codice a prefisso (ma immagino che tu la definizione l'abbia presa da quel libro).
Il problema è la frase in alto:

Semmai se il primo che si costruisce è vuoto... Forse l'autore si è confuso e dopo dando per giusto quello che aveva scritto sopra ha aggiunto la frase sotto:

Ecco, anche io ho pensato subito che dovesse essere il primo insieme ad essere vuoto per garantire anche il prefisso, perché in R1 per definizione ci vanno i suffissi (quindi devono esistere i prefissi tra le coppie di W3...).

E l'errore a me sembra MOLTO grosso...insomma non è un termine con un altro, è sbagliata l'affermazione ("se l'ultimo insieme è vuoto..."), la citazione, nonché affermare che W3 è a prefisso...

In effetti tra le dispense online non ho trovato questo tipo di relazione tra insieme vuoto e codice a prefisso, occorrerebbe leggere quello scritto del 1990.

Originariamente inviato da wingman87

Anzi, riflettendoci meglio credo che l'errore sia meno grave, mi spiego: è innegabile che il codice W3 ha una caratteristica che il codice W2 non ha, infatti se prendi uno stream continuo di parole dell'insieme W3 puoi decodificarle in modo "continuo", nel senso che hai la certezza che la decodifica possa proseguire senza intoppi, anche se a volte con del ritardo (come spiegavi qualche post sopra), invece nel caso di W2 c'è almeno una sequenza di caratteri che se ripetuti non permettono di decidere come decodificare la stringa finché la ripetizione non termina.
Esempio:
0011111111111...
Ricordando che W2={0,001,101,11}
finché la sequenza di 1 non termina non possiamo sapere se 001 è la parola 001 oppure la concatenazione di due 0 e 11

Credo quindi che l'autore volesse sottolineare questa caratteristica ma si è confuso ed ha usato un termine errato. Personalmente non so come è definita questa caratteristica.

PS: come vedi ho cambiato opinione nel corso del messaggio, ho preferito comunque lasciare anche la prima parte, così è possibile ripercorrere completamente il mio pensiero.

E qui mi smonti , il ragionamento è corretto. Ma la caratteristica che dici tu come si chiamerebbe? Perché l'unica cosa che si avvicina è l'essere un codice istantaneo (senza ritardi di decodifica), ma ancora una volta (cito testualmente), il libro afferma che "un codice è istantaneo se e solo se è a prefisso". Nessuno dei 3 codici sarebbe a prefisso, secondo noi, quindi nessuno dovrebbe essere istantaneo.

In quest'ottica, W3 però sembrerebbe istantaneo (pur ammettendo ritardi di decodifica finiti), mentre W2 no (sono potenzialmente infiniti, almeno credo, visto il tuo esempio). Purtroppo il libro (un libro universalmente adottato dalle università) anche in questo caso non specifica cosa intende precisamente per "istantaneo": ammettere nessun ritardo o un piccolo ritardo finito? Perchè un codice W = { 00, 01, 11 } è sicuramente istantaneo (appena finisce la parola, sappiamo qual è), mentre W3 dell'esempio dovrebbe mostrare un ritardo piccolo (non riesco a trovare un buon esempio...).

In ogni caso, in settimana chiederò direttamente al prof. e vi farò sapere. Inutile dire che ti ringrazio enormemente per le tue ricerche e il tuo sforzo!