Gut, wir waren stehen geblieben beim Thema Kodierung und wir hatten
uns zuletzt bedeutungserhaltende Abbildungen angesehen, das heißt also
Abbildungen, die, wenn man geeignete Interpretationen anwendet, die
Bedeutung entsprechend nicht verändern.
Wir hatten uns angeschaut, was ein Homomorphismus ist, weil
Homomorphismen geeignete Abbildungen sind, um Übersetzungen
anzuschauen.
Und wir hatten gesehen, dass ein Homomorphismus sozusagen das Ganze
erhält unter der Konkatenation.
Wenn ich also ein Homomorphismus auf ein konkateniertes Wort anwende,
dann kann ich auch den Homomorphismus auf die Teilworte anwenden und
danach das Ergebnis konkatenieren.
Und ein Homomorphismus hatten wir gesagt, ist Epsilon-frei, wenn jedes
Wort aus dem Grundalphabet, über den die Sprachen gebildet werden,
nicht auf Epsilon abbildet.
Wir hatten gesehen, wenn man doch das leere Wort hat, also das leere
Wort darf ja durchaus hinterher vorkommen und ist allgemein drin in
der Menge aller Wörter, die über einem Alphabet gebildet werden.
Wenn ich das leere Wort in einen x-beliebigen Homomorphismus reintue,
muss wieder das leere Wort rauskommen.
Das hatten wir gezeigt über die Definition der Länge.
Und wir waren stehen geblieben bei diesem Lemma und wollten uns das
jetzt anschauen.
Und was besagt das Lemma?
Also wir haben zwei Alphabete A und B und wir haben zwei Abbildungen H
und G, die von der Menge aller Wörter von dem einen Alphabet in die
Menge aller Wörter über dem anderen Alphabet anwenden.
Und jetzt seien diese Homomorphismen der Gestalt, dass sie für die
einzelnen Worte im ursprünglichen Alphabet immer das selbe Ergebnis
bilden.
Das heißt, wenn ich ein Wort hernehme oder ein Zeichen aus dem
ursprünglichen Alphabet, ist das ein Wort aus der Sprache über alle
Wörter über diesem Alphabet.
Wenn ich das in einen Homomorphismus reintue, bekomme ich dann halt
entsprechend ein Wort, also es muss nicht ein einzelnes Zeichen sein,
es können mehrere Zeichen sein, ein längeres Wort aus der Menge aller
Wörter aus dem zweiten Alphabet.
Und wenn das immer dasselbe Ergebnis gibt für H und G, für die
einzelnen eine Länge langen Worte aus der Sprache, also die Zeichen
aus dem Alphabet, dann gilt, dass die Homomorphisme komplett gleich
ist.
Dann ist es völlig egal, was für ein Wort welcher Länge ich reinstecke
in den Homomorphismus, dann kommt auch immer dasselbe Ergebnis bei G
raus.
Mit anderen Worten, wie ich die einzelnen Zeichen aus dem
Grundalphabet abbilde, legt vollständig fest, wie der Homomorphismus
insgesamt abbildet.
Das kann man jetzt wieder zeigen durch vollständige Induktion, indem
man wieder anfängt mit einem Induktionsanfang und über die Länge der
Worte geht.
Und ich schaue mir dann immer Worte an, die immer ein Zeichen länger
werden.
Für das Wort mit der Länge 0, das Epsilon-Wort, ist das trivial.
Wir hatten schon vorher gesehen, dass Homomorphismen Epsilon immer auf
Epsilon abbilden.
Dementsprechend gilt das für jeden Homomorphismus.
Also sei das Ganze gegeben für ein Wort der Länge N aus der Menge
aller Wörter.
Und wir nehmen uns jetzt ein einzelnes Zeichen aus dem Alphabet A her
und wir haben die Induktionsvoraussetzung, dass für die Wörter der
Länge N H von W gleich G von W gilt.
Jetzt machen wir aus diesem H von W der Länge N ein Wort der Länge N
plus 1, indem wir hinten einfach ein beliebiges Zeichen aus dem
Alphabet dran tun und müssen dann zeigen, dass H von W um dieses
Zeichen X erweitert, verlängert auf Länge N plus 1, dass das das
gleiche Abbild hat, als wenn ich das in G reinstecke.
Und dann kann man einfach rechnen.
H von W konkateniert mit X ist H von W konkateniert mit H von X.
Das ist die Definition eines Homomorphismus und das ist die
Voraussetzung für das Lemma.
W war jetzt ein Wort der Länge N.
Dementsprechend gilt die Induktionsvoraussetzung.
Statt H von W können wir G von W schreiben.
H von X muss sein gleich G von X.
Das ist nämlich die Voraussetzung des Lemmas.
Das heißt eben, dass immer auf das gleiche Wort abgebildet wird, wenn
ich ein einzelnes Zeichen X aus dem Alphabet reintue.
Und dann ist dementsprechend das Ganze das Ergebnis G von W X gemäß
Definition Homomorphismus und dementsprechend gilt das Lemma.
Soweit, so klar.
Mit dieser Eigenschaft kann ich jetzt noch eine zweite Abbildung
definieren und zwar oder eine besondere Art des Homomorphismus
definieren.
Angenommen, ich habe eine Abbildung, die einzelne Zeichen A abbildet
in die Menge aller Wörter über dem Alphabet B.
Also ich nehme ein X aus A her und bilde das ab, irgendein Wort, das
über B gebildet wird.
Und jetzt sei diese, das sei die Funktion F.
Und da definiere ich mir jetzt eine davon abgeleitete Abbildung F
Sternchen Sternchen, die jetzt nicht von A nach B Sternchen abbildet,
sondern von A Sternchen nach B Sternchen.
Also nicht einzelne Zeichen, sondern Wörter beliebiger Länge.
Und es seien zwei Sachen definiert.
Das eine sei, dass das leere Wort wieder auf das leere Wort abgebildet
wird.
Das ist wichtig, weil wir wollen am Ende einen Homomorphismus
erreichen, erhalten.
Und ansonsten für jedes beliebige Wort aus A Sternchen sei halt
gegeben, dass F Sternchen Sternchen WX abbildet auf F Sternchen
Sternchen von W konkateniert mit der Einzelabbildung, die durch F
definiert wird.
Das heißt, das Ganze ist wieder eine induktive Definition.
Die Wörter werden in der Länge immer kleiner gemacht, indem hinten ein
X abgespalten wird, also ein einzelnes Zeichen abgespalten wird.
Das X muss es... und dann das wieder rekursiv angewandt wird auf das
verbleibende Restwort W.
Und dieses F Sternchen Sternchen ist wieder ein Homomorphismus.
Man kann das schon sehr leicht ahnen.
Man kann das durch vollständige Induktion beweisen.
Ist auch ein relativ einfacher Beweis.
Und dieses F Sternchen Sternchen, wenn wir es auf diese Art und Weise
definieren, heißt ein durch F induzierter Homomorphismus.
Das heißt, das ist der Homomorphismus, der dadurch festgelegt wird,
dass ich einmal festlege, wie die einzelnen Zeichen aus dem Alphabet
abgebildet werden.
Und das ergibt dann automatisch einen Homomorphismus, der alle Wörter
als Homomorphismus aus dem über A gebildeten Alphabet nach B Sternchen
abbildet.
Mit diesem Verfahren, dass man hinten was abschneidet und dann
zusammentut, kann man jetzt sich anschauen, Kodierung, also eine
Abbildung durch einen Homomorphismus, oder besser gesagt eine
Übersetzung von Wörtern aus dem einen Alphabet über dem einen Alphabet
A zu Wörtern über dem anderen Alphabet B.
Und das sei ein Homomorphismus.
Und dann möchte man natürlich noch ein paar andere Eigenschaften
wissen, zum Beispiel, ob das Ganze injektiv ist.
Das ist eine Eigenschaft, die ist nicht im Allgemeinen für beliebige
Homomorphismen einfach zu sehen.
Es gibt aber wiederum einen Spezialfall von Homomorphismen, sogenannte
präfixfreie Homomorphismen.
Und für die ist das einfach zu sehen.
Was bedeutet präfixfrei?
Das ist das, was man sich schon vorstellen kann.
Das bedeutet, dass wenn ich mir anschaue, auf was wird denn
abgebildet.
Also ich bilde von irgendeinem Alphabet in ein anderes Alphabet ab, in
das, was ich abbilde.
Das sind meine Kodwörter.
Das ist mein Kod, mit dem ich die Wörter aus A Sternchen kodiere.
Wenn diese Kodwörter, auf die ich abbilde, derart sind, dass nie ein
Kodwort Präfix eines anderen Kodes ist.
Das heißt, es darf kein Kodwort geben, das irgendwie so anfängt, dass
da der Anfang beliebiger Länge ein anderes Kodwort ist.
Dann nennen wir das Ganze präfixfrei.
Dann kann man relativ einfach zeigen, dass jeder präfixfreie Kod, also
jeder Homomorphismus dieser Art, der präfixfreie Ergebnisse liefert,
dass der injektiv ist.
Vorher noch ein kleines Problem.
Wenn wir uns die umgekehrte Richtung anschauen, also wenn wir wieder
aus B Sternchen zurück abbilden wollen nach A Sternchen, wenn wir also
den Kod, den wir durch den Homomorphismus erhalten haben, dekodieren
wollen.
Wieder auf das ursprüngliche Urbild zurückrechnen wollen.
Da muss man beachten, dass ein Homomorphismus nicht notwendigerweise
sujektiv ist.
Das heißt, nicht jedes Wort aus B Sternchen muss notwendigerweise ein
Kodwort sein.
Und wenn ich jetzt dekodiere, ich also von B Sternchen zurück abbilde
nach A Sternchen, dann muss ich irgendwie was überlegen für den Fall,
dass irgendein Wort aus diesem B Sternchen gar kein gültiger Kod ist.
Dass der gar nicht Abbild dieses Homomorphismus ist, des
ursprünglichen war es und muss da irgendwie mir was einfallen lassen,
dass ich das kennzeichne.
Und das kann man relativ einfach damit machen, indem man so ein
Spezialwort einführt.
Hier so ein umgekehrtes T genommen.
Das soll einfach stehen für undefiniert, nicht dekodierbar.
Und wenn ich dann also die Dekodierung definiere, dann bildet die ab
von B Sternchen nach A Sternchen vereinigt mit oder multipliziert mit
diesem umgekehrten T Sternchen.
Oder andersherum, ich vereinige das Alphabet mit diesem zusätzlichen
Zeichen, das bei nicht dekodierbar mit reingeschleust wird und bilde
darüber alle Wörter und daran wird abgebildet.
Wenn also W kein Kodwort ist, dann muss ich meine Dekodierung halt so
definieren, dass dann irgendwo dieses Spezialsymbol eingefügt werden
soll.
Einfaches Beispiel angenommen, wir haben so ein Homomorphismus, der
bildet ab alle Wörter, die sich aus A, B und C irgendwie
zusammensetzen in eine binäre Kodierung, in binäre Folgen, also nach
0, 1 Sternchen.
Das jetzt brauche ich nach dem, was ich vorher gelernt habe, nur noch
festlegen, welches die Urabbilder sind und kann dann diesen durch
diese Urabbildungsdefinition induzierten Homomorphismus hernehmen.
Also nehmen wir her, wir haben diese Abbildung H von A, die sei 1, H
von B gleich 0, 1 und H von C gleich 0, 0, 1.
Man sieht, das ist präfixfrei, also es gibt keine Folge aus Nullen und
Einsen, die jetzt mit einem anderen Kodwort anfängt.
Das ist ganz simpel dadurch gelöst, dass ich erst mal mit Nullen vorne
aufstocke, bis ich dann was richtiges rein tue und das immer länger
werden lasse, bevor die erste 1 kommt.
Und die Dekodierung bildet dann entsprechend jetzt ab von den binären
Wörtern in die Wörter über dem Alphabet, die halt um dieses
Sonderzeichen ergänzt wurden.
Und wenn man dekodieren möchte, klar, man möchte erstmal wieder die
Urbilder zurückhaben, also 0, 0, 0, 1, wenn ich das dekodiere, soll C
rauskommen und wenn ich sowas dekodiere, wie 0, 1, 0, 1, kommt B, B
raus.
Jetzt sieht man auch schon, warum dieses mit dem Präfixfrei so schön
und einfach zu handhaben ist bei der Dekodierung.
Ich habe im Prinzip ja das Problem, wenn ich so einen Kod habe, dass
da ja keine Wortgrenzen drin oder in diesem Fall Zeichengrenzen drin
definiert sind.
Ich habe also ursprünglich mal definiert, die einzelnen Zeichen, auf
was werden die abgebildet und habe jetzt irgendwie ein Wort und will
das abbilden auf ein Wort, das aus mehreren Zeichen besteht bei der
Dekodierung.
Und ich möchte aber nur auskommen mit dem Wissen darüber, wie ich die
einzelnen Zeichen des Alphabets mal abgebildet habe.
Jetzt kann man sich überlegen, wenn man jetzt so einen beliebig langen
Kodwort bekommt, das aus mehreren Zeichen entstanden ist, aus dem
Ursprungsalphabet zusammengesetzt, dann muss ich ja irgendwie wissen,
wo sind da letztendlich Zeichengrenzen, wenn ich nur diese
Informationen habe.
Und das kann ich dadurch machen zum Beispiel, dass alle Kodwörter die
gleiche Länge haben.
Dann brauche ich immer nur zu zählen und weiß dann nach Länge, habe
ich ein neues Urbild oder neues Abbild eines einzelnen Zeichen gehabt,
gemäß der Homomorphismus-Definition kann zurück abbilden oder ich kann
das halt über präfixfreie Kodes machen.
Durch die präfixfreien Kodes weiß ich auch, brauche ich nur von links
nach rechts so lange durchzugehen, meine Zeichen, bis ich ein
vollständiges Kodwort zusammen habe.
Ich weiß, das Kodwort kann dann nicht länger sein, weil sonst wäre das
ja der Präfix eines Kodwortes und das darf es eben nicht sein.
Das heißt also, wenn ich sowas habe wie 0101, gehe ich von links nach
rechts durch.
01, vollständiges Kodwort, weise ich jetzt in B.
Die nächste Folge, 01, vollständiges Kodwort, weise ich jetzt in B,
kann es dekodieren in BB.
Und wenn ich dann zum Beispiel eine einzelne 0 nur bekomme und sonst
nichts, dann weiß ich, das war kein Kodwort.
Das ist nie durch den Homomorphismus festgelegt werden.
Also muss ich das abbilden auf irgendwas, was das ungültige Zeichen
enthält, zum Beispiel nur das ungültige Zeichen alleine.
Dementsprechend, wenn man jetzt diese Dekodierung allgemein für dieses
Beispiel hinschreibt, kann man das eben so hinschreiben, dass man
sagt, man dekodiert ein Wort W und macht folgende Fallunterscheidung.
Falls es Y ist, muss es Y sein.
Falls es mit 1 anfängt und dann kommt noch irgendwas, dann wird die 1
halt auf das A abgebildet und dann muss ich mich um den Rest kümmern.
Falls es halt 01 ist, weise ich es in B und dann den Rest mich darum
kümmern.
Falls es 001 war, kommt das auch wieder auf C abgebildet und ich muss
rekursiv den Rest machen.
Und falls es irgendwas anderes ist, dann ist es etwas, was ich nicht
kenne und dann wird einfach das ungültige Zeichen ausgegeben.
Also so wie wir das für 01, 01 gerechnet haben, kann man das auch hier
für rechnen.
1 ist dann A, bleibt 001, 01 übrig.
Dann muss man gucken.
001 war das C, also AC bleibt 01 übrig.
01 war das B, also kommt ACB raus.
Bleibt nichts mehr übrig.
U von Y war Y, also ACCB konkateniert mit Y, gleich ACB.
Und ich habe Ihnen schon erklärt, warum das geklappt hat.
Das hat eben deshalb geklappt, weil ich von links nach rechts
durchgehen kann und sobald ich ein vollständiges Code worde habe, weiß
ich, es kann kein anderes sein, eben wegen der Präfixeigenschaft.
Also kann ich dann direkt die Abbildung machen.
Oder andersherum, wenn man sich die Definition anschaut, es war in
jeder Zeile klar, welche Definition man anwenden soll.
Man nennt das Ganze auch dann wohldefiniert halt.
Also der Code ist wohldefiniert, wenn ich immer weiß, welche Zeile,
welche Abbildung ich machen kann.
Es gibt keine Ambiguität, es gibt keine Doppeldeutigkeit.
Es ist eindeutig, welche Regel ich bei der Rückabbildung anwenden
soll.
Problematisch wird es halt, wenn der Funktionswert auf mehreren Wegen
gerechnet werden kann.
Also wenn ich in dieser Fallunterscheidung jetzt einen von mehreren
Fällen habe, den ich theoretisch anwenden könnte.
Das muss nicht heißen, dass ich damit nicht dekodieren kann.
Also ich kann eine Funktion machen, die dekodiert, die durchaus nicht
eindeutig ist, welchen Fall ich in dieser Abbildung jetzt anwenden
muss, die mehrere Fälle zulässt.
Nur die muss dann so strukturiert sein, dass, wenn mehrere Fälle
möglich sind, also wenn es mehrere mögliche Rückrechnregeln gibt, dass
trotzdem immer noch dasselbe Ergebnis rauskommt.
Das kann man durchaus definieren, das kann man machen.
Das ist natürlich nicht so schön.
Da ist es schwierig mit umzugehen, da ist es schwierig zu überprüfen,
ob auch das Richtige rauskommt.
Deswegen nennen wir das halt eben nicht wohl definiert.
Oder auch lassen wir besser die Finger von.
Also immer aufpassen, dass entweder wohl definiert ist, dann ist es
schön einfach und funktioniert gut.
Oder dass man halt wirklich aufpasst, dass man auch immer den gleichen
Funktionswert erhält.
Und das zu beweisen ist unter Umständen schwierig.
Und deswegen für präfixfreie Codes kann man es ganz einfach machen,
dass man das eben hinschreibt, also Y auf Y.
Falls W irgendwie ein Codewort ist eines einzelnen Zeichens aus dem
ursprünglichen Alphabet von A, dann wird es gleich direkt dekodiert
und der Rest gemacht.
Und falls es den nicht gibt, dann eben ungültig, nicht dekodierbar.
Ein einfaches Beispiel für so einen präfixfreien Code ist UTF-8.
UTF-8 ist ein Code, um Unicode-Zeichen zu definieren.
Es dient dazu, um halt von der Menge der Zahlen, der Codepoints in
Unicode abzubilden auf halt eine binäre Zahl, die für diesen Codepoint
steht.
Und da macht man das so.
Man hat ja auf der linken Seite nicht nur ein einzelnes Unicode
-Zeichen stehen, sondern eine ganze Folge von Unicode-Zeichen.
Das heißt, ein Wort ist zusammengesetzt aus vielen Unicode-Zeichen und
daraus muss jetzt wieder irgendwie eine ganz große, lange Zahl, eine
Folge von Nullen und Einsen gemacht werden.
Die einfachste Idee wäre nämlich Zeichen gleicher Länge her und
schreibe einfach die Codepoints immer in Felder gleicher Länge
hintereinander.
Das ist ein einfacher Homomorphismus.
Den gibt es auch.
Der nennt sich UTF-16.
Der hat den Nachteil, die Idee dahinter ist, dass man das vielleicht
nicht so geschickterweise macht, weil man eventuell Speicher
verschwindet.
Wenn man sich nämlich anschaut, die Zeichen, die es so in Unicode
gibt, da gibt es viele Zeichen, die werden sehr häufig verwendet.
Zum Beispiel lateinischen Buchstaben oder auch korillische Buchstaben
oder irgendwas, was verwendet wird, um viel Text zu schreiben.
Das ist etwas, das in Unicode sehr häufig vorkommt.
Aber es gibt auch sehr viele Zeichen, die kommen vielleicht nicht so
häufig vor.
Irgendwelche kleinen Emojis oder es gibt Länderflaggen in Unicode.
Es gibt Zeichen, die die Schreibrichtung umdrehen und das ist zum
Beispiel sehr unwahrscheinlich, dass wenn ich mal angefangen habe, von
links nach rechts zu schreiben, dass ich alle zwei Zeichen meine
Schreibrichtung wieder umkehre.
Das mag es mal hin und wieder geben, aber wird meistens nicht
vorkommen.
Und wenn ich dafür immer gleich möglichst breites Feld habe, sodass
ich alle Unicode-Points in die gleiche Feldlänge reinbekomme, dann
verschwende ich halt viel Platz.
Deswegen hat man mit UTF-8 einen präfixfreien Code gemacht.
Und wenn man da reinschaut, da gibt es wieder einen Request for
Comments für.
Das heißt, das Ganze ist auch irgendwie verknüpft mit der Internet
Engineering Taskforce am Ende.
Also es gibt einen Request for Comments, den Nummer 3629, der legt das
fest, wie das funktioniert.
Und UTF-8 ist eben ein präfixfreier Code und die Präfixe hat man, die
Präfixfreiheit hat man dadurch gemacht, dass man so eine Unterteilung
macht der Code-Points, die es so gibt.
Man unterteilt denen in Intervalle die Code-Points und das Ganze hier
in Dexadezimalschreibweisen mal hingeschrieben.
Also für alle Code-Points, die zwischen 0 und 7f liegen, die kriegen
als Präfix erstmal eine 0.
Dann die Code-Points, die zwischen 8 0 und 7ff liegen, die kriegen
halt sozusagen ein zusammengesetztes Wort aus zwei Präfixen.
Die kriegen 1 1 0 und dann wird hinten noch was drangehängt mit 1 0
und so weiter und so fort.
Und diese Anzahl der Bits, aus denen sich das zusammensetzt, die
werden halt immer größer.
Wir sehen halt oben für das erste Intervall brauchen sie nur 8 Bit, um
die zu dekodieren und danach für das zweite Intervall brauchen sie
schon 2 x 2 8 Bit, für das dritte Intervall 3 x 8 Bit und für das
letzte Intervall 4 x 8 Bit.
Das heißt, man kann sich jetzt schon vorstellen, die Zeichen von denen
man erwartet, dass sie häufig vorkommen, die sollten halt in der
ersten ersten Intervall liegen und die, die am wenigsten vorkommen,
die sollten halt im letzten Intervall vorkommen.
Und auch dadurch, dass das jetzt präfixfrei ist, kann man jederzeit
von links nach rechts durchgehen.
Wenn ich eine 0 sehe, dann weiß ich, die nächsten sieben Bits, die
kommen, gehören zu einem Zeichen aus dem ersten Intervall.
Wenn ich 1 1 0 sehe, dann weiß ich, okay, ich muss jetzt die nächsten
5 Bit hernehmen und dann sollte eine 1 0 kommen und ich muss die
nächsten 6 Bit hernehmen und so weiter und so fort.
Das heißt, im Prinzip kann man das so interpretieren, wie viele Folge
-Oktette man noch bekommt.
Also wenn 0 vorne steht als erstes, gibt es kein Folge-Oktett.
Wenn eine 1 1 0 steht, dann besteht das Ganze aus insgesamt zwei
Oktetten.
Das heißt, es kommt noch ein Folge-Oktett.
Dann, wenn ich drei 1 stehen habe, dann besteht das Ganze halt aus
drei Oktetten.
Und wenn ich vier 1 stehen habe, besteht das Ganze aus vier Oktetten.
Und man füllt dann diese Xer, die man hat, die man frei befüllen darf,
dann entsprechend aus, durch die niedrigsten Bits,
wie man sie hätte, als würde man diesen Unicode-Codepoint einfach
binär als Zahl auf der Zweierbasis füllen.
Also, ein einfaches Beispiel.
Angenommen, wir hätten diesen Unicode-Codepoint 2 2 2 b in
Hexadezimalschreibweise geschrieben, das heißt, das Ganze fällt rein
in dieses Intervall von 8 0 0 0 bis 4 mal die F.
Wir wissen also schon mal, dass wir dann durch Nachgucken in der
Tabelle drei Oktette brauchen.
Das erste Oktett fängt mit 1 1 0 an, das zweite Oktett mit 1 0 und das
dritte Oktett auch mit 1 0.
Schauen wir uns an, wenn ich jetzt 2 2 2 b in Dual-Binär-Darstellung
hinschreibe, ist das eben diese Folge aus insgesamt zwei Oktetten oder
vier Blöcken aus vier Bits, also insgesamt 16 Bits.
Und jede Unicode-Zahl, jeden Unicode-Codepoint kann ich immer in 16
Bit darstellen, deswegen funktioniert diese UTF-16-Darstellung, in die
man einfach sagt, alle kriegen die gleiche Länge.
Das würde entsprechend so aussehen, mit 16 Bit dargestellt.
Und jetzt muss man das entsprechend zerlegen.
Ich habe drei Oktette, das letzte Oktett enthält 6 Bits, das heißt die
letzten 6 Bits aus dieser Zahl, die muss ich hochkopieren in das
letzte Oktett.
Die nächsten 6 Bits aus der Zahl muss ich auch wieder hochkopieren in
das zweite Oktett.
Bleiben noch vier Bits übrig, die ich noch nicht hochkopiert habe und
die kommen dann halt in das erste Oktett rein.
Und daraus ergibt sich dann halt die Unicode-Codierung von diesem
Zeichen, das Sie hier entsprechend sehen, mit Präfixen für die Oktette
halt dargestellt und farblich codiert, wo welche Bitfolge herkommt.
Also summa summarum sollten Sie halt wissen, was sind Übersetzungen,
dass man Übersetzungen als Homomorphismen darstellen kann, dass solche
Homomorphismen Codes definieren, dass ich also von Wörtern aus dem
einen über dem einen Alphabet in das andere Alphabet abbilden kann.
Und das worin ich abbilde, das nenne ich halt die Codes, die Abbilder.
Und dass es halt sowas wie präfixfreie Homomorphismen gibt, die man
leicht wieder dekodieren kann, wo man eine einfache
Dekodierungsvorschrift angeben kann.
Und UTF-8 halt als Beispiel eines solchen präfixfreien Codes, der gut
für die Dekodierung von so UTF-8 Zeichen gedacht ist.
Jetzt ist ja bei UTF-8 schon diese Idee angekommen.
Häufige Zeichen sollten möglichst wenig Bits haben, nicht so häufige
Zeichen sollten möglichst lange Bits haben, damit am Ende die Anzahl
der Bits, die ich zur Codierung so eines Zeichen brauche, möglichst
gering wird.
Wenn man sich das anschaut bei Unicode, also ich weiß, ich könnte es
in 16 Bit kodieren.
Ich könnte jedes Unicode Zeichen in 16 Bit kodieren.
Manchmal reichen 8 Bit aus und manchmal brauche ich 4 mal 8 Bit, also
32 Bit deutlich mehr.
Das heißt, damit das funktioniert, wenn man das auf typischen Text
anwendet, sollte natürlich im Mittel weniger als 16 Bit pro Zeichen
rauskommen.
Und das funktioniert halt nur dann, wenn es halt so eine Inbalance
gibt, was die Häufigkeit der einzelnen Zeichen anschaut.
Und wenn man jetzt mit präfixfreien Codes arbeitet, gibt es eine
Codierung, die mir garantiert, dass ich die kürzeste mögliche
präfixfreie Codierung für ein bestimmtes Alphabet finden kann.
Und das ist die sogenannte Huffmann-Codierung.
Mit der Huffmann-Codierung definiert mir ein Homomorphismus, der aus
einem Alphabet abbildet in einen Code, der mir halt durch diesen die
Huffmann -Codierung vorgegeben wird.
Und der, wenn ich die Häufigkeiten kenne, mit der die Zeichen aus dem
Alphabet vorkommen, entsprechend mir den kürzesten, möglichst
präfixfreien Code gibt.
Also formal ist es eine Abbildung von A Sternchen in Z2.
Das heißt, es kommen also Bit Folgen aus Nullen und Einsen heraus,
also nach Z2 Sternchen.
Es ist Epsilon-frei.
Und typischerweise wird so die Huffmann-Codierung auf beliebige Wörter
über dem Alphabet A Sternchen angewandt.
Und Huffmann-Codierung, Huffmann-Codierung kennen Sie alle.
Das ist das, was in die ganzen SIP-Verfahren meistens darauf beruhen.
Also GNU-SIP, B-SIP2 etc.
basieren alle mit kleineren Variationen und Arten und Weisen, wie ich
dann noch ein bisschen Verwaltungsinformationen vor und dahinter
stecke, auf diese Huffmann-Codierung.
Es gibt einen relativ einfachen Algorithmus, wie ich für ein
beliebiges Alphabet, wenn ich die Häufigkeiten der Vorkommen der
Zeichen aus dem Alphabet kenne hinterher, mir diesen Huffmann-Code
berechnet.
Also angenommen, wir hätten ein Wort aus A Sternchen und wir kennen
die Vorkommen aller Zeichen in diesem Wort aus A Sternchen.
Dann kann ich für dieses Wort aus A Sternchen einen Huffmann-Code
berechnen.
Und damit ich das kann, setze ich jetzt einfach voraus, dass in diesem
Wort mindestens jedes Zeichen einmal vorkommt.
Das kann ich machen ohne Beschränkung der Allgemeinheit, O, B, D, A.
Warum?
Angenommen, es gäbe in dem Wort Zeichen, die nicht vorkommen.
Dann kann ich die einfach aus meinem Alphabet rausnehmen und brauche
für die auch entsprechend keinen Code zu haben.
Und wenn ich die aus dem Alphabet rausnehme, dann kann ich wieder
einen Homomorphismus haben, der mir die Dinger nicht abbildet.
Die Konstruktion dieses Huffmann-Codes kann man sich leicht als ein
Baumverfahren vorstellen, indem man aus den Zeichen des Alphabetes
einen Baum klustert und am Ende gibt mir der Baum, den ich da
geklustert habe, entsprechend den Huffmann-Code vor.
Ich kann dann für das Wort aus diesem Baum entsprechend dann den Code
wieder ablesen, indem ich einfach Pfade aus diesem Baum verfolge, mir
gucke, was steht in den Blättern und daraus den Code zusammenbaue.
Einfaches Beispiel.
Es sei dieses Wort gegeben, das besteht aus Zeichen A, B, C, D, E und
ich habe irgendwie gewusst, welche oder ich kann zählen, wie häufig
die Zeichen vorkommen und habe dann diesen Baum berechnet.
Wenn ich den jetzt anwenden will, also angenommen, der Baum ist vom
Himmel gefallen, den hat mir irgendeiner berechnet.
Wenn ich damit jetzt kodieren möchte, das Wort, dann muss ich mir als
erstes anschauen, okay, das A, in welches, in was wird das kodiert und
um das rauszufinden, muss ich den kürzesten Weg von der Wurzel des
Baumes bis zu dem Blatt hinnehmen, das mir das A vorgibt.
Und das ist einfach hier immer runter gehen, immer 0, 0, 0,
dementsprechend ist dreimal die 0 der Code für das A.
Für die Konstruktion des Baumes scheint es wohl wichtig gewesen zu
sein, wie häufig die einzelnen Zeichen vorkommen.
Und da steht dann hier zusätzlich noch an dem Blatt dran, da steht zum
Beispiel dabei für das A, dass das zweimal oben in dieser Wortfolge
vorgekommen ist.
Das B kam zweimal vor, das C kam dreimal vor und das D kam dreimal
vor.
Das F sogar siebenmal und das E fünfmal.
Dementsprechend wird man erwarten, dass für A und B kürzere Codes
gewählt werden als für F und E vielleicht ein kürzerer Code als F und
C und D muss irgendwo zwischen E, F und B liegen.
Und die Frage ist natürlich, kommen die jetzt so viel häufiger vor,
dass ich da einen längeren Code zum Beispiel nehmen kann als für die,
die zweimal vorkommen und ist das, wenn es siebenmal vorkommt, schon
so viel länger, dass ich dafür dann einen kürzeren Code verwenden
kann.
Und wenn ich mir das anschaue, was hinterher rauskommt, die Tiefe, wo
dieses Blatt aufbaut, wenn ich mir also den Baum in so Ebenen
aufteile, die Tiefe, wo dann hinterher das Blatt vorkommt, bestimmt
mir natürlich die Länge des Codes.
Das heißt hier, das F ist auf Ebene 1, 2, kriegt also, muss ich zwei
Kanten verfolgen, kriegt also dementsprechend einen Code der Länge 2,
die 5 auch.
Okay, auch wenn sie unterschiedlich häufig vorkommen, kriegen sie den
gleichen Code.
Und hier A, B, C und D liegen auch auf der gleichen Ebene, auf der
Ebene 3, kriegen also einen drei Längen langen Code.
Und das kann man entsprechend als Tabelle dann auch hinschreiben und
sieht dann, dass man da einen präfixfreien Code hat.
Und die Eigenschaft ist halt, dass das der kürzeste präfixfreie Code
ist, um dieses Wort hinterher zu codieren.
Wenn man das Ganze konstruieren will, geht man von unten nach oben
vor.
Man baut diesen Baum von unten nach oben auf.
Man schreibt sich erstmal die Blätter hin, mit den einzelnen Zeichen
und zusammen mit ihrer Häufigkeit, wie sie in diesem Wort vorkommen.
Wenn man das jetzt formal hinschreibt, dann definiert man sich halt
Mengen.
Man kann sozusagen jede Ebene von Knoten auf diesem Baum kann man als
Menge sich auffassen.
Und diese Menge sind halt Tupel aus dem Zeichen, das codiert werden
soll und der Häufigkeit, wie es vorkommt.
Und ganz am Anfang M0 enthält halt die Menge aller Blätter.
Das heißt, da unten gibt es nur einzelne Zeichen.
Also haben wir dementsprechend eine Menge M0, die halt aus den Tupeln
besteht.
Das A kam zweimal vor, das B kam zweimal vor, das C dreimal, das D
dreimal, das E fünfmal und das F siebenmal.
Und jetzt fange ich an, neue Mengen zu konstruieren, eine Menge M1,
eine Menge M2 etc., indem ich anfange, diese Tupel, die in dieser
Menge M0 sind, zusammenzulegen.
Also Anfang jetzt schon mal schön hingeschrieben, weil das ist
natürlich ein bisschen gemogelt hier.
Ich habe jetzt mal diese Elemente da hingeschrieben.
Das sind die, wie sie vorher in dem Baum drin waren und die sind schon
so angeordnet, dass sie hinterher auf der richtigen Ebene des Baumes
liegen.
Das weiß ich zu dem Zeitpunkt noch nicht, auf welcher Ebene die liegen
werden.
Eigentlich stehen die alle erstmal gleichberechtigt nebeneinander,
aber da wir das Ergebnis schon kennen, haben wir halt gemogelt und die
schon mal so schön hingeschrieben, dass man sie auch hinterher schön
sich anschauen kann.
Was ich jetzt mache ist, wenn ich so eine Menge M0 habe, dann fange
ich an, Tupel zusammenzulegen und zwar die Tupel mit den kleinsten
Häufigkeiten.
Das heißt, ich nehme mir das Tupel her mit der kleinsten Häufigkeit
und dann das Tupel mit der zweitkleinsten Häufigkeit und lege die
beiden zusammen.
Kann durchaus sein, dass diese Zusammenlegung nicht eindeutig ist.
Kann ja sein, dass ich zum Beispiel fünf Tupel habe, die alle mit der
gleichen Häufigkeit vorkommen.
Wenn das der Fall ist, wähle ich mir halt eine beliebige
Zusammenlegung von diesen beiden Tupeln zusammen.
Ich lege halt immer zwei Tupel zusammen und zwar die mit den kleinsten
Häufigkeiten und wenn das nicht eindeutig ist, kann ich rein zufällig
wählen, welche ich da zusammenlege.
Und was ich jetzt mache ist, wenn ich dieses Zusammenlegen als
Mengenoperationen hinschreibe, dann ist das nichts anderes, als dass
ich aus der Menge MI die beiden Tupel mit den kleinsten Häufigkeiten
entferne und neues Tupel reinmache, das jetzt aus den Zeichen besteht,
die da zusammengelegt wurden und zwar egal in welcher Reihenfolge.
Die werden einfach als Menge hingeschrieben.
Das heißt, interessiert mich keine Reihenfolgenoperationen und die
Häufigkeit dieser neu gebildeten Zeichenmenge sei einfach die Addition
der Häufigkeiten der jenen Tupel, die ich da zusammengelegt habe.
Wenn ich das im Grafen mache, also meine ursprüngliche Menge, wenn ich
das im Grafen mache, dann markiere ich mir einfach die beiden mit den
kleinsten Häufigkeiten, also hier zwei A und zwei B und lege die
zusammen zu einem neuen Knoten mit A, B und der Häufigkeit 4.
Diese Information darüber, dass ich da A, B eigentlich zusammengelegt
habe, die kann ich an der Stelle schon vergessen, weil ich jetzt keine
Blätter mehr habe.
Wenn ich hinter den Code bestimmen will, dann arbeite ich mich immer
bis zu den Blättern vor und lese bei den Blättern dann erst ab, wie
ich codieren muss.
Das heißt, die Information darüber, dass ich jetzt A und B
zusammengelegt habe und dass da 4 rauskommt, ist eigentlich völlig
egal.
Hat ja auch in der Zusammenlegung keinerlei Bedeutung.
Also wenn ich die Zeichen zusammenlege, hinterher neue Zeichen
zusammenlege, dann gucke ich mir ja gar nicht an, welche Zeichen da
drin stehen.
Das Einzige, worauf ich meine Entscheidung basiere, ist die
Häufigkeiten der Tupel.
Muss man aber eine Sache beachten, warum ich da trotzdem nur 4
hinschreiben kann, weil ich lege ja zusammen und rein formal bilde ich
hier die Vereinigung von den Zeichen, die ich da zusammengelegt habe.
Und würde ich jetzt an irgendeiner Stelle, wenn ich diese neuen Mengen
bilde, da eine Vereinigung kriegen, plötzlich zwei Tupel kriegen, die
dasselbe sagen, also gleiche Häufigkeit haben und gleiche
Zeichenmenge, dann würden die ja in dieser Menge zu einem Knoten am
Ende zusammenfallen.
Warum kann das nicht passieren?
Warum kann das nicht passieren, dass ich da in dieses Problem
reinlaufe, sondern warum kann ich da einfach, wenn ich das
hinschreibe, mir das vergesse?
Da könnte man sich jetzt einen kleinen Beweis überlegen, warum es nie
sein kann, dass bei diesem Zusammenlegen zweimal dasselbe rauskommt.
Und das hat einfach damit zu tun, ich habe ja unten in den Blättern
unterschiedliche Zeichen stehen.
Und jetzt lege ich immer zusammen und zusammen.
Und wenn ich dann plötzlich auf irgendeiner Ebene zwei
Zusammenlegungen hätte, die aus dem gleichen Zeichen besteht, dann
müsste ich ja irgendwo bei der Ebene vorher schon mal was
zusammengelegt haben, was aus Zeichen liegt, wo ich parallel selbe
Zeichen zusammengelegt habe.
Und das würde ja bedeuten, dass ich unten auf der Blattebene auch
dasselbe Zeichen mehrmals haben müsste mit unterschiedlichen
Häufigkeiten.
Und das kann gemäß der Definition von M0 eben nicht der Fall sein.
Könnte man also zum Beispiel durch vollständige Induktion beweisen,
dass das nicht passiert.
Gut, also die beiden werden zusammengelegt zu einer 4.
Danach bleiben hier unten 3c und 3d übrig.
Die werden zusammengelegt, haben Häufigkeit 6.
Dann 4, muss ich mir das anschauen, sind jetzt noch übrig 4, 5e, 6,
7e.
Die hier unten wurden immer herausgenommen.
Gut, 4 und 5 sind diejenigen, die werden zusammengelegt.
Dann haben wir 9, 6 und 7.
Also werden 6 und 7 zusammengelegt und dann werden noch 9 und 13
zusammengelegt.
Und ganz am Ende habe ich dementsprechend den einen einzelnen Knoten,
der ist der Wurzelknoten meines Baumes.
Und jetzt muss ich nur noch eines machen, damit ich auch hinterher mit
diesem Baum kodieren kann.
Ich muss den Kanten Namen geben.
Und den Kanten gebe ich halt immer einen Namen, indem ich zum Beispiel
sage, die Kante, die den linken Sohn oder den linken Nachfolger
betrifft, kriegt halt die 0 und die rechte Kante kriegt halt eine 1.
Wenn ich die so beschrifte, dann kann ich eben für jedes Zeichen, was
ich habe, den Huffman-Code ablesen, indem ich jetzt halt in diesem
Baum den kürzesten Pfad nehme.
Und den kürzesten Pfad, das muss halt immer logischerweise ein Pfad
sein, der nicht einen Schritt aus der Ebene zurück macht, sondern der
direkt immer nur in den Baum tiefer geht.
Den kann ich natürlich einfach dadurch finden, indem ich von unten
nach oben hochgehe, indem ich halt unten vom Blatt sozusagen mir
rückwärts den Code aufbaue und immer in Richtung Wurzel gehe und dabei
mir merke, welche Kanten ich mit welcher Beschriftung durchlaufen
habe.
Genau, das sind halt je nach Rechtsführung.
Und ja, das ist halt formal, es ist eine Konkatenation, kann ich dann
entsprechend machen.
Das ist halt der Baum, der am Ende dann rausgekommen ist, das ist der
Baum von vorhin, den wir uns gesehen haben mit diesem prefixfreien
Homomorphismus.
Jetzt kann man sich schon leicht überlegen, dass so ein Huffman-Code
im Allgemeinen nicht eindeutig ist.
Zum einen kann es durchaus manchmal Mehrdeutigkeiten geben, welche
Sachen ich zusammenlege.
Also kann, wenn ich halt Tupel habe mit gleicher Häufigkeit und habe
vier Stück davon, dann habe ich ganz viele verschiedene Möglichkeiten,
zwölf Möglichkeiten, wie ich die zusammenlegen kann.
Dementsprechend kommt natürlich auch ein unterschiedlicher Huffman
-Code raus oder ganz einfach, ich kann einfach die Labels an den
Kanten vertauschen.
Ich kann also, statt links eine 0 zu schreiben, kann ich eine links
eine 1 schreiben und rechts eine 0.
Kommt formal ein anderer Huffman-Code raus, aber letztendlich von der
Länge her kommt immer dasselbe bei raus.
Jetzt kann man das Ganze noch ein bisschen vereinfachen.
Zum Beispiel, wenn wir an geschriebenen Text denken, dann ist es
vielleicht nicht sinnvoll, dass man immer einzelne Zeichen kodiert,
sondern man wird sicherlich feststellen, bei längeren Texten werde ich
vielleicht so Häufigkeiten nicht auf den Buchstaben eines Alphabets
bekommen, sondern vielleicht bekomme ich Häufigkeiten bezüglich von
Tupeln aus Buchstaben, also zweierfolgen aus Buchstaben oder
vielleicht aus dreierfolgen aus Buchstaben.
Sprich, ich gucke mir nicht einzelne Zeichen aus dem Alphabet an,
sondern ich gucke mir immer ganze Blöcke einer fixen Länge aus dem
Alphabet an, aus denen dann hinterher die Wörter aufgebaut werden und
kann daraus eine Kodierung machen.
Ich baue mir mit anderen Worten so eine Art neues Alphabet her, das so
aus Blöcken fixer Länge besteht, gucke mir deren Häufigkeiten an und
mache dann für diese Blöcke entsprechend eine Kodierung.
Formal kann man das halt zu einem neuen induzierten Homomorphismus
erweitern, indem ich mir halt Wörter der fixen Länge B aus dem
Alphabet hernehme und dieser Homomorphismus, dieser induzierte
Homomorphismus dann von Wörtern der Länge B abbildet nach Wörtern aus
dem Alphabet Groß B.
Also wichtig, Hoffman Codes, kürzester möglicher Präfix freier Code.
Gibt einen Algorithmus, wie man diesen Baum bestimmen kann und was
dann halt B-Zip und G-Zip noch machen ist, halt die Magie ist da drin,
wie lang mache ich die Länge des Blockes, zum Beispiel habe ich noch
irgendwelche Heuristiken und natürlich auch die ganzen
Verwaltungsinformationen.
Wenn ich eine beliebige Datei mit G-Zip kodiere, dann muss ich
natürlich auch den Code, den ich jetzt verwendet habe, irgendwie mit
übertragen, mit abspeichern in der Datei, damit ich, wenn ich
hinterher dekodiere, entsprechend diese Tabelle des Codes vorliegen
habe.
Das muss also zum Beispiel rein in die Datei.
Oder ich muss halt auch irgendwie kodieren, wann ist sozusagen das,
was ich dekodieren soll in der Datei, diese Nutzlast, wann ist die zu
Ende.
Und da ist zum Beispiel bei G-Zip, wenn ich das richtig weiß, 0
terminiert.
Das heißt, wenn nur Nullen kommen, irgendwo am Ende, dann ist dieser
Code vorbei.
Und solche Sachen gibt es da halt.
Da kann man lustige Sachen mitmachen.
Insbesondere kann man dann Huffman-Codes finden, die dann halt
Primzahlen entsprechen.
Und dann kann man Dateien als Primzahl kodieren und lauter verrückte
Sachen, die man damit auch noch machen kann.
Nur damit es in so eine Größenordnung kam, wenn man sowas in G-Zip, so
wie in G-Zip der Huffman-Code implementiert ist, mit der Blocklänge,
die die verwenden und so weiter und so fort.
Wenn man das so als auf durchschnittlich geschriebenen Text anwendet
und man dann jetzt nicht die, zum Beispiel ASCII-Zeichen mit 8 oder 7
Bit fixer Länge kodiert, sondern diesen Huffman-Code berechnet, ist
Kompressionsverhältnis so Pi mal Daumen ungefähr 1 zu 10.
Das heißt, Sie können mit der Präfix freier Code dieser Datei mit
hinterher nur ungefähr die Größe 1 Zehntel haben, der ursprünglichen
naiven Kodierung, wenn man immer Codes gleicher Länge verwendet.
Wir verlassen jetzt mal zur Abwechslung so ein bisschen im Bereich der
theoretischen Informatik.
Und wir gehen jetzt in den 20-Prozent-Teil der technischen Informatik,
den Sie hier in der Vorlesung auch bekommen werden.
Sie werden noch hinterher in Rechnerorganisationen und in technischer
Informatik 1 entsprechend das Ganze noch vertieft kennenlernen, aber
hier lernen Sie so ein bisschen die Grundlagen kennen, also so die
abstrakten Konzepte, die Sie dann mehr und mehr ausarbeiten werden.
Und weil es halt Grundbegriff der Informatik ist, so ein bisschen
werden wir natürlich immer noch den Verweis machen auf die
theoretische Informatik.
Aber Sie werden auch sehen, dass Sie auch hier das Ganze
praxisrelevant anwenden wollen, wenn Sie nämlich hinterher echt
anfangen wollen, echte Rechner zusammenzusetzen.
Und wir machen Informationsverarbeitung.
Das heißt, wir verarbeiten Daten und Sie hatten schon gesehen, eines
am Anfang der Vorlesung, Sie haben Nachrichten, die Sie persistent
machen, entweder persistent in der Zeit oder persistent über die
Strecke hinweg, über die Distanz hinweg.
Das eine war die Übertragung, das andere war die Speicherung.
Und damit Sie Daten speichern können, brauchen Sie jetzt erstmal
irgendwie einen Speicher, in dem Sie Daten ablegen können.
Und wenn Sie Speicher, irgendwelche Sachen ablegen wollen und
speichern wollen, dann müssen Sie als erstes wissen, wie groß ist das
überhaupt, was ich im Speicher ablege.
Da kommt dann der Begriff Bit und Byte zum Beispiel ins Spiel.
Sie alle haben ja sicherlich wahrscheinlich schon mal einen Rechner
gekauft und haben auch geguckt, wie viel Hauptspeicher der hat.
Und allgemein, wenn Sie jetzt so Daten abspeichern im Binärsystem, so
wie das im Rechner gemacht wird, einer bestimmten Länge, dann können
Sie ja sicherlich angeben, was so da die Größenordnungen sind.
Und wenn ich so 8 Bit zusammensetze, was für eine Größe hat das?
Das ist ein Byte, das kennen wir noch.
Wenn ich jetzt 1024 Bytes habe, wie nenne ich das Ganze?
Noch mal laut, ein Kilobyte.
Und wie nennen Sie sowas, wenn Sie 1024 Kilobyte haben?
Und was nennen Sie 1024 Megabyte?
Und 1024 Gigabyte?
Und 1024 Terabyte?
Und 1024 Petabyte?
Und 1024 Exabyte?
Und wissen Sie sowas?
Sie haben alle keine Ahnung.
Wären Sie in den USA und würden so Ihren Speicher angeben, Ihnen würde
das letzte Hemd weggeklagt.
Sie wären ein armer Mann, wenn Sie eine Firma hätten und so und so
viel sagen, hier 1024 Gigabyte, 1024 Byte ist ein Kilobyte.
Sie wären ein armer Mann, Ihnen würde man den Hintern wegklagen.
Warum?
Weil das nämlich nicht stimmt.
Also, das Bit besteht aus den Zeichen 0 und 1.
Da werden Sie noch ganz viel hören.
Und wenn man heute 8 Bits zusammennimmt, dann nennt man das ein Byte.
Früher hat man das nicht Byte genannt, früher hat man das ein Oktett
genannt.
Und es gibt halt Abkürzungen für einen Bit.
Schreibt man direkt Bit hin.
Manchmal sieht man B, aber B ist halt blöd, weil das eigentlich schon
eine bestimmte Flächeneinheit benutzt.
Für das Byte nimmt man das große B.
Abfall hat eigentlich auch schon eine andere Bedeutung, ist eigentlich
ein Bell, aber nun gut, die Informatik hat sich halt durchgesetzt und
für das Oktett nehmen wir das kleine O.
Und jetzt kommen die Größenpräfixe, wenn wir in größere Räume
reingehen.
Also, früher gab es Hauptspeicher, der war sehr klein, da wenn man ein
paar hundert Bits hatte, war das gut.
Heute hat man, da konnte man das ganze noch in Bytes angeben und zwar
ohne irgendeinen Präfix zu verwenden, das war so klein.
Heutzutage haben Sie Hauptspeicher, der ist sowas wie 2 auf 32 Bytes
hoch und Festplatten, die haben sowas wie eine Milliarde, muss ich
aufpassen, eine Trilliarde, Moment, eine Trilliarde Bytes.
Wie groß ist das, eine Trilliarde Bytes?
Und welches Präfix verwenden Sie?
Verwendet für Ihr Festplattenhersteller.
Der sagt, das ist ein Terabyte, wenn das eine Trilliarde, habe ich es
richtig, das müsste eine Trilliarde sein, oder?
Ist das nur eine Milliarde?
Ne, Moment.
Das sind tausend, das ist die Million, das wäre die Mehrheit, ist das
keine Trilliarde?
Das ist Trillionen, ja Entschuldigung, das ist eine Trillionen, mein
Fehler.
Genau und dann sehen Sie schon den Unterschied, bei den Festplatten,
da nimmt man keine Zweierpotenzen und dann ist das wirklich sowas wie
ein Terabyte und Gigabyte und Megabyte.
Wenn man Zweierpotenzen hat, dann nimmt man was anderes.
Warum hatte man da mit Kilobyte und so weiter angefangen?
Naja, das kommt eigentlich aus dem Dezimalsystem, da hatte man zum
Beispiel für Meter gibt es den Kilometer und dann für Sekunden gibt es
die Mikrosekunde, bei Leistungseinheiten gab es dann halt Megawatt,
Gigawatt, Terawatt und so weiter, aber das basiert alles auf dem
Zehner -Logarithmus, also auf Größenordnungen, die mit Zehnerpotenzen
ansteigen.
Das sind also, das ist die Tabelle bei den Zehnerpotenzen und die
nehmen wir halt fälschlicherweise immer auch für die Zweierpotenzen,
aber eigentlich darf man es nicht.
Es gibt eine Norm, die das festlegt und es ist eigentlich auch
wichtig, dass man das unterscheidet.
Das hier ist das Ganze nochmal für die Zehnerpotenzen aufgeschlagen,
also vorne geht das halt immer, wird das immer kleiner,
Millimikronanopikofemtoato und entsprechend wird es immer größer, bei
1000 fängt es mit Kilo an, Mega, Giga, Tera, Peta, Hexa und mehr weiß
ich leider auch nicht.
Und dann kann man natürlich dann noch so Scherzsachen machen, dass man
die Sachen zusammensetzt.
Zum Beispiel gibt es dann so eine Längeneinheit, die heißt ein
Atopasec, das ist die von dem Herrn Worsch, die Lieblingseinheit, gibt
auch andere, die finden das ganz nett.
Kann sich irgendeiner was unter einem Atopasec vorstellen?
Wo sind die Physiker?
Die sind natürlich jetzt rausgelaufen, das ist doof.
Wer weiß, was ein Pasec ist?
Genau,
das ist also die Einheit, eine astronomische Einheit.
Jetzt muss man wissen, was eine astronomische Einheit ist, das machen
wir gleich.
Die astronomische Einheit, wenn man jetzt guckt, dass die Erde
sozusagen um eine astronomische Einheit sich verschoben hat, dann kann
man sich den Winkel anschauen von dem entfernten Planeten und unter
welchem Winkel sich sozusagen das Ganze dann verschoben hat.
Und zwar auf dieser, naja, Kreisbahn ist es ja nicht, Ellipse ist es,
also der Winkel, den man hat, der hat sich dann um eine Bogensekunde
verschoben.
Wenn man halt eine astronomische Einheit ist und dann muss man, damit
man das so sieht, halt entsprechend ein Pasec weit sein.
Astronomische Einheit ist der mittlere Abstand der Erde von der Sonne,
richtig?
Genau, das ist dann die astronomische Einheit.
Kann man sich ungefähr vorstellen, wenn man das jetzt mal in Metern
oder so ausdrückt, was so ein Pasec ist?
Pasecs sind gerade ungefähr 3 x 10 und 18 Meter, ist also sehr lang.
3 x 10 und 18 Zentimeter, Entschuldigung, 3 x 18 Zentimeter, das ist
ungefähr ein Pasec.
Wenn man dann ein Atopasec hat und das jetzt in Zentimeter umrechnen,
dann muss man halt Ato, das ist 10 hoch minus 18 mal 10 hoch 18 Meter,
dann sind also drei, das ist also ein Atopasec, wenn das Pasec 3 x 10
hoch 18 Zentimeter sind, dann ist ein Atopasec so ungefähr 3
Zentimeter.
Oder, wenn man es halt amerikanisch ausrechnet, das sind so Pi mal
Daumen ungefähr einen Inch.
Und deswegen finden die Leute das halt lustig, statt Inches so etwas
wie Atopasecs zu nehmen.
Das ist wahrscheinlich so ein Schelden-Cooper-Humor.
Bei den binären Größen haben wir, damit man das unterscheiden kann,
haben wir halt eigentlich offiziell andere Präfixe.
Das sind dann die Binary-Präfixe.
Es gibt also ein Kilo-Binary, es gibt ein Mega-Binary, ein Terra
-Binary und so weiter und so fort.
Und die kürzt man dann halt ab und das ist natürlich lustig, Kibi,
Mibi, Gibi und so weiter.
Nur streng genommen sollte das eigentlich theoretisch die Einheit
sein, mit der man gemäß des offiziellen Standards der International
Electronical Commission die Größen angeben soll.
Und wenn ich Ihnen sage, in den USA klagt man Ihnen dafür den Hintern
weg, dann ist das kein Scherz, sondern das ist passiert.
Da hat nämlich jemand sich beschwert, dass halt auf seiner Festplatte
steht, was weiß ich, die kann 50 Gigabyte damals und die hat halt
gesagt, Gigabyte, das ist doch das zur Basis 2 und hinterher war das
aber zur Basis 10 und dann gibt es halt große Gerichtsverfahren und
das hat man glaube ich sogar out of court sich dann geeinigt, also
außergerichtlich sich geeinigt.
Da sind dann irgendwelche unbekannten Geldzahlungen, Geldflüsse
gewesen, wahrscheinlich sehr viel Geld, damit die Klugscheißer, die da
den Prozess angezettelt haben, endlich die Klappe halten.
Und damit das halt nicht mehr passiert, hat man halt jetzt
sicherheitshalber diese Einheiten, mit der man eigentlich
Speichergrößen angeben kann.
Das heißt, als nächstes müssten Sie dann den RAM-Hersteller verklagen.
Nur da wird es halt schwierig, weil wenn der RAM-Hersteller sagt, er
hat so viel Gigabyte, aber er meint in Wirklichkeit binary Gigabyte,
Gigi, Gibi, dann hat er Ihnen mehr gegeben, als Sie eigentlich gedacht
hätten, was er Ihnen gegeben hat.
Dann wird es schwierig, da auf Schadensersatz zu klagen.
Also, Sie halten fest, Sie kennen das Bit, das Byte, Sie kennen die
offiziellen Binary-Prefixes für Größen und Sie kennen auch den
Unterschied zwischen dem Zehner- und dem Binary-System.
Und wenn Ihnen einer was von RAM in Gigabyte erzählt, wissen Sie, dass
das nicht notwendigerweise unbedingt die gleiche Größe sein muss, als
wenn Sie eine Festplatte in einer bestimmten Gigabyte-Terabyte-Größe
kaufen.
Gut, was ist jetzt für uns formal gesehen ein Speicher?
Ein Speicher ist für uns rein formal gesehen am Ende nichts anderes
als eine Abbildung oder andersherum, also das Ergebnis einer
Abbildung.
Viele unterschiedliche Speicherzustände ergeben hinterher eine Menge.
Was wir brauchen, wir brauchen also den, irgendwie müssen wir einen
Formalismus haben für diesen Speicher selber, der Werte aufnimmt.
Wir müssen irgendwie in der Lage sein, Werte aus dem Speicher
rauszulesen und wir müssen irgendwie in der Lage sein, einzelne Werte
in den Speicher reinzuschreiben.
Und das müssen wir irgendwie formal hinschreiben.
Jetzt könnte man sagen, warum, um Gottes Willen, müssen wir das denn
jetzt bitte schön formal hinschreiben?
Das soll einfach gebaut werden und Hauptsache, es funktioniert.
So Spezifikationen haben halt immer den Vorteil, wenn ich testen
möchte, ob das, was ich gebaut habe, auch so funktioniert, wie ich das
gerne hätte, dann ist es gut, wenn ich mal sauber hingeschrieben habe,
wie ist das denn bitteschön?
Also, wir brauchen Formalismen, damit wir testen können.
Wenn wir testen können, dann kann man so Testfälle sich erdenken.
Dann kann man so Szenarien feststellen, von denen man weiß, was das
Ergebnis sein muss.
Und dann kann man diese Testfälle abdecken.
Wenn jetzt die Testfälle alle positiv durchlaufen, dann weiß ich
leider noch nicht, ob ich es richtig gemacht habe.
Ich weiß nur, dass es für diese speziellen Testfälle funktioniert.
Wenn ich die Testfälle aber geschickt wähle, dann kann ich zumindest
grobe Fehler, so typische Fehler finden.
Wenn nämlich dann ein Testfall fehlschlägt, dann weiß ich zumindest,
dass es falsch ist.
Das heißt, durch solche Testfälle kann ich, wenn ein Testfall
fehlschlägt, zumindest feststellen, ob etwas falsch ist.
Und wenn man etwas formal hinschreibt, dann denkt man manchmal auch
ein bisschen nach und kann zum Beispiel Lücken in dem, wie man es sich
überlegt hat, dass man das macht, finden.
Und zum Beispiel für die Semantik von Programmiersprachen ist das sehr
wichtig, dass man sowas formal hinschreibt, dass man hinterher auch
einen Kompilierer finden kann, der das auch sauber und ordentlich
macht und jedes beliebige Programm auch richtig entsprechend passt und
das übersetzt in ein Programm, das das macht, was Sie auch wollen.
Sie üben funktionales Denken, das ist als Informatiker nie schlecht.
Wie stellen wir uns jetzt einen Speicher vor?
Für einen Speicher können wir uns mental so eine Tabelle aufbauen.
In der Tabelle gibt es Adressen und an einer Adresse steht ein
bestimmter Wert.
Jetzt kann man sich das so vorstellen als Tabelle.
Jede Zeile ist eine Adresse.
Ich könnte zum Beispiel die Zeilen durchnummerieren als Adresswert und
in der Tabelle steht ein Wert drin, den ich nachschlage.
Das sieht dann so aus.
Also links alle Adressen, zum Beispiel die Zeilen von 1 bis Anzahl der
Zeilen durchgezählt und rechts die Werte, die da drin stehen dürfen.
Häufig sind das natürlich Bitfolgen, da wir binär rechnen.
Also links Adressen als Bitfolgen, rechts die Werte, die wir eintragen
und in der Regel sind das auch Bitfolgen spezieller Länge.
Das heißt, ich habe links Bitfolgen endlicher spezieller Länge, ich
habe rechts Bitfolgen endlicher Länge.
Das bedeutet nichts anderes, als dass die Länge der Bitfolgen, die ich
links bei den Adressen mir eintrage, bestimmt, wie viele Zeilen ich
überhaupt in der Tabelle haben darf.
Bestimmt mir letztendlich die Größe des Speichers.
Im Sinne von, wie viele Werte kann ich abspeichern.
Und rechts, das sagt mir, wie groß kann der Wert maximal sozusagen
werden, den ich abspeichern kann.
Wie viele unterschiedliche Werte kann ich an einer Adresse
abspeichern.
Und wenn man dann sozusagen nimmt, Menge der möglichen Adressen mal
Menge der möglichen Werte, die ich pro Adresse abspeichern kann und
das Ganze in Bit entsprechend rechnet, dann kann man daraus die Größe
eines Speichers halt auf Binary in binärer Schreibweise
niederschreiben.
Wenn man jetzt einen Speicher formalisiert, dann ist ein Speicher
selber ja so eine Tabelle und so eine Tabelle ist eine Abbildung.
Ich bilde ab von der Menge der Adresse in die Menge der Werte.
Also wenn ich zum Beispiel einen Speicher mit vier Binary Gigabytes
habe, also Gigabinary Bytes, dann heißt, kann das zum Beispiel so
sein, dass ich von den Adressen, die aus 0 und 1 bestehen und die
Länge 32 haben, abbilde auf Werte, die zum Beispiel 8 binäre Zeichen
lang sein können.
Das sind dann also entsprechend 8 Bit oder auch 1 Byte abgebildet auf
8 Bit lang.
Das heißt genau Bytes und dann entsprechend mit den Adressen komme ich
dann auf den Speicher.
Ein Speicher ist in einem bestimmten Zustand.
Diese Abbildung, die ich da definiert habe, ist ein bestimmter Zustand
des Speichers.
Ich habe bestimmte Werte in irgendwelchen Adressen abgelegt und ich
kann jetzt zum Beispiel die Werte auslesen.
Also ich kann zum Beispiel mir anschauen, was ist der Wert an einer
bestimmten Adresse.
Das heißt, die Menge Adressen ist jetzt in diesem Modell des Speichers
prinzipiell fest und meistens, wenn man das in Silikon, in Silizium
gießt, in Silikon wäre interessant, das mal zu gießen.
Das wäre eine echte Herausforderung.
Also wenn man das in Silizium gießt, dann hat meistens sogar dieser
Tabelleneintrag einen physikalischen Ort.
Der ist da irgendwo fest, irgendwo auf einer kleinen Fläche im
Speicher vorhanden.
Man kann das jetzt analog sehen zu sowas wie zum Beispiel
Straßenadressen, wobei da die Analogie auch nur so und so weit geht.
Wenn ich also jetzt lesen will, muss ich mir wieder eine Abbildung
definieren und diese Abbildung nenne ich Memoried.
Und was diese Abbildung macht, die bildet halt ab von diesem Tupel
Memory und Adresse und bildet ab in die Menge aller Werte.
Also Memory und Adresse in die Menge aller Werte.
Und jetzt aufgepasst, hier passiert nämlich was Interessantes.
Da steht, bildet ab aus dem kathesischen Produkt von Mem und Adresse.
Mem sei der Speicher.
Was war der Speicher nochmal?
Der Speicher ist eine Abbildung.
Das heißt, ich habe hier ein Tupel aus einer Abbildung und einer
Adresse und bilde das ab auf einen Wert.
Ist mir aber egal, ich darf auch Abbildungen als Mengenwerte nehmen,
als etwas aus dem ich Tupel bilden kann.
Das heißt also formal, dieser Memory ist ein bestimmter
Speicherzustand und dieser Speicherzustand ist formal eine Abbildung.
Und die wird halt entsprechend abgebildet.
Und diese Abbildung selber, dieses MemRead, bildet ab von der Menge
aller Abbildungen, von Adresse, Menge aller Abbildungen, Memory, die
über so eine Adresse definiert sind, zu dem Wert.
Also ist kein Problem, weil wir können uns so eine Abbildung jederzeit
als Tabelle denken und deshalb ist das kein Problem, das als irgendwie
in Mengenform zu gießen.
Und jetzt kommt die Notation, die Ihnen mal gefehlt hatte, wo ich
gesagt hatte, hier müssten Sie alle schreien.
Diese Notation kennen wir noch nicht.
Wenn wir uns die Menge aller Abbildungen von einer Menge A nach B
anschauen, dann notieren wir uns das als B hoch A.
Das ist das, was Sie damals schon hatten.
Das haben wir auch an einer Stelle gebraucht, dass wir die Menge aller
Abbildungen uns angeschaut haben.
Da ein bisschen kontraintuitiv ist immer die Reihenfolge.
B hoch A ist also nicht die Menge aller Abbildungen von B nach A,
sondern die Menge aller Abbildungen von A nach B.
Bei endlichen Mengen kann man jetzt für die Kardinalität der Menge
aller Abbildungen sich entsprechend hernehmen, dass das Kardinalität
von B hoch Kardinalität von A ist.
Dementsprechend kann man auch ein Memory als allgemein beschreiben als
die Menge aller möglichen Abbildungen von Adressen auf Werten.
Das heißt also Memory bildet ab von Val hoch Adress, kathesisches
Produkt mit Adressen, in die Menge Val.
Also ein Speicher, eine Abbildung M zusammen mit einer Adresse wird
abgebildet auf den Wert dieser Abbildung an der Adresse A.
Umgekehrt will ich natürlich nicht nur aus dem Speicher lesen, ich
will auch in den Speicher schreiben können.
Und das ist ein wenig komplizierter.
Ich brauche also eine Abbildung, wo ich erstmal einen Speicher habe,
der irgendwie in einem bestimmten Zustand ist.
Dann brauche ich eine Adresse und dann brauche ich den Wert, den ich
an diese neue Adresse schreiben will.
Deshalb ist also die Menge, aus der ich abbilde, dieses kathesische
Produkt, aus Menge aller möglichen Speicher, aller möglichen Adressen
und aller möglichen Werte.
Und was herauskommt, ist wieder ein neuer Memory.
Also wieder eine neue Funktion, die von den Adressen auf die Werte
abbildet.
Das ist halt ein neuer, also ein Memory, ein Zustand, eine Tabelle M,
wird halt abgebildet auf eine neue Tabelle M'.
Und zwar in der Form, dass der Wert, wenn ich, oder andersrum, und
zwar in der Form, dass wenn ich eine beliebige Adresse auslese aus
diesem neuen Speicher, ich an der Stelle, wo ich was Neues geschrieben
habe, das Neue rausbekomme und an allen anderen Adressen das wieder
rausbekomme, was vorher schon im Speicher drin stand.
Das ist das hier.
Nichts anderes ist das hier formal hingeschrieben.
Kann man dann also auch wieder kürzer schreiben.
Und jetzt wird es ein bisschen kompliziert.
Also die Abbildung, Ziel- und Definitionsbereich bleibt gleich.
Aber dieses Typel aus Speicher, Adresse, neuer Wert wird halt
abgebildet wieder auf eine Abbildung.
Nämlich auf die Abbildung, die halt sagt, dass jede beliebige Adresse
A' in diesem neuen Speicher, in dieser neuen Abbildung, das ja das
Ergebnis des Speicherns, des Schreibens ist, dass halt entweder der
neue Wert ausgelesen wird an dieser neuen Adresse oder halt die alten
Werte an allen anderen Adressen ausgelesen werden.
Und wenn Sie sowas jetzt halt formal hinschreiben, dann können Sie das
einem Hardwarebauer geben und er baut Ihnen halt einen Speicher, der
das genau macht.
Das Ganze ist die Frage, ist das plausibel?
Macht das Sinn, so das Schreiben hinzudefinieren?
Ja, kommt drauf an.
Wenn Sie an einfachen Hauptspeicher denken, also konzeptionell
Hauptspeicher, dann ist das durchaus plausibel und sinnvoll.
Macht ja Sinn.
Wenn ich meinen Hauptspeicher, welchen Wert reinschreibe, dann sollen
ja die anderen Werte sich bitteschön nicht ändern, weil die will ich
ja später vielleicht noch mal haben und ich muss die ja auch
wiederfinden und die müssten entsprechend an ihren alten Adressen
liegen.
Es gibt aber halt noch andere Speicher, die anders sind.
Einfaches Beispiel, ein Cache.
Ein Cache soll halt dazu dienen, dass man schon mal in einem schnellen
Speicher Werte drin stehen hat, die man vielleicht in nächster Zeit
brauchen könnte.
Also man geht davon aus, meistens hat man irgendwo einen großen
langsamen Speicher, so einen Hauptspeicher und der Prozessor, der
liest halt Werte aus und verarbeitet die und dieses übertragen aus dem
Speicher zum Prozessor, also diese Funktion Memoid, die kostet halt
Zeit.
Das ist häufig eine Sache, die bremst den aus.
Der Prozessor, der ist ratta ratta ratta fast, schnell und der
Speicher, der ist langsam.
Also was macht man?
Man nimmt sich schnelleren Speicher her.
Schnellerer Speicher ist teuer, also hat man nicht so viel schnelleren
Speicher, wie man langsamen Hauptspeicher hat, aber man schaltet
diesen schnelleren Speicher zwischen Hauptspeicher und Prozessor und
das nennt man ein Cache.
Und die Frage ist jetzt, was soll in dem Cache drinstehen?
Es kann nicht alles drinstehen, was im Hauptspeicher ist.
Es ist kleiner.
Und das zum Beispiel, was in diesem Cache drinstehen soll, das soll
vielleicht davon abhängen, was ich als Letztes geschrieben habe.
Es kann auch davon abhängen, was ich als Letztes gelesen habe.
Es kann aber auch davon abhängen, was ich als Letztes geschrieben
habe.
Das heißt, die Werte in diesem Cache, das was in dem Cache drin ist,
die sollen sich halt ständig ändern, abhängig davon, was ich so in
letzter Zeit geschrieben oder gelesen habe.
Und dann gibt es auch noch eine andere Art von Speicher, die anders
funktioniert, die nicht so funktioniert wie diese Tabellenform,
sondern wo ich auf Dinge zugreifen will, nicht über Adressen, sondern
über Werte, die im Speicher abgelegt sind.
Das nennt man dann einen Assoziativspeicher, associative memory.
Das heißt, ich habe irgendwie einen Wert, von dem ich weiß, dass er im
Speicher liest und über diesen Wert adressiere ich andere Werte, die
im Speicher liegen.
Und zwar die Werte, die mit diesem Wert assoziiert sind.
Das ist zum Beispiel so etwas, wie das menschliche Gehirn das häufig
macht.
Wir haben häufig einen assoziativen Speicher, dass wir für bedingte
Dinge, für bestimmte Sachen, die wir im Speicher ablegen, uns
irgendwie andere Sachen damit assoziiert haben, die damit
zusammenhängen und die wir dann über, indem ich an das eine denke, das
andere abrufen kann.
Und sowas gibt es entsprechend auch vermehrt in neuen
Rechnerarchitekturen, dass man mit assoziativen Speichern arbeitet.
Insbesondere, wenn man hinterher mit neuronalen Rechnern arbeitet, ist
der assoziative Speicher interessant.
Also, was ist das Wesentliche an Speichern?
Das Wesentliche an Speichern ist, dass das, was ich abspeichere, ich
auch wieder rausholen kann.
Das ist im Prinzip das Gleiche.
Das heißt, wenn ich also reinschreibe in den Speicher und wieder
auslese, dann soll das wieder rauskommen.
Und für alles andere soll das andere rauskommen.
Und das ist gerade so bei Caches und assoziativen Speichern eben nicht
der Fall.
Das will ich nicht.
Mit dieser Spezifizierung kann man jetzt halt Testfälle organisieren.
Mit dieser Spezifikation kann man jetzt Sachen wirklich in Hardware
gießen, sodass sie sich so verhalten, wie die Spezifikation das ist.
Und man kann auf die Art und Weise auch die Bedeutung von Programmen
hinterher festlegen.
Also, was ist wichtig?
Das sollten Sie mitnehmen.
Es gibt Hauptspeicher.
Für das, was wir hier in der Vorlesung machen, stellen wir Ihnen uns
vor als eine Tabelle.
Das ist rein formal eine Abbildung.
Adressen sind in dieser Abbildung immer so etwas wie physikalische
Koordinaten.
Außer Sie haben sowas wie ein Cache oder haben etwas anderes, dann ist
es anders.
Aber bei uns sind das immer physikalische Koordinaten.
Und Sie wissen jetzt, dass man Abbildungen, also Speicher ist eine
Abbildung und man schreibt rein, dann kriegt man eine neue Abbildung.
Sie wissen jetzt, dass man Abbildungen auf Abbildungen auch abbilden
kann.
Dass also der Begriff von Definitions- und Zielbereich viel weiter
gefasst ist, als einfach so aus Mengen, die mit irgendwelchen
einzelnen Objekten da enthalten, die man irgendwie hinschreiben kann.
Gut, und damit wäre es das für heute.