Filter: Suche

Hashtabellen finden sehr oft ihren Weg in Anwendungen, bei denen es wichtig ist, bei einer relativ konstanten Laufzeit, Datensätze mit Hilfe eines Schlüssels zu finden.

Beispiel (Quellcode): hashtable.cpp
Download (Quellcode): hashtable.zip

Beschreibung

Die Funktion einer Hashtabelle ist sehr einfach. Die Schlüsselwerte werden mit einer Konvertierungsfunktion (Hashfunktion) in einen Wert gewandelt, der direkt als Index für ein Datenfeld benutzt wird. Durch die Verringerung des Schlüssels auf einen kleineren Wertebereich, kann es zu Kollisionen kommen. Das heißt auch, dass die Werte keine eindeutige Referenz für den Schlüssel sind. Somit muss, in der Designphase des Endproduktes, schon drauf geachtet werden, wie mit Kollisionen umgegangen werden soll. Da gibt es gleich einen ganzen Schwung an Möglichkeiten:

1. Ignorieren. Je nach Bedarf der Anwendung, kann der neue Schlüssel wichtiger sein als ein Älterer, z.B. oft bei Kompressionssuchbäumen oder statistischen Daten.

2. Datenfeld erweitern. Um die Kollisionen…

Um eine schnelle Suche über viele große Datensätze zu haben, ohne jeden Datensatz anfassen zu müssen, eignet sich ein Trigrammfilter. Er ähnelt dem Musterfilter, schliesst aber potentielle Datensätze direkt aus und liefert schneller kleinere Ergebnislisten.

Beispiel (Quellcode): trigramfilter.cpp
Download (Quellcode): trigramfilter.zip

Aufbereitung

In der Basis besteht dieser Filter aus mehreren Listen oder Feldern, die Trigrammen (immer drei Zeichen) zugeordnet sind. Am Anfang werden die Datensätze eingelesen, in alle möglichen Drei-Zeichen-Kombinationen zerlegt und die Datensatznummer in die entsprechende Liste der Kombination abgelegt. Die Datensatznummern sollten z.B. aufsteigend sein oder einem anderen Schema folgen, da dies später beim evtl. nötigen Vergleich einen Geschwindigkeitszuwachs gibt. Ein Dokument muss nicht mehrmals in einer Liste auftauchen, weil nur ermittelt werden muss, ob eine Kombination im Dokument existiert und nicht wo. Dies wäre optional.

Suche

Die Suche folgt dem Schema der…

Ein Filter für bestimmte Datenmuster ist immer dann brauchbar, wenn Datensätze eingegrenzt bzw. ausgeschlossen werden sollen. Es wird hier anhand eines Filters zur Eingrenzung von Zeichenkettensuchoperationen, mit einem Beispiel, beschrieben. Natürlich lässt sich dieses Verfahren auf beliebige Daten anwenden und ist eine effektive Hilfe die nötigen Suchoperationen stark zu verringern und somit die Laufzeit des Codes zu verbessern.

Beispiel (Quellcode): patternfilter.cpp
Download (Quellcode): patternfilter.zip

Beschreibung

Mit Hilfe einer Funktion zur Mustererzeugung, wird jedes Element des Objektes in einem Datenfeld (entspricht einem Alphabet) mit seinem Wert als vorhanden markiert. Besteht ein Element aus mehreren Teilen, kann auch der Hashwert verwendet werden. Dies ist für das zu durchsuchende Muster sowie für das gesuchte Muster gleich. Sind die gleichen Markierungen, für beide Muster, im Datenfeld vorhanden, sind gleiche Elemente in den Objekten.

Da aber die Position der Elemente nicht, ggf. Hashw…

Die binäre Suche hilft sehr schnell zu entscheiden, ob ein Element in einem sortierten Datenfeld vorhanden ist. Dabei werden maximal nur log2(n) Vergleiche benötigt, die Position zu finden, an der dieses Element sein sollte sofern vorhanden.

Beispiel (Quellcode): binarysearch.cpp
Download (Quellcode): binarysearch.zip

Beschreibung

Die binäre Suche schaut in der Mitte des Datenfeldes, ob der gesuchte Wert größer oder kleiner des Feldschlüsselwertes ist. Ist er kleiner, wird der untere Teil des Datenfeldes weiter benutzt, im anderen Fall der obere. Bei nächsten Durchlauf, wird mit dem entsprechenden Teilfeld weitergearbeitet. Die Suche ist beendet, wenn nur noch ein Element vorhanden ist und dieses dem gesuchten Wert entspricht.

Aufgrund dieser Vorgehensweise, ist es unbedingt notwendig, dass dieses Datenfeld sortiert ist. Nur in diesem Fall kann davon ausgegangen werden, dass nach dem Wertevergleich, das entsprechende Teilfeld den Suchwert nicht enthalten kann.

Beispieldarstellung

In diesem Bild wird di…