codice di Huffman estesa

Question

ho questo compito: trovare le parole in codice per i simboli in un dato alfabeto. Si dice che devo utilizzare Huffman binario su gruppi di tre simboli. Che cosa significa esattamente? Faccio a usare regolarmente Huffman su [Alfabeto] ^ 3? Se sì, come posso poi dire la differenza tra i 3 simboli in un gruppo?

Answer 1

Non riesco a dire, perché la vostra descrizione del problema non è poi così dettagliata, ma direi che significa che invece di codificare ogni simbolo nel vostro alfabeto singolarmente, si suppone di percorrere ogni tripla di simboli come gruppo.

Così, per esempio, se il vostro alfabeto è composto da a, b, e c, invece di generare una codifica per ciascuno di coloro che singolarmente, si potrebbe creare una codifica per aaa, aab, aac, ecc Ognuna di queste stringhe verrebbe trattato come un simbolo separata nel algoritmo di Huffman; è possibile distinguerli semplicemente facendo confronto tra stringhe su di loro. Se avete bisogno di accettare l'input di lunghezza arbitraria, si dovrà anche includere nei simboli dell'alfabeto che sono stringhe di lunghezza 1 o 2. Per esempio, se si sta codificando il aabacab stringa, si avrebbe bisogno di rompere quel giù nel simboli aab, aca e b.

Non che aiutano a rispondere alla tua domanda? Non ero abbastanza sicuro di quello che stai cercando, quindi non esitate a modificare la tua domanda o la risposta in un commento se questo non ha chiarito nulla fino.

Answer 2

Cibo per la mente: che dire di stringhe più brevi, e le permutazioni di "confini" del blocco? Che dire 1 e 2 stringhe di caratteri? Non basta contare fuori 3, 6, 9, 12, ... caratteri nel tuo testo di input e pad quindi nullo tutte le lunghezze irregolari, alla fine?

Se i pezzi possono essere di dimensioni variabili, poi diventa davvero interessante per trovare la soluzione migliore. Ho il sospetto che degenera in una specie di commesso viaggiatore problema, ma forse c'è un "teorema" puro o altro strumento là fuori per questo genere di cose.

Forse provare tutte le permutazioni di 3 caratteri, risparmiando il più utilizzato, quindi provare a trovare una buona misura per le lacune lunghe 1 e 2 char? Hmm, suona come potrebbe essere molto lento, ma fattibile utilizzando qualche tipo di divisione ricorsiva e approccio counquer: estrarre la lunga stringa di lunghezza blocco N, poi ricorsivamente codificante lacune come lunghezza N - 1

.

più domande che risposte, ho paura.