Millibytes

Wir lernen alle paar Monate oder mindestens alle paar Jahre neue Begriffe wie Kilobyte, Megabyte, Gigabyte, Terabyte, Petabyte und Exabyte kennen. Man muss immer aufpassen, weil damit die Potenzen von 1024 oder die von 1000 gemeint sein können. 1024 ist praktischer in der Informatik, aber 1000 ist praktischer für Anbieter von Festplatten, weil sie dann ein eindrucksvolleres Schild auf die Ware kleben können, ohne sehr unehrlich zu sein. Und bei Terabytes macht der Unterschied schon etwa 10% aus und es wird mehr wenn wir Exabytes oder Hepabytes oder Okabytes oder was auch immer man da erfinden wird, verwenden. Im Moment betrifft das Problem nur große Firmen wie Google und Google achtet bei der Einstellung von neuen Mitarbeitern sehr auf ein gewisses Mindestniveau, so dass sie nicht gefährdet sind, sich beim Festplattenhersteller wegen dieser 10-20% über den Tisch ziehen zu lassen.

Aber wie sieht es aus mit Millibytes? Das klingt komisch. Kleiner als ein Byte geht nicht, außer man überlegt etwas länger und kommt darauf, dass es noch Bits gibt, also Achtelbytes. Jedes Bit ist eine Antwort auf eine Frage, die nur mit Ja oder Nein beantwortet werden kann. Ein kleiner Nebenaspekt kommt mit Binärdaten ins Spiel. Diese sind üblicherweise als eine Sequenz von Bytes dargestellt. In Wirklichkeit sollte es eine Sequenz von Bits sein, das heißt, wir sollten genaugenommen beim letzten Byte wissen, welche Bits noch dazugehören und welche nur Füllbits sind, die wir ignorieren müssen. Das lässt sich durch entsprechende Binärformate in den Griff bekommen, wenn man angibt, wieviele Bits die Daten lang sind und dann die Bytes folgen.

Aber gibt es halbe Bits? Oder Millibits? So absurd ist die Idee nicht. Wenn wir eine Netzwerkverbindung haben, die absolut zuverlässig funktioniert, dann ist ein Bit das ankommt definitiv dasselbe wie das, was reingeschickt wurde. Es enthält also den Gegenwert von einem Bit Information darüber, was eingegeben wurde. Wenn der Kanal nun gar nicht funktioniert und zufällige Bits rauskommen, ist deren Informationsgehalt 0. Man erfährt gar nichts darüber, was gesendet wurde. Typische Verbindungen liegen irgendwo dazwischen. Das Bit was rauskommt, hat also etwas mit dem was reingesteckt wurde, zu tun, ist aber nicht 100% zuverlässig. Mit fehlerkorrigierenden Codes kann man die Zuverlässigkeit auf Kosten der Kapazität steigern. Analysiert man die ganze Situation, stellt man fest, dass ein physikalisch empfangenes Bit weniger als ein Bit Information bringt. Man braucht im Durchschnitt etwas mehr als ein übertragenes Bit, um ein Bit wirkliche Information von der Quelle wirklich mit einer gewünschten Zuverlässigkeit zu ermitteln. Die Zuverlässigkeit wird nie 100% erreichen, aber theoretisch 99.9999% mit so vielen Neunen wie man will. Am Ende des Tages bringt uns ein Bit, das physikalisch übertragen wird, also durchschnittlich nur 0.7, 0.95 oder 0.00012 Bits tatsächliche Information, weil es im Kontext der Fehlerkorrektur mit anderen Bits kombiniert werden muss. Und das sind dann 700, 950 oder 0.12 Millibits bzw. 87.5, 118.75 oder 0.015 Millibytes. Die Diskussion wegen 1024 und 1000 ist auch hier relevant, aber ich überlasse sie gerne den Lesern…

Share Button

Kompressionsprogramme

Jeder kennt diese Kompressionsprogramme wie gzip, arj, (win)zip, 7z und noch mehr. Sie sind praktisch, um Daten platzsparend aufzubewahren, bandbreitensparend zu übermitteln oder auch einfach nur um Daten zu einer Datei zusammenzupacken. Dabei hat die letzte Aufgabe eigentlich gar nicht viel mit Kompression zu tun, wird aber von manchen Werkzeugen zusätzlich zur Kmpression auch noch unterstützt. Ein weniger bekannter Grund für Kompression, der aber recht wichtig ist, ist im Bereich der Kryptographie. Wenn man Daten vor der Verschlüsselung komprimiert, ist es schwieriger, den Schlüssel zu erraten.

Witzigerweise hat sich in der Linux-Welt als Archivformat das .tar.gz-Format weit verbreitet, währned in der MS-Windows-Welt eher die zip-Dateien üblich sind, obwohl beide Formate auf beiden Plattformen relativ gut unterstützt werden:
Unter Linux kann man zwei Programme, zip und unzip finden oder einfach installieren, die ZIP-Dateien erzeugen und auspacken. Unter MS-Windows kann man z.B. cygwin installieren und hat dann auch tar und gzip dabei, oder man kann mit Winzip auch tar.gz-Dateien zumindest auspacken.

Hinter diesen beiden Formaten und den zugehörigen Werkzeugen stehen zwei verschiedene Ansätze. In der Linux-Welt und früher noch mehr in der Unix-Welt war es üblich, Werkzeuge zu haben, die eine Aufgabe sehr gut erfüllen und die sich mit anderen Werkzeugen kombinieren lassen. Herausgekommen ist gzip, das nur eine einzelne Datei oder einen Datenstrom komprimiert, nicht aber mehrere Dateien in ein Archiv zusammenführt, wofür andere Werkzeuge, z.B. tar herangezogen werden können. Man kann das aber mit einem Aufruf erledigen, indem man tar mit einer Option mitgibt, das das Archiv nach der Erstellung noch durch gzip geschickt werden soll oder vor dem Lesen durch gunzip. Dagegen mach zip alles in einem Werkzeug.

Bei genauerem Hinsehen gibt es aber noch eine subtilen, aber doch manchmal wichtigen Unterschied, der eigentlich wenig mit der Frage zu tun hat, ob man ein Werkzeug hat, das beide Aufgaben verbindet.

Im ZIP-Format werden die Dateien einzeln komprimiert und dann die komprimierten Dateien zu einem Archiv zusammengefügt. Bei .tar.gz ist es umgekehrt. Oft ist die Wahl durch Gewohnheiten oder durch Kommunikationspartner ein Stück weti eingeschränkt, aber es lohnt sich doch, diesen Unterschied zu kennen: Beide Ansätze haben ihre Vorteile in verschiedenen Situationen und deshalb ist es eigentlich gut, daß man auf beiden Plattformen auch beide verwenden kann.

Der Vorteil, erst zu archivieren und das Archiv zu komprimieren ist einfach, daß man dabei eine bessere Kompression erzielen kann. Da die Kompression ja darauf basiert, irgendwelche Gemeinsamkeiten, Regelmäßigkeiten oder allgemein Redundanzen von verschiedenen Sequenzen innerhalb der komprimierten Datei zu finden, ist es plausibel anzunehmen, daß man die Kompression manchmal verbessern kann, wenn dies über alle archivierten Dateien gemacht werden kann und nicht nur über die einzelnen archivierten Dateien. Als Beispiel habe ich einmal das /bin-Verzeichnis komprimiert:

$ ls -l bin.tar.gz bin.zip
-rw-r--r-- 1 bk1 brodowsky 3909375 2013-06-20 22:23 bin.tar.gz
-rw-r--r-- 1 bk1 brodowsky 7568659 2013-06-20 22:24 bin.zip

Man sieht also, daß die Wiederholungen und Ähnlichkeiten zwischen den Dateien dazu führen, daß trotz gleichem Kompressionsalgoritmus die tar.gz-Datei nur etwa halb so groß wie die zip-Datei ist.

Der Vorteil, erst zu komprimieren und dann die einzelnen komprimierten Dateien zu archivieren besteht darin, daß man leichter auf einzelne Dateien aus dem Archiv zugreifen kann. Bei tar.gz muß man alles vom Anfang bis zu der gesuchten Datei dekomprimieren, im Durchschnitt also etwas mehr als die Hälfte des Archivs, bei zip nur die eine Datei, die man wirklich will. Aus diesem Grunde wurde das zip-Format auch für die Programmiersprache java verwendet, um die Bibliotheken (jar-Dateien) zu speichern. Das sind ZIP-Dateien mit einem zusätzlichen Verzeichnis META-INF, das Metainformationen enthalten kann. Man kann jar-Dateien mit unzip auspacken und zip-Dateien mit jar xfvv.

Wenn man nun aber eine Datenbankspalte oder -tabelle komprimieren will, sind diese beiden Ansätze nicht so attraktiv. Im einen Fall werden die Zugriffe unakzeptabel langsam, im anderen Fall hat man mit einem einzelnen Datenbankattribut in einer einzelnen Zeile selten genug Masse, um von der Kompression profitieren zu können. Wie könnte man das trotzdem lösen? Vielleicht wäre eine Möglichkeit, daß man ab einer gewissen Datenmenge in der Spalte, also wenn es genug Zeilen gibt, bei denen dieses Attribut nicht null ist, die Daten analysiert und in einem mit der Tabelle assoziierten Bereich Metadaten zur Kompression ablegt, die etwa aus mehrfach vorkommenden Bit- oder Byte-Sequenzen bestehen und diese auf andere Bit- oder Byte-Sequenzen abbilden, so daß die häufigeren kürzer sind als die selteneren gleicher Orignallänge. Solange die neu hinzukommenden Daten etwa den schon vorhandenen entsprechen, kann man sie damit auch komprimieren und tatsächlich die Datenbank kleiner machen, aber vor allem in manchen Fällen schneller und in Kombination mit Verschlüsselung vielleicht sogar sicherer.

Nebenbei bemerkt, daß es viele Werkzeuge gibt, die ähnlich wie die hier erwähnten Vertreter funktionieren:

  • lha, zoo und 7z funktionieren z.B. ähnlich wie zip.
  • compress, bzip2 und xz funktionieren ähnlich wie gzip
  • cpio funktioniert ähnlich wie tar

Weil compress in den 90er-Jahren auf patentierten Algorithemn basierte, hat man es praktisch vollständig durch gzip ersetzt, was auch die bessere Kompressionsraten auf Kosten des Zeitaufwands zum Komprimieren erzielt hat. Dann kam bzip2, das noch besser und noch langsamer komprimiert und xz, noch besser und noch langsamer.

tar hieß ursprünglich „tape archiver“, konnte als Bandlaufwerke ansprechen. Es wird aber seit 20 Jahren in meiner Erfahrung ganz überwiegend für Archivierung in Dateien verwendet und sehr selten für Bandlaufwerke. Dafür kam dann irgendwann cpio, das aber auch für beide Zwecke verwendbar ist, wie tar. Nur ist cpio weniger verbreitet und man muß wohl als durchschnittlicher Linux-Anwender häufiger die man-Seite anschauen, wenn man das verwendet, während man bei tar eher die wichtigsten Optionen auswendig kennen könnte.

Share Button

Zufallszahlen

Wofür braucht man überhaupt Zufallszahlen? Es gibt recht viele probabilistische Algorithmen, die besser funktinonieren, wenn man „gute“ Zufallszahlen hat. Besonders wichtig sind diese aber auch in der Kryptographie, zum Beispiel zur Generierung von Schlüsseln.

Die Qualität der Zufallszahlen ergibt sich aus der Vorhersehbarkeit des nächsten Werts. Wenn dieser z.B. mit heutigen Mitteln aus bekannten Werten berechnet werden kann oder nur schon dieser berechnete Wert mit höherer Wahrscheinlichkeit zu erwarten ist als bei Gleichverteilung, dann sind die Zufallszahlen nicht mehr optimal. Man kann dann zum Beispiel den „private key“ eines Schlüsselpaars erraten und dadurch die Sicherheit des Verfahrens vermindern.

Nun ist die Frage, ob es wirklichen Zufall in der Natur gibt. Nach heutigen Erkenntnissen glaubt man das und findet als Beispiel den radioakativen Zerfall. Also müßte nur jeder Rechner einen „Radiumkarte“ eingebaut bekommen und schon hätte man überall gute Zuzfallszählengeneratoren zur Verfügung. Doch es gibt einige andere Effekte, die man nutzen kann, z.B. Zenerdioden oder den Luftdruck. Radiowellen aus dem Weltall wären sicher auf den ersten Blick auch gut, aber da diese für jeden empfangbar sind, ist es sehr schwierig, eine Vorhersehbarkeit der Zufallszahlen auszuschließen. Zenerdioden eignen sich wohl auch ganz gut. So kann man recht gute Zufallszahlengeneratoren auf die CPU einbauen: RdRand (en.wikipedia.org) oder rdrand (Intel)

Ist das Thema damit gegessen? Vielleicht, zumindest für viele Anwendungszwecke. Vielleicht traut man dem nicht und braucht dort, wo es wirklich darauf ankommt, noch bessere Verfahren? Auf jeden Fall wird es noch eine Weile dauern, bis man das wirklich verwenden kann. Heute haben das neue Intel-CPUs, wann haben es auch CPUs anderer Hersteller? Wann wird das durch die verschiedenen Betriebssysteme genutzt? Mindestens ein paar Jahre dürfen wir uns noch darauf freuen, daß dieses Feature breit verfügbar ist.

Linux hat einen Zufallszahlengenerator auf OS-Basis, der als /dev/random ansprechbar ist. Dieser nutzt „Zufälligkeiten“ wie Tastatureingaben, Mausbewegungen, vielleicht auch Plattenbewegungen u.s.w. aus. Vielleicht nicht ganz so gut wie rdrand, aber dafür schon lange verfügbar. Vielleicht haben andere Betriebssysteme ähnliche Möglichkeiten.

Wie funktioniert das? Wenn man teilweise zufällige Informationen hat, dann läßt sich das nächste Stück mit einer gewissen Wahrscheinlichkeit vorhersagen. Typisches Beispiel wäre etwa ein Text, der eingegeben wird. Der kann einer abstrakten Sprache angehören, z.B. einer natürlichen Sprache, einer Programmiersprache (mit einer natürlichen Sprache für die Kommentare) oder so etwas. Wenn das einigermaßen fehlerarm eingegeben wird, dann läßt sich ein unvollständiges Wort oft auf nur wenige Arten vervollständigen, so daß von den vielen möglichen Zeichen einige wenige wahrscheinlich sind. Wenn man mal von einem 8-bit-Zeichensatz ausgeht, bringt dieses eine Zeichen vielleicht nur etwa 1 Bit an Information, wenn etwa zwei Vervollständigungen sehr wahrscheinlich sind, statt 8 Bit. Dieses eine Bit wäre idealerweise die Zufälligkeit, also ein Zufallsbit, wenn man es schafft, das herauszudestilieren.

Nun ist es bei eingegebenen Texten etwas schwieriger. Wenn das bekannte Texte sind, etwa weil es abgeschrieben wird, oder wenn es ein ehemaliger Minister schreibt, sogar kopiert wird, dann besteht die Zufälligkeit nur noch in der Auswahl der passenden Texte, aber auch bei selbstgeschriebenen Texten schränkt der Kontext ein, was passen würde und was wahrscheinlich ist. Hinzu kommt das Wissen des Schreibers, dessen „Fingerabdruck“, der sich auch in den verfaßten Texten (oder Programmen oder was auch immer geschrieben wird) ausdrückt. Vielleicht ist das Wissen eines Menschen groß genug, um für viele Jahre oder sogar ein Leben lang Texte zu produzieren, die genug Zufälligkeit enthalten, aber wenn keine neue Information durch Kommunikation einfließt, ist das doch zu hinterfragen. Aber viele von uns arbeiten in Bürotätigkeiten, die in irgendeiner Form überwiegend darin bestehen, zu kommunizieren oder doch zumindest etwas einzugeben oder zu schreiben. Vielleicht gibt es dabei gänzlich unkreative Tätigkeiten, wo man etwas ausfüllen muß und genau eine Lösung richtig ist. Aber alle auch nur teilweise kreativen Tätigkeiten produzieren Information, die ohne diese nicht da war und würden sich somit als Basis für die Zufallszahlengenerierung grundsätzlich eignen.

Wir brauchen vielleicht den Kontakt zu unseren Mitmenschen, um neue Ideen zu entwickeln. Und nun fließt die aufgenommene Information natürlich wieder ein. Deshalb ist die Zufälligkeit der geschriebenen Textinhalte nicht leicht abzuschätzen und sie sinkt vielleicht um eine Größenordnung, wenn man verschiedene der hier angesprochenen Aspekte zu fassen bekommt oder ignoriert, weil man sie für nicht fassbar hält. Nun kann man die Texte aber verlustfrei komprimieren. Wenn man viel darüber weiß, was wirklich die reine Information (oder der Zufallsgehalt) ist, auf eine Größe, die knapp über diesem Informationgehalt liegt. Nun kann man auch geschickte „Hash-Codes“ verwenden, die aus den Texten Bytesquenzen generieren, die etwas kleiner sind, als der Informationsgehalt. Wenn das gut gemacht wird, ist das ein brauchbarer Zufallszahlengenerator, der aber für kryptographische Anwendungen sofort einiges an Wert verliert, wenn man aus der Kommunikation der Person nach dem Verfassen des Textes oder gar aus der direkten Verwendung des Textes Rückschlüsse auf diesen ziehen kann.

Wenn der Text öffentlich oder teilweise öffentlich zugänglich wird, zum Beispiel auf einer Webseite erscheint, wie der Text, der hier gerade geschrieben wird, dann besteht die Zufälligkeit nur noch in der Auswahl des Textes von den Milliarden Webseiten, die es gibt, was aber nur noch maximal ein paar Dutzend Bits sind. Und wer will schon eine kreative Tätigkeit nur für die Zufallszahlengeneration ausüben, ohne daß die eigentlichen Ergebnisse dieser Tätigkeit sinnvoll verwendet werden? Und wer will das gar noch bezahlen?

Die Zeitabstände zwischen den Tastatureingaben sind sicher auch so etwas wie ein Fingerabdruck, was individuell den Schreiber erkennen ließe, aber die Zufälligkeit dieser Zeiten läßt sich viel besser nutzen, weil wir das nicht verwenden, um Information zu transportieren. Ich werde mich also auch nicht erinnern, welche Zeitabstände ich zwischen den Zeichen hatte, außer daß der Schreibrhythmus natürlich beim nächsten Mal ähnlich (aber nicht identisch) sein wird. Und die Zeitabstände sind auch nicht auf dieser Webseite nachlesbar.

Share Button