Dynamische Suche und Anzeige

Question

Ich habe eine große Last von Dokumenten, Text-Dateien, die ich nach relevanten Inhalten gesucht werden soll. Ich habe ein Suchwerkzeug gesehen, kann nicht remeber wo, das eine schöne Methode implementiert, wie ich weiter unten in meiner Anforderung beschreiben.

Meine Forderung lautet wie folgt:

• Ich brauche eine optimierte Suchfunktion: Ich liefere diese Suchfunktion mit einer Liste (einem oder mehr) teilweise abgeschlossen ist (oder vollständig) Worte mit Leerzeichen getrennt.
• Die Funktion findet dann alle Dokumente Wörter oder gleich dem ersten Wort enthält, dann diese gefundenen Dokumente in der gleichen Art und Weise suchen das zweite Wort mit, und so weiter, an dessen Ende es eine Liste gibt die aktuelle enthalten Wörter mit den Dokumenten (Name und Ort) verknüpft sie enthalten, für die komplette Liste von Wörtern.
• Die Dokumente müssen enthalten alle die Wörter in der Liste.
• Ich mag diese Funktion verwenden, um eine as-you-type Suche zu tun, damit ich die Ergebnisse in einer baumartigen Struktur in Echtzeit angezeigt und aktualisiert werden kann.

Ein möglicher Ansatz zu einer Lösung kam ich mit sich wie folgt: Ich erstelle eine Datenbank mit drei Tabellen (höchstwahrscheinlich mysql): ‚Dokumente‘, ‚Worte‘ und ‚Word_docs‘

.

• 'Dokumente' werden (idDoc, Name, Sitz) alle Dokumente.
• ‚Wörter‘ haben (idWord, Word), und sein eine Liste der eindeutigen Wörter aus allen Dokumenten (ein bestimmtes Wort erscheint nur einmal).
• 'Word_docs' hat (idWord, idDoc) und seine eine Liste der eindeutigen ID-Kombinationen für jedes Wort und dokumentiert es erscheint in.

Die Funktion dann mit dem Inhalt eines editbox auf jedem Tastendruck (außer Leerzeichen) aufgerufen wird:

• die Zeichenfolge Token versehen
• (hier meine Räder drehen ein bisschen): Ich bin sicher, dass eine einzelne SQL-Anweisung konstruiert werden kann, um die erforderliche Datenmenge zurückzukehren: (actual_words, DOC_NAME, doc_location); (Ich bin kein Hot-Nummer mit SQL), alternativ eine Folge von Aufrufen für jedes Token und analysieren-out die sich nicht wiederholende idDocs?
• dieser Datensatz (/ Liste / Array) wird dann zurückgegeben

Der zurückgegebene Liste-Inhalt wird dann angezeigt:

z.B .: callte mit: "seq sta cod" Displays:

sequence - start - code - Counting Sequences [file://docs/sample/con_seq.txt]
         - stop - code - Counting Sequences [file://docs/sample/con_seq.txt]
sequential - statement - code - SQL intro [file://somewhere/sql_intro.doc]

(und-so-on)

Ist das eine optimale Art und Weise, es zu tun? Die Funktion muss schnell sein, oder sollte es nur dann aufgerufen werden, wenn ein Raum getroffen wird? Sollte es Wortvervollständigung anbieten? (Haben Sie die Wörter in der Datenbank) Zumindest würde dies verhindern nutzlos Anrufe an die Funktion für Worte, die nicht existiert. Wenn die Wortvervollständigung: wie würde das umgesetzt werden

(Vielleicht könnte SO auch diese Art von Suche-Lösung verwenden Sie die Tags für das Surfen? (Im oben rechts auf Hauptseite))

Answer 1

Was Sie sprechen als invertierten Index oder Liste zu veröffentlichen, und arbeitet identisch wie zu dem, was Sie vorschlagen, und was Mecki schlägt. Es gibt eine Menge Literatur über invertierten Indizes gibt; Wikipedia-Artikel ist ein guter Anfang.

Besser, anstatt zu versuchen, es selbst zu bauen, verwenden Sie eine vorhandene invertierten Index Implementierung. Beiden MySQL und neuere Versionen von PostgreSQL haben die Volltextindizierung standardmäßig. Sie können auch Lucene für eine unabhängige Lösung prüfen wollen. Es gibt eine Menge Dinge in schriftlicher Form ein gut invertierten Index, einschließlich Tokenisierung, ergeben, Multi-Wort-Abfragen, etc, etc, und eine vorkompilierte Lösung zu prüfen, wird dies alles für Sie tun.

Answer 2

Der schnellste Weg ist mit Sicherheit nicht eine Datenbank überhaupt, denn wenn Sie die Suche manuell mit optimierten Daten tun, können Sie einfach auswählen Suchleistung schlagen. Der schnellste Weg, vorausgesetzt, die Dokumente ändern sich nicht sehr oft, ist auf Indexdateien zu erstellen und diese verwenden, um die Schlüsselwörter zu finden. Die Indexdatei wird wie folgt erstellt:

1. Alle eindeutigen Wörter in der Textdatei. Das ist die Textdatei durch Leerzeichen in Worte aufgeteilt und jedes Wort zu einer Liste hinzufügen, wenn bereits auf dieser Liste zu finden.

2. Nehmen Sie alle Wörter, die Sie gefunden haben und sortieren sie alphabetisch; der schnellste Weg, dies zu tun, wird unter Verwendung von Three Way Radix QuickSort . Dieser Algorithmus ist hart in der Leistung zu schlagen, wenn Strings zu sortieren.

3. Schreiben Sie die sortierte Liste auf die Festplatte, ein Wort eine Zeile.

4. Wenn Sie wollen nun die Dokumentdatei suchen, ignorieren sie vollständig, stattdessen die Indexdatei auf dem Speicher laden und binäre Suche verwenden, um herauszufinden, ob ein Wort in der Indexdatei ist oder nicht. Binäre Suche schwer zu schlagen ist bei der Suche großen, sortierten Listen.

Alternativ können Sie verschmelzen Schritt (1) und Schritt (2) in einem einzigen Schritt. Wenn Sie InsertionSort verwenden (die binäre Suche verwendet die richtige Einbauposition zu finden, ein neues Element in eine bereits sortierte Liste einfügen), haben Sie nicht nur einen schnellen Algorithmus, um herauszufinden, ob das Wort bereits auf der Liste ist oder nicht, für den Fall, es ist nicht, sehen Sie sofort die richtige Position zum einlegen bekommen und wenn man immer neue wie das einfügen, erhalten Sie automatisch eine sortierte Liste, wenn Sie zu Schritt erhalten (3).

Das Problem ist, müssen Sie den Index aktualisieren, wenn das Dokument ändert ... jedoch würde dies auch für die Datenbanklösung nicht wahr sein? Auf der anderen Seite, kauft die Datenbanklösung Sie einige Vorteile: Sie können es verwenden, auch wenn die Dokumente so viele Wörter enthalten, dass die Index-Dateien in den Speicher nicht mehr passen würde (unwahrscheinlich, da auch eine Liste aller englischen Wörter werden passen in den Speicher von jedem durchschnittlichen Benutzer-PC); Wenn Sie jedoch benötigen Indexdateien von einer großen Anzahl von Dokumenten zu laden, dann kann den Speicher zu einem Problem werden. Okay, können Sie umgehen, dass mit cleveren Tricks (zB der Suche direkt in den Dateien, die Sie in dem Speicher mmap mit abgebildet und so weiter), aber diese sind die gleichen Tricks Datenbanken bereits schnelle-Lookups ausführen verwenden, so warum neu zu erfinden das Rad? Weiterhin können Sie auch zwischen der Suche Worten und Aktualisieren von Indizes Sperrprobleme vermeiden, wenn ein Dokument geändert hat (das heißt, wenn die Datenbank die Verriegelung für Sie ausführen kann, oder das Update oder Updates als atomare Operation durchführen kann). Für eine Web-Lösung mit AJAX für Liste Updates nennt, eine Datenbank verwendet, ist wahrscheinlich die bessere Lösung (meine erste Lösung ist eher geeignet, wenn diese eine lokal ausgeführte Anwendung in einer niedrigen Niveau Sprache wie C geschrieben ist).

Wenn Sie das Gefühl, dass sie alle in einem einzigen ausgewählten Anruf zu tun (die möglicherweise nicht optimal sein, aber wenn man dynamacilly Web-Inhalte aktualisieren mit AJAX, erweist es sich in der Regel als die Lösung am wenigsten Kopfschmerzen verursacht), müssen Sie alle drei Tabellen JOIN zusammen. Mai SQL ist ein bisschen rostig, aber ich werde es versuchen:

SELECT COUNT(Document.idDoc) AS NumOfHits, Documents.Name AS Name, Documents.Location AS Location 
FROM Documents INNER JOIN Word_Docs ON Word_Docs.idDoc=Documents.idDoc 
INNER JOIN Words ON Words.idWord=Words_Docs.idWord
WHERE Words.Word IN ('Word1', 'Word2', 'Word3', ..., 'WordX')
GROUP BY Document.idDoc HAVING NumOfHits=X

Okay, vielleicht ist dies nicht der schnellste wählen ... Ich denke, es kann schneller erfolgen. Auf jeden Fall wird es alle entsprechenden Dokumente finden, die mindestens ein Wort enthalten, dann Gruppen alle gleich Dokumente zusammen mit ID, zählen, wie viele haben togetehr gruppiert wurden, und schließlich nur die Resultate aus, wo NumOfHits (die Anzahl der Wörter des IN-Anweisung gefunden) ist gleich der Anzahl der Wörter in der iN-Anweisung (wenn Sie für 10 Wörtern suchen, X 10).

Answer 3

Nicht sicher über die Syntax (dies ist SQL Server-Syntax), aber:

-- N is the number of elements in the list

SELECT idDoc, COUNT(1)
FROM Word_Docs wd INNER JOIN Words w on w.idWord = wd.idWord
WHERE w.Word IN ('word1', ..., 'wordN')
GROUP BY wd.idDoc
HAVING COUNT(1) = N

Das heißt, ohne dergleichen. Mit wie die Dinge sind viel komplexer.

Answer 4

Google Desktop Search oder ein ähnliches Werkzeug könnte Ihre Anforderungen entsprechen.