Okay, herzlich willkommen zur Vorlesung heute.
Heute fängt der letzte Teil der Vorlesung an und dieser Teil geht über
Informationstheorie.
Und genau, Informationstheorie hat drei Anwendungsgebiete.
Erstmal die Quell-Kodierung, dann die Kanal-Kodierung und dann hat es
Anwendungen und die Kryptographie.
Die Quell-Kodierung, da ist das Ziel, gegeben haben wir in der
Informationstheorie immer eine Quelle, die Ereignisse produziert mit
einer gewissen Wahrscheinlichkeit und die wollen wir übertragen oder
die wollen wir dann erstmal kodieren, diese Ereignisse.
Und in der Quell-Kodierung, da wollen wir die Redundanz verringern und
das heißt, die Hauptaufgabe darin besteht quasi die Daten zu
komprimieren.
Das heißt Datenkompressionen.
Ein aktuelles, das kennt ja jeder, Datenkompressionen, wenn man
irgendwie einen Datenstrom hat oder irgendwie einen Pfeil, dann wollen
wir den wirklich schwindig darstellen.
Dann gibt es noch eine andere, neuere Art von Daten, quasi die
Datenkompressionen und das sind komprimierte Datenstrukturen.
Also werden wir bei der Datenkompressionen ein Pfeil zum Beispiel auf
einmal komprimieren und dann wollen wir da irgendwie auf ein gewisser
Teilbereich zugreifen.
Dann müsste man jetzt traditionell alles wieder dekomprimieren und bei
komprimierten Datenstrukturen, da ist das nicht der Fall, da kann man
immer noch effizient auf ein Teil des Pfeils wieder zugreifen.
Und das wird nur ein geringer Teil der Vorlesung sein, aber das ist
eine interessante Anwendung.
Dann gibt es bei der Kompression verschiedene Arten.
Da gibt es verlustbehaftete und verlustfreie Kompressionen.
Also wenn Sie zum Beispiel an Bildkompressionen denken, da gibt es
Sachen, die das menschliche Auge zum Beispiel, da macht es keinen
Unterschied, ob da noch mehr Bits in einem Pixel kodiert werden.
Das heißt, die kann man weglassen und das heißt, bei manchen Sachen
wie Texte, da wollen wir aber den Text wieder genau original
rekonstruieren.
Das heißt, das ist zum Beispiel ein Beispiel für verlustfreie.
Und das Ganze hat natürlich auch eine hohe wirtschaftliche Bedeutung.
Zum Beispiel, wenn ich Mobilfunk telefoniere und ich kann die Daten
mit weniger Bits darstellen, dann spart man sich die Bandbreite.
Die zweite Themengebiet ist die Kanalkodierung.
Da ist es so, dass man einen Kanal hat, der gestört ist, zum Beispiel
bei Wi-Fi.
Wenn da was übertragen wird, dann gibt es eine gewisse
Wahrscheinlichkeit, dass das Datenpaket nicht ankommt und so weiter.
Oder dass ein Bit falsch ist und das ist ein gestörter Kanal, den kann
man modellieren und durch fehlgelegte Codes kann man das ausgleichen
und da wollen wir Beispiele kennenlernen.
Und das letzte Feld ist dann in der Kryptografie.
Mit diesen Konzepten, die wir kennenlernen werden, also wie Entropie,
kann man die Sicherheit eines Kryptosystems modellieren und kann da
Aussagen darüber machen.
Das Material für die Vorlesungen sind die Vorlesungsfolien und das
Buch Information und Kodierung von Martin Werner.
Das ist auch über das Uninetz bei Springer Online verfügbar.
Die ersten zwei Teile sind größtenteils aus diesem Buch.
Okay, also fangen wir an, das zu modellieren.
Also die Informationstheorie, die kommt von Claude Shannon, geboren
1916.
Also es ist quasi eine hundertjährige Jubiläum von Claude Shannon
dieses Jahr und der hat es 1948 das erste mal formalisiert, was
Information ist und so weiter.
Also wie gesagt, wir haben erstmal eine Menge von Zeichen und die wird
emittiert von der Quelle mit einer gewissen Wahrscheinlichkeit.
Also man denkt sich vielleicht ein Alphabet von 1 bis N und jedes wird
mit der Wahrscheinlichkeit von PI emittiert.
Und wir können quasi diese Informationsquelle X, kann man auch dann
als Wahrscheinlichkeit, als Zufallsvariable auffassen.
Also ein Beispiel, zum Beispiel ein Würfel, ein fairer Würfel, idealer
Würfel, der genau mit einem Sechstel jede Zahl produziert.
Und da ist der Erkenntnisgewinn nach einmal Würfeln ziemlich groß,
weil das ist genau ein Sechstel.
Das heißt, ich kann jetzt nicht sagen, ob es eine Zahl, also
normalerweise kommt eine Zahl nicht öfters vor.
Das heißt, alles ist gleich verteilt.
Es wird genau mit einem Sechstel geworfen und dann kann man nicht
irgendwie sagen, eine Zahl wird es wahrscheinlich öfters vorkommen.
Wenn ich einen Würfel habe, der gezinkt ist, wo eine Zahl, sagen wir
mal, mit der Wahrscheinlichkeit ein Halb geworfen wird, weil man da
irgendwie ein Gewicht hingemacht hat, dann ist die Wahrscheinlichkeit
zum Beispiel hier in dem Beispiel ein Halb.
Dann kann man mit hoher Wahrscheinlichkeit sagen, mit der
Wahrscheinlichkeit, dass ein Halb kommt, kommt die 1 zum Beispiel.
Das heißt, der Erkenntnisgewinn da ist kleiner.
Und jetzt will man ein Maß, der jetzt diese Information, die man
kriegt, misst.
Also man will was, das sagt ja, wenn irgendwas, also erstmal soll die
Information nicht nicht negativ sein, das heißt, wenn ich ein Ereignis
habe, dann soll das immer größer gleich 0 sein, das Informationsmaß.
Wenn ich ein sicheres Ereignis habe, als zum Beispiel eine Münze, die
immer auf eine Seite fällt, dann erhalte ich keine neue Information,
weil ich weiß ja vorher, auf welche Seite die fällt.
Das heißt, dieses Informationsmaß für ein sicheres Ereignis P1 gleich
1, das soll 0 sein.
So und eine kleinere Änderung der Wahrscheinlichkeit, also wenn das
von 1 auf 0,999 geht, soll auch nur eine kleine Änderung der
Wahrscheinlichkeit sein, das heißt, das Informationsmaß soll auch
stetig sein, die Funktion.
So und eine weitere Eigenschaft, die das Informationsmaß so füllen
soll, ist, dass wenn ich eine Zeichenkette, die doppelt so lang ist,
habe, dann soll die Information auch doppelt so groß sein.
Das heißt, wenn ich sage, ich habe zwei Ereignisse, P1 und P2, dann
soll die Information der multiplizierten Wahrscheinlichkeiten addiert
sein.
Und genau, wenn die unabhängig sind, dann ist das eben genau die
Summe.
So und eine Funktion, die all diese Bedingungen erfüllt, ist die
Logarithmusfunktion.
Und zwar log von 1 durch die Wahrscheinlichkeit.
So und das nennt man das, das ist unser Informationsmaß, das man
nimmt.
Und im Folgenden, wenn wir immer das zu Basis b gleich 2 machen, dass
wir das Ganze in Bits eingeben, in Binary Digits.
Genau, hier eine kleine Wiederholung, weil das wir jetzt brauchen,
über die Rechenregeln der Logarithmen, also das heißt, wenn ich zwei
Wahrscheinlichkeiten habe, xy und ich multipliziere die im
Logarithmus, dann ist es eine Addition der zwei Einzellogarithmen.
Der Kehrwert kriegt man, indem man das Fahrzeug herumdreht und dann,
was man auch öfters braucht, ist der Basiswechsel.
Also wenn ich einen Logarithmus habe zur Basis b und will einen
Umwandler zur Basis a, dann kann ich einfach durch den Logarithmus von
a zur Basis b teilen, dann kommt das raus.
Es ist ganz einfach, wie man das herleitet.
Man kann einfach das x schreiben als b hoch, als a, das x kann man
schreiben als a hoch, Logarithmus a zu x und dann kann man das
herleiten.
Und dann eine ganz wichtige Umgleichung, die da gilt für den
Logarithmus, ist, dass der natürliche Logarithmus hier von x kleiner
ist als x-1 oder jetzt in diesem Beispiel auf der Folie, da ist es der
Logarithmus 2.
Da müssen wir diese Umgleichung multiplizieren mit Log e von 2.
Das heißt, da kriegt man gerade so eine Gerade mit Log e von 2
Steigungen und die tangiert genau diese Logarithmuskurve im Punkt 1.0.
Genau,
dann zum Beispiel, wenn man jetzt eine Münze hat und das ist eine
faire Münze, das heißt jede Wahrscheinlichkeit tritt auf, jedes
Ereignis, also Gruppe oder Zahl, tritt auf mit Wahrscheinlichkeit 1,5.
Dann wäre der Informationsgewinn, der Logarithmus durch die
Wahrscheinlichkeit 1,5, wäre ein Logarithmus von 2 und das wäre gleich
1.
Und wenn man dieses Experiment, und diese Experimente sind unabhängig,
wiederholt, dann kann man hier aufsummieren über das Zeug und das
heißt, dann kriegt man Log 2 hoch K, was dann quasi K-Bits an die
Information ist, die man immerhin kriegt.
Jetzt wissen wir, was Information ist und über die Information kann
man jetzt die Entropie definieren und die Entropie ist eben genau das
mittlere Informationsgehalt pro Zeichen, das man rauskriegt aus der
Quelle.
Das heißt, nimmt man alle Ereignisse, die von der Quelle emittiert
werden und bildet da die Summe.
Das Log 2, 1 durch Px, das ist jetzt genau die Information und Px, das
ist genau die Wahrscheinlichkeit, dass ich diese Information erhalte.
Und das heißt, da gibt es jetzt natürlich Randfälle, also wenn man
hier Ereignisse hat, die zum Beispiel nie auftreten, dann kriegt man
hier die Wahrscheinlichkeit 0 und da kann man sich definieren, dass es
unendlich ist oder für den Fall, dass ich einen Logarhythmus von 0
habe, dann wird man das auch als 0 definieren, um diesen Randfall
abzudecken.
Das heißt, aber sonst gilt natürlich immer, dass die Entropie größer
ist als 0, weil das hier ist auf jeden Fall kleiner 1, weil die
Wahrscheinlichkeit, dass alle auch verdient gleich 1 sind, ist eine
Einzelwahrscheinlichkeit kleiner 1.
Das heißt, der Kehrwert ist also größer 1 und der Logarhythmus wird
positiv ab 1 und das Px ist auch 1.
Das heißt, es wird maximal, das wird so eine Übung, wenn alle
Ereignisse gleich verteilt sind, also wenn ich n Ereignisse habe und
jeweils habe ich eine Wahrscheinlichkeit von 1 nach n, dann habe ich
hier also 1 nach n und summiere über alle n Ereignisse auf 1 nach n,
dann wird das Log von n.
Das ist die maximale Entropie.
Wenn man dann z.B.
sagt, man hat einen Text mit 26 Buchstaben, dann ist die maximale
Entropie, also wenn alle gleich verteilt sind, jeder Buchstabe tritt
gleich oft auf, dann kriegt man da Log 26 zu Basis 2, was 4,7 ist.
Wenn man jetzt aber eine Verteilung hat, wie z.B.
in der deutschen Sprache, wenn man deutsche Texte analysiert, da die
Buchstabe zählt und die Wahrscheinlichkeit dann berechnet, dann kriegt
man was kleineres, also 4,1.
Das heißt, wenn man Zufall Sex hat, kriege ich einen höheren
Informationsgewinn, als wenn ich jetzt in der deutschen Sprache bin.
Und es ist natürlich auch so, dass man hier jetzt quasi
Einzelwahrscheinlichkeiten angeschaut hat von Buchstaben.
Wenn man jetzt Buchstabe Paare oder Buchstabe Triple nimmt, dann nimmt
es noch ab und ist eher in der Realität so bei zwei Bits pro Zeichen,
die man da einen Informationsgewinn hat.
So, wie sieht es aus bei einer Münze?
Die Entropie, also hier ist die Wahrscheinlichkeit, dass ich z.B.
Zahl erhalte.
Wenn die Wahrscheinlichkeit 0 ist, dass ich Zahl erhalte, dann ist
auch meine Entropie 0 und die nimmt dann immer zu, je fairer die Münze
wird.
Und wenn sie fair ist, also bei 0,5 Wahrscheinlichkeit, ist das
maximal.
Da ist es 1, wie gesagt, und dann nimmt es wieder ab, die
Entropiefunktion.
So, und genau, jetzt wollen wir natürlich, wenn wir die Informationen,
die Ereignisse wollen wir jetzt möglichst platzeffizient codieren.
Also was man wollte, ist ein Code für die Ereignisse, sodass die
mittlere Codelänge minimal wird.
Das heißt, jedes Zeichen, das ich da kriege aus der Quelle, dieses
Zeichen i, will ich jetzt ein Codewort zuordnen.
Das nennt man z i und das kommt aber aus dem Alphabet 01 Stern.
Und genau, und da wollen wir das minimieren.
Okay, und für sowas kann man einen Prefix-Code verwenden.
Das heißt, einen Prefix-Code kann man dann darstellen, also wenn ich
ein Alphabet habe mit Endzeichen, dann kann ich das darstellen als
Binärbaum.
Also hier in dem Beispiel habe ich acht Zeichen, a, b bis h und wenn
ich jetzt, dann kann ich jedes Zeichen, habe ich jetzt, brauche ich
jetzt diesen Binärbaum drüber.
Das heißt, ich fasse, genau, ich ordne, also ich kann das Alphabet
einteilen in zwei Hälfte, von a bis d und e bis h und alles, was in
der ersten Hälfte liegt, fängt mit 0 an und alles, was in der zweiten
Hälfte liegt, mit 1.
Und dann kann ich das so rekursiv weitermachen.
Also ich habe das Alphabet, wo nur das Subalphabet, wo a, b drin
liegt, das fängt dann mit 0 an und das mache ich so lang, bis ich an
einem, dass das Subalphabet die Größe 1 hat.
Und genau, und dann kriege ich diesen Codierungsbaum und die
Kantebeschriftung, die gibt mir dann an, den Code dieses Zeichens, das
dann am Blatt steht.
Und in dem Beispiel hat jedes Codewort oder jedes Zeichen hat ein
Codewort gleicher Länge, genau der Logarithmus von der Einzahl
Zeichen.
Also Beispiel, wenn ich zum c kommen will, muss ich erst die Ende von
0, 0 verfolgen, dann 1 und dann 0 oder f.
Das liegt in der zweiten Alphabet Hälfte, also muss ich 1, 0, 1 nehmen
oder das letzte Zeichen wird durch den Pfad 1, 1, 1 codiert.
Genau,
so die Tiefe eines Knotens ist einfach der kürzeste Weg, also ich
schaue mir einfach ein bestimmtes Symbol an, z.B.
d und der kürzeste Weg von der Wurzel zu dem Blatt, das nennt man die
Tiefe dieses Knotens.
Okay, und die mittlere, genau wenn ich jetzt die Quelle betrachte, die
dann diese Symbole emittiert, dann mit Wahrscheinlichkeit Pi, dann ist
aber die mittlere Codewortlänge genau definiert durch die
Wahrscheinlichkeit mal die Codewortlänge ni, die ich da für das Symbol
kriege und das aufsummiert über alle Codewörter.
Heißt hier das ni entspricht der Tiefe dieses Blattes in dem Baum.
In dem Beispiel hat man quasi das so gewählt, dass jedes Zeichen, also
wenn man es annimmt, jedes Zeichen wird mit 1 durch Anzahl Zeichen,
also 1 durch 8 emittiert, dann kriegt man diesen Baum und die mittlere
Codewortlänge ist dann 3.
Das ist hier ganz einfach.
Wenn ich jetzt da 1 weiter runtergehe in dem Codewortbaum, dann eine
Ebene, dann kann ich natürlich doppelt so viele Zeichen darstellen und
wenn ich ein Alphabet habe, das Sigma-Symbole hat, dann kann ich
natürlich mit Log Sigma viele aufgerundete Bits, das ist dann die
Tiefe, die ich brauche, um alle die Sigma-Symbole darzustellen und das
heißt also, ich kann jedes Ereignis dann mit höchstens Log Sigma
aufgerundete Bits darstellen.
Aber das ist jetzt noch gar nicht so interessant, weil wenn wir jetzt
eine Quelle haben, die ein Symbol besonders häufig emittiert, dann ist
dieses Verfahren, dass man jedes Zeichen mit der gleichen
Codewortlänge darstellt, nicht optimal.
Das heißt, interessant ist es jetzt was optimales zu finden und da
sind die Codes in variabler Länge, abhängend von der
Wahrscheinlichkeit.
Das heißt, was man sucht, ist so ein Codewortbaum und wenn man so
einen Codewortbaum hat, dann ist dieser Code, der da entsteht,
automatisch ein Präfix-Code.
Das heißt, wenn ich zwei Codeworte habe, dann ist kein Codewort ein
Präfix eines anderen Codewortes.
Das heißt, die Codeworte sind immer an Blättern repräsentiert und
nicht in inneren Noten.
Das heißt, man braucht dann auch keine Trennzeichen, wenn man so einen
Code hat.
Man fängt an, den String zu dekodieren, von links nach rechts, den man
mit diesen kokanäten Codeworten hat.
Das heißt, man startet an der Wurzel von dem Codewortbaum und wenn man
dann runter navigiert und an der Wurzel, an einem Blatt angelangt,
dann hat man ein Zeichen dekodiert und man geht wieder rauf zur Wurzel
und startet es von Neuem.
Jetzt gibt es natürlich auch Codes, wie zum Beispiel der Morse Code,
wo jeder Buchstaben durch kurz oder langes Zeichen kodiert ist.
Das bekannteste ist wahrscheinlich das SOS.
Das S wird durch drei kurze, das O durch drei lange Signale kodiert
und da gibt es aber Doppeldeutigkeit.
Also wenn ich einen String habe, der zum Beispiel A heißt, dann wird
es durch kurz und lang kodiert, aber das kann auch heißen E, was kurz
ist und T ist lang.
Das heißt, man braucht dann ein Trennzeichen und dieses Trennzeichen,
das brauchen wir bei Prefix Codes nicht, weil da kann man jeweils am
Ende des Codewortes entscheiden, dass es zu Ende ist.
Also eindeutig dekodierbar.
Und jetzt gibt es einen Zusammenhang zwischen der Entropie und, also
jetzt kann man zeigen, dass man gute Codes erstellen kann.
Das heißt, wenn man so eine Quelle hat und dargestellt als eine
Zufallsvariable, die das Zeug emittiert und die Entropie dieser
Zufallsquelle ist H von X, wie wir das vorher gesehen haben, dann
existiert ein Prefixcode für unsere X, für unsere Quelle mit dem Code
-Alphabet.
Das Code-Alphabet ist quasi der Verzweigungsgrad im Baum.
In unserem Fall ist es zwei, aus zwei Zeichen, sodass gilt, dass die
mittlere Codewortlänge für den Prefixcode N, also N' liegt aber genau
zwischen der Entropie und Entropie plus 1.
In der Vorlesung haben wir immer den Fall, dass dieser Codewortbaum
binär ist, betrachtet und die Verallgemeinerung nach D ist dann
eigentlich ganz einfach, wenn man das so betrachtet.
Das kommt auch im Buch, kann man das auch dann mit D machen.
Das wollen wir schnell beweisen und da braucht man dazu die kraftsche
Ungleichung, die sagt, dass wenn man ein binärer Prefixcode hat, mit K
-Codewörtern und Längen N1 bis Nk, dann ist es notwendig, dass diese
kraftsche Ungleichung erfüllt ist.
Und die sagt, dass wenn man das aufsummiert über 2 hoch minus die
Codewortlänge, also 1,5 hoch die Codewortlänge, dass das kleiner sein
soll als 1.
Wie sieht man das?
Wenn man diesen Codewortbaum betrachtet, auf der eigenen Ebene, dann
kann es da, weil er binär ist, 2 hoch i Knoten geben.
Und wenn ich, das schauen wir uns das Bild an, auf der nächsten Folie,
das hier die Ebene 0, 1, 2, 3, 4 und das heißt ja auf jeder Ebene, auf
erster Ebene gibt es 2, dann gibt es 4 Knoten, 8 und so weiter.
Und wenn ich jetzt einen Knoten habe, dann gibt es, also zum Beispiel
hier, für diesen Knoten auf Ebene 2 und mein maximales Codewort ist
auf Ebene n,
also n sei meine maximale Tiefe, dann blockiert mir dieser Knoten auf
Ebene i, blockiert mir genau n minus i, also 2 hoch n minus i viele
Knoten.
Das heißt, dieser hier, Satz 1, der blockiert dann 2 auf der nächsten
Ebene und Ebene 4 auf der übernächsten, auf der Plattebene.
Und jeder Codewortbaum liefert auch einen Präfixcode.
Und was man machen könnte, ist, dass man auch diese Codewortlängen,
die können wir nach Größe ordnen, also n1 sei die kleinste
Codewortgröße und bis nk und das alles aufsummiert.
Das gibt n und jetzt fällt mir auf, dass ich die Tiefe anders benennen
soll als n.
Sag mal irgendwie t.
Ah nein, okay, nein, also das ist ja die Codelänge, die Codewortlänge,
n1 bis nk die Ordnung und das nk hat dann die maximale, also n.
Und jetzt jedes Codewort zi, das spart genau, also wie wir gesehen
haben, 2 hoch n minus ni Blattnoten.
Und alle Codeworte, die die Blattnoten sparen, diese Blattnoten, die
gespart werden, sind disjunkt.
Das heißt, ich kann aufsummieren über alle Blattnoten, über alle
Codeworte, die spart genau 2n minus nk viele, die Summe darüber.
So viele Blätter sind gespart.
Wie viele Blätter gibt es da in diesem Baum?
Da gibt es höchstens 2n viele Blätter.
Und das heißt, ich kann auch höchstens 2n viele Sparer.
Das heißt, wenn ich das aufsummiere, dann muss es kleiner als 2n sein.
Das heißt, wenn ich jetzt also mit 2 hoch n dividiere, dann komme ich
hier genau auf die kraftliche Ungleichung.
Das kann man dann auch noch verallgemeinern auf eindeutig dekodierbare
Codes.
Unser Präfixcode ist ein Beispiel von eindeutig dekodierbar, aber da
gibt es noch mehr.
Das kann man auch zeigen, wird aber dann ein bisschen länger.
Das heißt, das lassen wir hier mal weg.
Das brauchen wir nicht unbedingt.
Und jetzt wollen wir diese zwei Seiten dieses Theorems zeigen.
Also einmal die linke Seite.
Ich will zeigen, dass die Entropie eine untere Schanke ist für die
mittlere Codewortlänge.
Naja, da kann man jetzt die Definition einsetzen von der Entropie.
Das war ja die Summe über die Wahrscheinlichkeiten.
Also PK mal der Log des Inversions von der Wahrscheinlichkeit.
Also 1 Codewortlänge.
Die nehmen wir da ab.
Und die Codewortlänge, also hier, dann klemmen wir PK aus.
Genau, das NK, die Codewortlänge, das ziehen wir in den Logarithmus
rein.
Und um das wieder auszugleichen, wenn man das in den Logarithmus
reinzieht, schreibt man dann einfach 2 hoch.
Und genau, das hat man abgezogen.
Also war das unter und dann steht es wieder oben.
Das heißt, steht dann dran PK mal Log 2 hoch minus NK durch PK.
Und jetzt benutzt man diese Ungleichung, die wir vorher gesehen haben.
Also der Logarithmus X kleiner ist als X minus 1 mal den Log E zur
Basis 2.
Also das ist nur eine Konstante, die ist jetzt nicht weiter wichtig.
Das heißt, also dieses da, können wir jetzt mit der Abschätzung.
Der Logarithmus fällt jetzt weg.
Das heißt, aus diesem 2 hoch minus NK PK im Logarithmus, heißt das
jetzt PK mal 2 hoch minus NK durch PK minus 1.
Dann kann man sich das PK wieder wegkürzen.
Und das heißt, hier steht dann wieder die kraftsche Ungleichung.
Und das ist dann also kleiner gleich 1.
Und diese PKs, das sind die Wahrscheinlichkeiten über alle K, über
alle Codewörter addiert sich dann, oder über alle Zeichen, die da
emittiert werden, summiert sich auch zu 1.
Und das erste ist also kleiner gleich 1 und das zweite 1.
Das heißt, das ist immer kleiner gleich 0.
Und somit haben wir diese linke Seite gezeigt.
Das heißt, wir sind dann immer größer mit als die Entropie.
Die zweite Sache ist dann die Abschätzung nach oben.
Das heißt, hier gilt die kraftsche Ungleichung und es existiert auch
ein Code, der das erfüllt.
Und wir sind immer noch frei, wie man die Codewortlänge wählt, solange
die Gleichung gilt.
Und wenn man das einfach so wählt, dass die Codewortlänge eigentlich
immer kleiner ist als die Wahrscheinlichkeit,
dann wird die immer noch erfüllt.
Und das heißt, wenn man das so macht und dann aber das Codewort um 1
verkleinert, also NK minus 1 nimmt, dann gilt,
dass das PK kleiner ist als 2 hoch 1 NK plus 1.
Und wenn man jetzt beide Seiten betrachtet, modifiziert mit Log von
PK, dann steht genau das dran, PK mal Log PK.
Genau, das logarithmiert man auf die zwei Seiten.
Also einmal der Log von PK und einmal der Log 2 von diesem da.
Und wir modifizieren das mit PK auf beiden Seiten.
Genau, dann kriegt man PK mal Log PK.
Und auf der Seite kriegt man das minus NK plus 1 mal PK.
Also steht dann NK mal PK.
Das ist dann gerade die durchschnittliche Länge plus PK.
Und das summiert man jetzt wieder auf über alle Codewörter.
Genau, dann kriegt man die durchschnittliche Länge.
Die PK alliert sich wieder zu 1 und das heißt, hier habe ich jetzt
wieder die Entropie und dann kriegt man wieder raus, dass die mittlere
Codewortlänge, genau, die Entropie nach oben abgeschöpft werden kann
mit der Entropie plus 1.
Und jetzt ist die Frage, jetzt wollen wir also so einen Präfixcode
bestimmen, der diese mittlere Codewortlänge minimiert.
Und da hat sich Claude Shannon und Fano Gedanken gemacht, wie man das
macht.
Ein Verfahren ist dann die Shannon-Fano-Codierung.
Das heißt, hier machen wir das so, jetzt haben wir die
Wahrscheinlichkeit aller Elemente.
Also in dem Beispiel haben wir 0,15 und 0,13 und so weiter.
Jetzt wollen wir es so aufteilen, ein Ereignis mit größerer
Wahrscheinlichkeit, sollen ein kleineres Codewort kriegen.
Und die Methode, die hier verwendet wird, ist, dass man das jetzt
partitioniert, diese Elemente.
Man summiert, man bildet die Präfixsumme dieser Wahrscheinlichkeiten
von oben.
Also man zählt 0,1591, dann 1,388 dazu und so weiter.
Und ich weiß, alles insgesamt ist 1.
Das heißt, ich gehe so weit, bis die Präfixsumme oder die Differenz
zwischen diesen zwei Partitionen, die ich hier zeige, minimal wird,
also nah an 0,5 ist.
Und dann ordne ich jedem, also als Codewort ordne ich jedem Zeichen
aus der ersten Hälfte eine 0 zu und aus der zweiten Hälfte eine 1.
Und das kann man rekursiv weitermachen.
Also ich kann jetzt hier bei Element meine erste Partitionierung kann
ich beibehalten.
Und jetzt habe ich aber dann die erste Hälfte, die eine gewisse
Wahrscheinlichkeit hat.
Und da partitioniere ich wieder so, dass die aufsummierte
Wahrscheinlichkeit wieder in zwei ungefähr gleich große Teile verlegt
wird.
Also so Teile, dass die Differenz maximal ist zwischen den zwei Teilen
und ordne im zweiten Bit entweder 0 oder 1 zu.
Das machen wir dann wieder rekursiv, hier auch.
Und wenn man dann noch mehr Schritte macht, dann hat man hier diese
Codes.
Also das ist nochmal der Algorithmus, den man dazu verwendet.
Das ist eigentlich nur was ich beschrieben habe.
Da gehen wir uns nicht näher darauf ein.
Was aber wichtig zu wissen ist, das ist der Codewort Baum, der da
erzeugt wurde durch diesen Algorithmus.
Aber leider ist es so, dass dieser Algorithmus, der liefert nicht der
optimale Code.
Es gibt Beispiele, da kann man einen besseren Codewort Baum
generieren.
Und dieser optimale Algorithmus, das ist der Huffman Algorithmus, der
die Huffman Codierung erzeugt.
Diese Art der Erzeugung, das war eher so top-down.
Also man hat die Wahrscheinlichkeiten aufsummiert und dann immer in
gleiche Partitionen teilen wollen.
Und Huffman macht das bottom-up.
Also ich habe diese Wahrscheinlichkeiten wieder summiert.
Ich habe sie vorliegen als einzelne Wahrscheinlichkeiten und habe die
wieder sortiert.
Und Huffman geht so vor, dass man immer die zwei kleinsten
Wahrscheinlichkeiten nimmt.
Also 0,05 in diesem Fall, das A und das C.
Das wird zusammengefasst als 0,1.
Dann der Teilbaum konstruiert.
Also mit der 0 gehe ich zum A, mit dem C gehe ich zu 1.
Und dann machen wir das rekursiv weiter.
Oder so machen wir das quasi weiter mit dem verkleinerten Alphabet.
Ich habe jetzt ein neues Metasymbol, das zur Zusammenfassung aus
Symbol A und C ist, das mit Wahrscheinlichkeit 0,1 vorkommt.
Und das wird dann wieder zusammengefasst.
Also die zwei Kleinsten sind 0,15 und 0,1.
Die wird wieder zusammengefasst zu 0,25.
Und jetzt sind die nächsten zwei Kleinsten 0,15 und 0,2.
Es gibt dann ein Metasymbol mit Wahrscheinlichkeit 0,35.
Und jetzt die zwei Kleinsten Wahrscheinlichkeiten hier wieder ist 0,25
und 3,5 wird zusammengefasst.
Und im letzten Schritt, wenn das aufhört, dann 0,4 und 0,6.
Das heißt, das ist eine andere Art, den Kotbaum zu generieren und
diese Art, den zu generieren, ist optimal.
Genau, also hier nochmal wieder ein Beispiel, wie man das ablesen
muss.
Das haben wir im vorherigen Kotbaum ja schon gesehen.
Das ist mit dem Zeichen D.
Das wird durch die Kante 1 erreicht von der Wurzel und es ist jetzt 0
,1 und 0.
Das ist der Algorithmus.
Man kann da zum Beispiel eine Priority Queue nehmen, um dann die
Wahrscheinlichkeiten darzustellen oder um die Ordnung, um die zwei
Kleinsten Elemente zu extrahieren, kann man das in der Priority Queue
speichern, dieses Symbol und mit der Wahrscheinlichkeit.
Das geht aber auch besser, wenn das vorher schon sortiert ist, dann
kann man das auch in linearer Zeit machen.
Durch einen Algorithmus, der drei Passes macht, über diesen Eingabe
-Array, der sortiert mit gegebenen Wahrscheinlichkeiten, wenn die
sortiert vorliegen und das geht auch sogar in place.
Aber das ist quasi dieser Algorithmus, den ich jetzt gerade
beschrieben habe.
Und dass das optimal ist und dass das das optimale Kotbaum ist, das
wollen wir jetzt schnell beweisen.
Also ich habe die Wahrscheinlichkeiten und jetzt sage ich, dieser
Huffman -Algorithmus berechnet mir der Baum mit minimaler mittlerer
Kotwartlänge.
Und um das zu beweisen, braucht man ein vorbereitetes Lemma und das
sagt mir, dass sich die zwei Symbole, also die zwei Symbole, die am
unwahrscheinlichsten auftauchen, sei das X und Y,
dann haben diese zwei Symbole X und Y den gleichen Vaterknoten oder
älteren Knoten.
Das geht relativ einfach.
Ich habe diesen Kotwartbaum für mein Alphabet mit den
Wahrscheinlichkeiten.
Dann nehme ich mir jetzt diese zwei Knoten raus, die den Zeichen mit
den gleichen Wahrscheinlichkeiten sprechen.
Also X und Y und genau, das heißt das T-Strich.
Das T-Strich wäre jetzt einfach mein beliebiger Kodierungsbaum, wo das
drin ist und wir können das einfach mal annehmen, dass die Tiefe von
dem Knoten X, dass die größer ist als die von Y.
Also hier in dem Bild sieht man das.
Und jetzt sagen wir, dass das Z sei das Vaterknoten von X.
Jetzt machen wir mal ein paar Fallunterscheidungen.
Also Fall 1 ist, dass das Z nur X als Nachkomme hat, also nicht Y.
Genau, dann könnten wir jetzt einfach mal, wenn es quasi nur ein
Nachkomme hat, dann kann man einfach Z löschen.
Und dann hätte unser Kotbaum die mittlere Kotwartlänge.
In dem Kotbaum wäre dann X kleiner.
Also der hat ja kein anderes Kind.
Das heißt, unser X wäre durch ein Bit mehr kodiert in diesem Fall, als
es eigentlich bräuchte.
Durch löschen von X geht es weg.
Also das heißt, es widerspricht der Optimalität von dem T-Strich und
das haben wir angekommen.
Gut, das heißt jetzt wissen wir, dass das Z hat also mindestens zwei
Nachfahren.
Und jetzt sei W, sei es ein Nachfahre von Z, mit maximaler Tiefe.
Das heißt, das ist hier ein Blatt.
Und genau, was ich jetzt machen könnte, ich könnte, weil die
Wahrscheinlichkeit von W,
weil T optimal ist, heißt eigentlich, dass W eine geringere
Wahrscheinlichkeit haben müsste als X.
Dass dieser Baum optimal ist, weil sonst habe ich ja, wenn W eine
größere Wahrscheinlichkeit hätte, dann hätte ich da einen längeren
Code zugeordnet.
Das heißt, das kann nicht auftreten.
Das heißt, ich muss das X und das W tauschen, um einen optimalen Baum
zu kriegen.
Das heißt, also jetzt ist es so, dass das Z genau zwei Nachfahre hat
und das X ist einer davon.
Und jetzt sei das der andere Nachfahre, sei Q.
Und Q hat jetzt eine größere Wahrscheinlichkeit als unser Y.
Und das heißt, wenn ich P und Y tausche, dann wäre das ein besserer
Baum.
Das heißt, dann ist der erst optimale Baum.
Das heißt, es muss so sein, dass Z, X und Y benachbart sind.
Das heißt, dieses Lemma, das brauchen wir jetzt in dem Beweis.
Also da nimmt man Induktion über die Einzahlzeichen.
Für ein Zeichen gilt natürlich, dass dieser Safman Baum optimal ist.
Jetzt wissen wir schon, die Induktionsvoraussetzung ist, dass für das
Alphabet mit Endzeichen das Ganze optimal ist.
Und jetzt geben wir ein Zeichen weiter.
Das fügt man hinzu.
Und die mittlere Kotwortlänge dieses Baumes, die nennen wir f und t.
Wobei ich dann quasi wieder die Wahrscheinlichkeit für jedes Zeichen
mit der Tiefe.
Das ist die mittlere Tiefe.
Jetzt haben wir zwei Bäume.
Einmal den Hafman Baum und den Baum der T-Opt, wo die mittlere
Baumtiefe noch besser sein soll als in unserem Hafman Baum.
Jetzt können wir dieses vorbereitende Lemma anwenden.
Das heißt, ich habe jetzt diese zwei Kodierungsbäume, T-Opt und T-Haf.
Und wir wissen, dass die zwei Elemente mit kleinster
Wahrscheinlichkeit, dass die auf tiefster Ebene sind und ein
gemeinsames Faderknoten hat.
Das heißt,
die Situation ist wie in dieser Darstellung abgebildet.
Sowohl im T-Opt als auch im T-Haf muss X und Y gemeinsam liegen.
Wenn man diese zwei löscht und den Faderknoten vereinigt, wird es
reduziert auf diese Bäume T-Opt und T-Haf.
Das ist also der Baum, der entsteht, wenn das zusammengefasst ist.
Und da gilt jetzt, dass der Hafman Baum, da ist die mittlere
Kodwartlänge, die passen wir jetzt an, da wird dieses X, das wird
rausgenommen, auch dieses Y und dann wird dieser Knoten Z hinzugefügt.
Das heißt also, unser Hafman Baum kriegt eine mittlere Kodwartlänge.
Das T- von Haf wird quasi in den PX und PY abgezogen und das gleiche
gilt auch für unseren optimalen Baum.
Das würde bedeuten, dass dieser optimale Baum, also T-Opt, dass der
ein besserer Kodierungsbaum gewesen wäre, als unser Hafman Baum mit
einem weniger nach Induktionsvoraussetzung, das quasi ein Widerspruch
zur Induktionsvoraussetzung ist.
Es heißt, dieser Hafman Baum oder dieser Hafman Algorithmus erzeugt
uns einen optimalen Kod, was ganz schön ist.
Jetzt gibt es aber auch Nachteile in diesem Verfahren.
Also wenn ich dann erst meine Zeichen bekomme und dann natürlich
umwandeln muss in Kodworte, dann muss ich das über den Baum machen und
dann gibt es Verzögerungen.
Durch die Kompression, die ich da bekomme, reduziere ich die Redudenz.
Das heißt, ich werde auch fehlanfälliger.
Um das Verfahren durchzuführen, brauche ich dann erstmal die
Wahrscheinlichkeit.
Das heißt, wenn ich meinen Text habe, muss ich erst über den ganzen
Text drüberlaufen, um die Wahrscheinlichkeit zu berechnen.
Das heißt, es ist ein statisches Verfahren.
Es gibt auch adaptive Verfahren.
Das heißt, man schaut sich Blöcke an und dann macht man das für einen
Block.
Dann gibt es aber auch andere Kodierungsverfahren, wie zum Beispiel
Lempel -Zif.
Also wenn zum Beispiel Gzip verwendet wird, da ist ein Lempel-Zif
implementiert.
Das heißt, das macht eine andere Kompression mit Rückverweise.
Wenn man einen Text hat und da kam schon mal ein Substring vor, dann
macht man Rückverweis auf diesen vorherigen Substring.
Das sind aber andere Verfahren, die es da gibt.
Jetzt gibt es natürlich auch Alphabete.
Also hier das war eine Alphabetgröße 6.
Dann kriegt man aber statt Block von 6 aufgerundet, was 3 wäre, kriegt
man hier eine mittlere Kodwortlänge, die geringer ist, wenn man das
ausrechnet.
Und genau, wenn man jetzt ein Alphabet hat, das selber nur zwei
Zeichen hat, also zum Beispiel schwarzes Bit und weißes Bit, dann
kriegt man einen Code, der aber dann quasi das 0 Bit und das 1 Bit
zuweist.
Das ist immer noch, wie man gesehen hat, von der Entropie höchstens 1
entfernt.
Also wenn man jetzt zum Beispiel einen Fax hat und man hat irgendwie
einen Schwarzungsgrad von 15 Prozent, dann kann man die Entropie
ausrechnen.
Das gibt 0,61.
Das heißt, mein Code, den ich da kriege, mein Huffman Code, der wird
dem schwarzen Bit eine 0 und dem weißen Bit eine 1 zuordnen.
Das heißt, das wäre immer noch in dem Bereich, also Entropie plus 1.
Also hätte ich dann 1,61 Bit, wäre die obere Schränke und mein Huffman
Code produziert mir eine mittlere Kodwortlänge von 1.
Aber das ist natürlich sehr schlecht, weil ich will ja näher in diese
Entropie hin und darum kann man dann auch einfach mehrere Zeichen
zusammenfassen.
Also in dem Beispiel sagen wir mal zwei.
Ich fasse zwei Zeichen zusammen.
Also ich betrachte zwei Bildpunkte.
Also einmal weiß-weiß, weiß-schwarz, schwarz-weiß und schwarz-schwarz.
Und dann kriege ich eine andere Wahrscheinlichkeitsverteilung.
Das hier ist es nicht gleich mit der Wahrscheinlichkeitsverteilung,
weil da ist der Schwärzungsgrad 15 Prozent.
Hier in dem Beispiel wäre der Schwärzungsgrad 30 Prozent.
Aber kann man quasi auch so machen, dass diese Verteilung auch 15
Prozent Schwärzungsgrad wäre.
Und dann kann man hier wieder einen Huffman Code zuordnen und dann
kommt man doch näher an die Entropie an.
Man kriegt erstmal für diese Verteilung natürlich eine größere
Entropie, weil da gehen wir über vier Ereignisse.
Und das ist auch die Entropie für ein Alphabet über die Größe zwei.
Und das heißt, wenn man das pro Einzeichen betrachtet, muss man das
natürlich wieder durch die Anzahl an zusammengefassten Zeichen teilen.
Also das teilt man dann wieder durch zwei.
Und hier in dem Beispiel kriegt man hier eine Entropie raus von
ungefähr 1,7 für die 1,74 für diese Verteilung.
Und wenn man das dann durch zwei teilt, also das pro Zeichen
betrachtet, kriegt man 0,88 raus.
Was heißt, dass ich dann näher an 0,16 wieder dran bin.
Das heißt, je mehr man zusammenfasst, umso näher kann man dann auch an
diese 0,61 ankommen.
Und eine spezielle Sache, die man da machen kann, ist, also jetzt
haben wir quasi Blöcke zusammengefasst, Fixerlänge.
Was man aber machen kann, ist variable Länge.
Das heißt, eine Lauflängenkodierung.
Das heißt, hier ist aber die Idee, dass man dann sagt, ich habe diese
Sequenz an weiß-schwarze Ereignissen, weiß-weiß-schwarz und so weiter.
Und jetzt kann man das kodieren, indem man sagt, ja also ich fasse,
ich sage jetzt es kommen drei weiße, dann kommt ein schwarzes, dann
kommen zwei weiße und dann kommt ein schwarzes.
Das heißt, ein Run besteht aus Ereignissen, wie oft weiß vorkommt und
dann schwarz.
Also dreimal, zweimal, hier kommt dann gleich ein schwarzes, das heißt
null mal weiß, also null.
Das heißt, ich kriege da eine neue Folge.
Und das heißt, jetzt statt dieses Originalbild zu kodieren, kodiere
ich jetzt einfach diese Lauflängen.
Das heißt, man könnte es auch, genau, da muss man eben auch die
Wahrscheinlichkeiten wissen.
Wenn man eine endliche Quelle hat, dann kann man die natürlich
bestimmen, aber man kann es auch einfach modellieren.
Also in dem Beispiel wäre es einfach, dass man sagt, man hat eine
geometrische Verteilung, man hat eine Wahrscheinlichkeit, dass ein
schwarzes Pixel kommt, das ist vielleicht 0,2 zum Beispiel und dann
ist die Wahrscheinlichkeit, und wenn das geometrisch ist, sage ich mal
0,8, 0,2 mal 0,8 ist dann die Wahrscheinlichkeit, dass ich einen Run
der Länge 1 habe und 0,8 hoch 2 mal 0,2 ist dann 3 und so weiter.
Das heißt, ich habe hier so eine geometrische Verteilung und da ist
der Erwartungswert 1 durch PS.
Also das ist das Ereignis, die Wahrscheinlichkeit, dass ein schwarzes
Bit kommt.
Und genau, das heißt, im Mittel habe ich da Runs, die haben die Länge
1 durch PS, also in dem Fall, dass ich 0,2 habe als
Wahrscheinlichkeit, habe ich im Mittel 5.
Das heißt, ich kann dann 5 Zeichen auf einmal kodieren.
Jetzt kann ich quasi wieder die Wahrscheinlichkeiten, die ich da
kriege, für diese Runs nehmen und kann darüber einen Code bilden, zum
Beispiel der Shannon-Fano-Code, den wir gesehen haben und kann dann
dieses kodieren.
Und das heißt, insgesamt bin ich dann, und ich glaube, dazu haben wir
eine Übungsabgabe, bin ich dann kleiner, als wenn ich dann einfach
einen Huffman-Code über Blöcke geringer Länge mache.
Also hier zum Beispiel Länge 2.
Das heißt, das wäre jetzt erstmal der Block zu Codes, zu Prefix-Codes.
Und jetzt will ich was zeigen, was diese Datenstrukturen, die ich
erwähnt habe, also diese komprimierte Datenstrukturen.
Da gibt es jetzt zwei, also bisher haben wir irgendwie betrachtet,
dass ich so eine Quelle habe, wo sich Zeichen emittiert mit einer
gewissen Wahrscheinlichkeit und jetzt machen wir das genau.
Jetzt handelt es sich um Objekte.
Also ich habe Objekte, ein kleines Beispiel.
T, das hat eine feste Größe n.
Also ich kann zum Beispiel sagen, ich habe zum Beispiel Bäume der
Größe n oder Fotografen der Größe n oder irgendwie vielleicht auch ein
Bitvektor der Länge n oder ein Vektor der Länge n.
Und da bezeichne ich jetzt mit f t von n, das ist die die Anzahl aller
Objekte, die es da gibt.
Verschiedene Objekte der Länge n.
Und genau, das heißt, wie viele Informationen brauche ich um alle
diese Objekte zu unterscheiden.
Also wenn es f t von n Objekte gibt, um die in Bitstream zu codieren,
brauche ich also Informationen.
Genau, brauche ich quasi den Log, genau den Zweierlog zu dieser
Anzahl.
Das ist quasi die untere Schranke, die ich brauche, um all diese
Objekte zu unterscheiden.
Also das hier z t ist die informationsstellische Schranke, die ich da
habe.
Also wenn ich da drunter gehe, dann kann ich zwei dieser Objekte nicht
mehr unterscheiden.
So genau.
Und jetzt nennt man eine Datenstruktur, nennt man es succinct und
succinct heißt sowas wie kurz, knapp, bündig.
Wenn die Platzkomplexität gerade diese informationsstellische Schranke
ist, in Bits, plus ein sublinearer Term.
Und ich will aber trotzdem noch Operationen effizient darauf
ausführen.
Das heißt, ich will das mit minimalem Platz darstellen und will aber
trotzdem noch Operationen ausführen.
Dieser kleine O von n Term, also dieser sublineare Term, den nennt man
auch der Index Teil.
Das ist so Redundanz.
Das ist, was ich drauf mache, was quasi darüber hinaus geht, um
einfach nur die Objekte zu unterscheiden.
So, genau.
Machen wir ein Beispiel.
Zum Beispiel ein Bitvektor der Länge n.
Also das sind alle Sequenzen der Länge n über binärem Alphabet.
Und ich will zwei Operationen unterstützen.
Eine ist Access, die andere ist Rank.
Access, also ich will einfach den Werten an jeder Stelle zugreifen.
Das ist einfach, wenn man ein Bitvektor einfach so darstellt.
An jeder Stelle ist dann eine 0 oder 1 drin und will das IT zugreifen.
Und ich bin da im RAM-Modell, dann kann ich einfach sagen, ich will
zur Stelle i.
Das ist einfach.
Die zweite Operation ist Rank 1.
Und Rank, das gibt mir die Prefix-Summe aller Bits bis zu einer
bestimmten Position i.
Das heißt, wenn ich einen Bitvektor habe und da steht 0 oder 1 drin,
man kann auch dieses Fax, das wir gerade betrachtet haben, dieses
Faxbild, wo 0 oder 1 drin sind, schwarz oder weiß, kann man auch
betrachten.
Dann habe ich einen Index i und ich will wissen, wie viele schwarze
Pixel sind da bis zu einer gewissen Stelle i.
So, dieser Bitvektor, wie viele verschiedene Instanzen, der lange n
gibt es da, da gibt es genau 2 hoch n.
Das heißt, ich brauche genau 2 hoch n, der Logarithmus davon, also n
Bits an Platz für dieses Objekt.
Das heißt, also das Access kann einfach unterstützt werden mit n
Platz, aber diese Prefix-Summe, wie viele Einser sind gesetzt im
Prefix, das kann man nicht so einfach in konstanter Zeit realisieren.
Also effizient heißt eine konstante Zeit oder Logarithmus-Zeit zu
diesem n.
Also auf keinen Fall linear.
Jetzt gibt es eine Datastruktur, mit der ich das machen kann und das
sind diese Indexstrukturen.
Die sehen folgendermaßen aus.
Also man kann diese Operation, Rank, kann man einfach unterstützen,
wenn man viel Speicherplatz benutzt.
Ich kann zum Beispiel für jede Position i, kann ich mir abspeichern,
das Ergebnis von Rank von i.
Das wäre dann aber, wenn dieser Bitstring n ist, dann heißt, um da die
Prefix -Summe am letzten an n, also b, an letzter Position zu
speichern, kann dieses Ergebnis bis zu n groß sein, wenn alle Bits
gesetzt sind.
Das heißt, ich brauche Log n an Zeichen.
Log n Bits brauche ich, um die Zahl abzuspeichern.
Das heißt, das ist zu viel, weil dann hätte ich insgesamt, wenn ich
das für jede Position mache, hätte ich n mal Log n Bits.
Deshalb gibt es da jetzt so ein Schema.
Das ist ein Zwei-Level-Index.
Das heißt, ich unterteile, das ist mein Bitvektor, und den unterteile
ich erstmal in Blöcke der Länge L1.
Das sind Super-Blöcke.
Die Länge dieser Super-Blöcke wäre Log n Quadrat.
Das heißt, das Logarithmus ist ein Quadrat.
Das erlaubt mir für jeden dieser Blöcke, es gibt n durch L1 viele,
kann ich mir also für jeden dieser Blöcke erlauben, n Bits
abzuspeichern.
Weil dann habe ich insgesamt immer noch n durch L1 mal Log n viele
Bits, die ich dafür brauche.
Und das ist immer noch sublinear, weil ich habe n durch Log n an Bits,
die ich dann für diese Information brauche.
Das ist das P1.
Das speichere ich mit dem Ergebnis ab, bis zu Blockgrenzen.
Das P1 von i ist Rank 1 von i mal L1.
Das heißt, ich kann Rank anfragen, kann ich beantworten bis zu
Blockgrenzen, die also mit L1 Blockgrenzen mit diesen Super-Blöcken.
Das heißt, man kann das jetzt weitermachen.
Und zwar kann man diese Blöcke jetzt nochmal unterteilen in neue
Blöcke der Länge L2.
Und da wählen wir uns eine Blocklänge von 1,5 Log n.
Das heißt, das ist analog.
Also jetzt speichere ich mir auch dieses Ergebnis, Rank 1 mal L2.
Das wäre jetzt aber immer noch groß, wenn ich das so speichern würde.
Und darum mache ich das relativ.
Relativ zum Blockanfang.
Das heißt, wenn ich hier das Ergebnis speichere für den Block mit
diesem L2, dann mache ich das relativ zu dem Rank, das ich hier habe.
Und das heißt, diese Einträge in P2, die sind nie größer als die
Blockgröße von L1.
Weil ich bin ja relativ zu diesem Blockanfang.
Das heißt, was ich hier verbrauche, ist genau Log von L1 viele Bits.
Das heißt, wenn ich dann Log von Log n zum Quadrat habe, dann ist es
genau gleich wie zweimal Log Log n.
Das heißt, für jeden Eintrag da brauche ich zweimal Log Log n.
Das heißt, die Größe dieses Arrays P2, wo ich mir die relativen Counts
abspeichere, ist genau n durch dieses L2.
Das heißt, es ist n durch ein halbes Log n.
Das ist also n durch zweimal Log n.
Also zweimal n durch Log n mal den Platz, den ich brauche, was Log Log
n ist.
Oder zweimal Log Log n.
Das heißt, das Ganze ist dann hier in kleinen O von n.
Weil ich habe ja oben habe ich n mal Log Log n und da habe ich Log n.
Das Log Log n ist kleiner als das Log n.
Das heißt, wenn ich das asymptotisch betrachte, dann ist das in
kleinen O von n.
Das heißt, jetzt können wir alles beantworten bis zu Blockgrenzen.
Also Blockgrenzen im zweiten Level.
Aber was passiert, wenn ich jetzt innerhalb eines Blocks was berechnen
will?
Da kann man jetzt ausnutzen, dass unser Block, dieser Block L2, die
Länge ist so gering, also Log 1 halb n, dass ich mir jetzt... also
alle Möglichkeiten dieser Blöcke, da gibt es nur zwei hoch die
Blocklänge viele Möglichkeiten für solche Bitvektoren.
Und das heißt, wenn ich 2 hoch Log n hoch 1 halb habe, dann entspricht
es gerade der Wurzeln.
Da es so viele verschiedene Bitvektoren gibt.
So und für alle diese Log n viele verschiedene Bitvektoren, die ich da
habe, kann ich dieses Rank innerhalb von diesem kleinen Bitvektor
vorberechnen.
Das heißt, wie viele Möglichkeiten habe ich da?
Ja, ich kann Rank an Position 0, 1, 2 bis L2 berechnen.
Das heißt, ich habe dann Wurzeln mal Log 2.
Das ist die Anzahl Möglichkeiten.
Und wie viel Platz brauche ich, um das Ergebnis abzuspeichern?
Ja, da brauche ich aber genau Log von diesem L2, was Log n hoch 1 halb
war.
So, das heißt, dieses ganze Ding, also meine Tabelle P3, wo ich das
vorberechnet habe, um das für alles vorzuberechnen, das nennt man auch
den 4-Russen-Trick.
Für diese Tabelle, die ist Wurzeln mal Log n hoch 1 halb mal Log Log n
hoch 1 halb.
Die ist auch sublinear.
In der Praxis kann man das sogar so machen, dass wenn das für so einen
kleinen Block ist, das Zählen von einzelnen Bitvektoren, also ein
Computerwort, so klein ist das, das ist halt durch eine CPU-Operation
ist da vorhanden.
Das heißt, das kann man in einem Zyklus auch in verständlicher Zeit
machen.
Das heißt, wenn man dieses Rank jetzt ausrechnen will, dann auch für
ein bestimmtes Position i, dann kann man das einfach dadurch machen,
dass man sagt, ja, ich schaue in welchem Superblock das ist.
Das ist dann, das zeigt man durch dieses L1, da kriegt man die Summe
aller Einzelnen bis zum Superblock.
Dann rechnet man sich aus den Eintrag im kleineren Block, das ist dann
i durch L2.
Und dann braucht man den relativen Index in dem kleinen Block, der
dann nur noch die Länge Log n hoch 1,5 hat.
Und da schaut man dann in der Logup-Table nach, das ist der grüne
Part.
Das heißt, das kann man also in konstanter Zeit ausführen.
Das heißt, diese Operationen, die können wir jetzt mal für Bitvektoren
ausführen.
Und die inverse Operation zu diesem Rank, also zu zählen, wie viele
Einser im Prefix sind, ist Select.
Da frage ich, ich will herausfinden, wo dieses i, die Eins-Bit in dem
Bitvektor gesetzt ist.
Und diese Operation, die kann man auch ähnlich zu dem Schema, das wir
gerade kennengelernt haben, kann man jetzt auch in konstanter Zeit
realisieren.
Und jetzt war das ja noch gar nicht so komprimiert, diese
Datenstruktur, die war nur so gesinkt.
Und wenn ich jetzt eine komprimierte Datenstruktur, der Platz soll
jetzt abhängen von der Entropie über den Text.
Das heißt aber, diesen Bitvektor, den ich gerade vorgestellt habe, den
kann man jetzt verwenden, um so eine komprimierte Datenstruktur
herzustellen.
Das heißt, jetzt nehmen wir hier so eine Sequenz, wieder über ein
Alphabet, der Größe Sigma.
Und jetzt ist es so, dass bisher die Entropie, die war ja immer mit
der Wahrscheinlichkeit über die Zufallsvariable definiert.
Und die kann man jetzt, wenn man statisch einen vorliegenden Text hat,
dann kann man natürlich die Einzahl vorkommen, einen Zeichen, kann man
natürlich zählen.
Das heißt, für den Buchstabe C, sei jetzt NC die Anzahl an Vorkommen
von Buchstabe C.
Und dann kann man sich die Wahrscheinlichkeit ausrechnen, indem man
sagt, das ist NC durch N.
Und dann ergibt sich für die Entropie in dem Fall, das ist ja die
empirische Entropie, nennt man das in dem Gebiet.
Und das 0, das deutet an, dass ich da hier einfach einen Kontext habe
von 0.
Also ich betrachte nur die Wahrscheinlichkeit von Buchstaben, ohne
dass ich da irgendwie den Buchstabe irgendwie in einem gewissen
Kontext sehe.
Also es gibt eine Verallgemeinerung, da ist das HK, da hängt das ab
von K-Buchstaben, die ich vormal im aktuellen Buchstabe betrachte.
Da kriegt man kleinere Werte.
Das heißt, das entspricht eigentlich dieser Entropie, die wir
kennengelernt haben, nur empirisch.
Und jetzt eine komprimierte Datenstruktur, die wird jetzt
repräsentiert aber durch, die soll Platz haben, N mal die Entropie von
dieser Sequenz plus diesen kleinen Indexteil.
Und eine der wichtigsten komprimierten Datenstrukturen ist der
sogenannte Wafer Tree.
Und der hat es ganz viel gemeinsam mit den Konzepten, die wir vorher
schon kennengelernt haben, nämlich mit dem Kotbaum.
Also erstmal, was kann diese Datenstruktur?
Also ich habe eine Sequenz gegeben und jetzt will ich für die Sequenz
zwei oder auch drei Operationen anbieten.
Also ich will den Zugriff auf das ID-Symbol erlauben und effizient und
ich will diese Rank-Funktion effizient realisieren.
Das heißt, das Rank ist jetzt eben, vorher war das die Anzahl Einser
im Präfix vom Bitvektor und jetzt ist das die Anzahl ein Vorkommen von
Symbol C im Präfix des Bitvektors.
Und der Wafer Tree, der ist aber definiert, indem man sagt, man nimmt
für die Symbole, erstellt ein Präfix-Code, einen Baum, der hat dann
die Topologie dieses Präfix-Baums und jetzt in jedem Knoten speichere
ich mir, also hier haben wir ein Beispiel, in jedem Knoten speichere
ich mir, also im Wurzelknoten speichere ich mir alle Symbole, die in
der Sequenz vorkommen.
Also ich speichere mir die Sequenz selber.
So und jetzt wird die Sequenz aufgeteilt in zwei Teilsequenzen und
zwar in der ersten Teilsequenz sind, das ist hier das linke Kind, sind
alle Symbole, deren Codewort mit 0 startet und in der zweiten Hälfte
alle, die mit 1 startet.
So und das machen wir jetzt regressiv und die Topologie von dem Baum
ist genau die Topologie von dem Codewort-Baum.
Und jetzt speichern wir sich also, anstatt man sich die komplette
Sequenz speichert, das wäre nämlich jetzt teuer, weil ich habe ja eine
Tiefe von die mittlere Tiefe hier, mal dann die Vorkommen von
Symbolen.
Also jedes Symbol wird so oft vorkommen wie die Codelänge mal 1.
Also die Gesamtkomplizität, die Platzkomplizität wird dann quasi
multipliziert mit der Codelänge eines jeden Buchstabens.
Das heißt es ist ja nicht komprimiert.
Jetzt speichern wir sich nur ab für jedes Symbol immer das Bid, also
auf Level L, das Bid an Position L, für jedes Symbol.
Also hier das A fängt mit 0 an, also speichern wir 0, das A fängt mit
einer 1 an, also speichern wir auf Level 0 die 1.
Und das heißt, es reicht nur diese Bid-Faktoren ab zum Speichern, um
all diese Operationen zu erfüllen.
Und wenn ich jetzt davon ausgehe, dass der Text die Alphabetgröße
Sigma ist und ich teile das immer auf binär in zwei Teile, also ich
habe eine Tiefe von Log Sigma und das ist auch der Platz, den ich
brauche, um ein Symbol darzustellen.
Naiv.
Das heißt, wenn ich jetzt da Bid-Faktoren speichere auf jeder Ebene,
der Länge n und die sind auf jeder Ebene höchstens n Bids, dann
brauche ich für den Gesamt-Waveletrie, brauche ich dann n Log Sigma
Bids.
Das entspricht jetzt zunächst dem Platz der Originalsequenz.
Und dann brauche ich dann zusätzlich die Topologie.
Also ich habe Sigma Kinder im Binärbaum, das heißt insgesamt Sigma
viele Knoten hier und da brauche ich, wenn ich da jeweils einen
Pointer speichere, habe ich dann nochmal Sigma Log n Bids zusätzlich.
Jetzt wollen wir mal sehen, wie man diese Rank-Anfrage beantworten
kann, nach einem bestimmten Symbol.
Jetzt wollen wir Rank A, also ich will wissen, wie viele A's sind bis
zur Position 11 da drin und das kann man jetzt reduzieren dann, also
auf Ranks, auf diesen Bid-Faktoren.
Das heißt, man fängt an an der Wurzel und fragt sich ja, wie viele A's
sind da drin und das kann man jetzt reduzieren, indem man weiß ja, in
welcher Alphabet-Hälfte dieses A ist oder was der Code von dem A ist.
Das A fängt mit einer Null an, also reicht es mir erst mal zu sagen,
weil das A in der Hälfte ist, das mit Null anfängt, kann ich erst mal
zählen, wie viele Nuller sind da drin bis zu der Position.
Und da stelle ich fest, da sind 1, 2, 3, 4, 5 Nuller drin, das kann
ich mit dieser Datastruktur in Standardzeit machen.
Also kann ich die Frage reduzieren auf, wie viele Symbole sind jetzt
da im Prefix von 5, weil ich habe jetzt genau hier bis zu der 11 habe
ich genau 5 Symbole, die mit Null anfangen.
Und dann weiß ich, die zweite Buchstabe ist wieder Null, das heißt,
ich kann hier wieder zählen, wie viele Nuller sind hier drin.
Das sind drei Stück und Rank von Null lässt sich natürlich durch Rank
von 1 ausrechnen, indem man einfach sagt, wenn ich das bei Position i
will, kann ich einfach sagen, i minus Rank von 1, das gibt mir Rank
von Null.
Das heißt, ich brauche da keine zusätzliche Datastruktur für Rank Null
oder Rank 1, also Rank 1 reicht für beide Fälle.
Und jetzt im letzten Schritt weiß ich, dass das A mit einer 1 kodiert
ist.
Jetzt kann ich dann also zählen, wie viele A's in dieser Subsequenz
sind.
Und ich komme ein Blatt an und im Blatt ist dieses Teilalphabet nur
noch hat Größe 1, ist also das Symbol selbst.
Und dann weiß ich, jetzt sind da zwei A's drin.
Das heißt, diese Rank-Anfrage lässt sich reduzieren auf höchstens log
Sigma viele Rank-Anfragen auf Bitvektoren.
Das heißt, dieser Zählvorgang lässt sich jetzt statt linear, mit
linearer Zeit oder mit Scanning, lässt sich das mit nicht viel mehr
Platz aufwenden, weil ich jetzt durch diese Rank-Struktur auf den
Bitvektoren habe ich nur dieses sublineare viel Platz.
Und genau, bisher war die Platzkomplexität natürlich N mal log Sigma
und jetzt kann ich einfach, indem ich die Topologie eines Huffman
-Baums anwende, ich bilde den Huffman-Code über diese Sequenz oder für
die Sequenz, für die Verteilung der Buchstaben.
Genau, baue ich dann den Huffman-Baum und das heißt, jetzt ist die
mittlere Anfragezeit genau die Entropie von der Sequenz.
Das heißt, in dem Beispiel, wenn ich das aufbaue mit den
Geschwindigkeiten, kriege ich eine Entropie von 2,14 raus.
Das heißt, wenn ich das mit N multipliziere, mit 19, dann kriege ich
40, irgendwas.
Das heißt, das ist ein bisschen kleiner als 41 Bits, die optimale
Darstellung.
Mit dieser balancierten Topologie, die ja schon platzsparend war, weil
es quasi kein vollständiger Binärbaum ist, habe ich 49 Bits gebraucht
für die Darstellung und jetzt mit dieser Huffman-Topologie bin ich
dann also sehr nah dran an der optimalen Darstellung von 42 Bits.
Das heißt, das war jetzt eine komprimierte Darstellung eines Objekts
und man kann trotzdem effizient Anfragen beantworten.
Und genau diese Struktur, dieser wavelet, wavelet tree, der wird zum
Beispiel heute im Genome-Sequencing, Next-Generation-Sequencing
eingesetzt, um Pattern-Matching zu machen.
Mit dieser Rank-Funktion lässt sich effizient Pattern-Matching
implementieren.
Und der Text, also der Index, der es zulässt, dann in effizienter Zeit
das Pattern-Matching zu machen.
Also wenn m die Patternlänge ist, ist m mal genau die Zeit für dieses
Rank, also log n, log sigma.
Genau, der ist kleiner als der Text selber.
Also der ist komprimiert.
Und man kann natürlich dann auch dieses Excess, lässt natürlich auch
zu jedes beliebige Zeichen wieder zu extrahieren.
Und das Excess ist noch leichter als dieses Rank.
Und das kommt dann in der Übung dran.
So, eine zweite Sexing-Struktur ist das sogenannte Elias-Ferno-Coding.
Und das kann zum Beispiel auch verwendet werden, um dieses Fax, diese
Lauflängen -Codierung zu codieren.
Also sei x eine Aufsteigend-Sequenz im Universum von 0 bis n-1.
Und dann lässt sich, also die naive Darstellungsweise wäre es einfach,
wenn ich m Zahlen da drin habe in der Sequenz, dann wäre die naive
Darstellung m mal log n Bits.
Und jetzt gibt es aber eine Darstellung, diese Elias-Ferno-Codierung,
die das besser macht.
Die macht das in m mal log n durch m abgerundet, plus 3m.
Und dann wieder so einen sublinearen Term in m.
Und ich kann aber trotzdem noch in konstanter Zeit auf jedes Element
x, y in dieser Sequenz zugreifen.
Und das tritt in vielen Anwendungen auf, so Aufsteigend-Sequenzen.
Also zum Beispiel, wenn man einen Graphen darstellt, hat man eine Art
der Zinslisten, die kann ich aufsteigend sortieren.
Und anstatt die einfach unkomprimiert abzuspeichern, kann ich die mit
Elias -Ferno abspeichern.
Oder wenn man an Suchmaschinen denkt, dann ist der innovatierte Index
die Hauptdatenstruktur, also die meistverwendete Datenstruktur
überhaupt, wahrscheinlich heutzutage.
Also Grundlage von allen modernen Suchmaschinen.
Und da notiere ich mir für jedes Wort, in welchem Dokument dieses Wort
vorkommt.
Und die Dokumente sind durchnummeriert und dann speichere ich das
natürlich auch aufsteigend an.
Dann kann ich mit dieser Codierung effizient darauf zugreifen und habe
es auch trotzdem noch komprimiert.
Genau, und jetzt sind es zwei Minuten, da höre ich ein bisschen auf.
Das kommt dann nächstes Mal dran, wie das funktioniert.