Ich möchte Binärdaten in einer XML-Datei (mit Python, aber was auch immer) codieren und dekodieren. Ich muss mich der Tatsache stellen, dass ein XML-Tag-Inhalt illegale Zeichen hat. Die einzigen zulässigen sind in XML-Spezifikationen beschrieben:
%Vor%Was bedeutet, dass die nicht erlaubten sind:
1 Byte kann 256 mögliche codieren. Mit diesen Einschränkungen ist das erste Byte auf 256-29-8-1-3 = 215 Möglichkeiten beschränkt.
Von den 215 Möglichkeiten der ersten Bytes verwendet base64 nur 64 Möglichkeiten. Base64 generiert 33% Overhead (6 Bits werden zu 1 Byte, sobald sie mit base64 codiert wurden).
Meine Frage ist also einfach: Gibt es einen Algorithmus, der effizienter als base64 Binärdaten in XML kodiert? Wenn nicht, wo sollten wir anfangen, es zu erstellen? (Bibliotheken, etc.)
Hinweis: Sie würden diesen Beitrag nicht beantworten mit "Sie sollten XML nicht verwenden, um Binärdaten zu codieren, weil ...". Tu es einfach nicht. Sie könnten bestenfalls argumentieren, warum Sie nicht die 215 Möglichkeiten für die Unterstützung schlechter XML-Parser nutzen sollten.
NB2: Ich spreche nicht über das zweite Byte, aber es gibt sicherlich einige Überlegungen, die bezüglich der Anzahl der Möglichkeiten und der Tatsache, dass 10xxxxxx den UTF8-Standard einhalten sollte, wenn wir die zusätzlichen Unicode-Ebenen verwenden (was wenn nicht?).
Ich habe das Konzept in einem C-Code entwickelt.
Das Projekt befindet sich auf GitHub und heißt schließlich BaseXML: Ссылка
Es hat 20% Overhead, was gut für eine binäre Version ist.
Ich hatte es schwer, es mit Expat, dem hinter der Szene liegenden XML-Parser von Python (der XML1.1 NICHT UNTERSTÜTZT!), arbeiten zu lassen. So finden Sie die Binary-sichere BaseXML1.0-Version für XML1.0.
Ich werde vielleicht später die "for XML1.1" -Version freigeben (sie ist auch binär sicher und hat einen Overhead von 14,7%), sie ist fertig und funktioniert zwar, aber nutzlos mit Python-integrierten XML-Parsern. Ich möchte (noch) Leute mit zu vielen Versionen verwirren.
Danke Aya für den Asci85 Link, da gibt es sehr gute Ideen.
Ich habe sie unten für unseren Fall entwickelt.
Für 1 Byte Zeichen (0xxxxxxx): 96 Möglichkeiten pro Byte
+ UTF-8 ASCII-Zeichen 0xxxxxxx = + 2 ^ 7 - UTF-8 Kontrollzeichen 000xxxxx = -2 ^ 5 + XML erlaubt UTF-8 Kontrollzeichen (00000009, 0000000A, 0000000D) = +3 - XML-Entity nicht erlaubte Zeichen (& lt ;, & gt ;, & amp;;) = -3 BEARBEITEN: Dies ist für XML1.0-Spezifikationen. XML 1.1-Spezifikationen ermöglicht die Verwendung von Steuerzeichen außer 0x00 ...
Für 2-Byte-Zeichen (110xxxxx 10xxxxxx): 1920 Möglichkeiten pro 2 Byte
+ UTF-8 2-Byte-Zeichen 110xxxxx 10xxxxxx = + 2 ^ 11 - UTF-8 illegale nicht-kanonische Zeichen (1100000x 10xxxxxx) = -2 ^ 7 Für 3-Byte-Zeichen (1110xxxx 10xxxxxx 10xxxxxx): 61440 Möglichkeiten pro 3 Byte
+ UTF-8 3-Byte-Zeichen 1110xxxx 10xxxxxx 10xxxxxx = + 2 ^ 16 - UTF-8 illegale nicht-kanonische Zeichen (11100000 100xxxxx 10xxxxxx) = -2 ^ 11 - Unicode reservierte UTF-16-Codepunkte (11101101 101xxxxx 10xxxxxx) = -2 ^ 11 Und ich werde die Berechnung für 4-Byte-Zeichen nicht machen, das ist sinnlos: die Anzahl der möglichen wäre vernachlässigbar und es gibt zu viele illegale UTF-8-Zeichen in diesem Bereich.
Sehen wir uns nun an, welche Kombinationen wir für einen 3-Byte-Bereich (24 Bit) machen können:
Es gäbe andere Möglichkeiten (wie ein 3-Byte-Char-Ende oder das Starten im Raum, aber wie 4-Byte-Zeichen, das wäre schwer zu bewerten (für mich) und wahrscheinlich vernachlässigbar).
Gesamtzahl der Möglichkeiten:
Wie viel Aufwand bedeutet das?
18% overhead . Viel besser als Base64's 33% Overhead und Ascii85's 25% Overhead! BEARBEITEN: Dies ist für XML1.0-Spezifikationen. Bei XML1.1 (nicht allgemein unterstützt) beträgt der theoretische Overhead 12,55%. Es gelang mir, einen binären sicheren Algorithmus mit 14,7% Overhead für XML1.1 zu erstellen.
Die schlechte Nachricht ist, dass wir nicht so leicht 18% erreichen können, ohne ein großes "Wörterbuch" (dh lange umklingende Sätze) zu verwenden. Aber es ist einfach, 20% zu bekommen, und ziemlich einfach, aber weniger praktisch, um 19% zu bekommen.
Gute Kandidaten für Codierungslängen:
NB: 0,84 ist die durchschnittliche "Nützlichkeit" eines Raumbits (20,32 / 24).
Wir müssen ein "Dictionary" erstellen, das die "Space-Möglichkeiten" (randoms Sequenz von Bits, deren Länge 5, 10, 20 oder 21 Bits abhängig von der gewählten Codierungslänge für den Algorithmus ist - wählen Sie einfach) in die utf8-kompatiblen Sequenzen (utf8 Bitsequenz, deren Länge entsprechend 6, 12, 24 oder 25 Bit ist).
Der einfachste Ausgangspunkt wäre die Kodierung der 20-Bit-Sequenz in 24-Bit-kompatible UTF-8-Sequenzen: Das ist genau das Beispiel, das oben zur Berechnung der Möglichkeiten genommen wurde und das sind 3 UTF-8 Bytes lang (also müssen wir nicht Sorgen über nicht abgeschlossene UTF8 Zeichen).
Beachten Sie, dass wir die 2 Byte (oder mehr) UTF-8-Zeichen verwenden müssen, um den 20% Overhead zu erreichen. Mit nur 1 Byte langen UTF8-Zeichen können wir mit RADIX-24 nur 25% Overhead erreichen. Die 3 Byte langen UTF-8-Zeichen benötigen jedoch nicht den 20% Overhead.
Das ist die nächste Herausforderung für diese Frage. Wer möchte spielen?:)
20 binäre Bits zum Verschlüsseln: ABCDEFGHIJKLMNOPQRST
Resultierende UTF-8-Zeichenfolge mit dem Namen "encoded": 24 Bit lang
Mathematischer Kodieralgorithmus (nicht auf irgendeiner bekannten Programmiersprache basierend):
%Vor%Und so erhalten Sie nur 20% Overhead.
Dieser Algorithmus bietet noch keine Möglichkeit, die String-Terminierung zu verwalten, wenn die zu codierende Zeichenkette kein Vielfaches von 20 ist. Der Dekodieralgorithmus muss ebenfalls bereitgestellt werden, aber das ist ziemlich einfach (vergessen Sie nicht, zu werfen Ausnahmen, um die Uneinheitlichkeit der Decodierung zu erzwingen.)
Es ist schlimmer als das: Sie haben tatsächlich nicht 215 verschiedene Bytewerte, die Sie verwenden können. Die resultierenden Binärdaten müssen in jeder Codierung gültig sein, in der die XML dargestellt wird (was mit ziemlicher Sicherheit UTF-8 ist), was bedeutet, dass viele, viele Bytefolgen verboten sind. 0xc2 gefolgt von 0x41 wäre nur ein zufälliges Beispiel. XML ist Text (eine Folge von Unicode-Zeichen), keine binären Daten. Wenn es übertragen wird, wird es mit einer Codierung codiert (die fast immer UTF-8 ist). Wenn Sie versuchen, es als Binärdaten zu behandeln, dann fragen Sie meiner Meinung nach nach mehr Ärger als es wert ist, sich damit zu befassen.
Wenn Sie das immer noch tun möchten ...
XML ist Text. Versuchen wir also nicht, Ihre Binärdaten als Binärdaten zu kodieren. Das wird nicht zu einem einfachen oder offensichtlichen Weg führen, es in ein XML-Dokument zu übertragen. Versuchen wir stattdessen, Ihre Binärdaten als Text zu codieren!
Versuchen wir eine sehr einfache Kodierung:
Dies bedeutet, dass Sie ausschließlich Zeichen aus den Ebenen 1 bis 16 verwenden. Alle eingeschränkten Zeichen befinden sich in Ebene 0 (der BMP), so dass Sie hier sicher sind.
Wenn Sie dieses XML-Dokument dann als UTF-8 für die Übertragung codieren, benötigt jedes dieser Zeichen 4 Bytes zum Codieren. Sie verbrauchen also 32 Bits für jede 20-Bit-Originaldaten, was 60% Overhead im Vergleich zur reinen Binärcodierung der Originaldaten darstellt. Das ist schlimmer als die 33% von base64 , was es zu einer schrecklichen Idee macht.
Dieses Codierungsschema ist leicht verschwenderisch, da es keine BMP-Zeichen verwendet. Können wir BMP-Zeichen verwenden, um es besser zu machen? Nicht trivial. 20 ist die größte Größe, die wir für die Gruppen verwenden können ( log(0x10FFFF) ~ 20.09 ). Wir könnten Schemata so umgestalten, dass sie so wenig wie möglich als BMP-Zeichen verwenden, da sie weniger Speicherplatz für die Kodierung mit UTF-8 benötigen, aber das würde die Kodierung sehr erschweren (die verbotenen Zeichen sind verstreut) ), aber es kann nur für etwa 6,25% der Bitmuster (Anteil der Unicode-Zeichen, die in der BMP sind) zur Verbesserung führen, und für die Mehrheit dieser 6,25% würden wir nur ein Byte speichern. Bei zufälligen Daten verringert sich der Overhead von 60% auf etwa 55%. Das Ergebnis wäre immer noch viel schlechter als base64, abgesehen von einigen sehr komplizierten Daten . Beachten Sie, dass der Overhead jedoch datenabhängig ist. Bei 0,2% der Bitmuster erhalten Sie tatsächlich Komprimierung anstelle von Overhead (60% Komprimierung für 0,012% der Muster und 20% Komprimierung für 0,18% der Muster). Aber diese Fraktionen sind wirklich niedrig. Es ist es einfach nicht wert.
Um es anders auszudrücken: Wenn Sie alles mit 4-Byte-UTF-8-Sequenzen codieren wollen, müssen Sie natürlich 32 Bits pro Sequenz verwenden, aber 11 dieser Bits sind fest und unveränderbar: Die Bits müssen passen das Muster 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx und dort sind nur 21 x s drin. Dieser Overhead von 60% ist in UTF-8 integriert. Wenn Sie dies als Basis für eine Codierung verwenden möchten, die den Overhead von base64 verbessert, beginnen Sie von hinten!
Ich hoffe, dass Sie davon überzeugt sind, dass Sie die Dichte von base64 nicht mit irgendeinem Schema dieses Typs verbessern können.
Tags und Links xml utf-8 unicode compression xml-serialization