Encoder des données binaires dans XML: Existe-t-il de meilleures alternatives que base64?

Merci Aya pour le lien Asci85, il y a de très bonnes idées.

je les ai développés ci-dessous pour notre affaire.

---

UTF-8 caractères possibles:

---

Pour 1 octet (0xxxxxxx): 96 possibilités par octet

• + UTF-8 ASCII chars 0xxxxxxx = +2^7
• - contrôle UTF-8 jars 000xxxxx = -2^5
• + XML allowed UTF-8 control chars (00000009, 0000000A, 0000000D) = +3
• - entité XML non autorisé(<, >, &) = -3

EDIT: C'est pour XML1.0 spécifications. XML 1.1 specs permet l'utilisation de barres de contrôle sauf 0x00...

pour les caractères de 2 octets (110xxxxx 10xxxxxx): par 2 octets

• + UTF-8 2 octets char 110xxxxx 10xxxxxx = +2^11
• - UTF-8 charrues illégales non canoniques (1100000x 10xxxxxx) = -2^7

Pour les 3 octets de caractères (1110xxxx 10xxxxxx 10xxxxxx): 61440 possibilités par 3 octets

• + UTF-8 3-octets char 1110xxxx 10xxxxxx 10xxxxxx = +2^16
• - UTF-8 chars non canoniques illégaux (11100000 100xxxxx 10xxxxxx) = -2^11
• - Unicode reserved UTF-16 codepoints (11101101 101xxxxx 10xxxxxx) = -2^11

et je ne ferai pas le calcul pour les caractères de 4 octets, c'est inutile: le nombre de possibles serait négligeable et il y a trop de caractères illégaux UTF-8 dans cette gamme.

---

les possibilités de codage dans let's dites un espace de 3 octets

---

voyons donc quelles combinaisons nous pouvons faire sur un espace de 3 octets (24bit):

• 0xxxxxxx 0xxxxxxx 0xxxxxxx: C'est 96*96*96 = 884736 possibilités
• 0xxxxxxx 110xxxxx 10xxxxxx : 96*1920 = 184320 possibilités
• 110xxxxx 10xxxxxx 0xxxxxxx : C'est 1920*96 = 184320 possibilités
• 1110xxxx 10xxxxxx 10xxxxxx : c'est 61440 = 61440 possibilités

il y aurait d'autres possibilités (comme un caractère de 3 octets ou commençant dans l'espace mais comme des caractères de 4 octets, qui seraient difficiles à évaluer (pour moi) et probablement négligeables).

nombre Total de possibilités:

• un espace de 3 octets A 2^24 = 16777216 possibilité.
• possibilités compatibles UTF-8 en cet espace est 884736+2*184320+61440 = 1314816 possibilités.

combien de frais généraux cela signifie-t-il?

• 24 bits espace utilisable: Log2 (16777216)=24 (Bien sûr! c'est pour la compréhension mathématique)
• cet espace UTF-8 bits utiles: Log2 (1314816)=20,32 bits utiles.
• cela signifie que nous avons besoin de 24 bits d'espace pour coder 20,32 bits d'information utile, c'est-à-dire: le minimum théorique les frais généraux sont de 18% overhead . bien mieux que 33% de frais généraux de Base64 et 25% de frais généraux D'Ascii85!

EDIT: C'est pour XML1.0 spécifications. Avec XML1.1 (pas largement soutenu...), le théorique surcharge est de 12,55%. J'ai réussi à faire un algorithme binaire sûr avec 14,7% de overhead pour XML1.1.

---

comment se rapprocher de cette hauteur de 18%?

---

la mauvaise nouvelle est que nous ne pouvons pas obtenir facilement que 18% ovearhead sans utiliser un grand" dictionnaire " (c'est-à-dire des ensembles d'encodage longs). Mais il est facile d'obtenir 20% , et assez facile mais moins pratique d'obtenir 19%.

bonnes longueurs de codage candidats:

• 6 bits peut encoder les 5 bits de poids avec 20% de frais généraux (2^(6*0,84) > 2^5)
• 12 bits peut coder 10 bits avec 20% de overhead (2^(12*0,84) > 2^10)
• 24 bits peut coder 20 bits avec 20% De Charge (2^(24*0,84) > 2^20)
• 25 bits peut coder 21 bits avec 19% de charge (2^(25*0,84) > 2^21)

NB: 0,84 est l '"utilité" moyenne d'un bit d'espace (20,32/24).

---

comment construire notre algorithme d'encodage?

---

Nous avons besoin de construire un "dictionnaire" qui cartographier les "space possibles" (séquence aléatoire de bits dont la longueur est de 5, 10, 20 ou 21 bits selon la longueur de codage choisie pour l'algorithme - il suffit d'en choisir un) dans les séquences compatibles utf8 (séquence utf8 bits dont la longueur est de 6, 12, 24 ou 25 bits en conséquence).

le point de départ le plus facile serait l'encodage de la séquence 20bits en 24bits compatibles UTF-8 séquences: c'est exactement l'exemple qui a été pris ci-dessus pour calculer les possibilités3 UTF-8 bytes long (donc nous n'aurons pas à nous soucier des caractères UTF8 Non-bromés).

notez que nous devons utiliser l'espace D'encodage UTF-8 de 2 octets (ou plus) pour atteindre les 20%. Avec seulement 1 octet de long UTF8 caractères, Nous ne pouvons atteindre que 25% de hauteur avec RADIX-24. Cependant, les caractères UTF-8 de 3 octets sont inutiles pour atteindre les 20%.

C'est le prochain défi pour cette question. Qui veut jouer? :)

---

Une proposition de l'algorithme, je vais le nom BaseUTF-8 pour XML

---

20 bits binaires à encoder: ABCDEFGHIJKLMNOPQRST

chaîne UTF-8 résultante nommée "encoded": 24 bits de long

algorithme mathématique d'encodage (non basé sur un langage de programmation connu):

If GH != 00 && NO != 00:
    encoded = 01ABCDEF 0GHIJKLM 0NOPQRST # 20 bits to encode, 21 space bits with restrictions (1-byte UTF-8 char not starting by 000xxxxx ie ASCII control chars)

If ABCD != 0000:
    If GH == 00 && NO == 00: # 16 bits to encode
        encoded = 0010ABCD 01EFIJKL 01MPQRST    
    Else If GH == 00:  # 18 bits to encode, 18 space bits with restrictions (1-byte  UTF-8 ASCII control char, 2-bytes UTF-8 char noncanonical)
        encoded = 0NOFIJKL 110ABCDE 10MPQRST
    Else If NO == 00:  # 18 bits to encode
        encoded = 110ABCDE 10MPQRST 0GHFIJKL

If ABCD == 0000: # 16 bits to encode
    encoded = 0011EFGH 01IJKLMN 01OPQRST

On "encoded" variable apply:
    convert < (0x3C) to Line Feed (0x0A)
    convert > (0x3E) to Cariage Return (0x0D)
    convert & (0x26) to TAB (0x09)

et c'est comme ça que vous obtenez 20% de frais généraux seulement.

cet algorithme ne fournit pas encore un moyen de gérer la terminaison de la chaîne, lorsque la chaîne à encoder n'est pas un multiple de 20. L'algorithme de décodage doit aussi être fourni, mais c'est assez facile (n'oubliez pas de lancer des exceptions pour forcer l'unicité du décodage).

c'est pire que ça: vous n'avez pas en fait 215 valeurs de byte différentes que vous pouvez utiliser. Les données binaires résultantes doivent être valides quel que soit l'encodage dans lequel le XML est représenté (ce qui est presque certainement UTF-8), ce qui signifie que beaucoup, beaucoup de séquences byte sont interdites. 0xc2 suivi de 0x41 ne serait qu'un exemple aléatoire. XML est du texte (une séquence de caractères Unicode), pas des données binaires. Lorsqu'il est transmis, il est encodé en utilisant un encodage (qui est presque Alwats UTF-8). Si vous essayez pour le traiter comme des données binaires, alors vous êtes, à mon avis, demandant beaucoup plus de problèmes que cela vaut la peine de traiter.

si vous voulez toujours faire ça...

XML est du texte. Alors n'essayons pas d'encoder vos données binaires en tant que données binaires. Cela ne conduira pas à un moyen facile ou évident de le faire apparaître dans un document XML. Essayons plutôt d'encoder vos données binaires en texte!

essayons un encodage très simple:

• Groupez vos données binaires en blocs de 20 bits
• Code chaque groupe de 20 bits comme le caractère Unicode U+10000 plus la valeur numérique des 20 bits.

cela signifie que vous utilisez exclusivement les caractères des plans 1 à 16. Tous les caractères restreints sont dans le plan 0 (le BMP), donc vous êtes en sécurité ici.

lorsque vous encodez alors ce document XML comme UTF-8 pour la transmission, chacun des ces caractères nécessiteront 4 octets pour être encodés. Donc, vous consommez 32 bits pour chaque 20 bits de données originales, ce qui est 60% supérieur par rapport à l'encodage binaire pur des données originales. c'est pire que 33% de base64 , ce qui en fait une idée terrible.

ce schéma d'encodage est légèrement inutile car il ne fait pas usage de caractères BMP. Peut-on utiliser des caractères BMP pour améliorer les choses? Pas trivialement. 20 est la plus grande taille que nous pouvons utiliser pour les groupes ( log(0x10FFFF) ~ 20.09 ). Nous pourrions remap out scheme pour utiliser certains comme caractères manu BMP que possible parce que ceux-ci prennent moins de place pour encoder avec UTF-8, mais non seulement cela compliquerait l'encodage beaucoup (les caractères interdits sont dispersés, donc nous avons plusieurs cas à gérer), mais il ne peut conduire à l'amélioration pour environ 6,25% des modèles de bits (fraction de caractères Unicode qui sont dans le BMP), et pour la majorité de ce 6,25%, nous sauverions seulement un octet. Pour les données aléatoires, les frais généraux diminuent de 60% à environ 55%. le résultat serait encore bien pire que base64 à l'exception de quelques données très compliquées . Notez que les frais généraux dépendent des données. Pour 0.2% des motifs de bits, vous obtiendrez en fait une compression au lieu d'une compression au-dessus de la surface (60% de compression pour 0.012% des motifs et 20% de compression pour 0.18% des motifs). Mais ces fractions sont vraiment bas. C'est juste pas la peine.

pour mettre cela d'une autre manière: si vous voulez encoder quelque chose en utilisant des séquences UTF-8 de 4 octets, vous devez utiliser 32 bits par séquence (bien sûr) mais 11 de ces bits sont fixes et immuables: les bits doivent correspondre au modèle 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx et il n'y a que 21 x S là-dedans). Ce overhead de 60% est construit en UTF-8 donc si vous voulez utiliser ceci comme base de n'importe quel encodage qui améliore le overhead de base64, vous commencez par derrière!

j'espère que cela vous convaincra que vous ne pouvez pas améliorer la densité de base 64 en utilisant tout schéma de ce type.