MiniString

Eine 6-Bit String Encoding Library für .NET-Standard.

Wann sollte MiniString verwendet werden?

Der offensichtliche Vorteil von MiniString ist die minimale Größe der Strings. Die meisten Zeichensets verwenden 2 Bytes(=16 Bit) oder mehr pro Zeichen. MiniString verwendet lediglich 6 Bit pro Zeichen. Dies ist besonders in Szenarien in denen jedes einzelne Bit einzelnen Unterschied machen kann von großem Vorteil(z.B. Übertragungen über das Netzwerk, Abspeichern in großen binären Dateien).

Diese kleine Größe kommt jedoch nicht ohne Abschnitte: MiniString unterstützt nativ nur die Groß- und Kleinbuchstaben des lateinischen Alphabets(A-Z, a-z), die Zahlen 0 bis 9, den Unterstrich(_) sowie das "null-Zeichen"(null). Sämtliche anderen Zeichen werden über deren UTF-16LE  mit 24-Bit Speicherbedarf serialisiert. Durch diese Restriktion bietet sich der MiniString also primär für Maschinen-generierte Strings(z.B. IDs) an. Aus diesem Grund wurde auch "_" anstatt beispielsweise des Leerzeichens als zusätzlich unterstütztes Zeichen gewählt.

Wie wird MiniString verwendet?

Die einzigen zwei relevanten öffentlichen Methoden sind MiniString.Encode sowie MiniString.Decode.

Die erste Methode enkodiert einen String, die zweite dekodiert.

Wie werden Strings serialisiert?

Wie bereits erwählt wird jedes nativ unterstürztes Zeichen als 6 Bit dargestellt. Einige Beispiele:

Zeichen Dezimal Binär
null 0 000000
1 1 000001
7 7 000111
A 11 001011
X 34 100010
c 39 100111
i 45 101101
_ 63 111111

Würden wir nun ein einzelnes Zeichen - hier "_" zur einfachen Visualisierung - serialisieren erhalten wir nun den 6-Bit Wert 111111. Um das ganze jedoch sinnvoll weiter verwenden zu können muss das ganze in ein 8-Bit System übertragen werden.

In diesem Beispielfall werden somit zwei leere/Füller Bit eingefügt:

00111111

Diese zwei überschüssige Bits können wir uns jedoch zu nutze machen sobald wir mehr als ein Zeichen serialisieren. Um es weiterhin schön visualisieren zu können verwenden wir dieses mal "__".

Wir erhalten nun 111111 für den ersten Unterstrich und erneut 111111 für den zweiten. Diese müssen nun wieder in das 8-Bit System übertragen werden. Das ganze funktioniert analog zu oben, jedoch fügen wir dieses mal stat zwei leere/Füller Bits die ersten zwei Bits des zweiten Wertes vorne an. Die verbleibenden vier Bit des zweiten Werten werden daraufhin in ein neues Byte geschrieben und vier Füller Bit eingefügt um das Byte zu vervollständigen.

Wir erhalten den Binärwert

11111111 00001111

Somit würden drei Unterstrichen("___") derartig aussehen:

11111111 11111111 00000011

Und vier("____") so:

11111111 11111111 11111111

Somit sind wir nun an dem Punkt angekommen an dem MiniString einen Vorteil erzielt: Vier Zeichen mit drei Bytes serialisiert.

Zur Vollständigkeit betrachten wir erneut einmal das Hello_World Beispiel von oben:

82 10 195 243 31 206 54 140 2

01010010 00001010 11000011 11110011 00011111 11001110 00110110 10001100 00000010

Nun gibt es jedoch auch Momente(von denen zwar mit MiniString abzuraten ist, jedoch ist es nicht immer vermeidbar) in denen wir Zeichen serialisieren müssen die nicht nativ unterstützt werden. Wie Beispielsweise das Deutsche "ä". MiniString nutzt hier 24-Bit - also den Speicherplatz von 4 kompletten Zeichen - um dies repräsentieren zu können. Ein null Zeichen gefolgt von 2 ungenutzten Bit, gefolgt von 16 Bit welche den UTF-16LE Codepoint des Zeichen angeben.

Zeichen haben einen sogenannten Codepoint in deren Encoding. Dies ist ein numerischer Wert der dieses Zeichen repräsentiert. Wenn wir die obere Tabelle betrachten hat der Buchstabe "X" den Codepoint 34 in MiniString. Da wir mit 6-Bit nur eine geringe Anzahl an Zeichen(64) repräsentieren können müssen wir also auf den Ort in einem anderem Encoding verweisen in dem das Zeichen zu finden ist. Im Falle von MiniString wird auf UTF-16 verwiesen.

Fangen wir an: Zuerst benötigen wir das sogenannte null-Zeichen(000000). Dessen Bedeutung in MiniString ist es anzugeben, dass die nächsten 18 Bit eine Referenz auf UTF-16LE ist und nicht regulär zu interpretieren sind.

Daran fügen wir nun den Codepoint von ä(228 - 11100100 00000000 = 16 Bit) sowie zwei leere Bit an.

Wir haben also die folgenden 6-Bit Ketten:

000000 010000 001110 000000

Und übertragen diese wieder wie gewohnt in das 8-Bit System:

00000000 11100100 00000000

Wozu dienen nun diese zwei zusätzlichen Bit? Als "Padding". Das Problem ist, dass UTF-16LE 16 Bit für ein Zeichen verwendet(Teils auch 32 Bit, diese werden jedoch intern in .NET als zwei getrennte Zeichen behandelt). Da MiniString mit 6-Bit Blöcken arbeitet vertragen sich 16 Bit nicht sonderlich gut damit. Die einfachste und am wenigsten invasivste Lösung war es somit die 16 Bit einfach zu 18 Bit "aufzustocken" und somit wieder eine gut mit 6 Bit Blöcken verträgliche Bitzahl zu haben.

Download & Kompilieren

$ git clone https://github.com/PatrickSachs/MiniString.git
$ cd MiniString/MiniStringLib
$ dotnet build

Quellcode

Der Quellcode kann hier eingesehen werden.

MiniString ist MIT lizenziert.