Suchindezies erstellen

[negaH]

Je gößer der Speicherverbrauch des Suchindex sein darf je schneller kann man suchen. Z.b. jede Datei wird als DAWG eingelesen und somit auch komprimiert. Die Suche nach einem 5 Zeichenwort wäre nun bei 100.000 Dateien = 100.000 * DAWG Laden + 100.000 * 5 Zeichenvergleiche. Dies wäre enorm effizient. Ein DAWG ist ein Directed Acyclic Word Graph, der sozusagen eine komprimierten Tree von Worten darstellt.
Angenommen das Laden eines DAWG per MMF dauert 0.5ms dann dauert die Suche darin selbst bei enorm großen Dateien nicht länger als 0.5ms.
Wortbasierte Textdateien können ca. auf 1/5 komprimiert als DAWG gespeichert werden. D.h. solche DAWG's würden zwar extrem schnelle Indexe ermöglichen wäre aber auch ziemlich speicherfressend. Allerdings jeder andere Index der eine exakte Suche ermöglichen soll wäre wesentlich größer.

Wenn der zusätzliche Speicherverbrauch gleich 0 sein soll, so müsste man die Datei selber jedesmal durchsuchen. Auch dafür gibt es sehr effiziente Verfahren, Boyer Moore zB.

D.h. du musst jetzt einen Komprimis finden, zwischen Speicherverbrauch + Performance + Exaktheit udn Komplexität der Suche. Angebracht wäre es z.b. einen temporären Suchpool der zu letzt gesuchten Begriffe zu benutzen. In diesem Suchpool sind die exakten Ergebnisse der letzen Suchen gespeichert. Wird erneut nach diesem Begriff gesucht so wird im Cache gesucht. Wird eine neue Datei in die Liste aufgenommen, so muß das aber dann berücksichtigt werden.

Ich habe z.B. auch schon per DAWG einen Suche implementiert. Dabei war die Komplexität der Suchkriterien das K.O. Kriterium. Das Suchmuster war komplex. Statt nun zu jeder Datei einen DAWG zu speichern, wurde der DAWG Erzeugungsalgorithmus zu EINER Datei optimiert. Nun wurden in einem DAWG die Suchmuster codiert und jede Datei so als würde man ein DAWG von dieser erzeugen eingelesen. Aber deren Daten wurden nur mit denen im Suchmuster DAWG abgeglichen. Angenommen im DAWG wurden 100 verschiedenen Wörter gespeichert so suchte dieser Algorithmus quasi in parallel nach dem Vorkommen dieser Wörter in den Dateien. Im Gegensatz dazu würde man beim Boyer Moore Algo. 100 mal die gleiche Suche pro Datei durchführen müssen.

Gruß Hagen