So, hallo, ich begrüße Sie zur letzten Vorlesung.
Wir sind das letzte Mal stehen geblieben bei einem Wavel-Tree, einer
Index -Data-Struktur zur Lösung von Range-Queries.
Und da wiederhole ich mal schnell, was das war.
Ein Wavel-Tree über eine Punktmenge von Punkte im n-Kreis-n-Grid.
Das war so definiert, dass...
Also genau, hier hat man die Punkte gehabt von x1 bis xn und die
zweite Komponente war irgendwie Zahlen von 1 bis n.
Und genau, jetzt hat man die Punkte genommen, das Punkteset, und
rekursiv aufteilt nach dem Wert von dem x-Wert, anstelle i, und wenn
da der x-Wert kleiner war als n-Halbe, dann käme der linke Teilwurm an
den rechten Teilwurm und dann hat man das rekursiv so weitergemacht.
So, und was wir besprochen haben letztes Mal, ist dann wie man Count
-Queries löst, also gegebenen Rechteck, ich will lösen oder ich will
wissen, wie viele Punkte sind da drin.
Und das haben wir reduziert auf ein einfaches Problem.
Und zwar sind da quasi nicht alle vier Seiten frei, sondern nur zwei
Seiten.
Das heißt, eine Range-Dominance-Querie, das heißt, wie viele Punkte
liegen, sind größer als eine bestimmte xy-Koordinate.
Und wenn man das viermal löst, dann kann man jetzt hier diese blaue
Fläche berechnen, indem man quasi einmal dieses Gesamte nimmt, dann
die zwei Flächen hier oben und rechts abzieht und dann den Schnitt
wieder dazu zählt, wenn man das zweimal abgezogen hat, dieses
Dunkelrote hier, und dann kann man das allgemein lösen.
Das heißt, das einzige Problem war, diese Dominance-Querie zu lösen,
und das haben wir gezeigt, dass man da jeweils...
man hat quasi xy-Punkt, und jetzt, wenn das eben klein ist als in
halbe, diese x-Koordinate, dann gibt es zwei rekursive Aufrufe,
nämlich einmal... dann gibt es quasi einen rekursiven Aufruf in der
linken Teilbeamung rein, und man zählt hier alles dazu, wie groß die
rechte Teilbeamung ist, quasi rechts und größer, der y-Wert größer als
mein geforderte y-Wert ist, und dann diese Punkte hier drin, die haben
wir mit dem Rank-Querie berechnet, und bis zu dem Punkt, und dann
durch Abzug, also in halbe minus dieses Ding, gibt es die Punkte hier
oben, und dann haben wir quasi nur einen rekursiven Aufruf, also
entweder links oder rechts.
Das heißt, die Gesamtpropezität war dann logarithmisch natürlich, weil
die Logarithmen sind n, weil wir jedes Mal das Problem halbieren, und
wir sind davon ausgegangen, dass man diese Rank-Querie, also
bestimmen, wie viel Einser hier im Präfix von so einem Bitfactor ist,
in konstanter Zeit machen kann.
Okay.
Genau.
Das ist ein bisschen komplexer, als wenn man eine Dominance-Reporting
-Querie macht.
Das heißt, man will nicht nur wissen, wie viele Punkte da drin sind,
sondern auch die Punkte in der Ausgabe.
Und da muss man natürlich nicht nur zwei rekursive Aufrufe, sondern
mehr rekursive Aufrufe, weil man auch die Punkte...
Ich muss das noch vergrößern hier.
Genau.
Das ist der Algorithmus von der Folie.
So.
Und der sieht ähnlich aus zu dem, was wir kennen.
Aber das sind jetzt quasi noch mehrere Aufrufe.
Schauen wir uns das an, wie das funktioniert.
Ja.
Also ich habe hier einen N-Grid.
Und da habe ich die Punkte, die da drin liegen.
Und genau.
Dann habe ich hier N-Halbe, da, wo ich den aufteile.
So.
Und dann habe ich wieder mein Rechteck, für das ich diese Querie lösen
will.
Das heißt, ich habe jetzt hier wieder, quasi zähle ich wieder, wie
viele Punkte hier unten drin liegen.
Das ist dieses Y-Au, dieses Rank, das mir quasi angibt, wie viele
Punkte hier in dem Bereich bis zu Y sind größer als N-Halbe.
Genau.
Das gibt mir jetzt diese Menge.
Und bis Y habe ich genau Y Punkte.
Das heißt, dieser Bereich hier, die Größe, das war Y minus Y, Y-Au.
So.
Und genau.
Jetzt gibt es wieder zwei Fälle.
Also entweder geht mein Rechteck hier, geht quasi, ist links von mein
N -Halbe.
Das ist dieser Fall hier.
Dann muss ich jetzt alle Punkte, die hier liegen, reporten.
Und auch alle, die hier reporten.
Und sonst gehe ich in den linken Teilbeamt rein und löse das aber für
X minus dieses N-Halbe.
Die gleiche Querie.
Das heißt, ein interessanter Fall ist jetzt dieser, wo ich quasi hier
alle reporten muss.
Und da hier dann quasi nochmal eine Regression reingeht.
So.
Das heißt, jetzt müssen wir verstehen, was diese Bedingungen sind.
Also die Bedingung heißt, dass Y minus Y-Au, das sind quasi wie viele
Punkte hier drin liegen, wenn da jetzt quasi alle Punkte drin liegen
hier, dann lösen wir keinen Reporter.
Das heißt, das gilt nur, wenn hier mindestens ein Punkt drin liegt.
Und das ist genau der Fall, wenn das Y minus Y-Au kleiner ist als N
-Halbe.
Wenn es gleich N-Halbe ist, dann liegt hier nichts drin.
Dann ist das leer, dann gibt es nichts zu be...
Also, weil dann ist das...
dann ist das da oben, also wir wollen das da oben, die Punkte
einsammeln, dann ist das leer und wir müssen nichts machen.
So.
Und hier unten ist es dann genau gleich, also Y-Au.
Wenn das gleich N-Halbe ist, dann ist das...
der Bereich hier oben auch leer, weil alles hier unten liegt.
Und dann geht es hier auch nicht rein.
Das heißt, wir machen nur eine Regression, wenn da auch Punkte
wirklich drin sind.
So.
Und das heißt, was da unten dann passiert, oder in der Hälfte, ist,
dass die Einfrage jetzt einfacher ist, weil wir wissen, alle Punkte in
diesem Subbaum, der entsteht, wenn man das weglässt, liegt drin bis zu
der Grenze Y-Au.
Da hat man nur noch eine Grenze und das ist quasi nur noch...
wir wollen alle Reporte, die groß sind, alles Y-Au.
Und das... genau.
Und das ist... das passiert dann hier.
Da haben wir quasi nur diese Grenze nach unten.
Und... genau.
Und kommt immer... die Regression wird immer aufgerufen, wenn da oben
noch Punkte liegen.
Und das sind jetzt quasi genau wieder die gleichen Bedingungen.
Also man hat wieder dieses Y-Au ausgerechnet, wie viele Punkte hier
drin liegen, dann Y-Y-Au, wie viele Punkte hier drin liegen.
Und wenn das gleich N-Halbe ist, dann ist oben leer.
Dann geht man nicht rein und sonst geht man rein.
Das heißt, pro Report ein Punkt.
Also ich gehe immer nur in die Regression rein, wenn da was drin
liegt.
Und das heißt, pro Punkt ist das dann logarithmisch.
Das heißt, wenn ich nachher K-Punkte ausgabe, dann habe ich K mal Log
N Komplexität.
Das heißt, das ist die Ausgabekomplexität.
Genau, so.
Und das heißt, da gehe ich einmal, gehe ich dann quasi hier rein,
mache für jeden Punkt logarithmisch einen Aufwand und dann rufe ich
das einfach wieder regressiv auf.
Und dann war's das auch schon.
Also das ist quasi so ein Zusatz.
Der ist nicht schwer.
Genau, das gilt jetzt aber leider nicht für allgemein, wenn ich
irgendwie vier Grenzen habe, sondern nur, wenn ich zwei Grenzen habe.
Und... genau.
Und jetzt, was man aber immer noch braucht...
Aber man kann das erweitern, als es auch geht.
Das erkläre ich hier jetzt nicht, wie das geht.
Das gibt es in weiterführenden Vorlesungen.
Ich habe da eine Vorlesung Advanced Data Structures, da wird das dann
ganz genau gemacht.
Oder auch in Textindizierung.
Was ich dann jetzt noch zeige, ist erstens mal, wie das mit dem
Bitvektor geht, dass man das zählen kann, wie viele Bits da gesetzt
sind bis zu einer bestimmten Position und dann eben, was das auch für
eine Anwendung hat, zum Beispiel in Textindizierung.
So, genau.
Also wie zähle ich, wie viele Bits da gesetzt sind bis zu einer
bestimmten Position?
Naja, hier ist erst mal eine Lösung, die braucht linear viele Bits.
Also wenn ich einen Bitvektor habe, der Länge n, dann brauche ich
genau nochmal so viele Konstante mal Bits, Konstante mal n Bits, um
das zu machen.
Wenn ich das so einfach mache, wie das hier dargestellt ist.
Und zwar, hier ist die Idee einfach, man gruppiert jetzt diese Bits in
Blöcke und man kann die Blöcke so wählen, dass die zum Beispiel
logarithmisch groß sind.
Also ich fasse logarithmisch viele Bits zusammen.
Ein Computerwort zum Beispiel.
Und was ich dann mache, dann speichere ich mich für jedes Wort,
speichere mir die Summe aller Bits, die vor dem Block kommen ab.
Also zum Beispiel hier habe ich im ersten Wort 4 Bits gesetzt.
Das heißt, ich speichere mir im nächsten Wort dann quasi was als
Präfix da vorkommt.
Also 4 Bits und im nächsten Wort kommen nochmal 4 Bits.
Dann speichere ich mir für das nächste Wort 8 Bits.
Und dann waren da 3 Bits, dann speichere ich mir 11 Bits und so
weiter.
Das heißt, jetzt kann ich diesen Rank ausrechnen für alle Wortgrenzen,
indem ich einfach in die Tabelle reinschaue.
Ich teile einfach meinen Index durch die Blockgröße.
Das seht ihr hier.
Und dann habe ich da meine absolute Ranks.
Und so ein Rank, so ein Wert, der braucht logarithmisch viel Platz.
Das heißt, aber ich habe nur n durch logarithmisch viele Blöcke.
Das heißt, ich habe O von n, die Größe meines Arrays, B Rank.
Und jetzt hat man ein Problem, wenn mein Index innerhalb vom
Maschinenwort ist.
In der Praxis geht es dann so, ich muss dann zählen, wie viele Bits
sind bis zu der bestimmten Position gesetzt in dem Computerwort.
Dann würde man erst mal, wenn dieser Rest ist O, würde man dieses Wort
um O shiften, nach rechts.
Und dann würde man zählen, wie viele Bits dann noch in dem restlichen
Wort drin sind.
Ich würde eine Maske drauflegen, dass die letzten O-Bits quasi noch
gesetzt sind.
Kommt immer darauf an, wie man das betrachtet.
Und dann ist das Problem quasi zu zählen, wie viele Bits im
Computerwort gesetzt sind.
Und da gibt es einen Maschinebefehl dafür, PopulationCount nennt sich
das.
Und das kann man darauf anwenden.
Das heißt, nur in Zyklusen hat man konstanter Zeit diese Berechnung
gemacht.
Man kann es auch anders machen, man kann einen Block, wenn der Lock
rhythmisch ist, kann man aufteilen in einen Block der Größe 1,5 Log N.
Das macht man dann für die zwei Blöcke, 1,5 Log N und 1,5 Log N sind
die groß.
Und dann kann man sich eine Tabelle machen, die das für alle
Bitsequenzen der Länge 1,5 Log N macht.
Diese gibt es.
Das heißt, ich habe 2 hoch 1,5 Log N viele Möglichkeiten.
2 hoch 1,5 Log N, das ist Wurzel N.
Und das heißt, das ist auch nicht sehr speicheraufwendig, weil das
quasi alle Möglichkeiten nur Wurzel N, also sublinear sind.
Und dann besteht meine Anfrage einfach daraus,
nachzuschauen, für diesen Eintrag in die Tabelle speichern wir dann
ab, für welches Präfix oder Suffix von diesem Computerwort, an dem ich
interessiert bin, was da der Count ist.
Das heißt, so geht es theoretisch in konstanter Zeit.
Genau, das heißt, so geht es in linearem Platz und man kriegt es aber
auch in sublinearem Platz hin, wenn man dieses Schema einfach zweimal
anwendet.
Erst schreibt man das in noch größere Blöcke auf, wo man das einfach
in Log N² Größe wählt.
Dann hat man nur N durch Log N² viele Blöcke.
Und dann speichert man sich da den absoluten Count.
Dann kommt insgesamt daraus, dass man N mal Log N Bits, also Log N
Bits brauche ich, um den Count zu speichern, durch Log² N, das heißt,
das ist N durch Log N Bits, das ist der sublinear Platz.
Dann kann man dann wieder innerhalb dieser größeren Blöcke relative
Counts abspeichern, zum Beginn von so einem großen Block.
Und da die großen Blöcke sind der Log² N, das heißt, wenn ich hier
einen relativen Count abspeichere, dann ist die Größe höchstens Log²
N.
Und um eine Zahl abzuspeichern, die bis zu Log² N groß ist, brauche
ich nur Log von Log² N, was Log Log N Bits sind.
Und wenn ich dann Log Log N Bits habe, dann kann ich den relativen
Count für kleinere Blöcke abspeichern, zum Beispiel der Größe in ½ Log
N.
Und da habe ich nur zwei durch Log N viele.
Das heißt, das ist dann insgesamt N mal Log Log N durch Log N viele
Bits.
Und das ist immer noch sublinear.
Und auf der letzten Ebene mache ich dann wieder diesen Trick, dass ich
die Tabelle abspeichere, die Größe Log N, Wurzel N oder ich mache den
Maschinenbefehl.
Das heißt, insgesamt kann man das sogar in sublinear auf den Platz
machen.
So, das war jetzt alles ein bisschen schnell.
Dann machen wir das nochmal und auch eine Anwendung dazu.
Das ist unser Suffix Array, den ihr kennt.
Und ich habe auch die Boris-Wheeler-Transformierte vorgestellt.
Also alle sortierten Suffixe und diese Boris-Wheeler-Transformierte,
die mir immer den Buchstaben vor so einen bestimmten Suffix gibt.
Und da kann man jetzt Range Search anwenden, um Pattern Crease zu
lösen.
So, genau.
Was brauchen wir dazu?
Da brauchen wir ganz wenig Platz jetzt.
Also man hat jetzt nur die Boris-Wheeler-Transformierte und diese
erste Spalte von den sortierten Suffixen.
Und diese erste Spalte von den sortierten Suffixen, die speichert man
sich jetzt auch noch komprimiert, indem man einfach speichert, wo
jeder Buchstabe, den man hat, quasi anfängt in dieser sortierten Folge
von Suffixen.
Das heißt, dieses $ zum Beispiel, das fängt an Position 0 an.
Dieses a, alle Suffixe, die mit a beginnen, fängt an Position 1 an.
Alle Suffixe, die mit b beginnen, fängt an Position 9 an.
Und so weiter.
Das heißt, ich habe, wenn mein Alphabet Sigma groß ist, so haben wir
das im Moment benannt, die Alphabetgröße, dann haben wir Sigma viele
Pointer.
Und das ist Sigma mal log n Bits, das ist sehr klein.
Also wenn man z.B.
ein Byte-Alphabet hat, dann sind das 256 mal 32 Bit für einen Pointer.
Und jetzt sage ich, wir können einfach nur mit diesem Array, C-Array
nennen wir den für Count, weil der zählt, das ist auch so eine
Präfixsumme von Buchstaben, die kleiner sind wie ein bestimmter
Buchstabe, und die Bücher sind wieder transformiert, nur mit diesen
Hilfsmitteln können wir Pattern-Matching machen.
Okay, wie geht es?
Ich, genau, ich habe, initial habe ich den leeren String und der
matcht alle Suffixe.
So, und jetzt will ich ein Pattern matchen, und jetzt geht es anders,
als wir es bisher gehabt haben, nicht von links nach rechts, sondern
von rechts nach links.
Ich habe immer schon was, das ich gematched habe, und jetzt will ich
da was voranfügen.
Heißt, wenn ich jetzt z.B.
ein Pattern habe, B-A-A, und ich will alle Suffixe, die mit A
beginnen, und ich habe schon alle Suffixe hier eingekreist, oder quasi
markiert, die mit Epsilon beginnen, dann suche ich jetzt alles, was
auch noch vor diesem Epsilon ein A hat.
So, und das heißt, ich muss einfach nur zählen, wieviel A's gibt es in
der Buchstabe, die wieder transformiert sind.
Und wenn ich das, wenn ich das als Weltschatz wie Vorlage habe, dann
kann ich diese Country-Macher auf diesen Buchstaben.
So, das gibt mir 4.
Und ich weiß auch, wo alle Suffixe anfangen, die mit A beginnen.
Das heißt, ich muss einfach da schauen, wo beginnt alle Suffixe mit A,
in Position 15.
Und dann, um das Ende von dem neuen Intervall zu kriegen, muss ich
einfach die 4 dazuzählen und eins abziehen, um dann quasi innerhalb
von dem Intervall zu sein.
So, und genau, und das geht jetzt genauso weiter.
Also, wenn ich jetzt wissen will, ich will alle Suffixe, die mit A
beginnen, dann zähle ich jetzt einfach A, wieviel Suffixe, die mit A
beginnen.
Dann auch noch ein A davor, und das sind diese zwei A's in Position 15
und 18.
Und mit einer Range Query kann ich erstmal alle A's bestimmen, die mit
irgendwas beginnen, was lexographisch kleiner ist.
Das sind 1, 2, 3, 4, 5, 6.
Und dann kann ich alle A's bestimmen, die ein Suffix sind, das
lexographisch kleiner oder gleich ist.
Das sind 8.
Und dann ist mein neuer Bereich, fängt dann mit A an, und dann gefolgt
von allem, was lexographisch kleiner ist.
Das ist alles von 1 bis 6.
Das sind diese 6 Suffixe, die mit A beginnen, mit irgendwas, das
kleiner ist als mein A, quasi als Nachvorgang.
Und dann habe ich quasi diese zwei, die mit A beginnen.
Das heißt, dieses Pattern Matching, das müsste jetzt nicht genau...
Ich erwarte es nicht, dass man das genau versteht, wie das geht, aber
behalte ich einfach durch dieses Zählen von Buchstaben in der Boris
-Wehler -Transformierten, kann ich immer dieses Intervall bestimmen.
Und das heißt, das reduziert sich jetzt auf m mal, wenn mein Pattern m
lang ist, m mal zu bestimmen, wie viele Buchstaben in einem bestimmten
Präfix sind.
Und das ist eine Anwendung vom Alpha Tree.
Das heißt, ich kann meinen Text nehmen und mein Text, das ist quasi
wie Punkte, der hat eine x-Koordinate und die y-Koordinate ist das
Buchstabe selbst.
Und jetzt teile ich das Alphabet auf in eine untere Hälfte, in eine
obere Hälfte und alles, was in der unteren Alphabethälfte liegt,
markiere ich mit einer 0 und alles, was in der oberen Hälfte liegt,
markiere ich mit einer 1.
Und dann teile ich das jetzt in jeder Ebene wieder auf, regressiv.
Das heißt, die Höhe dieses Baumes ist die Log von unserem Alphabet,
also Log Sigma, auf jeder Ebene, kein Buchstabe geht verloren.
Das heißt, ich habe auf jeder Ebene wieder höchstens n Zeichen, das
heißt, diese Darstellung, die benötigt n mal, und das ist die Tiefe,
ist Log Sigma, also n Log Sigma Bits und das ist genau die Größe von
meinem Originaltext.
Das heißt, ich kann jetzt meinen Text einfach wegschmeißen und durch
diese Struktur ersetzen, durch den Alpha Tree, über den String.
Und genau, dieses Rank, also ich weiß jetzt mal, wie viele As sind
jetzt im Präfix drin, also bisher haben wir immer Dominance-Grid
gemacht, das heißt, mir war quasi interessiert, wie viele dann quasi
nicht im Präfix lagen, sondern im Subfix.
Jetzt ist mir interessiert, wie viele Punkte da oder wie viele
Buchstabe im Präfix liegen.
Und dann geht es ja einfach, indem ich jetzt sage, okay, das A, das
weiß ich, wo das liegt.
Das A, das liegt in der ersten Alphabethälfte.
Das heißt, um zu bestimmen, wie viele As da gibt bis zum bestimmten
Präfix, muss ich dann, wenn ich weiß, dass das A in der ersten
Alphabethälfte liegt, gehe ich dann in den linken Teilbaum.
Ja, also hier rechts habe ich das A aufgeschrieben, dass das A
entspricht dem Code 001.
Das liegt erstmal in der ersten Alphabethälfte, nochmal in der ersten
Alphabethälfte, in der zweiten Alphabethälfte, wenn man das aufteilt.
Das heißt, genau, da kriegt man jetzt, da gibt es genau eins, zwei,
drei, vier, fünf Elemente, die null sind, das heißt, fünf Elemente bis
dahin liegen in der ersten Alphabethälfte.
Heißt, man hat das Problem reduziert auf eine neue Sequenz, die in der
ersten Alphabet, die Sequenz, die aus den Zeichen besteht, die in der
ersten Alphabethälfte liegen.
Und jetzt weiß ich wieder, dass das in der ersten Alphabethälfte
liegt, das A von diesem Subalphabet.
Das heißt, ich mache wieder einen Rank, und zwar wieder auf null.
Zeige, wie viele Nuller da drin sind.
Da sind drei Nuller drin.
Und im letzten Schritt ist es dann, ist es in der zweiten
Alphabethälfte, habe ich das blau markiert, dieses Rank, das heißt,
man macht ein Rank 1, und dann kommt der 2 raus.
Genau, so, und hier habe ich nochmal ausgelistet, was ich Ihnen gerade
erzählt habe, mit dem Platz für dieses Rank auf diesen Bitvektoren.
Und genau, also was wir vorhin nicht so gemacht haben, ist, also die
Survival Tree, der besteht quasi jetzt nur aus diesen Bits.
Also ich brauche nur diese Bits, ich brauche nicht diese
Originalsequenz, die ich quasi nur zur Veranschaulichung nochmal hier
hellgrau unterlegt hinzeichnet habe.
Genau, so.
Und das heißt, wenn man das mal vergleicht, also dieser Index nennt
man FM-Index, das habe ich da auch bei der Textinhaltsierung schon mal
erwähnt gehabt.
Und wenn man das vergleicht, wie viel Platz das braucht, also diese
Originaltext, das wäre quasi 1, wenn man den Suffix Tree nimmt, dann
braucht das ungefähr 20 mal so viel, Suffix Array 5 mal so viel, und
dieser Self-Index, dieser FM-Index, der ist sogar, quasi der ist
sogar, sieht man hier in dem Beispiel, der könnte sogar kleiner sein,
weil einige Buchstaben mal in weniger Bits dargestellt sind.
Zum Beispiel dieses A, braucht ja nur 2 Bits statt 3.
Und das kann man quasi noch besser machen, indem man diesen Maple Tree
balanciert oder umformt, und zwar kann ich einzelne Zeichen, die oft
vorkommen, durch einen kürzeren Code ersetzen, zum Beispiel Huffman
Code, und dann kriegt man automatisch eine Entropie-Codierung da noch
rein.
Und dann kann man das noch besser machen, weil diese Bitvektoren, da
gibt es jetzt wieder viele Runs, und jetzt kann man diese Bitvektoren
auch noch durch, also das Move-to-Front haben wir gehabt in dem
Stringology -Part, oder in der Übung dazu, das war in der Vorlesung,
aber da gibt es auch noch Run-Length-Encoding, ich schreibe quasi hin,
ich habe eine 0 und die kommt so oft mal vor, und dann habe ich eine 1
und die kommt, also ich habe erstmal einmal eine 0 ganz oben in der
Wurzel von dem Baum, dann habe ich zweimal eine 1, einmal eine 0 und
so weiter, und wenn da lange Runs dran sind, dann komprimiert das
ziemlich gut, und dann kann man dieses Frank, diese Operation, kann
man dann trotzdem noch effizient darauf ausführen, das heißt, genau,
das ist quasi die eine Möglichkeit, wie man Text komprimieren kann und
trotzdem noch drin suchen kann.
Ja, und das ist, konzeptionell ist das ziemlich, ja, ziemlich einfach
mit diesem Rifle-Tree.
Genau, so, und das sind auch jetzt, glaube ich, alle Folien, die ich
heute vorstellen wollte, und bin dann soweit fertig mit dem letzten
Thema, und, genau, nächste Woche gibt es noch einen Termin, jetzt
kommt noch Übung, und, genau, dann verabschiede ich mich.
Wir machen heute weiter mit der Übung, und zwar ist es die letzte
Übung im kompletten Semester.
Heute haben wir vier Themen, oder, ja, vier Punkte, auf die ich
eingehen möchte.
Heute geht es um geometrische Algorithmen, dazu wiederhole ich am
Anfang nochmal, sage ich mal, ein bisschen was Grundlegendes, und
motiviere geometrische Algorithmen.
Dann gehe ich auf drei Teile ein, einmal den Ansatz der Sweep-Line,
das ist, sage ich mal, erstmal nur ein Prinzip, was man nutzen kann,
um verschiedene algorithmische Probleme in der Geometrie zu lösen, und
da möchte ich dann ein bisschen genauer in das sogenannte Problem der
Skyline -Berechnung eingehen.
Genau, als zweiten Punkt werde ich dann auch nochmal detaillierter auf
die Linien-Schnitt-Berechnung eingehen, da hatten wir ja auch einen
ausführlichen Teil aus der Vorlesung, und da möchte ich nochmal was
dazu sagen, wie man das dann mit Linien-Segmenten machen kann, die
sich nicht nur schneiden, sondern sich auch überlappen können.
Als letzter Teil möchte ich nochmal darauf eingehen, wie man
Orientierung von Punkten im Verhältnis zu anderen Punkten bzw.
zu Linien berechnen kann, weil das haben wir eben bei uns in der
Vorlesung auch verwendet für ein, zwei Algorithmen, da wurde dann
gesagt, okay, das glauben wir jetzt einfach mal, dass das
funktioniert, da möchte ich euch eine Methode vorstellen, wie man das
auf elegante Art und Weise berechnen kann.
Beginnen wir erstmal mit allgemeinen Sachen zu geometrischen
Algorithmen.
Ihr habt jetzt schon ein paar Probleme kennengelernt, die man
betrachten kann, verschiedene geometrische Probleme, und die Frage ist
jetzt erstmal, naja, warum gibt es da ein spezielles Segment, was
geometrische Algorithmen heißt, und der Grund ist letztendlich, dass
man, wenn man eine Geometrie zugrunde legen kann, viele Probleme
einfacher lösen kann.
Also wir hatten zum Beispiel in der Vorlesung und auch in der Übung
das TSP-Problem, und wenn man das allgemein betrachtet, ist das nicht
so einfach zu berechnen.
Insbesondere ist es auch nicht approximierbar.
Wenn man jetzt aber dann in den Bereich der Geometrie wechselt, kann
man erstmal annehmen, okay, wir gucken uns das im metrischen Raum an,
das heißt, wir sind einmal symmetrisch, also die Kante zwischen zwei
Knoten haben gleiche Gewichte, egal ob es eine Vorwärts- oder
Rückwärtskante ist, also ungerichtete Kanten, und gleichzeitig gilt
eben die Dreiecksungleichung.
Und wenn man diese Voraussetzung hat, dann kann man eben zeigen, naja,
in jedem dieser metrischen Systeme kann man eine 2,5-Approximation
berechnen und garantieren.
In den Systemen gibt es verschiedene metrische Systeme, zum Beispiel
kann man die Manhattan-Distanz zugrunde legen, wo man dann irgendwie
so einen Krit von Punkten hat und nur waagerechte und senkrechte Wege
gehen kann.
Oder man kann zum Beispiel die Euclidische Metrik zugrunde legen, und
für die Euclidische Metrik sind wir sogar noch besser.
Für die Euclidisches TSP-Problem können wir sogar eine Y-Approximation
angeben.
So, jetzt habe ich hier mal die Laufzeit für das Euclidischen TSP
-Problem an die Tafel oder an den Projektor gezeichnet.
Die ist dann irgendwie n mal Logarithmus von n hoch irgendwas, wo von
1 durch Y und noch was komisches in Abhängigkeit von der Anzahl
Dimensionen ist.
Und da jetzt erstmal meine Frage an euch.
Ihr kennt ja Approximationsalgorithmen schon und werden da
verschiedene Klassen.
Und die Frage an euch, wisst ihr, in was so einer Klasse die Laufzeit
liegt und die Approximation?
Okay, also für die Klausur vielleicht nochmal anschauen.
Wir hatten da ja FP-Tas und P-Tas usw.
Und das hat letztendlich den Approximationsalgorithmen kategorisiert
in Abhängigkeit, was für eine Approximationsgarantie man geben kann
und abhängig davon, wie die Laufzeit ist.
Und der Algorithmus hier ist eben P-Tas.
Und das heißt, dass man eine Y-Approximation angeben kann.
Also der Approximationsfaktor ist 1 plus, minus irgendwie Y.
Und das Y kann man auch frei wählen und beliebig klein machen.
Und gleichzeitig ist der Algorithmus polynomiell in N.
Er ist aber nicht polynomiell in 1 durch Y, weil das halt hier im
Experiment steht.
Wenn das polynomiell in 1 durch Y wäre, dann würde es nicht in P-Tas,
sondern in FP-Tas liegen.
Weil da eben beide Anforderungen erfüllt sein müssen.
Ja,
sonst gibt es noch einen Haufen weitere Probleme, die man lösen kann.
Viele dieser Probleme sind, finde ich, eigentlich ganz interessant,
durch Computerspiele motiviert.
Dass man sich vor 20, 25 Jahren irgendwann mal überlegt hat, okay, wie
kann man Computerspiele so programmieren, dass sie auch auf den damals
super schlechten Rechnern laufen konnten.
Und da hat man halt eigentlich immer irgendeine Geometrie, sage ich
mal, im zweidimensionalen Spiel, an dem mehrdimensionale Spiele
zugrunde liegen.
Es gibt da verschiedene predestinierte Datenstrukturen, die man
benutzt, um auf einem bestimmten dimensionalen Raum Queries zu fahren.
Zum Beispiel Waveletrees, das habt ihr jetzt vorhin gesehen.
Da gibt es dann aber für alle möglichen Dimensionen verschiedene
Varianten.
Für manche Dimensionen auch spezielle Varianten.
Zum Beispiel hier der Quadtree, wo man hier ein zweidimensionales Grid
hat.
Punkte in einem Grid und da möchte man halt zum Beispiel irgendwelche
Bereichsanfragen machen und die Datenstruktur sieht dann so aus, dass
man ähnlich wie beim Waveletree den Raum unterteilt und den Rekursiv
unterteilt und in Plättern dann den linken beziehungsweise den rechten
Teil weiter abbildet und man eben dann in dieser Datenstruktur
Rekursiv suchen kann.
Verschiedene Facetten hier, zum Beispiel die Triangulierung hier.
Das ist, sage ich mal, für euch nicht so bekannt, aber ist auch
aktuelles Forschungsgebiet.
Ein Kollege von mir beschäftigt sich mit der Triangulierung und
versucht das nicht nur parallel, also im Shared Memory zu lösen,
sondern auch Distributed, sprich auf Supercomputern mit, was weiß ich,
1000 oder einer halben Million Cores, um da dann wirklich riesengroße
Graphen zu triangulieren.
Und eines der Muster, die man da immer wieder anwendet, um
geometrische Probleme geschickt zu lösen, ist eben die Sweepline.
Und was man da eben ausnutzt, einmal man legt eine Sortierung zugrunde
und versucht dann durch die Sortierung das Problem um eine Dimension
zu verringern.
Wenn man sortiert hat, dann betrachtet man nur noch die zweite
Dimension, wenn man im Zweidimensionalen ist, und hat das Problem dann
einfach vereinfacht.
Dann gibt es ja Erweiterungen, wo man dann zum Beispiel nur
topologische Sortierungen betrachtet, sprich die Sortierung ist nicht
eindeutig, sondern es gibt nur bestimmte Abhängigkeiten von Elementen
und wenn man sowas zugrunde legt, kann man Probleme teilweise dann
effizienter lösen.
Zum Prinzip der Sweepline erstmal was Allgemeines.
Man möchte, wie gesagt, das Problem strukturiert abarbeiten, in der
Regel durch Sortierung, und nutzt dabei eben Nähe aus, die durch den
Raum, in dem man sich befindet, gegeben ist.
Diese zwei Prinzipien, die hier jetzt stehen, die sollten euch
eigentlich auch schon bekannt sein.
Einmal, dass nahe Objekte sich beeinflussen können, und sich nicht
nahe Objekte eben in der Regel nicht so stark beeinflussen.
Das hatte man dann bei dem Linienschnitt, da hatte man aktive
Segmente, und die waren genauso in der Priority Queue, dass die
nebeneinander liegenden Segmente, oder Segmente, die sich an das
Sweepline schneiden und an das Sweepline nebeneinander liegende Punkte
erzeugen, dass die auch in der Datenstruktur, in der wir die aktiven
Segmente verwalten, nebeneinander liegen.
Und auch nur nebeneinander liegende Segmente können sich irgendwann
schneiden.
Also wenn zwischen einem Segment irgend ein anderes daneben liegt,
dann ist der nächste Schnitt auf jeden Fall nicht von zwei Segmenten,
die einmal links und einmal rechts von einem anderen Segment liegen.
Die können sich irgendwann schneiden, aber eben nur, wenn dieses
Segment, was dazwischen lag, irgendwann weg ist.
Und dafür hatten wir dann eben auch eine Aktion, wenn ein
Liniensegment endet, wurde auch eine Aktion ausgeführt, und wenn sich
zwei Liniensegmente schneiden, dann hat man eben die Reihenfolge der
nachfolgenden Strahlen umgedreht, weil jetzt auf einmal das Segment,
was vorher links vom anderen war, bei einem Schnitt danach auf einmal
rechts vom anderen war.
Und das ist letztendlich die komplette Grundlage oder der komplette
Ansatz von dem Linien-Schnitt-Algorithmus.
Gut, jetzt möchten wir uns mit einem wirklichen Problem beschäftigen,
hier das Skyline-Problem, und wollen den C-Plane-Algorithmus anfassen,
dass wir das Skyline-Problem lösen können.
Beim Skyline-Problem haben wir verschiedene Gebäude gegeben, hier
eingezeichnet durch grün und blau, und ein Gebäude hat immer einen
Punkt, an dem er auf der x-Koordinate beginnt, und einen weiteren
Punkt, an dem er endet, und er hat eine bestimmte Höhe.
Und was man jetzt berechnen möchte, ist die Skyline über die Gebäude,
und man hat zwei Erkenntnisse.
Die erste Erkenntnis ist, es gibt immer nur eine Höhenänderung in der
Skyline, wenn man ein End- oder Startpunkt hat von einem Gebäude, oder
wenn sich zwei Gebäude schneiden.
Und wir versuchen eben durch Sortierung das Problem auf ein
eindimensionales Problem zu reduzieren.
Jetzt schauen wir uns das mal an.
Die relevanten Punkte habe ich jetzt hier eingezeichnet, das sind
einmal die Punkte, wo die Gebäude anfangen und enden, und die
Schnittpunkte.
Und was wir jetzt berechnen wollen, ist die Skyline, sprich wir
versuchen mit irgendeinem Algorithmus, hier über die Punkte in
sortierter Reihenfolge zu iterieren, und die Skyline hier als fette
Linie zu berechnen.
Das soll eigentlich klar sein, gibt es dazu Fragen?
Und jetzt möchten wir das Problem effizient lösen, also einfach wäre
irgendwie eine n-Quadrat-Lösung, wo man jedes Gebäude einfach mit
jedem anderen Gebäude abgleicht und es versucht zu schneiden.
Und was wir jetzt hier machen wollen, ist ein N-Log-N-Algorithmus, wir
haben aber erstmal das Problem, wenn wir jetzt als grundlegende
Datenstruktur ein Array benutzen, ist Einfügen und Löschen in O von N.
Und wenn wir eine verkettete Liste verwenden, dann haben wir eben ein
Problem mit der Positionsbestimmung.
Und der nageligende Ansatz ist einfach eine Priority Queue zu
verwenden.
Gut, das hier ist jetzt eigentlich auch schon wieder ein Thema weit.
Deswegen möchte ich jetzt auf die Dokumentenkamera umswitchen.
Haben wir noch genug Zeit?
Hat jemand von euch eine Idee, wie man die Skyline in N-Log-N
berechnen kann?
Ich versuche die Aussage jetzt nochmal zu wiederholen.
Wir wollen nicht jedes Gebäude mit jedem vergleichen, sondern wir
wollen die Anzahl Vergleicher pro Gebäude auf N-Log-N reduzieren und
dadurch N-Log-N kriegen.
Ich möchte jetzt einfach mal den Algorithmus hier als Pseudocode
draufschreiben und währenddessen einfach ein bisschen dazu erklären.
Pseudocode ist vielleicht auch nicht schlecht, sich ab und zu mal,
wenn ihr Klausurenaufgaben macht, ein bisschen Pseudocode
aufzuschreiben, weil meine Erfahrung ist, dass wenn man einen
Algorithmus aufschreiben soll, man viel länger braucht, wenn man den
komplett schriftlich aufschreibt, weil man dann mehr Text schreiben
muss und teilweise Sachen weglässt.
Wenn man aber ein bisschen geübt ist, Pseudocode zu schreiben, muss
man auf der einen Seite weniger schreiben und auf der anderen Seite
fällt einem auf, was im Algorithmus noch fehlt.
Deswegen ist Pseudocode so eigentlich eine ganz sinnvolle Sache und
deswegen versuche ich das hier jetzt auch einfach mal euch ein
bisschen vorzumachen.
Gut, also was wir machen wollen ist, wir wollen die Skyline berechnen
und als Eingabe, sage ich jetzt einfach mal, haben wir eine Liste.
Und die nennen wir Groß L.
Und was wir jetzt machen wollen, ist, wir transformieren die Gebäude
in Punkte, die für uns später interessant sein werden.
Und das sind letztendlich genau Punkte, an denen die Gebäude beginnen
und enden, weil das sind genau unsere interessanten Punkte.
Und aus diesen Punkten erzeugen wir uns jetzt eine Datenstruktur.
Wir iterieren hier also jetzt über die Elemente in der Liste.
Dazu brauche ich jetzt erstmal einen Index und dann iterieren wir
jetzt über jedes Element aus der Liste.
Und ich definiere jetzt einfach hier, dass mein Input so aussieht.
Also jedes Element aus der Liste besteht aus einem Triple.
Und da habe ich einen b-Wert drin, einen e-Wert und einen h-Wert.
Und jetzt ist eigentlich auch schon klar, wie die Liste ungefähr
aussieht.
Also man hat immer einen Beginnpunkt auf der x-Achse, einen Endpunkt
und eine Höhe.
Und für jedes dieser Gebäude machen wir jetzt folgendes, dass wir eine
Liste L haben und in dieser Liste L fügen wir jetzt letztendlich zwei
Punkte hinzu.
Und die bestehen einfach aus dem Beginnpunkt, aus der Höhe, aus dem
Label, welches uns sagt, okay, diese Action, die jetzt hier kommt, ist
ein Beginnpunkt.
Und diesen Index i, der uns einfach sagt, okay, das ist das ite
eingegebene Gebäude.
Und wir geben noch einen zweiten Punkt mit ein.
Das ist eben die Endaction.
Die besteht aus dem Endpunkt, der Höhe, dem Namen der Action und auch
der Gebäude-ID.
Und was wir jetzt eben hier auch sehen, naja, jeder Punkt aus der
neuen Liste ist vom Typ Position, Höhe, Label und irgendwie Gebäude
-Index.
Und als nächstes erhöhen wir einfach den Gebäude-Index um eins.
Weil wenn wir als nächstes Gebäude hinzufügen, wollen wir eben einen
Index haben, der eins höher ist.
So, jetzt ist die Vorschleife eigentlich auch schon rum.
Wir haben uns die neue Liste L' hier aufgebaut.
Und was wir jetzt machen, wir sortieren die Liste abhängig, wann die
Action ausgeführt werden soll.
Und die Sortierung ist bei uns jetzt einfach, dass wir die Liste L' in
lexikografischer Ordnung sortieren wollen.
Sprich, wir wollen, dass wenn die Action, also erst nach dem X-Wert
sortieren, dann nach der Höhe, dann nach dem Typ der Action und dann
nach dem Index.
Das ist jetzt bei uns eigentlich nicht so wirklich wichtig, aber was
ich auf jeden Fall möchte ist, dass hier auf jeden Fall nach dem X
-Wert sortiert ist.
Und was wir dann noch brauchen, das haben wir ja vorhin schon uns ein
bisschen ausgedacht, wir brauchen eine Priority Queue und ich sage
jetzt am Anfang ist die einfach mal leer.
Und was wir jetzt machen wollen, wir wollen einfach über jede unserer
Action drüber iterieren in sortierter Reihenfolge.
Und dazu machen wir einfach eine Weilschleife, solange unsere Liste L'
eben nicht leer ist, machen wir was Spezielles.
Und was wir jetzt machen ist, wir speichern uns die aktuelle Position
von der Action auf der X-Achse.
Und die ist eben das erste Element in der sortierten Liste und davon
die Position.
Jetzt ist die Frage, warum gibt es hier einfach die Variable pos?
Naja, ich habe hier einfach gesagt, okay, alle Elemente aus der Liste
sehen halt genau so aus.
Und dann ist eigentlich auch klar, dass es hier diesen Eintrag
Position in diesem quadribbel oder wie man das auch immer nennen mag
gibt.
Im Pseudocode kann man halt viele Sachen weglassen, die man eigentlich
machen muss, wenn man programmiert, aber es sollte halt aus dem
Gesamtkontext vom Pseudocode dann schon irgendwie klar sein, was jetzt
da passiert und nicht irgendwelche neuen Variablen oder sowas
herzaubern und man weiß nicht, was da drin steht.
Jetzt haben wir auf jeden Fall mal die aktuelle Position und was wir
dann machen, naja, jetzt nehmen wir wirklich Elemente aus L' raus,
also solange die Liste nicht null ist und die aktuelle Position ist
gleich dem ersten Element, was in der Liste jetzt gerade drin ist.
Warum mache ich das?
Naja, es können in der gleichen Position mehrere Actions stattfinden
und ich möchte jetzt eben erstmal alle Actions an der Position
ausführen, bevor ich dann wirklich eine neue Höhe abgebe.
Und das kann ich halt nur so lange machen, bis die Liste nicht leer
ist oder die nächste Action weiter rechts liegt von der aktuellen
zuerst gelesenen Action hier.
Dann nutze ich halt wieder das ToDo-Prinzip und sage, okay, jetzt
nehme ich das nächste Element aus der Liste raus und das besteht halt
aus Position, Höhe, Label und Index.
Und das ist genau das, was ich hier eben auch eingegeben habe.
Und da nehme ich mir das erste Element raus und lösche es auch gleich
aus der Liste raus.
Dazu eben nochmal gesagt, naja, also hier sage ich jetzt die ganze Z
-Liste.
Was man hier eigentlich verwenden würde, um einigermaßen gut zu
sortieren, wäre wahrscheinlich Array.
Und man kann hier auf das Array auch immer einen neuen Eintrag am Ende
hinzufügen in konstanter Zeit.
Das funktioniert alles.
Im Solocode schreibt man dann offenbar jetzt nicht hin, was für ein
Datentyp das ist.
Wenn aus dem Gesamtkontext rauskommt, was für eine Datenstruktur man
nutzen müsste, um die Gesamtlaufzeit zu kriegen.
Wenn das offensichtlich ist, dann schreibt man das einfach nicht dazu.
Wenn das nicht offensichtlich ist, dann muss man das halt noch dazu
schreiben.
Und was wir jetzt haben, naja, wir haben zwei Typen von Action.
Wenn wir eine Action haben, die ein Labelbeginn hat, dann tun wir
folgendes.
Wir fügen einfach in die Priority Queue das Gebäudeende hinzu.
Also zur Priority Queue fügen wir ein Tuple aus Höhe und Index hinzu.
Und was es letztendlich macht, ist, naja, wir haben hier unsere
Skyline, unsere Gebäude.
Und wir haben bei der Action begonnen.
Und in der Priority Queue, wenn wir diese Action einlesen, haben wir
diese Höhe abgespeichert.
Sprich alles, was erstmal hier rechts kommt, bis wir diese Höhe hier
rauslöschen, hat auf jeden Fall diese Höhe.
Irgendwann kommen wir an diese Action ran, wenn das Gebäude hier
beginnt.
Und dann fügen wir diese Höhe hier ein in die Priority Queue.
Und die Priority Queue sortiert auch absteigend nach Höhe.
Sprich, wenn man das erste Element aus der Priority Queue rausnimmt,
dann kriegt man eben diese Höhe.
Und die Höhe ist eben valide, bis die Höhe aus der Priority Queue
später bei uns rausgelöscht wird.
Oder ein Element in die Priority Queue eingefügt wird, welches eine
noch höhere Höhe hat.
Gut, also Einfügen haben wir.
Jetzt habe ich gesagt, irgendwann muss diese Höhe hier eben wieder
rausgelöscht werden.
Und das wird eben genau gemacht, wenn wir jetzt im Else-Fall sind.
Sprich, wenn wir keinen Beginn haben, also keine Beginn-Action,
sondern eine End-Action.
Was wir dann machen ist, wir löschen aus der Priority Queue das
Element mit dem Schlüsselindex.
Also hier haben wir einmal den Wert vom Priority Queue-Eintrag und
hier haben wir den Key.
Und jetzt geben wir einfach nur den Key an und sagen, ok, löscht es
uns raus.
Kleine Frage, wenn man eine Priority Queue hat, aus der man nicht
rauslöschen kann, aber Decrease Key und Delete Min, wie könnte man das
implementieren?
Also man hat keine Remove-Funktion,
aber Decrease Key und Delete Min.
Ja,
genau.
Also die Antwort war, man macht Decrease Key auf Minus und Endlich und
holt es dann raus.
Hier müsste man eben die Vergleichsoperation so machen, dass man das
Element rauskriegt, wenn man es auf Minus und Endlich setzt, weil wir
ja Absteigen sortiert haben.
Gut, also das hier funktioniert auf jeden Fall mit einer Priority
Queue, die einigermaßen mächtig ist.
Und da wissen wir auch aus der Vorlesung, das geht alles in Log N
Laufzeit.
Und wir fügen eben für jedes Gebäude nur zwei Elemente ein und
holen...
fügen ein Element ein und holen es halt später wieder raus.
Und was wir jetzt hier halt gemacht haben, naja, wir haben uns die
aktuelle Position geholt.
Wir haben jede Action an der Position abgehandelt.
Diese Weilschleife hier ist eigentlich nur dafür da, dass wenn man
sowas hier hat, dass wenn an einer Position mehrere Gebäude anfangen
oder enden, dass man eben all diese Actions abgearbeitet hat, dass die
Priority Queue also genau das abbildet, was man sehen würde, wenn man
hier genau so eine Epsilon-Linie danach legen würde.
Und an der Priority Queue zu dem Zustand, nachdem man hier alles
abgearbeitet hat, ist eben das erste Element genau diese Höhe hier.
Und diese Höhe gibt man jetzt aus.
Also sagen wir, falls die Priority Queue nicht leer ist, schreiben wir
die aktuelle Position und dann die Höhe von dem ersten Element in der
Priority Queue.
Genau.
Und wenn die Priority Queue leer ist, naja, was ist dann passiert?
Naja, man ist hier am Ende angekommen, hat die letzte Action
ausgeführt, hat das letzte Gebäude, das Ende des letzten Gebäudes
rausgenommen und was man dann halt noch ausgeben muss, dass
die aktuelle Position eben null ist.
Und dann sind wir fertig.
Gut, gibt es zu dem Algorithmus noch Fragen?
Gut, letztendlich ist auch klar, warum das in NlogN funktioniert.
Hier haben wir eine For-Loop über jedes Element, das ist O von N.
Hier sortieren wir lexikografisch in NlogN.
Hier iterieren wir mit diesen beiden While-Loops insgesamt über jede
Action.
Es gibt zwei In-Action-Actions und für jede Action führen wir entweder
Add oder Remove aus, welches jeweils in NlogN ist, also NlogN.
Genau.
Dann kann man das Skyline-Problem eigentlich noch ein bisschen
erweitern auf dieses Problem, um nicht-dominierende Punktmengen zu
finden.
Hier haben wir jetzt eine Punktmenge und die nicht-dominierende
Punktmenge sind jetzt genau jene Knoten, die von keinem anderen Knoten
dominiert werden.
Und man wird von einem Knoten dominiert, also für ein B wird von einem
A dominiert, wenn zum einen gilt, naja, der Knoten ist...
also jede Dimension ist mindestens genauso, oder jeder Index, ja
genau, jeder Wert der Dimension ist mindestens genauso groß oder
kleiner als der Wert vom Punkt B, der dominiert werden soll.
Und es gibt mindestens einen Wert oder eine Dimension, wo der Punkt
eben einen kleineren Wert hat.
Jetzt kann man sich mal diese beiden Punkte angucken.
Sind beide Punkte der nicht-dominierten Punktmenge?
Also, dass dieser Punkt von diesem Punkt dominiert wird, ist klar,
weil die erste Bedingung gilt, dass jeder Eintrag von diesem Punkt auf
jeden Fall kleiner gleich dieser ist.
Und es gibt auf jeden Fall einen Eintrag hier, wo dieser Punkt A einen
wirklich kleineren Wert hat als dieser Punkt.
Sind diese beiden Punkte im nicht-dominierten Set oder nicht?
Genau, das ist korrekt.
Euer Kollege hat gesagt, naja, es liegt nur der linke Punkt im nicht
-dominierten Punkt Z.
Ganz einfach aus der Begründung, da man für diesen Punkt einen Punkt
will, der diesen Punkt dominiert.
Und das ist eben genau der Punkt hier links, weil der X-Wert auf jeden
Fall kleiner ist.
Also hat man diese Bedingungen schon erfüllt und der Y-Wert genauso
groß.
Also ist auch der X-Wert genauso groß oder kleiner und dann ist auch
diese Bedingung hier erfüllt.
Also letztendlich sind das hier nur genau die Eckpunkte.
Und wenn man sich einen Zustand von unserem Skyline-Algorithmus
anguckt, dann bilden die aktiven Punkte eben auch immer genauso eine
Skyline.
Hier ist es natürlich ein bisschen geometrisch verdreht, weil man hier
dominierend so betrachtet oder die Punkte ausgeben möchte, die hier
eher entlang der konvexen Hülle liegen als im Vergleich zur Skyline.
Aber einfach mal hier das Problem nochmal genannt, dass es bekannt
ist.
Und ihr wisst, dass man da vieles verallgemeinern kann, insbesondere,
dass es auch für beliebig viele Dimensionen anwendbar.
Dann zum vorletzten Thema, die Linienschnitte.
Da hatten wir einen Algorithmus aus der Vorlesung.
Und den Algorithmus hatten wir erstmal nicht für das komplette Problem
definiert.
Wir hatten da Sachen ausgeschlossen.
Ein Ausschluss war zum Beispiel, dass mehrere Sekmente am gleichen
Punkt beginnen dürfen.
Wir hatten weiter ausgeschlossen, dass sich zwei Segmente nicht
überlappen dürfen.
Also mehrere Punkte existieren können, die zwei Segmente gleich haben.
Und dann wurde kurz mal angesprochen, okay, das kann man lösen.
Und ganz kurz gesagt, naja, so und so kann man es machen.
Da wollte ich jetzt einfach mal noch ein bisschen genauer drauf
eingehen.
Also was wir machen, ist wir lösen eigentlich zwei Probleme.
Wir sagen erstmal, okay, wir lösen das Problem ganz normal.
Und kriegen dann aber nicht diese Überlappungen raus.
Und dann fahren wir danach nochmal in den Nachbearbeitungsalgorithmus.
Und der ist jetzt hier beschrieben.
Was wir machen ist, wir gucken uns für jedes Segment die Steigung an.
Und dann den Y-Achsenabschritt und dann die X-Koordinate.
Und daraus machen wir für jeden Punkt so ein Tuple.
Und sortieren dann lexikografisch.
Und was wir dann eben bekommen ist, naja, die Segmente sind so
sortiert, dass Segmente, die auf der gleichen Geraden liegen,
gruppiert sind.
Und dann scannen wir letztendlich einfach nochmal über die sortierte
Folge.
Und gucken uns an, welche Elemente sich jetzt wirklich überlappen.
Und geben die Überlappungen dann aus.
Ich wollte jetzt gerade nochmal kurz aufzeichnen, dass das in jedem
klar ist.
Sagen wir, wir haben jetzt hier, wir befinden uns im
Zweidimensionalen.
Wir haben verschiedene Segmente.
Zum Beispiel hier zwei Segmente, ich zeichne die jetzt so leicht
übereinander.
Aber was ich jetzt hier eigentlich andeuten möchte, ist, dass diese
beiden Segmente überlappen.
Dann haben wir hier zwei andere Segmente, die liegen zwar hier auf der
gleichen Geraden, überlappen sich nicht.
Und dann haben wir hier nochmal zwei andere Segmente, die liegen auf
keiner Geraden mit einem anderen Segment.
Und was wir jetzt eben machen, naja, wir gucken uns den Winkel an von
den Segmenten hier.
Und gleichzeitig die Positionen, an denen die Segmente die X- und Y
-Achse schneiden.
Und haben eben jeweils danach dann sortiert.
Also wir haben erstmal nach dem Winkel sortiert, was dazu führt, dass
alle Segmente, die den gleichen Winkel haben, nah beieinander stehen.
Also dieses Segment liegt nah bei diesem Segment.
Wenn wir jetzt hier aber ein anderes Segment haben, welches den
gleichen Winkel hat, dann liegen die auch nah beieinander.
Und deswegen haben wir als zweiten Wert den Y-Eintrag, wenn sich hier
die Elemente mit der Y-Achse schneiden.
Und das führt eben dazu, dass diese beiden Segmente wirklich
nebeneinander liegen und danach erst dieses Segment kommt.
Genau, also haben wir dann die Segmente sortiert vorliegen.
Also erst dieses Segment, dann dieses Segment, dann dieses Segment,
dann dieses Segment, dieses, fünf und sechs.
So, es kommt das und dann das und dann erst später die.
Die beiden Segmente, weil diese beiden Segmente eben einen weniger
steilen Winkel haben als dieses Segment hier.
Und was man dann eben macht, man geht einfach durch die sortierte
Reihenfolge, durch die sortierte Folge durch.
Und jetzt sind eben Segmente, die auf einer gerade liegen, kopiert.
Also hier zum Beispiel diese beiden Segmente.
Und da benutzt man für diese Segmente eben wieder so einen Sweep-Line
-Algorithmus, um eben wirklich Überlappungen zu finden.
Genau, und die Überlappungen findet man dann eben auch nicht in
Linearzeit, sondern muss dann eben wieder auf so einem Range arbeiten.
Hat dadurch dann auch wieder, also einmal fürs Sortieren und während
dem linearen Scan über die Elemente und prüfen, welche Segmente, die
auf dieser einen gerade liegen, auf der auch ich liege, mit welchen
überlappe ich.
Das kann man dann eben auch in NlogN ausgeben, beziehungsweise
berechnen.
Plus Anzahl an Überlappungen natürlich.
Genau, das war's dazu.
So, jetzt haben wir noch einen letzten Punkt.
Und zwar hatten wir den Cram-Scan-Algorithmus in der Vorlesung
vorgestellt bekommen.
Da ging es letztendlich darum, aus einer Punktwolke die konvexe Hülle
zu finden.
Und der Algorithmus ging ja so vor, dass man hier eine Punktwolke
hatte und die hat man eben nach der X-Koordinate sortiert.
Sprich, man hatte hier auch wieder so einen Sweep-Line-Ansatz, wo eben
jeder Punkt eine Action war.
Und man hat dann diesen Punkt hier, den ersten Punkt, mit dem nächsten
Punkt verbunden.
Und dann hatte man eine neue Action, da hat man den letzten Punkt mit
dem Action-Punkt verbunden.
Und wenn man jetzt eben so eine Drehung nach links hatte, dann hat es
dazu geführt, dass dieser Linienverlauf hier nie konvex werden kann.
Und das hat uns letztendlich gesagt, wir müssen diesen Punkt hier
wieder rauswerfen und dann werden wir mehr konvex.
Und per Invariante haben wir dann gesehen, wir fügen jeden Punkt zu
unserer bisherigen konvexen Hülle einmal hinzu und löschen ihn auch
höchstens einmal, weil dann ist er draußen.
Also es könnte sein, dass man dann den nächsten Punkt auch noch
löschen müsste.
Wenn wir hier noch einen Punkt hätten, dann müsste man nicht nur
diesen Punkt löschen, sondern auch diesen, weil wir hier, wenn wir
hier rausgehen, dann ja auf jeden Fall auch nie mehr konvex werden
können.
Deswegen müssen wir diesen Punkt löschen und haben dann diese zwei
Punkte rausgelöscht, aber würden die auch später nie mehr bearbeiten.
Und dazu hatten wir dann einen Algorithmus, der lineare Zeit braucht,
wenn er drüber sweept, und eben Endlog Endzeit, wenn er sortiert.
Wenn man natürlich eine sortierte Eingabe hat, dann hat man einen
Linearzeitalgorithmus.
Letztendlich haben wir einfach geglaubt, dass wir diese Operation
hier, ob wir einen Winkel haben oder ob dieses Liniensegment bei
Hinzufügung des neuen Punktes nach links oder rechts abknickt, dass
wir das in Linearzeit berechnen können und hatten das dabei belassen.
Und jetzt möchte ich eine einfache Möglichkeit beschreiben, wie man
das dann in der Realität ziemlich effizient machen kann.
Weil letztendlich, was man machen kann, ist, man kann sich einfach
irgendwie so eine ziemlich komische if-else-Verschachtlung ausdenken,
je nachdem, ob der Punkt jetzt hier einen größeren x-Wert hat, einen
kleineren x-Wert und so weiter, sodass das dann halt irgendwie passt.
Das ist aber ziemlich ineffizient.
Was ich jetzt hier vorstelle, ist ein Ansatz, wo man die Determinante
benutzt und anhand des Wertes von der Determinante weiß, ob man so
eine links- oder eine rechtsdrehung hat.
Und das allgemeine Prinzip oder die Veranschaulichung davon ist
letztendlich, man hat hier drei Punkte, P1, P2 und P3 dürfte das sein
und die Determinante berechnet Trapeze unter jeweils zwei der Punkte.
Und die Determinante addiert die Trapezflächen genau so auf, dass wenn
wir eine Linksdrehung haben, also counterclockwise, dann ist die
Determinante von Punkt 1, 2, 3 positiv.
Und wenn wir eine Rechtsdrehung haben, dann ist die Determinante
negativ und wenn es einfach geradeaus weitergeht, dann ist die
Determinante null.
Und letztendlich kann man das hier ziemlich einfach ausrechnen.
Was man macht ist, man verschiebt den Punkt P1 an den Punkt 0,0.
Dadurch muss man dann die anderen Punkte natürlich auch mit
verschieben.
Das ist aber letztendlich nur eine Subtraktion.
Und dann berechnet man davon den Betrag.
Teilt es durch 1,5, wobei das Teilen auch eigentlich überhaupt nicht
nötig ist und hat dadurch oder damit durch ziemlich wenig
Multiplikationen und Subtraktionen bestimmt, ob man eine Rechtskurve
oder einen Rechtsabklick oder einen Linksabklick hat.
In diesem Beispiel hier hätte man einen Knick nach links und würde
dann einen negativen, einen positiven Wert rausbekommen.
Und was wir hier eben haben wollen, bei dem Speedplane Algorithmus,
wir wollen immer negative Werte, weil wir immer einen Rechtsknick
haben wollen, ohne im Ausnahmefall auch eine Gerade, die fortgeführt
wird.
Dieser Ansatz hier, der ist aber viel allgemeingültiger und kann für
verschiedenste Problemstellungen in der Geometrie verwendet werden.
Zum Beispiel, naja, hier jetzt schon eingeführte Cranium-Scan, aber
auch wenn man zum Beispiel enthalten sein von einem Punkt in einem
Polygon testen möchte, hier jetzt im konvexen Polygon, da funktioniert
das nämlich super.
Wir haben jetzt hier das konvexe Polygon.
Wir wissen also alle Punkte, die auf dem Polygon liegen.
Wenn man den nächsten Punkt betrachtet, dann liegt dieser immer
counterclockwise und es gibt zwei Fälle, entweder der Punkt liegt
außerhalb oder der Punkt liegt drinnen.
Hat jemand eine Idee, wie man prüfen kann, ob der Punkt, den man jetzt
betrachtet, innerhalb oder außerhalb von diesem konvexen Polygon
liegt?
Mit Hilfe der Vorschrift bzw.
der Aussage, ob jetzt ein Linksknick oder ein Rechtsknick kommt?
Gut, also letztendlich kann man sich zwei Fälle anschauen, entweder
das, fangen wir mit dem ersten Fall an hier, entweder der Punkt liegt
im konvexen Polygon und was man dann sieht, wenn man zwei benachbarte
Punkte auf dem Polygon anschaut und dann verlängert um die Gerade zum
Punkt, dann hat man in jedem Fall, wenn man die Punkte im Polygon
counterclockwise durchgeht, auf jeden Fall einen Linksknick und der
Linksknick hat einen größeren Winkel als der Linksknick, den der
nächste Punkt auf dem Polygon machen würde.
Und daraus kann man letztendlich dann herleiten, dass wenn das für
alle benachbarte Punkte auf dem Polygon zutrifft, dann liegt der Punkt
auch wirklich im konvexen Polygon.
Ein Gegenbeispiel ist jetzt dieser Punkt hier, der außerhalb von dem
Polygon liegt und wenn wir uns counterclockwise diesen und dann diesen
Punkt anschauen und um den Punkt, den wir betrachten wollen,
erweitern, dann haben wir hier jetzt erstmal einen Knick nach rechts,
aber dieser Winkel hier, der hier unten existiert, ist auf jeden Fall
auch größer als der Winkel, als wenn man diese Gerade hier um den
nächsten Punkt auf dem Polygon erweitern würde.
Letztendlich fesst man einfach alle benachbarten Punkte auf dem
Polygon, vergleicht den mit dem Punkt, der in der Anfrage enthalten
ist und bekommt dann die Antwort.
Gibt es dazu eine Frage?
Gut.
Ja, nochmal zusammenfassend letztendlich die letzten Vorlesungen, die
bei uns dran waren.
Wir hatten eben einmal die String-Algorithmen zur Wiederholung, naja,
wir hatten uns halt angeguckt, was ein suffix-Array ist, wir hatten
uns angeguckt, was ein LCP-Array ist, wir hatten uns dann angeguckt,
wie man darauf dann Pattern-Matching machen kann.
Damals in der Übung mithilfe vom suffix-Array und beschleunigt dann
durch das LCP-Array und später haben wir dann noch komprimiertere
Datenstrukturen angeschaut, da ist dann der WaveFetree in der ganzen
Vorlesung das Paradebeispiel gewesen.
Und hier jetzt dann im ersten Teil der Vorlesung heute die gleiche
Anfrage, die ich damals in meiner Übung vorgestellt habe, Pattern
-Matching hatten wir damals mit dem suffix-Array beschleunigt durch
das LCP-Array und hier nochmal zusätzlich das succinct abgespeichert
mithilfe von dem WaveFetree.
Was man auch sagen kann, der WaveFetree ist jetzt hier größtenteils in
der Stringologie verwendet worden, aber letztendlich kann verwendet
werden in diesem Beispiel heute um String-Algorithmen zu
implementieren, aber eben auch um geometrische Algorithmen zu
implementieren, indem man eben diese Bereichsabfrage ziemlich
geschickt implementieren kann.
Gut, dann sieht man sich hoffentlich nächsten Dienstag, falls es keine
Fragen mehr gibt, wäre es das von meiner Seite aus.