4 - Suchen

• 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

• 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

• 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

• ermöglichen effizientes Suchen, da Speicherort des gesuchten Schlüssels in konstanter Zeit erechnet werden kann

• Implementierung als Feld

• berechnet Hashwert aus Schlüssel x

• Hashwert auf Intervall beschränkt, das Adressen der Speicherorte widerspiegelt

  
  

• 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

• 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

• 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: 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

• verwendet zweite Hashfunktion, die durch Anzahl der bereits durchsuchten Speicherpositionen parametriert

• effektiver Sondiervorgang, wenn h(x) und h’(x) unabhängig

• 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

• 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

• 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

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)

• 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

• 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)