Ich weiß nicht, was sie in normalen Windows-Suche verwenden. Aber es gibt eine Technik, in der Sie Indizierung von Dateien gleichzeitig verwenden und den Index später für schnellere Suche verwenden (z. B. Windows-Suche 4.0)
Gibt es einen anderen Weg, schneller zu suchen? Können Sie aus der Sicht der Implementierung arbeiten? (Vorausgesetzt, dass ich es möglicherweise implementieren muss)
Um es einfach zu verstehen, lassen Sie es mich so sagen:
Angenommen, ich möchte eine Suchanwendung erstellen, die ähnlich wie die in Windows verwendete Suchoperation ausführt.
Meine Frage ist: Welche Möglichkeiten / Wege / Ansätze gibt es, um eine solche Anwendung zu erstellen? (und die sind schneller als die bestehenden.)
(Kann eine binäre Suchbaumart verwendet werden?)
Es gibt grundsätzlich zwei Techniken, die für die Volltextsuche über große Korpora verwendet werden: Buchungslisten und Suffix-Arrays.
Eine Buchungsliste ist eine Liste von (Begriff, Dokument_ID) Paaren, optional mit einer Position im Dokument. Wenn Sie es sortieren oder nach Begriffen hashen, haben Sie einen effizient durchsuchbaren Volltextindex.
Es gibt verschiedene Techniken, um Buchungslisten kleiner, schneller zugänglich, schneller zu aktualisieren und flexibler zu machen, einige auf Kosten der Genauigkeit. Lucene ist wahrscheinlich der beste standardmäßige Post-Listen-basierte Text-Indexer, der heute verfügbar ist, und (im Gegensatz zu Ihrem früheren Kommentar) kann er Text indexieren, der in PDF-, Microsoft Word-Dateien gefunden wurde. Das Projekt Lucene.net , das von Thomas Maierhofer verlinkt wird, sieht wie ein ziemlich vernünftiger Port aus, obwohl Sie natürlich immer ein etwas hinter der Spitze dessen, was in der Java-Version vor sich geht.
Für ein Korpus, das viel größer als der Speicher ist, müssen Sie die Veröffentlichungsliste ziemlich genau auf der Festplatte speichern. Das spricht gegen einen einfachen binären Suchbaum, um darauf zuzugreifen: Wenn Sie hunderttausend Dokumente mit je zehntausend Wörtern haben, haben Sie eine Milliarde Postings, was bedeutet, dass Ihr binärer Suchbaum eine minimale Tiefe von 30 hat. Das Problem dabei ist dass die 30 Knoten auf dem Pfad von der Wurzel des Baumes zum Blatt sich im Allgemeinen in verschiedenen Teilen Ihrer Festplatte befinden - also muss die Platte 30 Mal suchen, um die Postings für einen Begriff zu finden! Das sind ungefähr 2½ Sekunden, was sehr langsam ist.
Es gibt jedoch eine modifizierte Version der Binärbaum-Datenstruktur, die als "B-Baum" bezeichnet wird, die kann . Lucene verwendet eine einfache Datenstruktur, die einer B-Struktur sehr ähnlich ist, aber massive Aktualisierungen viel einfacher unterstützt. Ich habe eine sehr einfache Version dieser Datenstruktur in meinem eigenen dumbts-Projekt geschrieben implementiert eine Volltext-Suchmaschine für meine E-Mail in einigen Python-Seiten. Ich benutze es jeden Tag, es ist freie Software, und es funktioniert ziemlich gut für das, wofür ich es verwende, aber es ist nicht genau ein Weltklasse-Suchsystem wie Lucene.
Als Beispiel, wie Sie Buchungslisten auf Kosten der Genauigkeit verkleinern können, ist das Managing Gigabytes-Buch (und das mg4j project ) hat eine Datenstruktur, die als "signed minimum perfect hash table" bezeichnet wird, die die indexierten Begriffe nicht speichert - nur Hashes von ihnen. Es gibt also eine geringe Wahrscheinlichkeit für ein falsch positives Ergebnis - Sie müssen die Dokumente abrufen, die den Begriff enthalten sollen, um zu bestätigen, dass sie das wirklich tun.
Suffix-Arrays, die eine viel kompaktere und etwas langsamere Version von radix trees (aka tries) sind, werden von GLIMPSE und ein paar anderen Programmen implementiert, aber sie sind heutzutage nicht mehr in Gebrauch. Sie haben eine gewisse Flexibilität, die in der Datenstruktur der Buchungsliste nicht vorhanden ist - sie ermöglichen beispielsweise die Suche nach regulären Ausdrücken und Suchen mit Rechtschreibfehlern, aber sie sind nicht ganz so schnell. Es hat kürzlich einige Arbeiten mit der Burrows-Wheeler-Transformation gegeben, die auf Suffix-Arrays basiert und einen Komprimierungsalgorithmus bereitstellt, bei dem die komprimierte Datei der Volltextindex ist! Die am besten dokumentierte Version heißt FM-Index , obwohl ich gehört habe, dass es ältere Versionen der Technik gibt, vielleicht unveröffentlicht. Im Gegensatz zu den anderen oben beschriebenen Techniken, denke ich, dass dies nicht funktioniert, wenn die Dokumente PDF-Dateien oder ähnliches sind - Sie könnten immer noch denselben Ansatz verwenden, um eine Textversion jeder Seite zu extrahieren und zu indizieren, aber Sie nicht habe nicht den Vorteil, das Originaldokument zu komprimieren.
Mein Bekannter Tim hat eine wirklich gute einführende Serie von Blog-Postings geschrieben auf der Suche im Jahr 2003, die immer noch ziemlich gut sind. Sie decken dieses Material (mit Ausnahme der jüngsten Entwicklungen) in viel mehr Tiefe.
Ravi: Ist das die Art von Informationen, die du suchst?
Edit: Danke für die Korrektur meiner Formatierung, Martin!
Sehen Sie sich Lucene an. Es ist eine super schnelle Suchbibliothek für Text (Dateien). Es steht auch Lucene.NET zur Verfügung. Wenn Sie es selbst implementieren möchten, ist es ein guter Ausgangspunkt und Benchmark für Ihre Implementierung.
Suchen Sie nur nach Dateinamen oder möchten Sie sich auch den Inhalt ansehen? In welcher Sprache möchten Sie dies umsetzen?
Wenn Sie nur nach Dateinamen suchen, ist ein Index eine große Leistungssteigerung. Wenn Sie jedoch jede Datei, nach der Sie suchen, öffnen müssen, hilft der Index nur beim Öffnen nur dieser Dateien wo sich der gesuchte Inhalt befindet möglicherweise befindet.
Sie müssen immer noch jede Datei öffnen, bis Sie gefunden haben, wonach Sie Ausschau halten.
Volltextsuche: Stellen Sie sich vor, Sie hätten ein Wörterbuch mit Wörtern, und für jedes Wort schreiben Sie auf, welches Dokument das Wort und den genauen Ort des Wortes in diesem Dokument enthält. Dies wird als Volltextindex bezeichnet und ermöglicht beispielsweise die boolesche Suche und das Abgleichen einer exakten Wortgruppe. Die Volltextindizierung kann problemlos auf Millionen von Dokumenten skaliert werden und wird von Windows Search 4.0 im Allgemeinen verwendet. Siehe auch Lucene oder Sphinx.
Konzeptsuche: Bei der konzeptuellen Suche können Sie eine Reihe relevanter Wörter (oder sogar ein ganzes Dokument) eingeben und Dokumente zurückgeben, die Ihrer Eingabe am ähnlichsten sind. Basierend auf Ihrer Sammlung von Dokumenten erzeugt es Konzepträume, die es ihm ermöglichen, semantische Verknüpfungen zwischen Wörtern abzuleiten. Dadurch können relevantere Suchergebnisse zurückgegeben werden, da der Computer die gesuchten Konzepte "versteht" und konzeptuell ähnliche Wörter und Ausdrücke findet. Dies wird von Unternehmenssuch- und eDiscovery-Lösungen häufig verwendet. Produkte, die konzeptionelle Suche anbieten, umfassen Engenium und Autonomy.
Meta-Suche: Anstatt direkt auf dem Inhalt zu suchen, suchen Sie nach Informationen zum Inhalt, die als Metadaten bezeichnet werden. Metadaten können Elemente wie Tags, Schlüsselwörter, Autorenname, Zeitstempel usw. enthalten. Wenn Sie zum Beispiel das ungefähre Datum kennen, zu dem ein Dokument geschrieben wurde, können Sie diese Metadaten in Ihre Suchkriterien aufnehmen, um Ihre Suche schneller einzuschränken Ergebnisse.
Wie Sie sehen können, gibt es viele Möglichkeiten, sich der Suche zu nähern, und jede beinhaltet viele verschiedene Arten von Datenstrukturen. Wenn es ein bestimmtes Gebiet gibt, auf das ich näher eingehen soll, kann ich das für dich tun.
Es gibt viele Forschungsarbeiten zur Volltextsuche im Internet, und es gibt viele Quelltexte. Wenn Sie sich diese ansehen, werden Sie sehen, dass die Verwendung eines binären Suchbaums auf modernen Hardware keine guten Ergebnisse liefern wird. Ein binärer Suchbaum ist eine sehr spezifische Datenstruktur, die auf einer modernen CPU mit mehrstufigem Cache nicht so schnell wie möglich ist. Schnelle Datenstrukturen haben einen höheren Fan Out als 2.
Außerdem ist das Problem eher für einen (Radix) -Trie geeignet. Siehe Wikipedia.
Tags und Links .net search full-text-search data-structures filesystems