Volltextindizierung?

[Gast]

Cool, ein Forum, in dem man sich nicht anmelden muss. =)

Ich hab nun schon im Internet ein paar Seiten gelesen, aber mir wird einfach nicht klar, was genau die Volltextindizierung sein soll.

Bis jetzt hab ichs so verstanden, dass Inhalt von Feldern stichwortartig notiert und diese Stichpunkte in einer weiteren Tabelle gespeichert werden mit Verweis auf die Tabelle, wo der Rest steht.

Stimmt das so?! Wäre super, wenn das jemand kurz und bündig mir klären könnte oder einen netten Link hat.

[MadMan2k]

http://de.wikipedia.org/wiki/Volltextindizierung#Technik

[HellHorse]

Konkret für MySQL:
http://epsilondelta.wordpress.com/2006/02/08/dissecting-mysql-fulltext-indexing/

[HajottV]

Hi,


Ich hab nun schon im Internet ein paar Seiten gelesen, aber mir wird einfach nicht klar, was genau die Volltextindizierung sein soll.

Bis jetzt hab ichs so verstanden, dass Inhalt von Feldern stichwortartig notiert und diese Stichpunkte in einer weiteren Tabelle gespeichert werden mit Verweis auf die Tabelle, wo der Rest steht.


Okay, machen wir mal ein Beispiel für zwei Dokumente:


Dokument 1 = Dieser Text beschreibt invertierte Listen.
Dokument 2 = Und hier ist noch ein Text. Noch ein Text.


Als erstes werden diese Dokumente vorverarbeitet, d.h.:

- Satzzeichen werden eliminiert
- Groß/Kleinschreibung wird normalisiert
- häufige Wörter (sogenannte Stopwörter), wie "dieser", "und", "der", "die", "das", "ist", "noch" werden rausgeworfen

Fortgeschrittene Textprozessoren machen auch eine grammatikalische Reduktion der Wörter auf Wortstämme... und noch 1000 ganz tolle Sachen. ;)

Nach der Vorverarbeitung haben wir also:


Dokument 1 --> text beschreibt invertierte listen
Dokument 2 --> hier text text


Jetzt werden die verarbeiteten Wörter (man spricht nun von Indextermen) in eine Liste (*) eingefügt. Diese Liste bezeichnet man als: Wordindex


1 text
2 beschreibt
3 invertierte
4 listen
5 hier


In den Dokumenten werden nun die Terme durch ihre Zahl in der Liste dargestellt und die Häufigkeiten ausgezählt.

Notation: <index, häufigkeit>


Dokument 1 --> <1, 1> <2, 1> <3, 1> <4, 1>
Dokument 2 --> <5, 1> <1, 2>


Nun bildet man für jeden Term eine Liste mit der Dokumentnummer und der Häufigkeit des Terms in dem Dokument.

Der Indexterm "text" kommt in Dokument 1 und Dokument 2 vor. In Dokument 1 mit Häufigkeit 1 und in Dokument 2 mit Häufigkeit 2.

Notation: [dokumentnummer, häufigkeit]

Also:


1 --> [1, 1] [2, 2]


Die gesamte Datenstruktur nennt man eine invertierte Liste. Sie sieht dann so aus (*):


1 --> [1, 1] [2, 2]
2 --> [1, 1]
3 --> [1, 1]
4 --> [1, 1]
5 --> [2, 1]


Den kompletten obigen Vorgang nennt man Indizierung.

Wie funktioniert jetzt eine Suche?

Angenommen, ein Benutzer sucht jetzt nach dem Suchbegriff "text".

Dann passiert folgendes:

Zuerst durchläuft die Eingabe die gleiche Vorverarbeitung wie die Dokumente. Also wenn der Benutzer "ein text." eingibt, dann wird da "text" draus. Dann wird der Wortindex nach dem Begriff durchsucht. Wird er nicht gefunden, dann gibt es kein Dokument. Wird der Begriff gefunden, dann liefert der Wortindex eine Nummer zurück... in dem Beispiel hat der Term "text" den Index 1. Nun wird auf die invertierte Liste für den Index 1 zugegriffen. Das liefert:


1 --> [1, 1] [2, 2]


Hier steht also: Dokument 1 enthält "text" 1x und Dokument 2 zweimal.

Jetzt kann man also einen Link auf Dokument 1 und Dokument 2 zurückgeben.

Bei mehreren Termen in der Suche wird mehrfach auf die invertierte Liste zugegriffen und die Häufigkeiten werden nach ausgeklügelten Verfahren verrechnet.

Echte Suchmaschinen berücksichtigen die relative Häufigkeit der Wörter im Dokument (kommt das Wort in einem kurzen Dokument häufig vor, dann ist das Dokument wohl wichtiger für das Wort als wenn es in einem langen Dokument nur einmal auftritt) sowie die Gesamthäufigkeit in allen Dokumenten... und machen noch gaaanz viele andere Dinge.

Wenn Du noch Google'n möchtest, dann such mal nach:


information retrieval
invertierte Liste
TF-IDF
vektorraummodell


Wenn Du wirklich in die Materie einsteigen möchtest... findest Du hier (http://www-users.kawo2.rwth-aachen.de/~hajott/Diplom.pdf) die Diplomarbeit eines unglaublich brillianten Informatikers zu dem Thema. :massa: :massa: :massa: :massa:

Ich arbeite inzwischen auch in der Branche. :biggrin:

Gruß

Jörg

(*) "richtige" Suchmaschinen haben da sehr ausgeklügelte Datenstrukturen, komprimierte B*-Bäume, Skiplisten...

[Shink]

Schreib grad selbst an einer Diplomarbeit zu einem Thema, dass damit zu tun hat ("Grid-distributed IR using LSI"). Vielleicht find ich ja etwas sinnvolles, das ich zitieren kann...

[HellHorse]

- häufige Wörter (sogenannte Stopwörter), wie "dieser", "und", "der", "die", "das", "ist", "noch" werden rausgeworfen
Dachte ich zuerst auch. Kannst du dir den Sock vorstellen, den ich kriegte, als ich rausfand, dass Google das Web nach the (http://www.google.ch/search?q=the) und a (http://www.google.ch/search?q=a) indiziert. :umassa:

[Coda]

Omg X-D

[HajottV]

Schreib grad selbst an einer Diplomarbeit zu einem Thema, dass damit zu tun hat ("Grid-distributed IR using LSI"). Vielleicht find ich ja etwas sinnvolles, das ich zitieren kann...

Ah,

vielleicht könnte das in dem Zusammenhang das hier für Dich interessant sein: PLSI (Hofmann, Probabilistic latent semantic analysis)?

Das ist eine probabilistische Entsprechung von LSI... hier werden die Dokumenthistogramme über eine weitere Zufallsvariable z (die Aspekte) geglättet.

Hofmann, Probabilistic latent semantic analysis (http://www.cs.brown.edu/~th/papers/Hofmann-UAI99.pdf)

Nur mal so aus Interesse... wie verteilt man denn den LSI Algorithmus? Lokale Gradientenabstiege in den Nodes und dann Austausch?

Gruß

Jörg

[HajottV]

Dachte ich zuerst auch. [...]

Das oben war eine extreme Vereinfachung.

Klar, wenn man professionelles Retrieval macht, dann werden auch Stopwörter indiziert - das braucht man spätestens dann, wenn man Phrasensuche machen möchte ("to be or not to be"). Das ist aber auch kein großes Problem, weil die invertierten Listen prima komprimierbar sind.

Gruß

Jörg

[DocEW]

Hui, Jörg, da hast du dir aber viel Arbeit gemacht - wow!

Hier noch ein weiteres nützliches Script:
http://www-mmdb.iai.uni-bonn.de/download.php?language=de

[Shink]

Nur mal so aus Interesse... wie verteilt man denn den LSI Algorithmus? Lokale Gradientenabstiege in den Nodes und dann Austausch?

Das ist eben die Frage... Herkömmliche Ansätze (z.B. Parallelisierung des Block-Jacobi-Ansatzes) haben einen erheblichen Kommunikationsaufwand, den ich mir nicht leisten kann.
Meine Frage war, wie gut der Ansatz ist, wenn ich die SVD "einfach" auf jedem Node ausführe. Antwort: In manchen Fällen sogar schlechter als ohne LSI, AUSSER ich hab Einfluss darauf, wo welche Dokumente liegen.
Mit meinem Ansatz erreiche ich beinahe die Qualität von unverteiltem LSI, bei deutlich reduziertem Rechenaufwand (ich hab ja pro Node nur einen Bruchteil der Dokumente. Da ich ja weit jenseits von linearer Komplexität bin, ist die Summe der verwendeten Zeit geringer als bei Rechnen ohne Verteilung).
Auch interessant: Bei gewissen Verteilungen (allerdings nicht per allgemeinem Algorithmus erreichbar) sind meine Ergebnisse sogar besser als ohne Verteilung.

Ich weiß; das Gelben vom Ei ist das alles auch nicht gerade, aber vielleicht kann ja jemand mit den Ergebnissen was anfangen.

Wenn du vom Fach bist: Weißt du eine tatsächlich universell einsetzbare Methode, um den (fast) optimalen Rang für die Rangreduktion herauszufinden?

[Trap]

SVD und Rang ist lineare Algebra, dafür benutzt man bei großen Matrizen doch Lapack, oder nicht?

[HajottV]

LSI hab ich noch nie implementiert, aber eine verwandte Sache. Wie man das sinnvoll verteilt, habe ich nie rausbekommen... augrund des Kommunikationsaufwand.

In manchen Fällen sogar schlechter als ohne LSI.

Oh, das hätte ich jetzt nicht gedacht... man lernt nie aus. Auf welchen Datensammlungen hast Du die Evaluation gemacht? TREC?

Mit meinem Ansatz erreiche ich beinahe die Qualität von unverteiltem LSI, bei deutlich reduziertem Rechenaufwand

Na das ist doch ein prima Ergebnis. :up:

Beim IR ist es eh so, daß man ja schon mit einer einfachen heuristischen Metrik wie SMART richtig gute Ergebnisse erzielen kann... um da signifikant besser zu werden, muß man richtig Aufwand betreiben. Aber wäre ja auch langweilig, wenn es so einfach wäre. :biggrin:

Zur Rangreduktion... ich weiß, was das ist, aber damit hört es dann auch auf. So sehr wie Du stecke ich bei Weitem nicht im Thema LSI nicht drin.

Gruß

Jörg

[Shink]

SVD und Rang ist lineare Algebra, dafür benutzt man bei großen Matrizen doch Lapack, oder nicht?
Gaynau. Nur dauert das bei großen Datenmengen eben "ewig" und ScaLapack hat da nix drin.
Auf welchen Datensammlungen hast Du die Evaluation gemacht? TREC?
Medline Text Collection.
TREC ist kostenpflichtig, oder?