Suchen in Listen
Liste von Elementen gegeben, von dem jedes aus Schlüssel und dazugehörigem Wert besteht
Aufgabe: Zu gegebenen Schlüssel dazugehöriges Element finden
Im einfachsten Fall: Schlüssel und Wert identisch
Suche in ungeordneten Listen - Sequenzielle Suche (Brute-Force)
einfachste Verfahren zur Suche in Listen
Durchlaufen der Liste bis Wert gefunden
Laufzeit: 0(n)
setzte keine Sortierung der Liste voraus
bei sortierter Liste existieren überlegenere Verfahren
Suche in geordneten Listen - Binäre Suche
nutzt Teile-und-herrsche Prinzip
Worst-Case-Laufzeit von 0(log n)
Ablauf
1) Beginne Suche beim mittleren Element
2) Schlägt Vergleich fehl, wiederhole 1) auf der Teilliste, in der sich das Element befinden muss
Hashtabelle Definition & Implementierung
Datenstruktur, bei der Speicherort der Elemente über mathematische Funktion (Hashfunktion) aus dem Schlüssel des Elements berechnet wird
ermöglichen effizientes Suchen, da Speicherort des gesuchten Schlüssels in konstanter Zeit erechnet werden kann
Implementierung als Feld
Hashfunktion - Definition
berechnet Hashwert aus Schlüssel x
Hashwert auf Intervall beschränkt, das Adressen der Speicherorte widerspiegelt
Hashtabellen - Eigenschaften
perfekt
minimal
Kollision
Hashverfahren
perfekt: Jeder Schlüssel hat anderen Speicherort
minimal: Anzahl der möglichen Speicherorte nicht größer als Anzahl der Schlüssel
minmal perfekte Hashfunktionen nur bei vorab bekannten, beschränkten Schlüsselmengen
Kollision: Wenn zwei unterschieliche Schlüssel im gleichen Hashwert bzw. Speicherort resultieren
Hashverfahren: besteht aus Hashfunktion und Strategie zur Kollisionsauflösung
Hashtabellen - Lastfaktor und Rehashing
Lastfaktor: Auslastung einer Hashtabelle
Je höher Lastfaktor, desto wahrscheinlicher Kollisionen
Einfügen & Suchen wird langsamer
Performance-Einbußen vermeiden: Größe der Hashtabelle wird bei Überschreiten eines bestimmten Lastfaktors dynamisch angepasst
Größenanpassung erfordert Rehashing aller Elemente
Hashtabellen - Kollisionsauflösung
Separate Chaining
Separate Chaining: Einzelnen Speicherorten werden Datenstrukturen zugeordnet, die mehrere Elemente aufnehmen können (z. Bsp. verkettete Listen)
bei Suche nach Element muss gg. auch Unterdatenstruktur durchsucht werden
Open Addressing
Open Addressing: Elemente werden direkt in Speicherort der Hashtabelle gespeichert
Wenn Speicherort belegt: Mit Sondierverfahren nach nächstem freien Speicherort gesucht
lineares Sondieren
Double-Hashing
Kuckucks-Hasing
Bei Suche nach Element wird bei Hash-Adresse begonnen - trifft man leeren Speicherort, ist Element nicht vorhanden
Schrittgröße zwischen durchsuchten Speicherpositionen konstant
alle Speicherpositionen werden getroffen
Sondiervorgang lang
Double Hashing
verwendet zweite Hashfunktion, die durch Anzahl der bereits durchsuchten Speicherpositionen parametriert
effektiver Sondiervorgang, wenn h(x) und h’(x) unabhängig
Kuckucks Hashing
jedes Element besitzt zweite Speicherposition, an die es verschoben werden kann, wenn es von erster Position verdrängt wird
mit zwei Hashtabellen mit unterschiedlichen Hashfunktionen realisiert
Problem: es kann ein Zirkel der Verdrängung entstehen, der sich nicht auflöst
Coalesced Hashing
Hybrid aus Separate Chaining und Open Addressing
Bei Kollision wird Kette der rivalisierenden Elemente gebildet (=separate Chaining), aber die Elemente in unterschiedlichen Positionen des ursprünglichen Arrays gespeichert (=Open Adressing)
betroffene Elemente referenzieren sich gegenseitig
LISCH
EISCH
Suchen in Zeichenketten
gegeben: Zeichenkette aus n Zeichen (=Suchtext) und Zeichenkette bestehend aus m Zeichen (=Suchwort), mit m<=n
Aufgabe: Prüfe, ob Suchwort im Suchtext enthalten
Falls ja, gib Position des ersten Vorkommens zurück
Naive Suche - Brute-Force
Vorgehen
1) Richte Suchwort am Anfang des Suchtextes aus
2) Prüfe, ob alle Buchstaben des Suchworts mit den zeichen im Suchtext übereinstimmen
Wenn ja, wurde das Wort gefunden. Gib aktuelle Position zurück und beende die Suche
Wenn nein, gehe zu 3)
3) Prüfe, ob das Ende des Suchtextes erreicht wurde
Wenn ja, ist das Wort nicht enthalten. Beende die Suche.
Wenn nein, verschiebe Suchwort um 1 Zeichen nach rechts und wiederhole ab 2)
Laufzeitverhalten
Knuth-Morris-Pratt-Verfahren
Idee
Vermeide wiederholte Vergleiche an der selben Textstelle (kein Rücksetzen im Text)
1) Durchführen einer Wortanlyse und erstellen einer Randtabelle
Rand zählt, wie viele Zeichen eines Wortes, sowohl dessen Anfang (=Präfix) als auch Ende (=Suffix) bilden. Überlappungen von Präfix und Suffix sind zulässig
Randtabelle enthält den Rand für jedes Teilwort bis zum j-ten Zeichen des Suchwortes
2) Suchen: Bei Scheitern an der Position j
Verschiebe das Suchwort um j - rand[j-1] Zeichen (bzw. 1 Zeichen bei j=0)
Setze Suche direkt nach dem Rand fort (=Zeichen im Suchtext, bei dem die Suche zuvor gescheitert ist)
Aufstellen einer Randtabelle hat immer Laufzeit 0(m), unabhängig vo Suchtext
Boyer-Moore-Horspool-Verfahren
Eigenschaften
Vereinfachung des Boyer-Moore-Verfahrens
verwendet nur vereinfachte Bad-Character-Heuristik, keine Good-Suffix-Heursitik
verwendet zur Berechnung der Verschiebung nicht das Zeichen, bei dem der Fehler auftrat, sondern immer das letzte Zeichen des aktuellen Textfensters
weniger Speicherbedarf, einfachere Implementierung
1) Aufstellen einer Verschiebungstabelle
allen Zeichen, die nicht im Wort enthalten sind, wird Verschiebung m zugeordnet (Wortlänge)
den Zeichen, die im Wort enthalten sind, wird Verschiebung m - j -1 zugeordnet, wobei j die letzte Position des Zeichens im Wort ist (nicht letztes Zeichen im Wort)
steht Zeichen nur an letzter Stelle des Suchwortes, wird ihm die Verschiebung m zugeordnet
2) Suchen
Beginne Vergleich am Wortende
Bei Scheitern, verschiebe Wort um Verschiebungswert des letzten Zeichens des Suchfensters
Worst-Case-Laufzeit
0(n*m)
Average-Case-Laufzeit
0(n)
Last changed2 years ago