AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Suchindezies erstellen

Ein Thema von sakura · begonnen am 17. Aug 2003 · letzter Beitrag vom 17. Aug 2003
 
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#2

Re: Suchindezies erstellen

  Alt 17. Aug 2003, 14:10
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
  Mit Zitat antworten Zitat
 


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 05:24 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz