Nota: questa domanda è stata riscritta per semplificare e generalizzare il problema. L'originale è disponibile sotto.
Supponiamo di aver creato un semplice schema di compressione per elenchi di numeri a 2 cifre. Ha 2 modalità:
- Modo 0: i numeri sono scritti così come sono, non compressi.
- Modalità 1: per ogni numero viene scritta solo la cifra, ma l'esecuzione dei numeri deve avere la stessa cifra delle decine. Ciò fornisce una compressione 2: 1 data una lista infinita di numeri con la stessa cifra delle decine.
La stringa di output compresso deve contenere solo le cifre 0-9, ad eccezione dei seguenti valori magici di 3 caratteri che devono essere utilizzati per cambiare la modalità di compressione:
-
***: passa alla modalità 0 -
*x*: passa alla modalità 1, dove x è la cifra delle decine comune per i numeri che seguono. Se la cifra delle decine cambia, l'interruttore della modalità 1 deve essere scritto di nuovo, con una cifra delle decine comune diversa.
Il compressore può passare liberamente tra le due modalità di compressione. Quindi, in due modi che l'elenco di numeri 11 12 13 14 21 22 23 24 può essere codificato sono:
***1112131421222324 (only mode 0, each number written out as-is)
*1*1234*2*1234 (only mode 1, only ones digits are written after the mode switches,
but mode 1 needed to be started twice, for each diff. tens digit)
Nell'esempio sopra, usando la modalità 1 hai salvato 5 caratteri, ma non è sempre così. Codifica dell'elenco 15 26 37 48 :
***15263748
*1*5*2*6*3*7*4*8
è più corto in modalità 0. E ovviamente, nei testi più complessi, le modalità devono essere mixate correttamente per fornire il risultato più breve. Ad esempio, codifica l'elenco 11 12 21 22 23 24 25 26 18 39 :
***11122122232425261839 (only mode 0)
*1*12*2*123456*1*8*3*9 (only mode 1)
*1*12*2*123456***1839 (mode 1 then mode 0)
la terza codifica fornisce il risultato più breve, mescolando correttamente le modalità di codifica.
Data questa specifica, un codificatore che cerca esaustivamente di mixare le 2 modalità mentre codifica una lista di numeri darà il risultato compresso più breve possibile. Ovviamente, un tale encoder impiega un tempo ridicolmente lungo - O (n ^ n). Cercando di pensare a un codificatore più efficiente, sono rimasto perplesso.
Quindi la mia domanda - è possibile, date le suddette specifiche, scrivere un codificatore che avrebbe prestazioni migliori di O (n ^ n) - che potrebbe prendere decisioni nel mixare le 2 modalità di compressione senza provare esaustivamente ogni singola combinazione? O l'algoritmo esaustivo è l'unico modo per ottenere la stringa compressa più corta possibile?
Grazie in anticipo a tutti coloro che condividono qualsiasi opinione su questo. Nota che il mio obiettivo è quello di capire il problema generale di compressione illustrato nella mia domanda, piuttosto che trovare / creare un efficiente compressore di liste di numeri.
=============================================================================
Below is my question as it was phrased originally, in terms of text encoding
=============================================================================
Ho ideato un semplice schema di compressione del testo UTF-16 con 2 modalità:
- Modo 0: le coppie di byte UTF-16 vengono scritte così come sono, non compresse.
- Modalità 1: per ogni carattere viene scritto solo il byte meno significativo, ma l'esecuzione dei caratteri deve avere lo stesso byte più significativo (essere dello stesso blocco unicode). Ciò fornisce una compressione 2: 1 data una stringa infinita di caratteri dallo stesso blocco unicode.
Supponiamo che occorra 3 byte per cambiare la modalità. Anche la commutazione del byte più significativo (blocco Unicode) sulla modalità 1 richiede 3 byte.
Di seguito sono riportati alcuni esempi di come il testo UTF-16 può essere codificato in base a questa specifica. Negli esempi,
"a" = any character from unicode block 1
"b" = any character from unicode block 2
"===" = 3-byte value indicating mode 0 is now active
"---" = 3-byte value indicating mode 1 is now active
Quindi il testo "aaaabbbb" (4 caratteri diversi dal blocco unicode1 e 4 caratteri diff. dal blocco unicode 2) può essere codificato come
===aaaaaaaabbbbbbbb (each letter takes up 2 bytes) -or-
---aaaa---bbbb (each letter takes up 1 byte, but mode 1 needed to be started twice, because b is from a different block than a)
Nell'esempio precedente, l'utilizzo della modalità 1 ha salvato 5 byte, ma non è sempre il caso. Codifica del testo "abab",
===aabbaabb
---a---b---a---b
è più corto in modalità 0. E ovviamente, nei testi più complessi, le modalità devono essere mixate correttamente per fornire il risultato più breve. Ad esempio, codifica il testo "abbbbbbab",
===aabbbbbbbbbbbbaabb
---a---bbbbbb---a---b
---a---bbbbbb===aabb
la terza codifica fornisce il risultato più breve, mescolando correttamente le modalità di codifica.
Ho scritto un codificatore, data questa specifica, che cerca esaustivamente di mixare le 2 modalità mentre codifica una stringa e produce il risultato più breve. Ovviamente, questo richiede un tempo ridicolmente lungo - O (n ^ n). Cercando di scrivere un codificatore più efficiente, sono rimasto perplesso.
Quindi la mia domanda - è possibile, date le suddette specifiche, scrivere un codificatore che avrebbe prestazioni migliori di O (n ^ n) - che potrebbe prendere decisioni nel mixare le 2 modalità di compressione senza provare esaustivamente ogni singola combinazione? O l'algoritmo esaustivo è l'unico modo per ottenere la stringa compressa più corta possibile?
Grazie in anticipo a tutti coloro che condividono qualsiasi opinione su questo. Tieni presente che il mio obiettivo è capire il problema generale di compressione illustrato nella mia domanda, piuttosto che trovare / creare un codificatore di testo efficiente.