Tutti i codici prefissi sono decorabili in modo univoco?

Question

Non riesco a pensare a nessun controexample ma non riesco a trovare alcuna affermazione su Internet o il mio libro di testo neanche.So che per ogni codice decorabile unicamente, esiste un codice di prefisso con la stessa lunghezza media.

Answer 1

È possibile dimostrare per induzione sulla lunghezza della codifica che qualsiasi stringa è decorabile in modo univoco.

Let $ s= s_1 ... s_n $ Sii qualche stringa codificata con un codice libero prefisso.Dal momento che il nostro codice è prefisso, esiste un prefisso unico di $ s $ , $ s_1 ... s_j $ che è una parola di codice. $ s_ {j + 1} ... s_n $ è anche una codifica valida (abbiamo rimosso un singolo codice da una concatenazione di codici), quindi dalla nostra ipotesi induttiva, $ s_ {j + 1} ... s_n $ è unicamente decodificabile, che completa la prova.