Considera un alfabeto dei simboli k e un requisito per codificare in modo ottimale una serie di valori di frequenza nota. La scelta ovvia per questo è usare la codifica di Huffman, che è nota per essere ottimale per questo problema. Consideriamo ora il requisito in più che quando i valori codificati sono ricevuti non sarà noto se i simboli che li rappresentano siano stati invertiti, così per esempio se la codifica suggerisce che "valore 1" è codificato come "aab", potrebbe essere ricevuto dal destinatario come "aab" o "baa". Pertanto, ogni codifica utilizzata non deve avere una codifica valida che contenga gli stessi simboli in ordine inverso.
Quando k > 2 , una possibile implementazione potrebbe essere quella di riservare uno dei simboli per un "bit di avvio" e assicurarsi che non venga mai utilizzato come simbolo terminale di alcun codice. Ma ci sono approcci migliori?
Aggiornamento
Proprio per questo chiunque può leggere di più di ciò di cui stavo parlando, puoi vedere l'implementazione finale che ho scritto (usando l'algoritmo che stavo suggerendo sopra, ad eccezione di quello invertito - riservo un colore per il marcatore finale e non usarlo nel primo simbolo, poiché è molto più semplice da implementare a causa del modo in cui l'algoritmo di Huffman antepone i simboli al codice man mano che cresce) qui: link
Sono ancora interessato a qualche idea migliore, se qualcuno ne può trovare uno.