Filter: 2013-09

Musterfilter zur Vergleichseingrenzung (Bloomfilter)

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

Musterfilter für einfaches Alphabet 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…