Fast Pattern Matching

FPM -DB

Fast Pattern Matching Database

Pattern-Matching ist eine Abfrage der Datensätze auf das Vorkommen einen bestimmte Teilstrings.

Die Idee war eine Datenbank-Indexierung zu finden, die speziell für Pattern-Matching bestimmt ist.

Die suche nach einem File, etwa *.h oder *.adb ist eine vereinfachte Form davon.

Eine kompliziertere Form ist z.B :

*Audi*A6*Baujahr*199*, oder *Ste??en*M??er*,

Jeder Index, der auf Reihenfolge basiert, versagt, sobald wir einen Stern am Anfang und am Ende der Suchmaske haben.

Eine konkrete Benutzung dieser Datenbank hatte ich für meine MP3-CD und Daten-CD Bestände geplant.

Bevor die Einzelheiten zur Implementation kommen, ist hier die Übersicht der Eigenschaften der FPM-DB:

(Die Anzahl der Datensätze sei N, meine DB hat momentan N=209711, System : Athlon 750, DB komplett im RAM)

Suchzeiten sind linear, O(N)
Einfügezeiten eines neuen Datensatzes sind nahezu konstant O(1) (Da kein Reindex oder Rehash nötig)
Speicherplatzbedarf ist linear, O(N)
Primäre Benutzung nach WORM-Prinzip (Write Once, Read Many), löschen von Datensätzen sollte Ausnahme sein, daher (noch) nicht implementiert
Die Suche kann parallelisiert werden (nicht implementiert)
Der Index kann angepasst werden (z.B. Namen, Files, Musik, usw.)
Suchzeiten auf meinem System (bis alle passende Datensätze markiert sind): Worst Case : 210 ms, Best Case : 10 ms (schwer zu messen)
Im Best Case benötigt DB etwa 75 Takte pro Datensatz (also ca. 75 Prozessor-Befehle) (bei mir ca. 10.000.000 Datensätze / s)
Im Worst Case liegt die Performance bei ca. 1000.000 Datensätze / s, Worst Case tritt eigentlich nie auf.
Meine üblichen Suchzeiten : 40 ms - 100 ms
Die Datenbank hat eine Baumstruktur. Suche in einem Teilbaum ist möglich

Wer Interesse an dem Source hat oder Einzelheiten der Implementierung(C++) wissen will, kann mir mailen (siehe unten)

Die Beschreibung des Fast Pattern Matching Verfahrens, den ich verwendet habe ist in pdf verfügbar : fpm.pdf

Das GUI zur der Datenbank-Engine ist nicht sehr benutzerfreuendlich. Da es mir nicht um die perfekte Oberfläche ging, sondern um Performance.

Ihr könnt die Windows Version hier dowloaden. Keine Installation nötig, einfach auspacken und starten. :-)

Download fpm.zip (226kb)

Alexander Kramer