Informatik (Fach) / A&D (Sortieren, Vergleichen) (Lektion)

Sortierprogramme, BM, BMH, KMP

Diese Lektion wurde von scarvy erstellt.

Lektion lernen

Diese Lektion ist leider nicht zum lernen freigegeben.

zurück  |  weiter 1 / 1

• Wie funktioniert die exakte Suche mit einem naiven Algorithmus? - wie könnte man diesen verbessern? = man vergleicht von Links an, bei Mismatch Pattern ein Zeichen nach Rechts - Das Problem der exakten Textsuche ist es, alle gültigenVerschiebungen zu finden.- Man kann aber z.B. auch sagen: Finde alle Suffixe von T, die Pals Präfix haben. Verbesserung: Idee 1: Überspringe ein Teilwort w von T, falls klar ist, dasses im Muster nihct enthalten is t(BM-Algorithmus 1977).Idee 2: Merke Informationen über bisherige Vergleiche undnutze diese, um neue, unnötige Vergleiche zuvermeiden (KMP-Algorithmus 1977).    
• Was sind die Vor- und Nachteile der exakten Suche ? Vorteile:- einfache Implementierung    -keine Vorverarbeitung- für natürliche Sprachen gut geeignet Nachteil:- vorherige Vergleiche werden nicht weiterverwendet- Untergrenze der worst-case Effizienz: O(m + n), denn alleZeichen im Muster/Text müssen mindestens einmal gelesenwerden.-> O(m*
  n) ist trivial erreichbar -nach Vorverarbeitung von T ist O(m) – das wäre unabhängig von derGröße des Textes!  
• Was zeichnet den Boyer-Moore- Algorithmus aus? - Pattern wird von rechts nach links verglichen -nutzt bei Mismatch 2. Heuristiken:  Bad-Charakter-Heuristik                                                         Good Suffix Heuristik
• Wie funktioniert Good-suffix Heuristik? 2 Fälle:□ Mismatch nochmal im Pattern: verschieben bis zum letztenAuftreten□ Sonst: bis hinter den Mismatch schieben0 1 2 3 4 5 6 7 8 …A B A A B A D A C …E A B A C       E A B A C                       B A …
• Effizienz vom naiven, KMP und BM Algorithmus? Laufzeiten Naiver Algorithmus:□ Best: O(n) Avg: O(n*m) Worst: O(n*m)□ Schnell zu implementierenKMP-Algorithmus:□ Best: O(n) Avg: O(n) Worst: O(n)□ Der AllrounderBM-Algorithmus:□ Best: O(n/m) Avg: O(n) Worst: O(n*m)□ Besonders für große Alphabete geeignet
• Wie funktioniert der KMP? Der Algorithmus von Knuth, Morris und Pratt nutzt die bei Über­ein­stimmung von Zeichen gewonnene Information aus. So brauchen die Zeichen nach einem Mismatch nicht noch einmal alle wieder von vorn verglichen zu werden. Im Ergebnis benötigt der Algorithmus in der Suchphase nur noch O(n) Vergleiche. In einem Vorlauf (preprocessing) analysiert der Algorithmus zunächst das Muster und speichert Information über seine Struktur in einem Array der Länge m. Die Vorlaufphase lässt sich in Zeit O(m) durchführen. Da mn, hat der gesamte Algorithmus eine Komplexität von O(n).
• KMP anhand von Beispiel. Beispiel:   0123456789... a b c a b c a b d a b c a b d a b c a b d Die Zeichen an den Positionen 0, ..., 4 haben über­ein­gestimmt. Der Vergleich c-d an Position 5 ergibt einen Mismatch. Das Muster kann bis Position 3 weiter­geschoben werden, und der Vergleich wird ab Position 5 des Textes fortgesetzt. Die Schiebedistanz richtet sich nach dem breitesten Rand des über­einstimmenden Präfixes des Musters. In diesem Beispiel ist das über­einstimmende Präfix abcab; es hat die Länge j = 5. Sein breitester Rand ist ab mit der Breite b = 2. Die Schiebedistanz beträgt j – b  =  5 – 2  =  3.   0123456789... a b a b b a b a a a b a b a c a b a b a c a b a b a c a b a b a c a b a b a c              
• Good-suffix-heuristik Beispiele: Beispiel:   0123456789... a b a a b a b a c b a c a b a b c a b a b Das Suffix ab hat bereits über­ein­gestimmt. Das Muster kann so weit geschoben werden, bis das nächste Vorkommen von ab im Muster auf die Textzeichen ab ausgerichtet ist, also bis Position 2. In folgender Situation hat das Suffix ab bereits über­ein­gestimmt. Es gibt im Muster kein weiteres Vorkommen von ab. Daher kann das Muster hinter das ab geschoben werden, also bis Position 5. Beispiel:   0123456789... a b c a b a b a c b a c b a a b c b a a b In folgender Situation hat das Suffix bab über­ein­gestimmt. Es gibt im Muster kein weiteres Vorkommen von bab. Aber in diesem Fall kann das Muster nicht wie eben an Position 5 geschoben werden, sondern nur bis Position 3, da ein Präfix des Musters (ab) mit einem Teil des über­einstimmenden Suffixes bab über­einstimmt. Wir bezeichnen diese Situation als Fall 2 der Gutes-Ende-Strategie. Beispiel:   0123456789... a a b a b a b a c b a a b b a b a b b a b Das Muster wird jeweils um die längere der beiden Distanzen geschoben, die sich aus der Gutes-Ende- bzw. der Schlechtes-Zeichen-Strategie ergeben.  
• Bad-Charakter heuristik Beispiel: Beispiel:   0123456789...a b b a b a b a c b a b a ba c b a b a c Der Vergleich b-c liefert einen Mismatch. Das Textzeichen b kommt im Muster an Position 0 und an Position 2 vor. Das Muster kann so weit geschoben werden, dass das letzte b des Musters auf das Textzeichen b ausgerichtet ist, also bis Position 2.
• Welche Vorwerarbeitungsprozesse gibt es beim BM, BMH,KMP? Für die Good-suffix-heuristic wird ein Array s benötigt  um diese Schiebedistanz zu bestimmen, sind zwei unter­schied­liche Fälle zu betrachten. Fall 1:   Das über­einstimmende Suffix kommt noch an anderer Stelle im Muster vor Fall 2:   Nur ein Teil des über­einstimmenden Suffixes kommt am Anfang des Musters vor Für die Bad-character-heuristik wird eine Funktion occ (Occurrence-Funktion) benötigt, die für jedes Alphabet­zeichen die Position seines letzten Vorkommens im Muster liefert, bzw. -1, falls das Zeichen im Muster überhaupt nicht vorkommt.
• Wie funktioniert BMH? Von Horspool stammt die Idee, nur die Schlechtes-Zeichen-Strategie zu verwenden, jedoch nicht das Zeichen heranzuziehen, das zu einem Mismatch geführt hat, sondern stets das ganz rechte Zeichen des Textfensters. Beispiel:     Das Suffix ab hat über­ein­gestimmt, der Vergleich c-a ergibt einen Mismatch. Der Boyer-Moore-Algorithmus (a) ermittelt die Schiebedistanz nach der Schlechtes-Zeichen-Strategie aufgrund des letzten Vorkommens von c. Der Horspool-Algorithmus (b) ermittelt die Schiebedistanz aufgrund des letzten Vorkommens von b, wobei das Vorkommen des b an der letzten Position des Musters nicht mitzählt. Auch im Horspool-Algorithmus tritt der günstigste Fall ein, wenn jedesmal beim ersten Vergleich ein Textzeichen gefunden wird, das im Muster überhaupt nicht vorkommt. Dann benötigt der Algorithmus nur O(n/m) Vergleiche.
• Effizienz von BM-Algorithmus Analyse Unter der Bedingung, dass das Muster im Text nicht oder nur eine konstante Anzahl von Malen vorkommt, führt der Boyer-Moore-Algorithmus in der Suchphase im schlechtesten Fall O(nm) Vergleiche durch. Der Beweis hierfür ist allerdings recht schwierig. Im allgemeinen Fall sind Θ(n·m) Vergleiche erforderlich, etwa wenn das Muster am und der Text an ist. Durch eine geringfügige Modifikation des Algorithmus lässt sich die Anzahl der Vergleiche aber auch im allgemeinen Fall auf O(n) begrenzen. Ist das Alphabet groß im Vergleich zu Länge des Musters, benötigt der Algorithmus im Durchschnitt O(n/m) Vergleiche. Dies ist der Fall, weil die Schlechtes-Zeichen-Strategie häufig Verschiebungen um m ergib
• Wie sortiert man am Besten? Man nimmt den Suchalgorithmus mit der besten Effizienz... - u.a. abhängig von der Länge der Liste und dem Grad der Sortiertheit
• Definiere isort. > -- insertion sort: die Elemente werden nacheinander an die richtige Position "geschoben" (vgl. insert).> isort :: (Ord a) => [a] -> [a]> isort []     = []> isort (x:xs) = insert x (isort xs)   > -- fügt ein Element in eine sortierte Liste ein > insert :: (Ord a) => a -> [a] -> [a]> insert x []     = [x]> insert x (a:as) = if x <= a >                   then (x:a:as) >                   else a : insert x as
• Definiere quicksort. -Was ist der Unterschied verglichen mit mergsort? > qsort :: (Ord a) => [a] -> [a]> qsort (x:xs) = qsort less ++ [x] ++ qsort more>  where >  less = filter (x >) xs>  more = filter (x <=) xs> qsort [] = []
• Wie funktioniert mergesort? Funktionsweise Mergesort betrachtet die zu sortierenden Daten als Liste und zerlegt sie in kleinere Listen, die jede für sich sortiert werden. Die sortierten kleinen Listen werden dann im Reißverschlussverfahren zu größeren Listen zusammengefügt (engl. (to) merge), bis wieder eine sortierte Gesamtliste erreicht ist. 
• Wie ist mergesort definiert? Merge-Sort=Zusammenmischen zweier sortierter Listen. mergeSort :: [Int] -> [Int]mergeSort [] = []mergeSort [a] = [a]mergeSort x = merge (mergeSort links) (mergeSort rechts)where(links, rechts) = splitAt (length x ’div’ 2) x > merge :: (Ord a) => [a] -> [a] -> [a]> merge [] ys = ys> merge xs [] = xs> merge (x:xs) (y:ys) | x <= y = x : merge xs (y:ys)>                     | otherwise = y : merge (x:xs) ys
• Wie ist die Komplexität von mergesort? Mergesort ist im Gegensatz zu Quicksort stabil, wenn der Merge-Schritt richtig implementiert ist. Seine Komplexität (Worst-, Best- und Average-Case-Verhalten) beträgt in der Landau-Notation ausgedrückt stets . Damit ist Mergesort hinsichtlich der Komplexität dem Quicksort gewissermaßen überlegen, da der Quicksort (ohne besondere Vorkehrungen) ein Worst-Case-Verhalten von besitzt. Die Wahrscheinlichkeit, dass dieser Fall auftritt, ist jedoch so gering, dass Quicksort in der Praxis bessere Ergebnisse erziel
• Wie ist die Effizienz von quicksort? Laufzeit Die Laufzeit des Algorithmus hängt im Wesentlichen von der Wahl des Pivotelementes ab. Im Worst Case (schlechtesten Fall) wird das Pivotelement stets so gewählt, dass es das größte oder das kleinste Element der Liste ist. Dies ist etwa der Fall, wenn als Pivotelement stets das Element am Ende der Liste gewählt wird und die zu sortierende Liste bereits sortiert vorliegt. Die zu untersuchende Liste wird dann in jedem Rekursionsschritt nur um eins kleiner und die Zeitkomplexität wird beschrieben durch . Im Best Case (bester Fall) wird das Pivotelement stets so gewählt, dass die beiden entstehenden Teillisten etwa gleich groß sind. In diesem Fall gilt für die asymptotische Laufzeit des Algorithmus . Diese Zeitkomplexität gilt ebenso für den Average Case (durchschnittlichen Fall)   Speicherverbrauch Wie bei der Laufzeit hängt auch der Speicherverbrauch von der Wahl des Pivotelements und der Art der vorliegenden Daten ab. Im günstigsten und durchschnittlichen Fall, bei einer Rekursionstiefe in nlog(n), wird auch nur eine Stapelgröße von nlog(n) benötigt.
• Wie ist die Komplexität von isort? Komplexität Die Anzahl der Vergleiche und Verschiebungen des Algorithmus ist von der Anordnung der Elemente in der unsortierten Eingangsfolge abhängig. Für den Average Case ist eine genaue Abschätzung der Laufzeit daher schwierig, man kann aber zeigen, dass der Average Case in liegt. Im Best Case, wenn das Eingabearray bereits sortiert ist, ist die Komplexität linear , d. h. sogar besser als bei den komplizierteren Verfahren (Quicksort, Mergesort, Heapsort etc.). Im Worst Case ist sie quadratisch .
• Wie funktioniert isort? Insertion Sort (Sortieren durch Einfügen) ist einer der am einfachsten zu implementieren Sortieralgorithmen. Der Algorithmus funktioniert nach folgendem Prinzip: Betrachte alle Elemente der Reihe nach und füge jedes Element an den richtigen Platz unter den bereits sortierten Elementen ein, wobei diese natürlich sortiert bleiben. Das momentan betrachtete Element wird eingefügt, indem alle größeren Elemente um eine Position nach rechts bewegt werden, und dieses Element auf dem freigeworden Platz eingefügt wird.
• Wie funktioniert countingsort? - man braucht ein Intervall- zählt alle Elemente mit Hilfe von Array -> schreibt sie wieder auf

zurück  |  weiter 1 / 1