Suchindezies erstellen

[sakura]

Rein theoretisch interessiert mich mal mögliche Lösungen zu folgenden Szenario. Ich habe mehrere Text/XML/HTML Dateien mit mehr oder weniger sinnvollen Inhalten. Wenn ich mal davon ausgehe, dass ich die Texte extrahieren kann, dann würde ich gerne mal einen Suchindex erstellen, der es mir gestattet über die gesamten Dateien hinweg schnell zu suchen. Vorstellung ist es mit Datenmengen von bis zu 100.000 Dateien in einer Größenordnung von vielleicht 100MB Roh-Daten immer noch extrem performant zu sein.

Wer kennt mögliche Ansätze, welche nicht auf Datenbanken oder dem MS Index Service basieren? Wo könnte ich generell vernünftig anfangen. :mrgreen:

Ich bin auch für Tipps zu interessanter Literatur dankbar ;-) Source Code wird allerdings nicht verabscheut, ist aber wohl eher unwahrscheinlich :?

...:cat:...

[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

[sakura]

Hi Hagen, danke für diese Infos. Also, Speicherverbrauch soll nur ein begrenzte Rolle spielen. Sagen wir mal, das 5-8 fache der zu durchsuchenden Texte ist kein Problem :)

Gibt es zu diesem DAWG Literatur die Du auf Anhieb empfehlen kannst?

...:cat:...

[negaH]

"The World's Fastest Scrabble Program" by Andrew W Appel and
Guy J Jacobson. Comm. ACM, 31(5) 572-579 (May 1988).

Suche mal im WEB nach "DAWG+Algorithm+Scrabble+Wordgames" es gibt dazu eine Homepage und eine Group bei Google/eg. Yahoo. Leider finde ich den Link nicht mehr.

Allerdings, falls du vorhast eine OpenSource Anwendung zu coden, könnte ich mich breitschlagen lassen und dir meine DAWG Sourcen zur Verfügung stellen. Momentan muß ich aber noch abchecken ob ich das überhaupt darf, es war eine Auftragsarbeit.

Gruß Hagen

[negaH]

Achso, eines noch bevor du anfängst in die falsche Richtung zu rennen. Ein DAWG ist zwar enorm effizient aber das hat auch Konsequenzen. Normalerweise nutzt man DAWG's z.b. in Rechtschreibprüfungen/ Wortvervollstängigungsalgos./ Mustersuchen usw. Alle diese Algos. setzen vorraus das die Eingangsdaten Wort basiert sind. Dies hat enorme Vorteile und auch Nachteile. Im Falle deiner Bedürfnisse neheme ich an das du HTML's per Preprocessing in solche Wörter zerlegen kannst. D.h. das DWAG würde struktiert über strukurierte Daten suchen. Wie gesagt bei HTML's wäre das enorm von Vorteil da die Suche unwichtige Muster von vornherein ausfiltert, zB. Tags usw. Will man aber damit über binäre Daten such so versagt dieses Verfahren.

Gruß Hagen

[sakura]

Leider nicht OpenSource :wall: Aber danke für das Angebot ;-)

...:cat:...

[sakura]

Es sollen schon Worte/Texte sein. Stellt sich jetzt noch die Frage, wie es mit Unicode-Texten (Russisch, Japanisch, Italienisch, Polnisch, ...) aussieht ;-)

...:cat:...

[negaH]

Kommerziell, Shareware oder was ? Einem Deal mit mir steht nicht's im Wege :)

Gruß Hagen

[negaH]

Die Frage nach der Sprache oder Unicode stellt sich nicht. Es hängt einzigst von der Filterung beim Preprocessing ab. Allerdings, will man zB. ein Wort als Ansi und Unicode suchen so muß man im Such-DAWG beide Versionen speichern.

Dafür kann man das DWAG so benutzen das man mit Wildcards suchen kann.

Gruß Hagen