Binario

[antonio02901]

Ho un elenco di numeri in binario di lunghezza
1
2
3
4
5
6
7

Vorrei altre stringhe sempre in binario che abbiano la lunghezza, che nn si possano confondere fra di loro nn so come fare di lunghezza

1
2
2
3
4
5
6

[_Tipper]

Io, sinceramente, non ho capito quello che devi fare...

[bryce1]

Secondo me vuole rappresentare i valori decimali usando sì i simboli "0" e "1" ma usando una codifica diversa. Il discorso sembra confusionario... ma penso di capire che gli vada bene la "codifica di Huffman" che sfrutta varie lunghezze dei numeri binari ottenuti.
Comunque il problema non è chiaro per niente...

Nicola

[antonio02901]

Praticamente mi servono 7 stringhe in binario che abbiamo lunghezza di
1,2,2,3,4,5,6

che nn si confondano tra di loro

[_Tipper]

Con "che non si confondano fra di loro" intendi che nessuna sia prefisso di un'altra? Cerchi dunque una codifica istantanea?

[_Tipper]

Ripensandoci non è possibile costruire una codifica istantanea, dato che ci sono due stringhe da 2 bit (disuguaglianza di Kraft). Al più si può costruire una codifica univocamente decodificabile, anche se non istantanea.

EDIT: non si può costruire nemmeno una codifica univocamente decodificabile, per via della stessa disuguaglianza.

[antonio02901]

Per me vabene anche non istantanea cosa mi consiglieresti di fare?

Si cmq che nessuna sia prefisso di un altra

[_Tipper]

Se ti va bene una codifica non univocamente decodificabile...

0
10
11
110
1110
11110
111110

Come detto, con quelle lunghezze, non si può costruire una codifica in cui non ci siano codici prefissi di altri...

[antonio02901]

E no mi spiace a me servirebbe qualcosa che puo essere identificata in una unica maniera, perche non si puo?? quel guadagno di un carattere ci puo essere anche alla 3a o 4a stringa l'importante che ci sia

[_Tipper]

"antonio0290":E no mi spiace a me servirebbe qualcosa che puo essere identificata in una unica maniera, perche non si puo??

Il problema è che, se non ho mal interpretato il teorema di Kraft-McMillan, una codifica univocamente decodificabile con codici della lunghezza che richiedi non può essere costruita.

[bryce1]

Questa potrebbe essere direttamente decodificabile:

0
100
101
110
1110
11110
111110

Purtroppo ha le lunghezze 1,3,3,3,4,5,6... e non è quella che volevi. Se qualcun'altro trova una sequenza migliore... meglio.

A mio parere dovresti trovare un'altro set di lunghezze con Huffmann, decidendo quello che ti è più comodo. Nota però che per usare Huffmann devi decidere le "probabilità"/"frequenze" dei diversi simboli che usi.

[antonio02901]

Se ci aggiungi una altra stringa da 2 e\` perfetto, oltre a quelle che stanno gia...

Pero nn credo sia fattibile al massimo puoi aggiungere
00
01
10
11

ma poi ritorniamo al punto di partenza che nn si puo codificare in un unica maniera.....


Ba speriamo che qualcuno ci risponde con una soluzione