I concorrenti più vicini che ho trovato finora sono yEnc (2%) e ASCII85 (25% di spese generali). Sembrano esserci alcuni problemi attorno a yEnc principalmente attorno al fatto che utilizza un set di caratteri a 8 bit. Il che porta a un altro pensiero: esiste una codifica binaria in testo basata sul set di caratteri UTF-8?Qual è la codifica binaria più efficiente del testo?
Per ispirazione, è possibile controllare the Twitter Image Encoding Challenge. Si tratta di codificare il maggior numero possibile di informazioni sull'immagine in 140 caratteri Unicode. È essenzialmente una versione smarrita della tua domanda specificamente legata ai dati dell'immagine.
Questo dipende molto dalla natura dei dati binari e dai vincoli che "testo" pone sul risultato.
Prima di tutto, se i dati binari non sono compressi, provare a comprimere prima della codifica. Possiamo quindi supporre che la distribuzione di 1/0 o singoli byte sia più o meno casuale.
Ora: perché hai bisogno di un testo? In genere, è perché il canale di comunicazione non passa attraverso tutti i personaggi allo stesso modo. per esempio. potresti richiedere un testo ASCII puro, i cui caratteri stampabili vanno da 0x20-0x7E. Hai 95 personaggi con cui giocare. Ogni carattere può teoricamente codificare log2 (95) ~ = 6.57 bit per carattere. È facile definire una trasformazione che si avvicina molto.
Ma: cosa succede se hai bisogno di un carattere separatore? Ora hai solo 94 caratteri, ecc. Quindi la scelta di una codifica dipende molto dalle tue esigenze.
Per fare un esempio estremamente stupido: se il tuo canale supera tutti i 256 caratteri senza problemi e non hai bisogno di separatori, puoi scrivere una trasformazione banale che raggiunge il 100% di efficienza. :-) Come farlo è lasciato come esercizio per il lettore.
UTF-8 non è un buon trasporto per dati binari codificati arbitrariamente. È in grado di trasportare valori 0x01-0x7F con solo il 14% di overhead. Non sono sicuro che 0x00 sia legale; probabilmente no. Ma qualsiasi cosa sopra 0x80 si espande a più byte in UTF-8. Tratterei UTF-8 come un canale vincolato che passa 0x01-0x7F o 126 caratteri univoci. Se non sono necessari delimitatori, è possibile trasmettere 6,98 bit per carattere.
Una soluzione generale a questo problema: assumere un alfabeto di N caratteri le cui codifiche binarie sono da 0 a N-1. (Se le codifiche non sono così scontate, utilizzare una tabella di ricerca per tradurre tra la nostra rappresentazione intermedia 0..N-1 e ciò che effettivamente invii e ricevi.)
Assumere 95 caratteri nell'alfabeto. Ora: alcuni di questi simboli rappresenteranno 6 bit e alcuni rappresenteranno 7 bit. Se disponiamo di simboli A 6 bit e B 7 bit, quindi:
A + B = 95 (numero totale di simboli) 2A + B = 128 (numero totale di prefissi 7 bit che è possibile effettuare È possibile avviare 2 prefissi con un simbolo a 6 bit o uno con un simbolo a 7 bit.
Risolvendo il sistema, si ottiene: A = 33, B = 62. Si crea ora una tabella di simboli:
Raw Encoded 000000 0000000 000001 0000001 ... 100000 0100000 1000010 0100001 1000011 0100010 ... 1111110 1011101 1111111 1011110
Per codificare, innanzitutto disattivare 6 bit di input. Se quei sei bit sono maggiori o uguali a 100001, spostare un altro bit. Quindi cerca il corrispondente codice di uscita a 7 bit, traduci per adattarlo allo spazio di output e invia. Sposterai 6 o 7 bit di input ogni iterazione.
Per decodificare, accettare un byte e tradurre in codice di output non elaborato. Se il codice non elaborato è inferiore a 0100001, sposta i 6 bit corrispondenti sull'output. Altrimenti sposta i 7 bit corrispondenti sull'output.Genererai 6-7 bit di output ogni iterazione.
Per dati distribuiti uniforme, penso che questo sia ottimale. Se sai di avere più zeri di quelli nella tua fonte, allora potresti voler associare i codici a 7 bit all'inizio dello spazio in modo che sia più probabile che tu possa usare un codice a 7 bit.
Sembra che tu abbia già la risposta, Mark. UTF-8 non è utile come codifica binaria poiché qualsiasi carattere UTF-8 più grande di un byte ha un overhead superiore al 25% anche per memorizzare testo (2 o più bit per byte). Le codifiche Base64 sono già migliori di quelle.
La codifica Base 64 è compatibile con ASCII e, poiché UTF-8 esegue la mappatura su ASCII per qualsiasi carattere sotto l'esagono '7F', UTF-8 ha * * la stessa densità della base 64. Detto questo, per codifiche veramente dense, 8 codifiche di bit come [Windows-1252] (http://en.wikipedia.org/wiki/Windows-1252) potrebbero essere un'idea migliore. –
Anche la codifica Windows-1252 o ISO-8859-1 verrà convertita in UTF-8 in molte situazioni, gonfiando i dati. Una codifica UTF-8 efficiente dovrebbe rappresentare più byte per carattere UTF-8. [Base32768] (https://github.com/qntm/base32768) è un tentativo. – bryc
Ovviamente il mio punto di vista, Maarten, è che si sta meglio usando la codifica base64 piuttosto che una ** multibyte ** UTF-8. Se stavo parlando di ASCII avrei ** detto ** ASCII. Per suggerire che ho sbagliato perché base64 è un sottoinsieme di UTF-8 è solo un inutile bisticcio. – Qwertie
Secondo Wikipedia "basE91 produce minor uscita ASCII semplice per compressa ingresso binario a 8 bit"
basE91 è più efficiente di base64 e Z85. Ma attenzione quando si visualizza il suo output in HTML. Usa caratteri come (<, >, &) che dovrebbero essere sfuggiti (Z85 ha anche questo problema). – bryc
Accanto a quelli elencati Wikipedia, c'è Bommanews:
B- News (o bommanews) è stato sviluppato per sollevare il peso del sovraccarico inerente alla codifica UUEncode e Base64: utilizza un nuovo metodo di codifica per riempire dati binari nei messaggi di testo. Questo metodo consuma più risorse della CPU, ma riesce a ridurre la perdita da circa il 40% per UUEncode al 3,5% (il punto decimale tra quelle cifre non è sporco sul monitor), evitando comunque l'uso di codici di controllo ANSI nel messaggio corpo.
È paragonabile a yEnc: source
yEnc è meno CPU di B-News e raggiunge circa lo stesso basso livello di sovraccarico, ma non evita l'uso di tutti i codici di controllo , lascia solo quelli che (sperimentalmente) hanno osservato effetti indesiderati su alcuni server, il che significa che è un po 'meno conforme a RFC di B-News.
Le FAQ di Bommanews non vanno a sapere quali codifiche di caratteri sono supportate. Presumo la maggior parte delle pagine di codice a 8 bit, sebbene '7F' possa essere presente, e * che sia un codice di controllo * ad es. nel set di caratteri OEM IBM. Anche nelle tabelle codici di Windows '81',' 8D', '8F',' 90' e '9D' sono caratteri di controllo. Attenzione quando si stampa questo stuf, perché i dati * andranno persi. –
@Maarten: B-News ha usato i caratteri 0x20 - 0xFF. Ogni carattere era una singola cifra di un numero di base 224, sfalsato di 0x20. Ogni riga di "testo" era un numero enorme convertito da e in binario nel processo di decodifica e codifica. Yenc utilizza quasi l'intero intervallo da 0x00 a 0xFF, ogni byte nell'input binario semplicemente copiato sull'output di testo, escaping solo 0x00, 0x0A e 0x0D (e il carattere di escape stesso, che non ricordo esattamente quale fosse esattamente). –
Alla fine ho rivisitato questo e ho votato. yEnc e B-news servono per gestire il protocollo delle notizie (NNTP se non mi sbaglio) e queste codifiche non mirano specificamente a un set di caratteri come UTF-8, ASCII o Windows-1252 a causa di ciò. Nota che questo errore è anche presente nella domanda, quindi sono un po 'ingiusto qui. –
La risposta breve sarebbe: No, non c'è ancora.
Mi sono imbattuto nel problema con la codifica di più informazioni nella stringa JSON, ovvero UTF-8 senza caratteri di controllo, barra rovesciata e virgolette.
Sono uscito e ho studiato quanti bit si possono spremere in byte UTF-8 validi. Non sono d'accordo con le risposte affermando che UTF-8 porta troppe spese generali. Non è vero.
Se si prendono in considerazione solo sequenze di un byte, è potente come standard ASCII. Significato 7 bit per byte. Ma se tagli tutti i personaggi speciali rimarrai con qualcosa come Ascii85.
Ma ci sono meno caratteri di controllo nei piani più alti. Quindi se usi blocchi di 6 byte sarai in grado di codificare 5 byte per blocco. Nell'output si otterrà qualsiasi combinazione di caratteri UTF-8 di qualsiasi lunghezza (da 1 a 6 byte).
Questo vi darà un risultato migliore di Ascii85: 5/6 anziché 4/5, efficienza dell'83% anziché 80%. In teoria andrà ancora meglio con una maggiore lunghezza del chunk: circa l'84% a pezzi da 19 byte.
A mio parere il processo di codifica diventa troppo complicato mentre fornisce pochissimo profitto. Quindi Ascii85 o qualche versione modificata di esso (sto guardando a Z85 ora) sarebbe meglio.
Ho cercato il codice binario più efficiente per la codifica del testo l'anno scorso. Mi sono reso conto che la compattezza non è l'unico criterio. Il più importante è dove sei in grado di usare una stringa codificata. Ad esempio, yEnc ha un overhead del 2%, ma è una codifica a 8 bit, quindi il suo utilizzo è molto limitato.
La mia scelta è Z85. È accettabile un overhead del 25% e la stringa codificata può essere utilizzata quasi ovunque: XML, JSON, codice sorgente ecc. Per i dettagli, vedere Z85 specification.
Infine, ho scritto Z85 library in C/C++ e lo uso in produzione.
Recentemente ho avuto bisogno di codificare binario come ascii e questo è quello che mi è venuto in mente. Non so se questo è il più efficiente (probabilmente no) ma è semplice e veloce. Fondamentalmente, codifico un byte come esadecimale ma invece di usare il set base (0-9, A-F), io uso (a-p). Poiché il set è continuo, non richiede alcuna ricerca nella tabella.
//buff is a unsigned character array containing the binary data
//N is the number of bytes to be encoded
string simple_encode(unsigned char *buff, int N)
{
string sEncode = "";
for(int i = 0; i<N; i++)
{
sEncode += (97 + (buff[i] >> 4));
sEncode += (97 + (buff[i] & 0x0F));
}
return sEncode;
}
//sbuff is a string containing the encoded ascii data
//szDecoded is an unsigned char array that has been allocated to 1/2
//the length of sbuff
//N is an integer pointer and returns the number of converted bytes
void simple_decode(string sbuff, unsigned char *szDecode, int *N)
{
*N = sbuff.length()/2;
for(int i=0; i < *N; i++)
{
szDecode[i] = ((sbuff.at(2*i)-97) << 4) + (sbuff.at(2*i+1)-97);
}
}
La domanda era presentare qualcosa con il minimo ammontare di spese generali. La codifica, che è fondamentalmente solo esadecimali con un alfabeto diverso, ha un overhead del 100%. È possibile eseguire anche la codifica esadecimale senza ricerca di tabelle o istruzioni di ramificazione aggiuntive.OK, è brutto da morire, ma almeno aderisce ad uno standard. –
noti che yEnc non si converte binari al testo, converte binario a qualcosa che è compatibile con il protocollo news (NNTP), che non necessariamente soddisfare tutte le esigenze di set di caratteri, e tanto meno che sarebbe stato tutto da stampare testo. –