Okay, wir hatten letztes Mal angefangen mit dem Kapitel über Hashing.
Und obwohl das ein relativ kurzes Kapitel ist, finde ich das
eigentlich das erste wirklich spannende Kapitel unserer Vorlesung aus
algorithmischer Sicht.
Wir hatten angefangen mit einer relativ einfachen, aber wichtigen
Technik, Hashing mit linearer Verkettung.
Und heute werden wir das analysieren.
Und das ist auch, glaube ich, ein spannender Moment in dieser
Vorlesung, weil wir das erste Mal einen richtig nicht trivialen Beweis
sehen werden, der außerdem für Sie vielleicht noch ein bisschen
ungewohnt ist, weil wir da sozusagen von 0 auf 100 die
Wahrscheinlichkeitstheorie einführen müssen.
Also in gewisser Weise ist das vielleicht der schwierigste Beweis in
der ganzen Vorlesung.
Ich hoffe aber, Sie davon überzeugen zu können, dass es ja trotzdem
nicht wirklich schwierig ist, wenn man sich ein bisschen darauf
einlässt.
Und sich vor allem auch nicht scheut, bei Schwierigkeiten Fragen zu
stellen.
Das ist nicht viel, aber bitte gucken Sie sich das wirklich genau an.
Bremsen Sie mich auch, wenn ich zu schnell bin.
Gut, aber fangen wir mal an mit der Grundidee von Hashing.
Wir hatten angefangen mit einer Methode, die nicht so richtig
funktioniert oder zumindest ziemlich schwierig ist, die aber sozusagen
die Idee von Hashing in Reihenkultur erklärt.
Und das möchte ich nochmal kurz wiederholen.
Also angenommen, wir hätten eine perfekte Hash-Funktion, die die
Elemente einer Menge M, die wir abspeichern wollen, injektiv abbildet
auf eine Tabelle mit M Einträgen.
Da muss natürlich die Tabelle mindestens M Betrag Einträge haben,
idealerweise mehr.
Und eine Art, das zu spezifizieren, was wir haben wollen, wäre ja auch
eine Datenstruktur invariante anzugeben, die hatte ich letztes Mal
noch nicht auf dieser Folie.
Was wir eigentlich wollen, ist, dass für alle Elemente aus der Menge
M, die wir speichern wollen, gilt, dass dieses Element an der Stelle
in dieser Tabelle gespeichert ist.
Und zwar an welcher Stelle?
Na ja, da, wo die Hash-Funktion es uns sagt.
Also wir nehmen den Schlüssel des Elements, wenden die Hash-Funktion
darauf an und wir wollen, dass E in dieser Stelle der Tabelle steht.
Und wir wollen außerdem noch, dass nichts anderes in der Tabelle
steht.
Also nur Elemente von M stehen in der Tabelle und leere Einträge
sollen halt irgendwie kenntlich sein.
Und das habe ich mal durch dieses Undefined-Symbol dargestellt.
Ja, wir haben gesehen, dass das nicht funktioniert, weil es nicht so
klar ist, wie man an perfekte Hash-Funktionen rankommt.
Und im Allgemeinen Hash-Funktionen Kollisionen erzeugen werden.
Das heißt, mehrere Elemente von M werden auf die gleiche
Tabellenposition abgebildet.
Wir hatten dann das Geburtstagsparadoxon uns angeschaut, um das zu
illustrieren.
Und die Lösung war eigentlich sehr pragmatisch.
Also wir können ja auch hergehen und sagen, dann speichern wir in der
Tabelle halt nicht direkt Elemente, sondern Mengen von Elementen.
Beziehungsweise repräsentiert als Folgen von Elementen.
Noch konkreter gesagt mit einfach verketteten Listen.
Die Datenstrukturinvariante, die wir dann kriegen, ist sogar noch
einfacher.
So ähnlich wie eben, wir wollen für jedes Element aus M nicht, dass E
gleich dem Tabelleneintrag ist, den H von key von E angibt, sondern es
ist Teil davon.
Weil der ja eine Menge oder eine Folge von Elementen abspeichert.
Beachten Sie hier, dass ich hier die übliche Mengennotation erweitere
für Folgen.
Also wenn etwas Element einer Folge ist, dann soll es halt an
irgendeiner Position in dieser Folge auftreten.
Oder wenn eine Folge Teilmenge von einer Menge sein soll, dann soll
halt die Menge, die durch diese Folge repräsentiert wird, Teilmenge
dieser Menge sein.
Ich hoffe, das gibt keine Missverständnisse.
Ich denke, das ist relativ intuitiv, was ich hier mache.
Also die Invariante wird, alle Elemente von E sollen in der Folge
stehen, die durch die Hash-Funktion angewendet auf den Schlüssel
spezifiziert wird und in dieser Tabelle abgespeichert ist.
Und umgekehrt sollen alle Tabelleneinträge Teilmengen der Menge M, die
ich abspeichern will, darstellen.
Wohlgemerkt, undefined, ich brauche jetzt nicht diesen hässlichen
Spezialwert für undefiniert, weil undefiniert ist einfach die leere
Folge oder die leere Menge, die dadurch repräsentiert wird.
Gibt es dazu noch Fragen?
Die Implementierung ergibt sich daraus fast zwangsläufig, man hat noch
ein paar Freiheiten, zum Beispiel beim Einfügen kann ich das irgendwo
in dieser Folge anfügen, aber bei einfach verketteten Listen ist es am
einfachsten, das am Anfang einzufügen.
Beim Löschen habe ich eigentlich wenig Wahl, ich muss halt diese Liste
durchlaufen und wenn ich das Element finde, wird es aus der Liste
gelöscht.
Wenn ich es nicht finde, sage ich, das war gar nicht drin oder ich
mache gar nichts, das kann man sich überlegen, was man da haben will.
Und beim Suchen muss ich halt auch durch diese Liste durchlaufen, wenn
ich es gefunden habe, liefe ich es zurück und sonst sage ich, war
nicht drin.
Wir hatten uns ein Beispiel angeguckt.
Die Analyse ist jetzt auch oberflächlich gesehen erstmal einfach, das
Insert braucht konstante Zeit, Remove und Find brauchen
zeitproportional zu Länge dieser Liste.
Blöderweise kann die halt so lang werden wie die Menge und dann kann
ich mir die Hashtabelle auch sparen.
Und an der Stelle ist es jetzt nützlich, Chaos anzurichten.
Die einfachste Art, hier sehr ordentlich vorzugehen, ist einfach,
alles an die gleiche Stelle zu speichern, aber dann müssen Sie immer
durch eine lange Liste gehen.
Da Sie nicht wissen, was in M drin steht, ist es schwer, irgendwas
Systematisches anzugeben, was niemals große Kollisionen erzeugt, aber
wir werden sehen, dass zufällige Hashtfunktionen eigentlich ziemlich
gut sind.
Und insofern ist es tatsächlich effizient, möglichst viel Chaos
anzurichten.
Und das ist im Prinzip auch dieser Algorithmus von Kindern, die ihr
Zimmer nicht aufräumen.
Sie schmeißen einfach ihre Spielzeuge an zufällige Positionen im
Zimmer und dann hat man die alle auf einem Blick sichtbar.
Während wenn man da irgendeine deterministische, systematische
Funktion einführt, die sagt, alle Autos kommen in das Fach von dem
Schrank und jetzt ist aber leider das Kind so ein Autofan, dass es die
nächsten zehn Geburtstage und Weihnachten nur noch Autos kriegt, dann
stapelt sich da alles.
Während Autos zufällig durch die Gegend schmeißen, funktioniert super,
man sieht alles.
Und das wollen wir mathematisch beweisen und dafür brauchen wir ein
bisschen Mathematik, logischerweise.
Blöderweise haben Sie noch keine Wahrscheinlichkeitstheorie gelernt,
das kommt erst im nächsten Semester.
Deshalb mache ich jetzt Wahrscheinlichkeitstheorie für den
Hausgebrauch, wie analysiere ich meinen Dreijährigen, auf einer Folie.
Die aber zugegebenermaßen relativ voll ist, aber ich denke in dem Fall
ist es sinnvoller, alles auf eine Folie, dass man die ganzen
Querbezüge weiter sieht und sich lieber ein bisschen mehr Zeit lässt.
Wahrscheinlichkeitstheorie wurde ursprünglich angeschaut als
Möglichkeit, um Glücksspiel zu analysieren.
Also man macht auch oft so das einfachste Wahrscheinlichkeitsding, was
man hat, man wirft Münzen und entscheidet ob Kopf oder Zahl und kann
daraus dann alle möglichen Sachen ausrechnen.
Wie wahrscheinlich ist es, dass bestimmte Folgen von Kopf oder Zahl
passieren usw.
Ich werde hier anders vorgehen, ich werde als Beispiel sofort unsere
Hashtabelle verwenden.
Und wir werden dann als zweites Beispiel das Geburtstagsparadoxon
sehen und feststellen, dass es das gleiche ist.
In der Mathematik fängt alles an mit Mengen, Mengenlehre.
Genauso ist es in der Wahrscheinlichkeitstheorie.
Das fundamentalste Ding ist eine Menge von Elementarereignissen Omega.
Und das sind in unserem Beispiel die Hashtfunktionen.
Also wir haben ja die Idee, zufällige Hashtfunktionen zu verwenden.
Und jetzt sagen wir halt, dann sind unsere Elementarereignisse halt
Hashtfunktionen.
Das heißt, die Menge aller Abbildungen von Schlüsseln auf die ganzen
Zahlen von 0 bis m-1.
m war unsere Tabellengröße.
Das ist eine ziemlich große Menge.
Wir werden tatsächlich auch sehr viel jetzt kombinatorisch rechnen
müssen.
Also wir werden im Endeffekt alles darauf zurückführen, solche
Elementarereignisse zu zählen.
Und das werden wir an einigen Stellen in den Beweisen dann tun müssen.
Aber das ist immer noch recht überschaubar.
Und ich denke, das haben Sie in HM gelernt.
Wie man zum Beispiel Funktionen zählt.
Also insbesondere, kann mir jemand sagen, wie viele solche Funktionen
es gibt?
Wie groß ist mein Omega in unserem Beispiel?
Also key ist die Menge der möglichen Schlüssel.
Ist jetzt erstmal irgendeine endliche Menge.
Kann mir jemand sagen, wie viele Elemente Omega hat?
Okay...
Da!
m hoch Betrag von key.
Genau.
Das ist das Schöne mit dieser Mengennotation.
Man muss nur die Mengen durch Zahlen ersetzen oder durch ihre Größen
und kriegt die Kombinatorik.
Das zeigt, dass das Ganze auch schon relativ simpel ist, was wir hier
machen.
Also nochmal für die Akustik.
m, das ist genau die Anzahl Tabelleneinträge, hoch die Anzahl
möglicher Schlüssel.
Sie können sich das auch vorstellen, Sie haben so eine Tabelle.
Sie müssen für jeden möglichen Schlüssel eine Tabellenposition
eintragen.
Also eine Wertetabelle ausfüllen.
Und dafür gibt es halt diese entsprechende Anzahl Werte.
Das ist eine Zahl zur Basis m mit so vielen Ziffern, wie es Schlüssel
gibt.
Wenn wir bedenken, dass das key ziemlich groß sein kann, sind das
astronomische Zahlen.
Das Schöne ist, das brauchen wir nur für die Beweise.
Wir müssen nie explizit mit diesen riesigen Zahlen arbeiten.
In der Implementierung oder sowas.
Okay, also das Omega ist irgendwie groß, aber einfach aufgebaut.
Dann gibt es was aus diesen Elementarereignissen, baue ich was
Allgemeineres.
Ereignisse, das sind einfach Teilmengen von Omega.
Zum Beispiel könnte ich definieren, die Menge E42 ist die Menge aller
Elemente aus Omega, also die Menge aller Hash-Funktionen mit der
Eigenschaft, dass der Schlüssel 4 und der Schlüssel 2 auf die gleiche
Tabellenposition abgebildet werden.
Also ich habe eine Kollision zwischen den beiden Schlüsseln 4 und 2.
Kann mir jemand sagen, wie groß die Menge ist?
Das ist
einfach m hoch Anzahl Schlüssel minus 1.
Wie kann man das sehen?
Machen wir mal so eine Fallunterscheidung für jeden möglichen Wert h
von 4.
Da gibt es ja schon mal m Stück.
Da haben wir sozusagen eine Rahmenbedingung an unserer Hash-Funktion,
nämlich dass außerdem dann h von 2 der gleiche Wert sein muss.
Und alles andere ist völlig egal.
Das heißt, wir haben für jeden konkreten Wert von h von 4 m hoch
Anzahl Schlüssel minus 2 Möglichkeiten, wie wir sicherstellen können,
dass h von 4 gleich h von 2 ist.
Also m mal m hoch Anzahl Schlüssel minus 2 ist m hoch Anzahl Schlüssel
minus 1.
Solche Rechnungen werden wir gleich brauchen, deshalb fange ich damit
langsam mal an.
Also wir haben gelernt, Elementarereignisse sind Hash-Funktionen.
Ereignisse sind Teilmengen von Elementarereignissen, also bei uns
Teilmengen von Hash-Funktionen.
Bisher war das alles nur Mengenlehre, es hat nichts mit
Wahrscheinlichkeitsrechnung direkt zu tun.
Wahrscheinlichkeitsrechnung wird daraus, indem wir den
Elementarereignissen Wahrscheinlichkeiten zuordnen.
Dem Ereignis x in Omega, für die müssen wir eine Wahrscheinlichkeit px
definieren.
Im Allgemeinen sind wir da sehr flexibel, wie wir diese px definieren
können.
Das Einzige, was gelten muss, ist, dass die Summe aller px 1 ist.
Das heißt, wir ziehen ein Elementarereignis aus der Gesamtmenge
möglicher Elementarereignisse und das ist dann das, was sozusagen
passiert.
Und darüber machen wir jetzt Aussagen.
Und das ist aber auch ganz simpel, weil fast immer in der
Wahrscheinlichkeitsrechnung nimmt man die Gleichverteilungsannahme.
Das heißt, die px sind alle gleich.
Und wenn die px alle gleich sind und sich außerdem zu 1 summieren
müssen, ist einfach px gleich 1 durch Omega-Betrag.
Also 1 durch Anzahl möglicher Ereignisse.
Also... gab es da eine Frage, ein Problem?
Also in unserem Fall wäre dieses ph, für eine konkrete Hashfunktion, m
hoch minus Anzahlsschlüssel.
Das ist alles super simples Zeug.
Was ist die Wahrscheinlichkeit eines allgemeinen Ereignisses?
Das ist ganz einfach.
Das ist einfach die Summe der Wahrscheinlichkeiten der
Elementarereignisse in E.
Das heißt, wenn ich die Gleichverteilungsannahme habe, muss ich im
Wesentlichen bestimmen, wie groß ist denn E.
Das dividiere ich durch Omega-Betrag und kriege meine
Wahrscheinlichkeit.
Zum Beispiel, unser Ereignis E4-2 hat die Wahrscheinlichkeit 1 durch
m.
Wie erkenne ich das?
Ich habe ja eben schon gefragt, wie groß ist das?
Das war m hoch Ki-Betrag minus 1, geteilt durch Omega-Betrag.
Das war m hoch Ki-Betrag.
Dann kürzt sich diese riesige Zahl raus und übrig bleibt etwas schon
viel Übersichtlicheres, nämlich 1 durch m.
Diese rein formale Sichtweise deckt sich vielleicht auch mit der
Intuition.
Die Wahrscheinlichkeit, dass zwei Schlüssel, die zufällig abgebildet
werden auf Werte zwischen 1 und m, also auf Tabellenpositionen, dass
die auf den gleichen Wert abgebildet werden, ist 1 durch m.
Oder eine andere Sichtweise, ich schaue mir die Position an, auf die 4
abgebildet wird, und das ist in dem Fall völlig symmetrisch und egal,
welche Position das ist, dann ist die Wahrscheinlichkeit, dass 2 auf
die gleiche Position abgebildet wird, einfach 1 durch m, weil 2 mit
gleicher Wahrscheinlichkeit auf jede Position abgebildet wird und es
außerdem völlig unabhängig davon ist, wo die 4 hin abgebildet wurde.
Aber mathematisch korrekt und formal und klar bewiesen geht das am
besten direkt mit der Kombinatorik.
Zumindest in so einem einfachen Fall wie hier.
Es gibt in der Wahrscheinlichkeitstheorie mengenmäßig Paradoxe, wo man
die Intuition komplett in die Irre führen kann.
Deshalb ist es manchmal besser, bis ganz zurück auf die Definitionen
zu gehen, die Kombinatorik zu machen und das auszurechnen.
Das werden wir hier auch tun.
Und in dem Fall ist das auch sehr einfach.
Okay, also jetzt wird es langsam interessant.
Das waren langweilige Definitionen, Elementarereignisse, Ereignisse,
Wahrscheinlichkeit von Elementarereignissen, Wahrscheinlichkeit von
Ereignissen.
Es kommen noch mehr langweilige Sachen.
Zufallsvariablen.
Aber da passiert schon ein bisschen mehr.
Wir bringen mehr und mehr diese mengentheoretischen Sachen zu
irgendwelchen quantitativen Aussagen, die vielleicht für unsere
Algorithmen relevant sind.
Oder dafür relevant, ob Sie bei der nächsten Party so eine
Geburtstagsparadoxon -Wette machen wollen oder sowas.
Zufallsvariablen, das sind Abbildungen von Omega auf die reelle Zahl.
Also Sie gucken sich so ein Ereignis an und sagen, Sie ziehen eine
Hash -Funktion und gucken für diese Wahl der Hash-Funktion,
was passiert da?
Irgendein Aspekt dessen, irgendeine Eigenschaft dieser Hash-Funktion,
die Sie numerisch ausdrücken können.
Zum Beispiel könnte das sein, Sie könnten definieren, die Anzahl der
Elemente, die auf die Tabellenposition 0 abgebildet werden, falls Sie
das interessiert.
Das sind Zahlen zwischen 0 und m-Betrag.
Und die kann für verschiedene Hash-Funktionen unterschiedlich groß
sein.
Also Sie haben hier mit der Zufallsvariable so etwas wie eine
Verallgemeinerung einer Zahl in einer wahrscheinlichkeitstheoretischen
Art und Weise.
Sie kriegen im Prinzip für jedes mögliche Element von Omega eine
andere Zahl.
Und wie wahrscheinlich es ist, dass Sie eine bestimmte Zahl
beobachten, können Sie halt ausrechnen.
Und diese Zufallsvariablen stehen im Allgemeinen im Zentrum von
wahrscheinlichkeitstheoretischen Rechnungen und Betrachtungen.
Deshalb sind die sehr wichtig.
Wir werden in dieser Vorlesung fast nur besonders einfache
Zufallsvariablen angucken, nämlich solche, die nur den Wertebereich 0
und 1 annehmen können.
Das sind sogenannte Indikatorzufallsvariablen, die eigentlich so ein
Ja -Nein ausdrücken.
Irgendein Ereignis hat eine bestimmte Eigenschaft oder das hat sie
nicht.
0 hat sie nicht, 1 hat sie.
Ein weiterer wichtiger Aspekt ist ein Erwartungswert.
Diese Verallgemeinerung von Zahlen auf Verteilung von Zahlen machen
die Dinge natürlich deutlich komplexer.
Und jetzt will man auf irgendeine vernünftige Art und Weise diese
Zufallsvariablen wieder durch eine einzige Zahl beschreiben.
Und die wichtigste Art, das zu tun, ist der Erwartungswert E von X.
Und das ist so etwas wie, wenn Sie ganz viele Experimente machen und
über die beobachteten Werte mitteln, was kommt denn da raus?
Und mathematisch ist das einfach, Sie summieren über alle möglichen
Elementareignisse, und multiplizieren die Wahrscheinlichkeit von Y,
PY, mit dem Wert der Zufallsvariablen, den Sie beobachten, wenn Y
gezogen wird.
Und da wir hier Gleichverteilungsannahme haben, ist das im Prinzip,
Sie summieren alle möglichen Werte der Zufallsvariablen und teilen
durch Omega-Betrag.
Zum Beispiel, wenn wir unsere Zufallsvariable hier nehmen, X, die
Anzahl der Elemente, die auf die 0.
Position der Tabelle abgebildet werden, dann kriegen wir gerade die
Größe von M, also die Gesamtzahlelemente durch M, das ist, glaube ich,
ziemlich intuitiv.
Das ist sozusagen die mittlere Anzahl Elemente, die auf einen
bestimmten Tabelleneintrag abgebildet werden.
Da die alle gleich sind, die Tabelleneinträge, ist das natürlich bei
der 0 genauso wie bei der 17 usw.
Wäre jetzt eine kleine Übungsaufgabe, das auch kombinatorisch
auszurechnen.
Ich habe da jetzt an Ihre Intuition appelliert, aber das könnten Sie
auch ganz hart ausrechnen, wenn Sie wollen.
Also bis hierhin waren alles relativ langweilige Definitionen, obwohl
ich hoffe, irgendwie ein Gefühl dafür entwickelt zu haben, worum es
hier geht.
Wir wollen eigentlich von dieser deterministischen Sichtweise von
Algorithmen oder Ereignissen weg zu einem Fall, wo wir nicht wissen,
was rauskommt.
Es kann viele Möglichkeiten geben und wir wollen damit rechnen.
Darum geht es hier.
Und jetzt kommt, wir brauchen ein einziges Theorem, mit dem man
unheimlich viel machen kann.
Und das ist die Linearität des Erwartungswertes.
Der Erwartungswert einer Zufallsvariable in x plus y ist der
Erwartungswert von x plus der Erwartungswert von y.
Jetzt muss ich noch erklären, was x plus y überhaupt ist.
Also gegeben zwei beliebige Zufallsvariablen x und y, also diese
Abbildung von Omega auf die ganzen Zahlen.
Wenn ich die Summe der jeweiligen Funktionswerte bilde, kriege ich
eine neue Zufallsvariable.
Die nämlich Omega abbildet.
Also für einen bestimmten Wert von Omega nehme ich den Wert von x.
Also für einen bestimmten Wert von x in Omega nehme ich den Wert von
z.
Für einen bestimmten Wert z aus Omega nehme ich den Wert von x für z
plus den Wert von y für z.
Also das ist ganz intuitiv komponentenweise, wie man die Summe von
Zufallsvariablen definieren kann.
Und das Schöne ist halt, den Erwartungswert einer Summe von
Zufallsvariablen kann ich berechnen als die Summe der Erwartungswerte.
Damit kann ich Sachen vereinfachen.
x plus y ist eine kompliziertere Funktion, aber den Erwartungswert von
x plus y kann ich berechnen, indem ich zwei einfachere Erwartungswerte
berechne, nämlich den für x und den für y und das Ganze einfach als
Zahlen addiere.
Und das nennt man die Linearität des Erwartungswertes.
Gibt es dazu Fragen?
Also wenn Sie diese relativ einfachen Definitionen verstanden haben,
kann ich Ihnen nicht nur die Analyse von Hashtabellen erklären,
sondern auch die Analyse von Quicksort und mehreren weiteren
Algorithmen, die wir hier in der Vorlesung kennenlernen werden.
Es sind immer wieder die gleichen Techniken.
Indikator, Zufallsvariable, Linearität des Erwartungswertes und ein
bisschen geschicktes Hin und Her argumentieren und schon haben wir
unser Ergebnis.
Deshalb ist es wichtig, dass Sie das da verstehen.
Also wenn es eine einzelne Folie gibt in dieser Vorlesung, wo es
besonders wichtig wäre, dass Sie die verstehen, ist es vielleicht die
da.
Sie können die Klausur auch bestehen, wenn Sie das nicht verstehen,
weil nicht alle unsere Algorithmen etwas mit Zufall zu tun haben.
Aber die Algorithmen, die etwas mit Zufall zu tun haben, können Sie am
besten verstehen, wenn Sie auch die Mathematik dahinter verstehen und
die wird hier zusammengefasst.
Gehen wir mal zum Geburtstagsparadoxon.
Da haben wir letztes Mal schon ein bisschen drüber geredet.
Wir haben uns gefragt, wie viele Gäste muss eine Geburtstagsparty
haben, damit mindestens zwei Gäste den gleichen Geburtstag haben.
Das ist jetzt, so wie ich es gerade gesagt habe, nicht besonders
sinnvoll, weil wenn ich davon ausgehe, dass meine Gäste zufällige
Geburtstage haben,
gibt es da eine gewisse Wahrscheinlichkeit, dass es zwei gibt, die den
gleichen Geburtstag haben.
Und ich werde jetzt hier irgendwie so eine Rechnung machen, die so
etwas sagt wie im Mittel, wie viele Gäste muss eine Geburtstagsparty
im Mittel haben, damit etwas gilt.
Was ich da ausrechne, zeige ich Ihnen gleich.
Das ist nicht genau das Gleiche wie die Rechnung, die ich Ihnen
letztes Mal vorgestellt habe.
Da habe ich gefragt, wie viele Gäste muss sie haben, damit es sich
lohnt, für sie eine 1 zu 1 Wette zu machen.
Rechnen wir das mal aus.
Wir haben Gäste, das sind unsere Schlüssel.
Ohne Beschränkung der Allgemeinheit, Zahlen 1 bis N.
Ich habe eine besonders herzliche Art, mit meinen Gästen umzugehen.
Die kriegen so eine Nummer angeklebt, wenn sie kommen.
Hallo Gast 3, möchtest du noch ein Bier?
Gut.
Was sind dann meine Elementarereignisse?
Mir geht es ja jetzt um die Geburtstage von denen, und zwar wie die im
Jahr liegen.
Und ich mache jetzt eine weitere Theoretiker-Vereinfachung.
Ich nehme an, dass wir genau 365 Tage im Jahr haben, und zwar immer.
Die Wahrscheinlichkeit, dass jemand am 29.
Februar geboren wird, ist leider ungefähr ein Faktor 4 kleiner als die
anderen.
Davon abstrahiere ich.
Ich nehme an, die Wahrscheinlichkeiten sind alle gleich.
Also ich habe Gleichverteilung auf dem Wahrscheinlichkeitsraum 0 bis
364, hoch 1 bis N.
Und man kann sich überlegen, dass der Fehler, den ich durch diese
Vereinfachung mache, relativ klein ist.
Jetzt definiere ich Zufallsvariable, und zwar gleich ganz viele.
Nämlich für jedes Paar von Gästen eine Zufallsvariable iij.
Das sind Indikator-Zufallsvariable, die 1 wird, genau wenn die den
gleichen Geburtstag haben.
Und das ist jetzt das Gleiche wie, meine Gäste sind die Elemente einer
Hashtabelle, und diese Hashtabelle hat 365 Einträge.
Mathematisch ist das das Gleiche.
Und offenbar habe ich hier eine Analogie zwischen der Tatsache, dass
zwei Gäste den gleichen Geburtstag haben, und einer Kollision von
Elementen einer Menge bezüglich einer Hash-Funktion.
So, jetzt kann ich ausrechnen, also ich definiere eine neue
Zufallsvariable.
Das ist die Anzahl Paare von Gästen mit gleichem Geburtstag.
Und damit ich Paare nicht doppelt zähle, sage ich, naja, also i muss
kleiner j sein.
Also dann ist meine Anzahl Paare mit gleichem Geburtstag definiert als
x gleich die Summe von i gleich 1 bis n, die Summe von j gleich i plus
1 bis n, iij, also meine Indikator-Zufallsvariable ij.
Und die Idee ist jetzt, wenn diese Variable x größer gleich 1 wird,
dann habe ich meine Wette gewonnen und wenn sie 0 ist, habe ich
verloren.
Und ich möchte jetzt als Ersatz für diese eigentliche
Wahrscheinlichkeitsabschätzung, die ein bisschen komplizierter ist,
möchte ich jetzt den Erwartungswert von x ausrechnen.
Und ich möchte also jetzt wissen, in welchen Situationen ist dieser
Erwartungswert 1 oder größer.
Das ist, was ich hier mit im Mittel meine.
Gut, und jetzt schreibe ich die Definition hin.
Ich setze einfach die Definition von x ein, also Erwartungswert Summe
i gleich 1 bis n, Summe j gleich i plus 1 bis n, iij.
Jetzt kann ich ganz oft Linearität des Erwartungswerts anwenden und
kann sozusagen diesen Erwartungswert-Operator hinter die Summe ziehen.
Also ich kriege Summe i gleich 1 bis n, Summe j gleich i plus 1 bis n,
Erwartungswert von iij.
So, jetzt können wir uns überlegen, was ist denn der Erwartungswert
einer Indikator-Zufallsvariable?
Gehen wir mal hierhin zurück.
Erwartungswert ist die Summe über alle Elemente und Omega die
Wahrscheinlichkeit, dass dieses Elementarereignis eintritt, mal den
Wert, den meine Zufallsvariable annimmt.
Die Wahrscheinlichkeit ist überall die gleiche, 1 durch Omega-Betrag.
Der Wert ist bei einer Indikator-Zufallsvariable 0 oder 1.
Die Fälle, wo es 0 ist, tragen offenbar nichts zum Erwartungswert bei,
also interessieren mich nur die Fälle, wo es 1 ist und die tragen alle
genau 1 durch Omega-Betrag bei.
Also da steht dann Anzahl der Fälle, wo ich eine 1 sehe, geteilt durch
Omega -Betrag.
Das ist aber gerade die Wahrscheinlichkeit des Ereignisses, dass meine
Indikator -Zufallsvariable 1 wird.
Das heißt, diese Summe hier ist gleich, ich schreibe einfach die
Summenzeichen ab und ersetze Iij durch die Wahrscheinlichkeit, dass
Iij gleich 1 wird.
Auch wenn wir immer wieder den Erwartungswert einer Indikator
-Zufallsvariable berechnen, ist das Gleiche wie einfach die
Wahrscheinlichkeit ausrechnen, dass diese Indikator-Zufallsvariable
den Wert 1 annimmt.
Und wie wahrscheinlich ist es, dass 2 Leute den gleichen Geburtstag
haben in unserem vereinfachten Modell, das ist einfach ein 365.
Und das haben wir hier als Beispiel auch schon ausgerechnet für den
konkreten Fall, wie wahrscheinlich ist es, dass die Gäste 2 und 4 den
gleichen Geburtstag haben, 1 durch M.
Und offensichtlich spielt es keine Rolle, ob ich hier 4 oder 2
einsetze oder irgendwelche anderen Zahlen.
Ich sollte nicht die gleichen Zahlen einsetzen, die
Wahrscheinlichkeit, dass Person 3 den gleichen Geburtstag hat wie
Person 3 ist natürlich 1, aber da muss man ein bisschen aufpassen.
Also wir haben hier einfach, diese Wahrscheinlichkeit ist 1 durch 365.
Die Anzahl Summanden, die ich hier habe, ist einfach die Anzahl der
geordneten Paare von Zahlen zwischen 1 und N.
I und J müssen außerdem noch unterschiedlich sein, das haben Sie
wahrscheinlich in HM mal gelernt, das ist gerade N mal N minus 1
halbe.
Also der Erwartungswert von X ist N mal N minus 1 halbe mal 1 durch
365.
Und jetzt haben wir gesagt, dieses komische im Mittel, wir wollen
wissen, wie groß muss N sein, damit X 1 wird oder größer.
Das ist einfach eine Gleichung, N mal N minus 1 halbe mal 1 durch 365
gleich 1, kann ich nach N auflösen.
Was habe ich gehört, das heißt Mitternachtsformel von Timo, das ist
gerade 1 halb plus Wurzel ein Viertel plus 730 und das ausgerechnet
ist ungefähr 26,52.
Das ist eine etwas andere Zahl als die 23, weil ich eine etwas andere
Definition habe, aber es gibt uns ein sehr gutes Gefühl dafür, ab wann
gleiche Geburtstage hier auftreten.
Vor allem können wir das jetzt auch schön verallgemeinern, also das
hier ist einfach 2 mal M, wenn ich einen Planeten nehme mit
Jahreslänge M.
Also wir haben sowas wie, 1 halb ist klein und ein Viertel ist klein,
aber das hier ist im Wesentlichen 2 mal die Jahreslänge.
Also die Anzahl Gäste, die ich haben muss auf einem beliebigen
Planeten ist ungefähr Wurzel 2 mal die Tageslänge.
Und das gilt jetzt halt auch für die Frage, wie groß muss meine
Hashtabelle sein, damit ich eine perfekte Hashtfunktion kriege, das
ist sowas wie quadratisch, es kommt da raus.
Gibt es Fragen zu dieser Rechnung mit dem Geburtstagsparadoxon?
Genau, das habe ich schon gesagt.
Die Standardformulierung ist, ab wann lohnt es sich zu wetten, dass
zwei Gäste mit gleichem Geburtstag da sind.
Da muss man ein bisschen mehr rechnen, da kommt dann N-Größe gleich 23
raus.
Das mit der Hashtabelle habe ich auch gesagt.
So, dann kommen wir jetzt zur Analyse unserer Hashtabellen-Geschichte.
Wir wollen folgenden Satz beweisen.
Für beliebige Schlüsselwerte k, behaupten wir, ist die erwartete
Anzahl kollidierender Elemente O von 1.
Das gilt nicht universell, sondern es genügt, dass unsere Tabelle
linear groß ist in der Menge der Eingaben.
Das gilt sicherlich nicht, wenn ich die Tabelle irgendwie nur 2 groß
mache.
Dann teilt sich alles auf zwei Tabelleneinträge und offenbar ist der
Erwartungswert dann linear.
Aber es genügt, die Tabelle linear zu skalieren mit der Anzahl
Elemente, die ich abspeichern will.
Im Gegensatz zu dem quadratischen, was ich brauchen würde, wenn ich
perfekte Hash-Funktionen haben will.
Warum interessiert mich das?
Die Anzahl kollidierender Elemente ist im Wesentlichen auch die
Ausführungszeit der Funktionen find und remove.
Das war ja Listenlänge.
O von Listenlänge war die Ausführungszeit.
Und die Listenlänge ist gerade die Anzahl kollidierender Elemente plus
minus 1, je nachdem, ob das Element da jetzt drin ist oder nicht.
Die Insert-Funktion ist sowieso konstant, da gibt es nichts zu
analysieren.
Also wenn ich diesen Satz hier bewiesen habe, dann weiß ich auch, die
erwartete Ausführungszeit der Operationen für meine Hash-Tabelle ist
konstant.
Und das ist, was ich haben will.
So, Beweis.
Wir nehmen jetzt mal einen festen Schlüssel, K, und definieren für
dieses K eine Zufallsvariable X.
Das nennen wir die Kollisionslänge.
Das ist einfach die,
wo steht das, M-Strich definiert, ah, hier unten, ja.
Wir definieren jetzt einen M-Strich, das sind gerade die Elemente mit
Schlüsselungleich K.
Die Elemente mit Schlüssel K interessieren uns hier nicht, weil da
gibt es halt höchstens eins von, und das steht da halt, und das ist da
nicht, und dann steht es da nicht, und diese Fallunterscheidung wollen
wir uns sparen.
Deshalb gucken wir uns jetzt nur die Elemente M-Strich an, die nicht
da drin sind.
Und abgesehen von diesem einen Element ist das im Wesentlichen die
Listenlänge, also T von H von K, weil der Tabelleneintrag an der
Stelle H von K, oder aber mengentheoretisch auch so die Menge aller
Elemente aus M-Strich, die mit diesem Schlüssel kollidieren, die also
den gleichen Hash-Funktionswert haben.
Das möchte ich ausrechnen.
Wie viele andere Elemente in meiner Menge kollidieren mit einem
bestimmten Schlüssel?
Oder wie viele Elemente in der Menge kollidieren damit, die nicht den
gleichen Schlüsselwert haben?
Das ist jetzt eine relativ komplizierte Hash-Funktion, eine relativ
komplizierte Zufallsvariable, und die Idee ist jetzt, die als eine
Summe von Indikatorzufallsvariablen auszudrücken.
Weil mit denen kann ich viel leichter rechnen.
Und das geht tatsächlich.
Ich definiere jetzt Indikatorzufallsvariablen X, E für Elemente aus M
-Strich.
Und zwar ist die Indikatorzufallsvariable 1, wenn eine Kollision
stattfindet, also H von E gleich H von K und 0 sonst.
So, jetzt kann ich rechnen.
Der Erwartungswert meiner Kollisionslänge X ist,
naja, also das Schöne ist, das X ist jetzt gerade die Summe der
Indikatorzufallsvariablen.
Also ich summiere über alle Elemente aus M-Strich, schaue, kollidiert
es?
Wenn ja, addiere 1.
Wenn es nicht kollidiert, interessiert mich nicht, addiere 0.
Also, X ist gleich Summe E in M-Strich X, E und damit ist
Erwartungswert von X gleich Erwartungswert der Summe E in M-Strich X,
E.
Jetzt wende ich wieder Linearität des Erwartungswerts an, ziehe also
diesen Erwartungswertoperator nach innen, Summe E in M-Strich
Erwartungswert von X, E.
Jetzt wende ich wieder die Erkenntnis an, dass der Erwartungswert
einer Indikatorzufallsvariable gleich der Wahrscheinlichkeit ist, dass
man eine 1 hat.
Also, ich kriege Summe E in M-Strich, Wahrscheinlichkeit, dass X, E
gleich 1 ist.
Naja, die Wahrscheinlichkeit, dass eine Kollision stattfindet, haben
wir schon ausgerechnet, ist 1 durch M.
Die Anzahl Summanden, die ich habe, ist M-Strichbetrag, also kriege
ich insgesamt als Erwartungswert von E, X, M-Strichbetrag durch M.
Ja, und ich habe jetzt gesagt, ich wähle M so, dass M-Betrag gleich O
von M ist.
Und dann ist das Ganze hier, dann steht hier O von M durch M und das
ist gerade O von 1.
Also die erwartete Kollisionslänge ist 1 und damit ist auch die
erwartete Ausführungszeit 1.
Und zwar für unsere Annahme, dass wir zufällige Hash-Funktionen
verwenden.
So, jetzt geht meine Frage an die Übungsleiter.
Ich bin heute mal ein bisschen langsamer als sonst.
Soll ich den Beweis jetzt zu Ende führen oder braucht ihr ganz
unbedingt...
Dann könnt ihr ja vielleicht nächstes Mal, wenn ich früher fertig bin,
übergebliebene Übungssachen machen oder sowas.
Okay, dann mache ich jetzt weiter, weil ich hoffe, Sie sind jetzt
warm.
Und dann haben wir diese Beweise durchgezogen und dann können wir die
Übung nochmal wiederholen oder so.
Aber nicht nochmal von vorne anfangen nächste Woche.
Okay, also sind wir jetzt fertig?
Haben wir jetzt gezeigt, dass Hashing mit linearer Verkettung eine
praktikable Datenstruktur ist, die zuverlässig und erwartet konstante
Ausführungszeit liefert?
Oder gibt es ein Problem?
Jetzt dürfen Sie natürlich nicht auf die nächste Folie weiterblättern.
Genau, also die Aussage war, naja, wie lange dauert es denn, diese
Hash -Funktion auszuwerten?
Und das ist tatsächlich eine Möglichkeit, das Problem zu sehen.
Also ich kann natürlich sagen, ja, ich kann Ihnen eine Möglichkeit
geben, wie man die Hash-Funktion in konstanter Zeit auswerten kann,
aber das wollen Sie nicht wissen, weil dann muss ich die tabellieren.
Ja, ich habe eine große Wertetabelle für jeden möglichen Schlüssel,
generiere ich einen Zufallswert, habe ich eine riesige
Initialisierungszeit, riesigen Platzverbrauch und dann ist danach
alles schnell, aber das will ich irgendwie nicht.
Ansonsten ist irgendwie nicht so klar, wie ich auch... also ich habe
erst gesagt, eine perfekte Hash-Funktion ist schwierig zu kriegen.
Bei näherem Hinsehen ist es auch schwierig, eine zufällige Hash
-Funktion zu bauen oder teuer.
Ja, also ich muss mir was anderes ausdenken.
Es gibt tatsächlich Methoden, zufällige Hash-Funktionen nachzubauen,
ohne viel Platzverbrauch, aber es ist immer noch irgendwie
Platzverbrauch, ich glaube linear in der Größe von M.
Und dann auch abhängig von M, das heißt, wenn Sie das dynamisch
machen, ist das wieder schwierig.
Das wollen Sie auch nicht wissen, wie das geht.
Das ist ziemlich komplizierte theoretische Informatik.
Die Lösung, die Sie in den meisten anderen Algorithmen-Lehrbüchern
finden, ist fast noch schlimmer.
Die analysieren den Algorithmus dann nicht für zufällige Hash
-Funktionen, sondern für zufällige Schlüssel.
Und das ist Unsinn, weil in der Praxis haben Sie eben nicht zufällige
Schlüssel, sondern Schlüssel, die aus einer bestimmten Anwendung
kommen.
Zum Beispiel in einem Compiler irgendwie Bezeichner Ihres Programms
und welcher Programmierer wählt schon zufällige Bezeichner?
Höchstens, wenn man irgendwie Programmieraufgaben unkenntlich machen
will oder so.
Tritt also gar nicht auf.
Zufällige Schlüssel wollen wir nicht.
Wir wollen ja gerade mit unserer theoretischen Analyse
Leistungsgarantien für die Praxis kriegen.
Und das kriegen Sie mit einer Analyse für zufällige Schlüssel nicht.
Sie kriegen da vielleicht irgendwie eine Intuition, dass das Ganze
vielleicht funktionieren könnte.
Aber wenn Sie dann die falsche Hash-Funktion haben, funktioniert es
dann in der Praxis doch nicht.
Und das wird sogar beobachtet.
Also was ja in der Praxis passiert, ist, dass man Ad-Hoc-Hash
-Funktionen verwendet, über die man nicht unbedingt etwas beweisen
kann.
Und dann geht es halt manchmal schief.
Und ich möchte Ihnen hier eine Möglichkeit vorstellen, Hash-Funktionen
so zu wählen, dass es garantiert nicht schief geht.
In einer gewissen wohlspezifizierten Art und Weise und die außerdem
sehr praktikabel sind.
Die Idee nennt man universelles Hashing.
Die Idee ist ganz einfach, die kann man am besten an diesem Bild hier
erläutern.
Dieses Omega bezeichnet die Menge aller Hash-Funktionen.
Bisher war das unser Wahrscheinlichkeitsraum.
Und er ist halt riesig.
Und es ist schwierig, aus diesem riesigen Raum gleich verteilte
Funktionen auszuwählen und dann auch konsistent zu verwenden.
Was wäre, wenn ich eine kleine Teilmenge H von Omega wähle und aus
dieser kleinen Teilmenge zufällige Hash-Funktionen wähle?
Also ich nehme bestimmte Hash-Funktionen, die ich effizient auswerten
und effizient speichern kann und wähle aus denen ein zufälliges
Element.
Und da muss man sich fragen, welche Eigenschaft muss dieses H haben,
damit das Ganze gut funktioniert?
Also ich hätte jetzt gerne Hash-Funktionen, die die Eigenschaft haben,
dass diese Analyse, die ich hier gemacht habe, immer noch
funktioniert.
Und diese Analyse beruhte im Wesentlichen darauf, dass ich für ein
beliebiges Element E in M' eine Kollisionswahrscheinlichkeit von 1
durch M habe.
Dann nehme ich das doch, um die Eigenschaften von H zu definieren.
Ich sage, eine Menge von Hash-Funktionen A ist universell, falls für
beliebige Schlüssel x und y, die ungleich sind,
und zufällig gewählte konkrete Hash-Funktionen klein H aus groß H
gilt, die Kollisionswahrscheinlichkeit ist 1 durch M.
Also die Wahrscheinlichkeit, dass der Hash-Funktionswert von x gleich
dem Hash-Funktionswert von y ist, ist 1 durch M.
Wenn ich diese Eigenschaft habe, funktioniert die Analyse weiterhin.
Und die Idee ist, vielleicht finde ich ja ganz einfache und ganz
kleine Teilmengen H, die diese Eigenschaft schon haben.
Also zunächst mal der Satz, den wir dann am Ende haben.
Wenn wir eine universelle Hash-Funktion haben, dann gilt Theorem 1
weiter.
Der Beweis ist ganz einfach, wir setzen Omega gleich H und machen den
Beweis einfach nochmal durch.
Also jeder einzelne Schritt, den ich hier gemacht habe, funktioniert
hier genauso.
Weil die ganzen Rechnungen hier funktionieren sowieso für jeden
Wahrscheinlichkeitsraum.
Und die einzige Stelle, wo ich was gebraucht habe, ist, wo ich diese
Wahrscheinlichkeit hier ausgerechnet habe.
Und die muss 1 durch M sein und genau das verlangt unsere Definition
universeller Hash-Funktionen.
Also bin ich fertig.
So, bin ich jetzt fertig?
Habe ich jetzt nachgewiesen, dass Hashing mit linearer Verkettung
praktikabel und effizient ist?
Wäre es der Meinung, dass wir jetzt fertig sind?
Nein, Sie können da nicht gehen.
Wäre es der Meinung, dass wir jetzt fertig sind, auch wenn Sie da
nicht gehen dürfen?
Einzelne.
Wer ist der Meinung, dass wir nicht fertig sind?
Ja, die haben recht.
Die anderen sind keiner Meinung.
Oder denen ist es zu doof, das zu sagen.
Natürlich kommen noch Folien.
Wir müssen jetzt natürlich noch konkrete solche Familien, universellen
Familien von Hash-Funktionen angeben.
Es könnte ja sein, dass das ganz schwierig ist oder die ganz teuer
auszuwerten sind.
Und dann wird uns diese Definition natürlich nichts nützen und auch
dieser Satz 2 nicht.
Das heißt, ich muss zumindest eine solche universelle Familie von Hash
-Funktionen angeben, die irgendwie effizient auswertbar ist.
Ich werde sogar mehrere solche Funktionen angeben und für eine werde
ich auch den Beweis durchführen.
Und zwar, ich mache hier eine vereinfachende Annahme, dass meine
Tabellengröße eine Primzahl ist.
Das kann man irgendwie rechtfertigen, indem man dann im Zweifel eine
etwas größere Tabelle nimmt, deren Größe eine Primzahl ist oder sowas.
Und ich kodiere meinen Schlüssel jetzt so, dass ich sage, das
funktioniert jetzt erstmal nur für Schlüssel fester Größe, nicht für
Strings oder so, lässt sich aber anpassen.
Ich schreibe meine Schlüssel jetzt als k-dimensionale Vektoren, wo
jede Komponente eine Zahl zwischen 0 und m-1 ist.
Das ist ohne Beschränkung der Allgemeinheit.
Also wenn zum Beispiel Ihre Tabellengröße eine schöne Primzahl 31 ist
oder sowas,
dann nehmen wir die Primzahl 65.
Ist das eine Primzahl?
Nein, Quatsch, das ist ja durch 5 teilbar.
67, ja, die Primzahl 67.
Ich hoffe, 67 ist eine Primzahl.
Dann nehmen Sie erstmal eine Binärkodierung Ihrer Schlüssel und hacken
die in Teile zu 6 Bits.
Das sind Zahlen zwischen 0 und 64 und damit auch Zahlen zwischen 0 und
67 -1.
Die letzten Werte verwenden Sie gar nicht.
Und so können Sie dann sehr einfach beliebige Werte durch Vektoren von
Zahlen zwischen 0 und Primzahl minus 1 kodieren.
Oder anders ausgedrückt, Sie können Ihre Schlüssel als Zahlen zur
Basis m kodieren.
Und wenn ich diese Umkodierung vorgenommen habe, die ich natürlich
auch effizient durchführen kann, ich muss halt nur Gruppen von Bits
extrahieren, dann kann ich relativ einfach definieren, was meine Hash
-Funktion hier macht.
Und zwar, ich brauche ja jetzt ganz viele Hash-Funktionen.
Die werden aber alle charakterisiert durch einen k-dimensionalen
Vektor von Koeffizienten.
Das sind auch wieder Zahlen zwischen 0 und diese Primzahl minus 1.
Und meine Hash-Funktion, wenn ich jetzt einen konkreten Vektor a habe,
dann ist der Hash-Funktionswert für einen konkreten Eingabevektor x
einfach das Skalarprodukt von a und x, Modulo der Primzahl m.
Und die Menge aller Hash-Funktionen, die ich so kriege, h a für die
gilt, a ist in 0 bis m minus 1 hoch K, nenne ich h Punkt, weil Punkt
das Skalarprodukt ist.
Und ich beweise, h Punkt ist eine universelle Familie von Hash
-Funktionen.
Sie können sich das auch bildlich vorstellen, also Sie zerhacken Ihren
Schlüssel in kleine Stücke, Sie multiplizieren das i-te Stück des
Schlüssels mit dem i-ten Koeffizienten, addieren die ganzen Werte auf
und nehmen das Ergebnis Modulo m.
Das ist eine Zahl zwischen 0 und m minus 1 und gibt Ihnen eine
Position in der Hash-Tabelle an.
Beispiel.
Hier habe ich jetzt nur noch mal die Definition von dem h a von x.
Nehmen wir mal an, die Tabellengröße ist 11, die Dimension ist 3 und
unser a ist der dreidimensionale Vektor 815.
Und unser Schlüssel ist 112.
Vielleicht haben Sie hier eine Telefonnummernliste und Sie wollen die
Nummer der Feuerwehr ablegen.
Dann ist der Hash-Funktionswert von 112 bezüglich 815 ist halt 815
Skalarprodukt 112.
8 mal 1 plus 1 mal 1 plus 5 mal 2 ist 19.
Modulo 11 ist 8.
Gibt es Fragen zur Definition von h?
Also denkbar einfach, also komponentenweises Multiplizieren und am
Ende noch eine Modulo-Operation.
Naja, wieso mache ich das?
Beweis.
Und der ist tatsächlich wieder eine einzige Folie, aber mit ziemlich
viel Mathe drauf, da müssen wir uns wieder ein bisschen Zeit nehmen.
Und danach höre ich aber auch auf, d.h.
danach kommt die Übung.
Diese Dinger machen wir dann beim nächsten Mal zum Vertiefen, aber
jetzt müssen wir durch diese eine Folie noch durch.
Dann sind Sie über den Berg sozusagen.
Also ich möchte zeigen, dass die Kollisionswahrscheinlichkeit zwischen
zwei beliebigen Schlüsseln, die unterschiedlich sind, 1 durch m ist.
Jetzt gucke ich mir diese beiden Schlüssel mal an, x und y, das seien
zwei beliebige Schlüssel, die unterschiedlich sind.
Da, die unterschiedlich sind, gibt es mindestens eine Position j, wo
sich auch die Koeffizienten unterscheiden.
Also nehmen wir an, xj ungleich yj.
Und jetzt mache ich Kombinatorik.
Ich zähle die möglichen Werte für a und damit auch die möglichen
Hashfunktionen aus meiner hoffentlich universellen Familie, für die
eine Kollision stattfindet.
Also für die gilt ha von x gleich ha von y.
Die Idee ist jetzt das folgende.
Ich behaupte jetzt das folgende.
Ich schaue mir erstmal die Werte, die Auswahl der Koeffizienten von a
an für die Positionen ungleich j.
Also die Werte von ai für i ungleich j.
Und dann behaupte ich, für jede Wahl, die ich da treffe, gibt es genau
eine Wahl von aj, sodass eine Kollision stattfindet.
Und das werde ich jetzt beweisen.
Und das ist einfach Rechnerei.
Und ich denke, das ist auf dem Niveau, was Sie in lineare Algebra
machen, oder sogar deutlich darunter.
Sie müssen nur jetzt die Schublade lineare Algebra aufmachen und da
auch dran denken, wie war denn das mit Modulorechnungen und ähnlichen
Körpern und sowas.
Sagen Sie mir, wenn ich falsch liege, weil das da noch nicht dran war,
aber das würde mich jetzt ein bisschen erstaunen.
Also wir wollen wissen,
wie muss ich aj wählen, sodass Summe i a i x i kongruent zu Summe i a
i y i Modulo m.
Das schreibe ich jetzt einfach um.
Ich lasse die Sachen mit j auf die linke Seite und alles andere bringe
ich auf die rechte Seite.
Dann steht hier aj xj minus aj yj.
Und das kann ich schreiben als aj mal xj minus yj.
Ist kongruent zu... naja, was stand hier?
Die Summe i a i y i.
Aber jetzt summiere ich nur die i, bei denen i ungleich j ist.
Und ich muss subtrahieren, was hier stand.
Das ist eben minus a i x i für i ungleich j.
Und das ganze kongruent Modulo m.
Und jetzt kommt die Stelle, an der die mathematische Magie reinkommt.
Ich habe einfach vom Himmel fallen lassen, m muss eine Primzahl sein.
Wieso eigentlich?
An dieser Stelle brauche ich es.
Die ganzen Zahlen Modulo einer Primzahl bilden einen endlichen Körper.
Und das ist jetzt ganz wichtig, weil in einem endlichen Körper kann
ich dividieren.
Oder genauer gesagt, bezüglich der multiplikativen Gruppe dieses
Körpers habe ich ein inverses Element.
Allerdings nur für den Fall, dass ich nicht die Null habe.
Zwischen Null kann ich nicht dividieren in einem Körper.
Aber das passt genau, weil ich weiß x i x j ungleich y j.
Das heißt, x j minus y j ist ungleich Null.
Das heißt, es gibt ein eindeutig bestimmtes inverses Element.
Und das eindeutig ist jetzt auch wichtig.
Also diese Konkurrenz gilt genau dann, wenn die folgende Konkurrenz
gilt.
Ich multipliziere einfach auf beiden Seiten mit dem eindeutig
bestimmten inversen Element von x j minus y j.
Das schreibe ich jetzt als x j minus y j hoch minus 1.
Also ich multipliziere auf beiden Seiten mit dem inversen Element
davon.
Dann verschwindet das hier.
Dann steht da a j kongruent komplizierte Formel.
x j minus y j invers mal diese komische Summe.
Mich interessiert gar nicht, was das für ein Wert ist.
Das einzig Wichtige ist, das ist ein eindeutig bestimmter Wert.
Das heißt, ich habe eine und genau eine Wahl für a j, für die gilt,
dass x und y kollidieren.
Und zwar für beliebige Wahlen der anderen Koeffizienten a i, i
ungleich j.
Und jetzt fange ich an zu zählen.
Wie viele Möglichkeiten habe ich, die Koeffizienten a i mit i ungleich
j auszuwählen?
Das sind gerade m hoch k minus 1.
Also ich habe k minus 1 Stellen, die ich auswählen kann.
An jeder Stelle kann ich m Werte wählen.
Wie viele Werte habe ich insgesamt?
Das sind m hoch k.
Was ist die Wahrscheinlichkeit, dass die beiden kollidieren?
Das ist einfach das Verhältnis von den beiden.
m hoch k minus 1 durch m hoch k ist 1 durch m.
Das ist genau das, was ich zeigen wollte.
Ich habe also gezeigt, h Punkt ist eine universelle Familie von Hash
-Funktionen.
Ich habe gezeigt, Hashing mit linearer Verkettung und Hash-Funktionen,
die ich zufällig aus dieser universellen Familie h Punkt auswähle, ist
ein Algorithmus zur Verwaltung von Wörterbüchern mit erwartet
konstanter Ausführungszeit aller wichtigen Operationen.
Jetzt muss ich noch argumentieren.
Ja, die Hash-Funktion auswählen geht auch schnell, wenn k eine
Konstante ist.
Das ist jetzt hier meine Annahme.
Aber wenn k keine Konstante ist, habe ich halt irgendwie große
Schlüssel und das Ganze ist immer noch linear in der Länge meines
Schlüssels.
Das ist also auch effizient.
Aber ich will die Formel nicht zu kompliziert machen, nehme deshalb
an, meine Schlüssel sind konstant viele Maschinenwörter.
Dann kann ich die Hash-Funktion auch in konstanter Zeit auswählen.
Also habe ich gezeigt, was ich will.
Beim nächsten Mal werden wir noch zwei weitere universelle Familien
kurz kennenlernen.
Und dann stelle ich ein anderes Verfahren für Hashing vor, das in der
Praxis manchmal noch einfacher, noch schneller ist.
Und das ist ein guter Punkt.
Gibt es noch Fragen zu dem, was ich heute gemacht habe?
Dann ist das ein guter Punkt, um nochmal 20 Minuten Übungen zu machen.
Genau, was wollen wir heute erzählen?
Also ich hätte jetzt mal kurz eine Folie, was wir organisatorisch
erzählen.
Und dann wird Sebastian nochmal näher auf Hashing eingehen, auf eine
interessante Anwendung aus der aktuellen Forschung.
Folgendes, wir bringen diese Woche auf dem Übungsblatt die erste
Programmieraufgabe.
Es wird darum gehen, einen erwarteten OV1-Pager zu implementieren.
Eigentlich eine ganz interessante Aufgabe.
Man kombiniert auf eine interessante Weise Hashing mit verkehrten
Listen, mit eben doppelt verkehrten Listen.
Das Blatt ist schon draußen.
Sieht so aus, wenn es richtig angezeigt werden würde.
Und sehr nett beschrieben hier.
Und nähere Informationen dazu gibt es auch in der Vorlesung vom
letzten Jahr, haben wir auch noch verlinkt.
Die Abgabe von dieser Programmieraufgabe erfolgt über den Park
Tomaten, den ihr anscheinend alle schon kennt auch.
Die Website habe ich hier nochmal angegeben.
Geht da drauf, meldet euch an mit eurem KIT-Account und da seht ihr
noch ein bisschen Informationen.
Dann könnt ihr fleißig abgeben und irgendwann wird es dann korrigiert,
auch von den Tutoren.
Im Gegensatz zu der vorherigen Vorlesung im letzten Semester, die ihr
gehört habt, werden wir darauf verzichten, Code-Styles zu überprüfen.
Es ist nicht notwendig, diese Prüfung zu bestehen.
Aber trotzdem solltet ihr natürlich euren Code gut formatieren und
Kommentare verwenden.
Plagiat ist verboten, klar.
Also nicht abschreiben, auch nicht untereinander.
Auch nicht aus dem Internet, das gibt null Punkte.
Diese andere Bestrafung, die es da so gibt.
Aber trotzdem ist es erlaubt, zu zweit abzugeben.
Wenn ihr das machen wollt, zu zweit abgeben, dann schreibt einfach in
den Kommentar oder so,
eure beiden Namen und Matrikelnummer drauf.
Okay, das war es schon von mir.
Wir haben jetzt während der Vorlesung die Übung schon zweimal
umgebaut.
Jetzt muss ich trotzdem noch ein paar Folien skippen, die holen wir
dann beim nächsten Mal nach.
Und kommen zu einer Anwendung von Hashtabellen, nämlich der Duplikat
-Erkennung.
Wir haben also das Problem, wir geben eine Folge von Zahlen, hier N
-Zahlen.
Die Frage, enthält meine Liste von N-Zahlen Duplikate, also gleiche
Zahlen, ja oder nein?
Wie könnte man das machen?
Ein erster Ansatz wäre, ich löse das Ganze durch Sortieren.
Das heißt, ich sortiere meine Liste von Zahlen und dann habe ich den
schönen Effekt, dass gleiche Zahlen nebeneinander stehen.
Das heißt, in dem Moment muss ich einfach einmal durch die Liste dann
noch durchlaufen und gucke, sind benachbarte Zahlen gleich?
Wenn ich so ein benachbartes Zahlenpaar gefunden habe, kann ich
aufhören und kann sagen, ja, hier sind Duplikate drin.
Wie wir noch sehen werden in der Vorlesung, hat es allerdings eine
Worst -Case-Laufzeit von Omega von NlogN.
Das werden wir, glaube ich, nächste Woche dann sehen.
Wir wollen das Ganze schneller machen, nämlich erwarte den Linearzeit
und das Ganze lösen wir mit Hashtabellen.
Der Algorithmus ist eigentlich ganz einfach.
Ich nehme eine Hashtabelle hier, füge nacheinander meine Zahlen ein
und schaue dann immer nach, ist die Zahl schon in meiner Hashtabelle
drin.
Wenn ich sie schon gefunden habe, bin ich fertig, kann sagen, ja, ich
habe ein Duplikat gefunden.
Ansonsten mache ich gerade weiter.
Das Ganze hat erwartete Laufzeit in O von N.
Wenn ich eine zufällige Hash-Funktion wähle und wenn natürlich meine
Hashtabelle groß genug ist.
Machen wir das Ganze mal an einem Beispiel.
Ich habe meine Folge von Zahlen und habe eine einfache Hash-Funktion,
hier einfach Modulo 7.
Füge da jetzt ein paar Elemente ein.
Und genau hier gibt es jetzt die erste Kollision.
Und das löse ich jetzt hier, wie wir auch in der Vorlesung gesehen
haben, mit einer verketteten Liste.
Das heißt, ein Insert geht wirklich in konstanter Zeit.
Ich füge das einfach am Kopf dieser verketteten Liste ein.
Und füge noch eins ein.
Und genau, jetzt komme ich zur 18, die schon drin ist.
Und jetzt komme ich an diese Position und muss diese verkettete Liste
hier langlaufen.
Das heißt, diese Find-Operation hat keine konstante Laufzeit, sondern
ist ein O von der Länge der Liste.
Das ist das Ganze nochmal im Pseudocode, das können wir jetzt in
Anbetracht der Zeit überspringen.
Schauen wir uns eine kurze Laufzeitanalyse an.
Ja, wir haben zwei Schritte.
Zum einen muss ich diese Hash-Tabelle anlegen.
Und dann muss ich diese Elemente da einfügen und immer nachgucken, ob
das Element drin ist oder nicht.
Das Erzeugen geht in Zeit O von der Tabellengröße.
Ich muss die Tabelle anlegen, muss alle Slots mit meinem Null-Pointer
initialisieren.
Und danach füge ich Schritt für Schritt diese Elemente ein.
Das Einfügen geht in konstanter Zeit.
Und für diese Find-Operation geht in O von der Listenlänge.
Aber, wie wir schon gesehen haben, ist es erwartet konstante Laufzeit,
wenn die Hash-Tabelle eben groß genug ist.
Und wir diesen Satz aus der Vorlesung immer gesehen haben, dass die
erwartete Listenlänge eben konstant ist.
Und somit habe ich also einen Linearzeitalgorythmus, der mir diese
Duplikate findet, indem ich eine Hash-Tabelle verwende.
Soweit ein einfacher Teil.
Bei Hashing haben wir gesehen, wir wollen immer irgendwie zu einem
Schlüssel ein Objekt ablegen.
Jetzt schauen wir uns eine Datenstruktur an, die nennt sich
Bloomfilter.
Und die ist ein Membership-Tester.
Also eine Datenstruktur, die mir nur sagt, gehört ein Element zu einer
Menge oder gehört es nicht dazu.
Und das Ganze ist auch noch approximate, also ungenau.
Die Datenstruktur darf Fehler machen.
Ziel ist also eine Menge von Elementen, die irgendwie groß sind, im
Vergleich zu unserem Bloomfilter, zu repräsentieren.
Und wir wollen zwei Operationen unterstützen, nämlich den Einfügen und
so einen Containment-Check, ist mein Element drin, ja oder nein.
Und zusätzlich lassen wir noch zu, dass diese Datenstruktur Fehler
machen darf.
Wenn ich so eine Contains-Abfrage mache und die liefert mir Falls
zurück, dann ist das Element auch wirklich nicht in der Menge drin.
Wenn ich aber eine Contains-Abfrage mache und die liefert mir True
zurück, dann kann es sein oder ist es sehr wahrscheinlich, dass das
Element drin ist.
Vielleicht macht die Datenstruktur aber auch einen Fehler.
Jetzt kann man sich überlegen, macht sowas überhaupt Sinn, wird es
gebraucht?
Und es ist tatsächlich so, also historisch kommt das Ganze aus dem
Spellchecking.
Ich will also in den Text gucken, ob die Wörter richtig geschrieben
sind.
Dafür hat Herr Bloom die Datenstruktur erfunden.
Damals war irgendwie Hauptspeicher knapp, ich konnte also so ein
ganzes Wörterbuch gar nicht im Hauptspeicher halten.
Und er hat sich diese Datenstruktur ausgedacht und damit konnte man
dann überprüfen, ist das Wort richtig geschrieben, ja oder nein, ist
es in meinem Wörterbuch drin.
Und man hat gesagt, okay, wenn manchmal ein Wort als richtig
geschrieben erkannt wird, obwohl es falsch ist, kann man das
hinnehmen.
Genauso wird es auch eingesetzt beim Webcrawling.
Wenn ich sehen will, habe ich meine Webseite schon besucht, dann will
ich auch nicht den ganzen Text da irgendwie durchforsten, was da drauf
steht.
Und zumindest bis 2010 war die Datenstruktur auch im Google Chrome
Browser integriert.
Da ging es darum, schädliche Webseiten zu erkennen.
Und da war die Idee, jeder von euch, der den Chrome Browser nutzt,
hatte eben so einen Blumenfilter lokal bei sich.
Und wenn dann eine Webseitenanfrage kam, hat man in den Blumenfilter
reingeguckt, ist diese Webseite schädlich, ja oder nein.
Im Fall von nein war klar, okay, der User kann da drauf.
Und falls er schädlich war, hat dann der Browser nochmal beim Google
Service nachgefragt, ist er denn wirklich schädlich, ja oder nein.
Und somit hat man diesen Webservice, der das Ganze immer wirklich
überprüft, entlastet.
Weil die Großzahl der Checks wurden lokal bei jedem auf dem Rechner
gemacht.
Jetzt natürlich die Frage, okay, wie sieht denn diese Datenstruktur
hier aus?
Also was wir machen, wir wollen n Elemente einfügen und brauchen dafür
k Hash-Funktionen.
Und das Einzige, die Datenstruktur an sich, ist dann ein Array von m
Bits.
Und damit sehen die Operationen, die wir unterstützen wollen, wie
folgt aus.
Ich mache einen Insert, indem ich mein Element k mal hashe und die
entsprechenden Bits in diesem Bit-Array auf eins setze.
Ein Containment-Check ist dann nämlich das folgende, ich hashe wieder
und nur wenn alle meine k Bits auf eins gesetzt sind, sage ich ja, das
Element ist in meinem Blumenfilter, ansonsten gebe ich Falls zurück.
Da habe ich auch noch ein kurzes Beispiel mitgebracht.
Hier, wir haben einen Blumenfilter mit 32 Bit, nehmen vier Hash
-Funktionen, fügen da jetzt ein Element ein.
Diese unterschiedlich bunten Pfeile sind eben die verschiedenen Hash
-Funktionen.
Setzen diese vier Bit, wenn ich jetzt eben direkt eine Containment
-Abfrage machen würde, hashe ich ja wieder genau auf diese vier
Positionen und sehe ja, alle vier Bits sind gesetzt, mein Element ist
im Blumenfilter enthalten.
Wenn ich eine weitere Query mache und frage, ist mein X2 denn im
Blumenfilter drin, dann kann es sein, dass ich zufällig an irgendeiner
Stelle lande, an dem so ein Bit gesetzt ist, aber ich finde auch eins,
bei dem es null ist.
Sobald ich eine Null gefunden habe, bin ich mir sicher, nein, mein
Element ist nicht im Set.
Wenn ich das jetzt auch einfüge, kommen wir zu dem Fall, ab dem die
Datenstruktur einen Fehler machen kann.
Es kann passieren, wenn ich jetzt hier mein Element Y abfrage, dass
ich zufällig auf vier Positionen lande, die auf 1 gesetzt sind.
In dem Fall wurden zwei Positionen von X1 und zwei Positionen von X2
auf 1 gesetzt.
Und genau in dem Fall sagt es die Datenstruktur, ja, Y ist drin,
obwohl es gar nicht in der Menge enthalten ist.
Und die spannende Frage ist natürlich, wie baue ich diese
Datenstruktur auf und wie groß ist denn diese
Fehlerwahrscheinlichkeit, mit der ich da eine falsche Aussage treffe.
Hier habe ich mal einen intuitiven Beweis mitgebracht, der nicht ganz
richtig ist, aber so eine grobe Approximation liefert.
Wir nehmen an, die Hash-Funktionen liefern Ergebnisse gleichverteilt
über dieses ganze Bit-Array und sind unabhängig voneinander.
Dann schauen wir uns die Wahrscheinlichkeit an, dass ein Bit nach N
inserts 1 ist.
Die Formel sieht ein bisschen kompliziert aus, aber wenn man es Stück
für Stück aufbaut, ist es eigentlich ganz intuitiv.
Der innere Teil hier ist die Wahrscheinlichkeit, dass ein beliebiges
Bit von einer beliebigen Hash-Funktion nicht auf 1 gesetzt wird.
Mit einer Wahrscheinlichkeit von 1 durch M setze ich ein Bit auf 1.
1 minus 1 durch M ist die Wahrscheinlichkeit, dass das Bit 0 wird.
Pro Einfügeoperation benutze ich ja kHash-Funktionen und ich mache
zusätzlich noch N inserts.
Ich inserte N Elemente.
Somit habe ich jetzt die Wahrscheinlichkeit, dass ein Bit nach dem
Einfügen von N Elementen gleich 0 ist.
Wieder das Gegenereignis davon und ich erhalte tatsächlich die
Wahrscheinlichkeit, dass ein Bit 1 ist nach N Elementen.
Und was man sich jetzt überlegen kann, ist die Wahrscheinlichkeit,
dass ich so ein false positive erwische.
Ah, ich bin zu weit.
Das kann man jetzt noch vereinfachen.
Dann kommt man hier auf das.
Das nehmen wir jetzt einfach der Zeit halber mal hin.
Und jetzt kann man sich überlegen, die Wahrscheinlichkeit für so ein
false positive ist ja genau die Wahrscheinlichkeit, dass meine kHash
-Funktionen allen 1 Bit liefern, obwohl ich sie eigentlich selbst gar
nicht gesetzt habe.
Und das ist dann nämlich genau einfach diese Wahrscheinlichkeit, dass
ich 1 Bit habe, hoch K.
Und damit, mit dieser Formel kann ich später noch ausrechnen, was ist
die optimale Anzahl an Hash-Funktionen, die ich brauche, dass ich so
ein N-Bit-Array mit minimaler Fehlerwahrscheinlichkeit bearbeiten
kann.
Jetzt war das alles recht abstrakt.
Schauen wir es uns an einem kurzen Rechenbeispiel an.
Nehmen wir an, ich habe irgendwie 100.000 Objekte.
Das können, was weiß ich, Strings sein, Webseiten, Wörter.
Und ich sage, ich hätte gerne einen Bloom-Filter, der eine Million
Bits hat.
Dann kann ich mit der Formel ausrechnen, okay, dann ist meine
Fehlerwahrscheinlichkeit minimal, wenn ich k gleich 7 Hash-Funktionen
verwende.
Und damit kriege ich eine Wahrscheinlichkeit für ein false positive
von unter einem Prozent.
Das heißt, nur in unter einem Prozent der Fälle macht meine
Datenstruktur einen Fehler.
Und damit kann ich da natürlich schon durchaus was anfangen.
Gibt es zu der Datenstruktur soweit mal Fragen?
Falls nicht, wird es jetzt noch spannend.
Kommen wir noch aus einem Beispiel, so ein Blick über den Tellerrand,
Beispiel aus der aktuellen Forschung vom letzten Jahr.
Jetzt geht es um verteilte Duplikaterkennung.
Wir wollen möglichst wenig Daten kommunizieren.
Zunächst mal das Problem, ich habe verschiedene Rechner, die
miteinander mit einem Netzwerk verbunden sind, und die haben eine
große Menge an Daten, zum Beispiel riesige Datenbanktabellen.
Und aus welchem Grund auch immer sind da Duplikate reingekommen, die
ich da nicht gerne drin hätte.
Dann ist die Frage, wie finde ich diese Duplikate so schnell wie
möglich und mit so wenig Kommunikation wie möglich.
Weil wenn die Rechner vielleicht weit weg auseinander stehen oder ich
nur ein LAN-Netzwerk dazwischen habe, kein schnelles Netzwerk, dann
ist die Kommunikation vielleicht teurer.
Und auch hier gibt es verschiedene Anwendungsbereiche in den
Datenbanken, für die Leute, die es mit Datenbanken auskennen.
Es gibt dieses Distink-Keyboard, das mir sagt, schmeiß mir alle
Duplikate aus meiner aktuellen Relation raus.
Und es kommt tatsächlich auch in der Wirtschaft vor, dass Firmen
riesige Datenmengen haben, in denen es nur ganz, ganz wenige
Inkonsistenzen gibt.
Und zusätzlich ist das Problem auch von theoretischer Natur her
interessant.
Ein ganz einfaches Beispiel, ein ganz einfacher Algorithmus nennt sich
Hash -basierte Repartitionierung.
Nehmen wir mal an, diese Boxen hier sind meine verschiedenen Rechner
und die Buchstaben da drin, beliebig große Datenobjekte.
Was dieser Algorithmus dann macht ist, er hasht jedes Datenelement und
verteilt die Range, auf die gehasht wird, wird verteilt über die
ganzen Rechner.
Also jeder der Rechner ist zuständig für einen Teil der Hash-Range.
So mit hashtischen Elements, guckt dann okay, für diesen Hash, welcher
Rechner ist da zuständig, schickt das Element an den Rechner hin und
der macht dann zum Beispiel diese Duplikaterkennung mit Hash-Tabellen,
die ich euch vorher gezeigt habe.
Während der Algorithmus so eigentlich relativ einfach ist, hat er den
unangenehmen Nebeneffekt, dass jedes Element mindestens einmal oder
genau einmal verschickt werden muss.
Wenn diese Elemente jetzt nicht gerade einzelne Buchstaben sind,
sondern riesengroße Datenbankzeilen, dann ist es wahrscheinlich zu
teuer.
Und die Kommunikation wird schnell das Bottleneck.
Was wir uns deswegen ausgedacht haben, war, dass man irgendwie vorher
schon Elemente rausfiltern will.
Wenn ich irgendwie eine Möglichkeit habe, um ein Element
festzustellen, welche Elemente sind denn garantiert nicht doppelt,
dann kann ich die einfach weglassen und in diesem zweiten Schritt
sende ich dann nur noch die Elemente, bei denen ich mir nicht sicher
bin, ob sie denn doppelt sind oder nicht.
Jetzt habe ich euch gerade vorhin den Blumenfilter vorgestellt.
Der macht ja genau sowas.
Ich gebe da irgendwie Elemente rein und wenn sie nicht drin sind, dann
sagt er mir das richtige Ergebnis.
Und wenn sie drin sind, dann sagt er ja vielleicht, ja oder nein.
Und was wir jetzt gemacht haben ist, wir haben uns einen speziellen
Blumenfilter angeguckt, nämlich den Blumenfilter, der nur eine Hash
-Funktion benutzt.
Damit ist meine Fehlerwahrscheinlichkeit auch direkt abhängig von der
Größe meines Bitarrays.
Und das ist natürlich ein bisschen unschön, wenn ich viele, viele
Elemente habe.
Dann brauche ich ein riesengroßes Bitarray und würde also auch
unendlich viel Speicher brauchen für das Ganze.
Es zeigt sich aber, dass man dieses Bitarray, wenn man damit geschickt
umgeht, kann man es komprimieren und landet dann bei sogar 30% weniger
Speicherplatz, als dieser traditionelle Blumenfilter brauchen würde.
Hat aber trotzdem noch die gleiche Wahrscheinlichkeit für einen False
Positive.
Und jetzt sind wir ja in einem Fall, in dem ich irgendwie mehrere
Rechner habe verteilt.
Also haben wir die Datenstruktur noch weiter auseinandergezogen, haben
gesagt, okay, dieses imaginäre riesengroße Bitarray verteile ich auf
die einzelnen Rechner.
Und wenn ich dann da Elemente einfügen will, naja, dann hasche ich
mein Element und sage dem einzigen Rechner jetzt noch, hier füge mal
dieses Element in den Filter hinzu, das ist drin.
Damit haben wir im Vergleich zu einem traditionellen Blumenfilter
schon mal direkt k-mal weniger Kommunikation, da ich ja nur einmal
haschen muss, um mein Element reinzusetzen.
Bei einem normalen Blumenfilter müsste ich ja k-mal haschen und
vielleicht k-Werte kommunizieren.
Also wenn ich diese Filterstruktur habe, dann sieht dieser ganze
Filteringprozess so aus, da will ich jetzt gar nicht im Detail drauf
gehen.
Es ist also nur, um diese Datenstruktur aufzubauen, diesen
platzeffizienten Filter, ist der Trick, dass ich mir nicht den ganzen
Filter aufbaue, also wirklich diese hunderttausende Millionen Bits,
dieses große Arrayaufbau, sondern ich merke mir nur die Stellen, an
denen eins gesetzt ist.
Und das sind dann meine Hash-Werte.
Und die sortiere ich, dann kann ich die effizient komprimieren,
verschicke die an alle, packe die im nächsten Schritt wieder aus und
dann mache ich so eine Zusammenführung dieser Hash-Werte.
Dann mache ich genau das, was dieser Blumenfilter macht.
Ich schaue mir die ganzen Pakete an, die ich von jedem enthalten habe
und gucke, sind da irgendwie zwei Hash-Werte doppelt.
Und wenn ja, dann ist es ja ein Indikator, okay, das Element könnte
doppelt sein.
Vielleicht ist es aber auch nur eine Hash-Kollision, das weiß ich ja
zu dem Zeitpunkt nicht.
Aber Elemente, die sicher nur einmal vorkommen, von denen weiß ich,
okay, die kommen global auch kein zweites Mal vor, deswegen kann ich
die im nächsten Schritt dann weglassen.
Und das merke ich mir eben und schicke das den Leuten, den
entsprechenden Knoten wieder zurück.
Ich sage also jedem Knoten, dein Wert 3, 4 und 5 kam vielleicht
doppelt vor, dafür sind die Werte 27, 42 und 18 sicher nicht doppelt.
Und das Ganze haben wir dann im Laufe meiner Masterarbeit auf
verschiedenste Arten und Weisen getunt.
Wir haben also alles, was irgendwie ging, parallelisiert.
Wir haben sortieren effizient gemacht, die Kommunikation getunt.
Und jetzt habe ich euch am Anfang diesen einfachen Algorithmus
gezeigt, der einfach nur was hasht, dahin schickt und der dann nochmal
lokal so eine Hashtabelle z.B.
aufbaut.
Und hier erzähle ich jetzt seit 10 Minuten, was in so einem Filter
aufbauen, ja, ich muss irgendwie hashten, ich muss sortieren, ich
komprimiere, ich dekomprimiere, ich merge.
Ist es den Aufwand wirklich wert?
Der Algorithmus sieht auf den Blick ja mal viel komplizierter aus und
viel aufwendiger aus, als das, was der andere Algorithmus macht.
Und das Ganze haben wir experimentell analysiert und es zeigt sich,
ja, es ist es tatsächlich wert.
Hier haben wir Eingabedaten, also 13 Gigabyte pro Rechnerknoten, Werte
von 16 Rechnerknoten bis 64.
Und dieser große Balken hier ist dieser naive Algorithmus, der einmal
alles hasht und einmal die Daten verschickt.
Und der andere Wert hier, das ist unser Algorithmus.
Und was sich zeigt, ist, dass obwohl wir so unheimlich viel
Mehraufwand haben, sind wir immer noch einen Faktor sechs schneller
als der naive Algorithmus und sind sogar wesentlich schneller, dreimal
so schnell, als der andere nur braucht, um seine 13 Gigabyte pro
Knoten zu verschicken.
Und es war ein Rechner, ein Parallelrechner hier an der Uni, der ein
verdammt schnelles Netzwerk hatte.
Aber wenn man da halt auch wirklich 13 Gigabyte pro Knoten durchjagt,
ist das Ding auch irgendwann verstopft.
Und genau hier ist es für den Fall, dass es keine Duplikate gibt,
jetzt kann man sagen, okay, das ist vielleicht auch ein bisschen
unfair.
Aber das Ganze funktioniert auch, wenn irgendwie bis zu 10 oder 25
Prozent meiner Einträge Duplikate sind.
Auch dann sind wir immer noch schneller, als wenn ich das naive
einfach einmal verschicken würde.
Und unsere initiale Aufgabe war ja, wir wollten möglichst wenig
Kommunikationsvolumen machen.
Also ist die Frage, liegt es wirklich an der Kommunikation?
Wenn man sich anschaut, wie viele Daten da hin und her geschickt
werden, dann verschicken unsere Algorithmen mehr als eine
Größenordnung weniger Daten als dieser klassische Algorithmus.
Gerade hier also im Fall von 64 Knoten jage ich fast einen Terabyte
Daten durchs Netz.
Und wir brauchen eben bei wenigen Duplikaten gerade mal 10 Gigabyte.
Und somit haben wir gezeigt, also in der Theorie hat sich das schon
herausgestellt gehabt, und wir konnten auch experimentell nachweisen,
dass der Algorithmus das tut, was er verspricht.
Und damit bin ich auch pünktlich noch fertig geworden.