Wie Volltextsuche realisieren?
-
Moin,
ich möchte eine Volltextsuche in einer größeren Masse (im Gigabytebereich) an Textdokumenten ermöglichen.
Die einfache Variante ist ein Wortindex, der für jedes Wort eine Liste von Dokumenten speichert, die das entsprechende Wort enthalten.
Das ist zwar einfach zu implementieren, jedoch lässt sich damit nicht nach Wortfolgen suchen. Und mir fällt keine vernünftige Möglichkeit ein, dies zu realisieren - außer eben die gesamte Datenmasse zu durchsuchen. Zwar kann man mithilfe des Wortindex einige Dokumente ausschließen, die nicht alle Worte der Wortfolge enthalten, das nützt aber nicht viel bei häufig vorkommenden Wörtern.Wie macht Google das? Dort kann man ja nach Wortfolgen suchen, indem man sie in Anführungszeichen fasst. Aber Google kann bei einer solchen Anfrage unmöglich seine gesamten Datenbestände durchkämmen - zumal so eine Anfrage in ~0.15s abgewickelt wird. In dieser Zeit müssten weltweit Anfragen an hunderttausend(e?) datenspeichernde Server gestellt werden, diese müssten jeweils ihre Gigabytes an Dokumenten durchgehen und die Ergebnisse rechtzeitig zurücksenden - und das alles in 150ms? Eher nicht, vermute ich mal.
Gibt es einige clevere Methoden, die man in diesem Fall gewinnbringend einsetzen könnte?
-
Ich weiß zwar nicht, wie es google macht, aber denke daran, daß der Wortindex die Worter und Dateipositionen hat und bei einer Kombianfrage alle Dateien mit dem einen Wort und alle mit dem anderen Wort aus dem Index anschaut und die nimmt, wo die deateien gleich sind und die wortposition des zweiten==wortpostiond des ersten + länge(erstes wort)? müßte für normale terabyteplatten schnell genug sein, hoffe ich.
-
Das sieht nach einer guten Lösung aus - allerdings mit dem Preis, dass der Index gigantisch anwächst und garantiert nicht mehr ins RAM passt. Allein die Indexeinträge für Wörter wie the/and/you etc. dürften jeweils im dreistelligen MB-Bereich liegen. Aber dafür dauert ein Suchvorgang höchstens noch wenige Sekunden, bei optimistischen Schätzungen.
Und für den Fall, dass die Wortfolge mindestens ein eher seltenes Wort enthält, lässt sich bestimmt noch gut optimieren.
Danke für den Vorschlag, ich werd's mal so versuchen.
-
Athar schrieb:
Das sieht nach einer guten Lösung aus - allerdings mit dem Preis, dass der Index gigantisch anwächst und garantiert nicht mehr ins RAM passt.
Das ist zum Glück recht egal. Du wirst den Index so bauen können, daß die Liste der dieses Wort enthaltenden Eintragsverweise in der Index-Datei am STück liegen. Oder eine Indexdatei als Baum, die nur Dateipostitionen auf die Vorkommensdatei hat. In der Vorkommensdatei dann an dieswr Position eine lin4eare Liste,
ups, jetzt kapiere ich das Problem. In der Vorkommensdatei unter "a" steht eine Liste ALLER Dateien.
Na, scheiß drauf. Andersrum optimieren. Jede Datei hat nur einen int als ID und in der Vorkommensdatei steht jeweils die ID und der Offset und die IDs sidn sortiert. Dann ist "kommtvor(wort1) and kommtvor(wort2)" nur ein log2(wortanzahlüberhaupt)*zeit(plattenzugriff)+log2(wortanzahlüberhaupt)*zeit(plattenzugriff)+max(anzahl(wort1),anzahl(wort2))*sequantiellPlatteLesen[also ungefähr nichts].
-
Jo, es ist bereits so, dass die Dokumente eine ID haben.
Aber obwohl sequentiell gelesen werden kann, ist die Vorkommenseintrag z.B. für "the" mit >100 Millionen Vorkommnissen recht groß. Wenn jetzt ein Scherzkeks nach fünf solchen Monsterwörtern sucht, kann's schon mal länger dauern (wenn ich micht nicht irre, dann muss ich nämlich anzahl(wort1)+anzahl(wort2)... Einträge von der Platte lesen).
-
Athar schrieb:
Jo, es ist bereits so, dass die Dokumente eine ID haben.
Aber obwohl sequentiell gelesen werden kann, ist die Vorkommenseintrag z.B. für "the" mit >100 Millionen Vorkommnissen recht groß. Wenn jetzt ein Scherzkeks nach fünf solchen Monsterwörtern sucht, kann's schon mal länger dauern (wenn ich micht nicht irre, dann muss ich nämlich anzahl(wort1)+anzahl(wort2)... Einträge von der Platte lesen).Nein, Du mußt nur log(wortanzahl)+log(wortanzahl)+log(wortanzahl)... den unendlich langsamen Schreib-Lesekopf positionieren (5ms!!!). Das sequentielle Lesen sobald er mal da ist ist quasi instant.
Wenn die Dokumente schon eine ID haben um so besser, dann ist das Lesen sequentielle Lesen ja perfekt schnell.
Leider sind 100Mio Vorkommnisse auch 100Mio*8Bytes, also 8M zu lesen wenn jemand nach "a" fragt. Geht noch.
Von den Wörtern weißt Du ja die Anzahlen. Vielleicht nimmst Du das erste Wort (das seltenste) und suchst es normal, vom zweiten Wort je nach häufigkeit
- ganze Vorkommensliste lesen und linear mit anderer Liste verglerichen. Beide sind ja sortiert, das geht in O(max(anzahl der Beteiligen Listen))
- in der Liste des zweiten Wortes binär suchen, ... Ach, was soll der Scheiß. Kann kar nicht besser sein. Die Listen der selteneren Worte sind entweder groß, dann vergleiche sequentiell, oder sie sind klein, dann mach es auch.
Ich glaube, es wird bei allen einigermaßen sinnvollen Suchanfragen weit unter einer Sekunde bleiben.
Also für Abfragenplanung noch zum auf der Platte liegenden Baum außer dem start des Worts noch die anzahl der Vorkommnisse abspeichern. Ich würde wenn möglich dem Dateisystem noch Arbeit aufbürden, pro Wortvorkommnisliste eine Datei. Und gelegentlich defragmentieren.
-
volkard schrieb:
Leider sind 100Mio Vorkommnisse auch 100Mio*8Bytes, also 8M zu lesen wenn jemand nach "a" fragt. Geht noch.
Eher 800M
Das lässt sich vielleicht noch auf 4.2-4.5 bytes/Eintrag drücken, wenn man die ID+Anzahl nachfolgender Positionen immer nur einmal am Anfang angibt.Von den Wörtern weißt Du ja die Anzahlen. Vielleicht nimmst Du das erste Wort (das seltenste) und suchst es normal, vom zweiten Wort je nach häufigkeit
- ganze Vorkommensliste lesen und linear mit anderer Liste verglerichen. Beide sind ja sortiert, das geht in O(max(anzahl der Beteiligen Listen))
- in der Liste des zweiten Wortes binär suchen, ... Ach, was soll der Scheiß. Kann kar nicht besser sein. Die Listen der selteneren Worte sind entweder groß, dann vergleiche sequentiell, oder sie sind klein, dann mach es auch.Ja, so hatte ich es vor (erst nach dem seltenen suchen). Wobei mir jetzt dämmert, dass das Wort wahrscheinlich schon verdammt selten sein muss, damit sich ein teilweises Überspringen beim Lesen der anderen Liste überhaupt lohnt.
Und außerdem brauche ich dann noch einen Index vom Index (zumindest für die häufigen Worte).Also für Abfragenplanung noch zum auf der Platte liegenden Baum außer dem start des Worts noch die anzahl der Vorkommnisse abspeichern. Ich würde wenn möglich dem Dateisystem noch Arbeit aufbürden, pro Wortvorkommnisliste eine Datei. Und gelegentlich defragmentieren.
Das wollte ich vermeiden, da man dann praktisch keine Optimierungsmöglichkeiten mehr hat. Entweder das Dateisystem macht das anständig schnell oder halt nicht... ob das Dateisystem mit Millionen Dateien gut fertig wird, müsste sich dann zeigen.
Die Wörterliste müsste aber ohne weiteres ins RAM passen, inklusive Indexposition und Anzahl. Da kann man dann eine feine map verwenden. Notfalls könnte ich vielleicht auch alle Wörter, die nur einmal vorkommen, rauswerfen. Ist meistens sowieso nur Unfug, nach dem nie jemand suchen würde, aber es gibt sehr viele davon.
-
Mist.
Naja, abgesehen davon, daß ich nur Quatsch geredet hatte, hoffe ich, daß die Unterhaltung Dir ein paar Ideen schneller gebracht hat, die Dir ein paar Tage später eh eingefallen wären.
Ich wäre trotzdem voll interessiert an einer kleinen Vorstellung der verwirklichten Ideen, wenns klappt.
Ich denke nicht daran, die seltensten Wörter zu streichen! Nein, im Gegenteil! Nach "a" und "the" und "an" wird nicht explizit gesucht, die haben keinen Informationsgehalt. Nur nach "Zonentaxonomie"(hat auch keinen, aber das weiß der Bot nicht) und "C++" und "malloc". Wenn Du "a" und "the" und "an" eifach ganz ignorierst, sind die Findungen fast genausogut.
Fremdsuchanbier wie google kännen übrigens Sachen wie "a" streichen, ohne daß der Normalsterbliche es bemerkt. Hat google afair auch lange Zeit gemacht. Jetzt nicht mehr, sie protzen mit Rechenpower, um keinen mehr nachkommen zu lassen.
-
Jo, das hat doch ein paar gute Denkanstöße gegeben.
Stimmt schon, die Einmalwörter sollten nicht rausfliegen, aber vielleicht muss man sie auch nicht unbedingt ständig im RAM halten.
Wenn ich's schaffe, das ganze auf anständige Suchzeiten herunterzubringen, meld ich mich nochmal. Sicher lässt sich z.B. durch Indizieren von häufigen Wortpaaren noch was machen.
Ich schlafe am besten noch mal drüber, frisch ausgeruht kommen einem meist die besten Ideen.
-
Vielleicht kannst du was mit dem parallllllel mustererkennenden Aho-Corasick- Algorithmus anfangen, der im Unix proggi fgrep eingebaut ist.
-
Athar schrieb:
Wie macht Google das?