Trigrammfilter zur Vergleichseingrenzung

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

Trigrammfilter für einfache Suchanfrage

Die Suche folgt dem Schema der Aufbereitung. Der Suchausdruck wird wieder in Kombinationen zerlegt und dazu die entsprechenden Listen herausgesucht. Nun werden die Listen miteinander kombiniert. Müssen alle Trigramme des Suchausdrucks, in den zu suchenden Datensätzen enthalten sein, werden die Datensatzübereinstimmungen in die Ausgabeliste geschrieben, die Dokumentnummern enthält.

Als Optimierung kann hier mit der kürzesten Liste angefangen werden und/oder doppelte Trigramme ausgelassen werden weil diese nur gleiche Listen liefern würden. Aufgrund der Tatsache, dass, im einfachsten Fall, nur geschaut wird ob die Kombinationen in den Datensätzen vorhanden sind und nicht deren Position geprüft wird, müssen die ermittelten potentiellen Datensätze noch einmal mit einem normalen Vergleich geprüft werden.

Codeanmerkungen

Die Ausrufparameter des Programms, bis auf das letzte, werden als zu suchende Objekte benutzt und deren Muster ausgegeben:
```
for(int n=0; n<argc-2; n++)
{
   strings[n] = argv[n+1];
}
```
```
106
107
108
109
```
Der letzte Aufrufparameter wird als Muster ausgegeben gesucht.
```
trigramFilter.FindDocument(argv[argc-1], search);
```
```
114
```

So ergibt

./trigramfilter "ein test" "zwei test" "drei test" "vier test" "fuenf test" vier

die Ausgabe

Trigram filter test...

Input:
 0: ein test
 1: zwei test
 2: drei test
 3: vier test
 4: fuenf test
Filter:
 3: vier test