Volltextsuche in Java?
Stefan Matthias Aust
Volltextsuche". Ich erinnere mich an Tenary Search Trees und auch
Lucent, doch er sagt "kein spezieller Server, du hast nur eine
Datenbank". Also Fat Client. Was eigenes? Wie am besten?
Was ist eine Volltextsuche? Ich gebe ein oder mehrere Worte eines Textes
ein und finde eine Referenz auf diesen Text. Ich kann mir also eine
Tabelle
WORDS
word varchar(30)
r_id int(4)
bauen, und dort zu jedem Wort eines Textes, einer Ressource, eine ID
ablegen, die diese Ressource bezeichnet. Alle Texte werden auf
Buchstaben mit lowercase beschränkt. Worte mit weniger als 3 Zeichen
werden nicht aufgenommen, des weiteren keine Worte als einer weiteren
Tabelle, die als zu häufig und nicht aussagekräftig definiert wurden.
Damit kann ich über "SELECT r_id FROM words WHERE word='auto'" jetzt
eine Liste von Ressourcen bekommen, die Auto erwähnen.
Doch die Liste ist komplett unsortiert. Würde es helfen, wenn ich noch
zähle, wie häufig jedes Wort in einer Ressource vorkommt und in einer
dritten Spalte einen Zähler ablege, der dann herangezogen werden kann,
um das Ergebnis nach der Häufigkeit zu sortieren?
Wäre es effizienter, zwei Tabellen zu benutzen?
INDEX WORDS
w_id: int(4) word: varchar(30)
r_id: int(4) w_id: int(4)
w_id ist eine eindeutige Zufallszahl, die jedem Wort zugeordnet wird
oder 0, falls dies ein Stoppwort ist, welches berücksichtigt wird.
Normalform erreicht und Platz gespart, aber langsamer?
Was mache ich, wenn ich nach Ressourcen suchen will, die zwei Worte
enthalten? "SELECT r_id FROM index WHERE w_id=:X AND r_id IN (SELECT
r_id FROM index WHERE w_id=:Y)"? Was, wenn meine Datenbank keine
Subselects kann? Was, wenn ich nach X aber nicht Y suchen will?
Was wenn ich die Schreibweise nicht genau kenne? Ich glaube, google hat
das am Anfang auch nicht unterstützt. Inzwischen macht er/sie/es jedoch
Vorschläge für die korrekte Schreibweise. Weiss das System einfach,
dass man statt "paralel" eigentlich "parallel" meint, indem es eine
Tabelle dafür hat? Zählt es, wie häufig jedes Wort ist und wenn ein
unbekanntes Wort - oder eines mit einer sehr geringen Häufigkeit -
auftritt, wird der Wortabstand berechnet und das Wort mit dem kleinsten
Abstand und der größten Häufigkeit als Alternative vorgeschlagen?
Soweit überblicke ich das ja alles noch. Doch was, wenn ich in diesem
Text z.B. nach "zwei Tabellen" suchen will, also nach einer
Wortkombination? Muss ich zusätzlich noch alle Wortpaare als "Worte" in
meiner WORDS-Tabelle aufnehmen? Oder eine Tabelle
INDEX2
w_id1: int(4)
w_id2: int(4)
r_id: int(4)
definieren, in der ich alle Paare ablege? Und bei drei
zusammenhängenden Worten? Oder kann ich doch nicht alle gleichen Worten
einer Ressource zu einem Datensatz zusammenfassen, sondern muss
stattdessen noch eine Wortnummer ablegen, der angibt, das wievielte Wort
einer Ressource dieses ist, damit ich dann bei Kombinationen puzzeln
kann: Die Wortindizes verschiedener der selben Ressource müssen
aufsteigend sein. Ich wüsste jetzt auf anhieb gar nicht, wie ich so ein
SELECT-Statement formulieren sollte. Ich könnte mir alle r_id,
w_no-Paare des ersten Worts holen und dann für die folgenden Worte mit
"SELECT COUNT(*) FROM index WHERE w_id=:X AND r_id=:Y AND w_no=:Z)"
prüfen, ob die Ressourcen überhaupt in Frage kommt.
Noch ein Problem - was mache ich, wenn sich eine Ressourcen ändert? Aus
INDEX alle Einträge mit der entsprechenden r_id entfernen und dann die
Ressource neu indizieren? Gerade um zu jedem Wort die w_id zu bestimmen
muss ich dann aber extrem viele Anfragen machen. Besser wäre wohl,
diese Tabelle komplett zu cachen. Groß kann die ja nicht sein, sagen
wir, 100.000 Worte mit durchschnittlich 6 Zeichen - das wären gerade mal
6 MB Zeichen. Hm, 12 MB in Java... eigentlich reichen mir a-z, ä, ö, ü
und ß. Die 15 häufigsten Zeichen kann ich in 4 bits kodieren, bleibt
1111 um die anzugeben, dass die nächsten 4 bits die 15 weniger häufigen
Zeichen enthalten. Passt. Damit sind das nur noch 3 MB. Zudem kann ich
gleiche Präfixe zusammenfassen bzw. das ganze gleich als TST ablegen...
Fehlt was? Geht das besser? Gibt es etwas fertiges? Alternativen?
bye
--
Stefan Matthias Aust //
www.3plus4software.de // Inter Deum Et Diabolum Semper Musica Est
Steffen Ramlow
> Lasst mich laut nachdenken: Ein potentieller Kunde sagt "baue mir eine
> Volltextsuche". Ich erinnere mich an Tenary Search Trees und auch
> Lucent, doch er sagt "kein spezieller Server, du hast nur eine
> Datenbank". Also Fat Client. Was eigenes? Wie am besten?
Also, ich hatte mal ein Projekt, da wurde genau das versucht. Ist an der
Performanz gescheitert, sobald nicht nur nach einem Wort gesucht wird und /
oder unscharf gesucht werden soll. Aus diesem Grunde wird es wohl auch immer
separate Volltextsysteme geben. Sogar die DB-Hersteller wie MS oder Oracle
nutzen keine relationalen Strukturen, um ihren DBs Volltext beizubringen.
Dazu kommt i.A. noch, das Fundstellen oft auch wichtig sind, dann
explodieren dir langsam aber sicher die Tabellen.
Um welche Mengen handelt es sich denn bei dir?
Joachim Arrasz
>>Lasst mich laut nachdenken: Ein potentieller Kunde sagt "baue mir eine
>>Volltextsuche". Ich erinnere mich an Tenary Search Trees und auch
>>Lucent, doch er sagt "kein spezieller Server, du hast nur eine
>>Datenbank". Also Fat Client. Was eigenes? Wie am besten?
es gibt mit Lucene doch eine Volltextsuche die OpenSource ist und
gleichzeitig Java. Soweit ich weiss ist inzwischen auch Htdig für Java
erhältlich.
Vielleicht hilft Dir das weiter
Gruss Achim
Stefan Matthias Aust
> Also, ich hatte mal ein Projekt, da wurde genau das versucht. Ist an der
> Performanz gescheitert, sobald nicht nur nach einem Wort gesucht wird und /
> oder unscharf gesucht werden soll. Aus diesem Grunde wird es wohl auch immer
> separate Volltextsysteme geben. Sogar die DB-Hersteller wie MS oder Oracle
> nutzen keine relationalen Strukturen, um ihren DBs Volltext beizubringen.
Moment, Oracle bietet in ihrer Datenbank Unterstützung für
Volltextsuche? Oder meinst du ein Zusatzprodukt?
> Dazu kommt i.A. noch, das Fundstellen oft auch wichtig sind
Ich dachte mir, es reicht die Ressource selbst zu finden und einfach
alle Vorkommen des/der Worte hervorzuheben. Aber prinzipiell hast du
natürlich recht. Grummel.
> Um welche Mengen handelt es sich denn bei dir?
Vielleicht 2 MB an Daten? Eigentlich lächerlich wenig... Vielleicht
sollte man einfach alles laden und dann im Client suchen :)
Steffen Ramlow
> Steffen Ramlow wrote:
>
>> Also, ich hatte mal ein Projekt, da wurde genau das versucht. Ist an
>> der Performanz gescheitert, sobald nicht nur nach einem Wort gesucht
>> wird und / oder unscharf gesucht werden soll. Aus diesem Grunde wird
>> es wohl auch immer separate Volltextsysteme geben. Sogar die
>> DB-Hersteller wie MS oder Oracle nutzen keine relationalen
>> Strukturen, um ihren DBs Volltext beizubringen.
>
> Moment, Oracle bietet in ihrer Datenbank Unterstützung für
> Volltextsuche? Oder meinst du ein Zusatzprodukt?
Grünau! Frag mich aber nicht nach Preisen.
>
>> Dazu kommt i.A. noch, das Fundstellen oft auch wichtig sind
>
> Ich dachte mir, es reicht die Ressource selbst zu finden und einfach
> alle Vorkommen des/der Worte hervorzuheben. Aber prinzipiell hast du
> natürlich recht. Grummel.
Naja, und was, wenn es z.B. ein Dokument mit 10.000 Seiten ist. Die willst
du doch nicht erst in den Client lutschen und dann festzustellen, dass nur
Seite 666 (jaaa!), das Gewünsche enthält.
>
>> Um welche Mengen handelt es sich denn bei dir?
>
> Vielleicht 2 MB an Daten? Eigentlich lächerlich wenig... Vielleicht
> sollte man einfach alles laden und dann im Client suchen :)
Wie jetzt, insgesamt? Menno, sag das doch gleich :) Ja, rein in den Client
mit den 2 MB und Feierabend. Oder meinetwegen auch in der DB, relational,
falls es mal 100 MB sind. Also wegen 2 MB würd ich mir nicht die VT-Option
von Oracle an die Backe nageln!
michael paap
> Vielleicht 2 MB an Daten? Eigentlich lächerlich wenig... Vielleicht
> sollte man einfach alles laden und dann im Client suchen :)
Sag mal... bei 2 MB ist es ja fast schon machbar, das ganze Zeug einmal
in einer HashMap zu indizieren... mit einer Liste der Fundstellen als
Value zu den Worten als Key. Oder liege ich da sehr falsch?
Gruß,
Michael
--
Sollte ausnahmsweise eine Mail-Antwort auf ein Posting vonnöten sein,
bitte folgende Adresse verwenden: newsreply@<Absender-Domain>.
Stefan Matthias Aust
>>> Lucent
> es gibt mit Lucene doch eine Volltextsuche
Oops, hatte ich falsch geschrieben. Ich weiss, doch ich meine, die
nutzt einen eigenen Server und speichert seine Daten in irgendwelchen
Index-Dateien. Ich werde mich damit aber nochmal beschäftigen.
Zumindest können die sogar mit der Levenshtein-Distanz suchen. Nett...
Ich habe gerade mal diesen Algorithmus ausprobiert und um 100.000
zufällige Strings gegen "Stefan" zu matchen (und da meinem Namen zu
finden) braucht meine Implementierung 0,4 sek. Da hätte ich mich (wieder
einmal) total in der Zeit vertan. Solange das im Hauptspeicher passiert,
nicht weiter schlimm. Ansonsten kann man der DB ja auch eine
entsprechende stored procedure verpassen. Also, die Ähnlichkeitssuche
fürchte ich jetzt gar nicht mehr ;)
Bleibt die Frage, wie ich nach Wortfolgen suche...
Roland Kunzke
Stefan Matthias Aust schrieb:
> Oops, hatte ich falsch geschrieben. Ich weiss, doch ich meine, die
> nutzt einen eigenen Server und speichert seine Daten in irgendwelchen
> Index-Dateien. Ich werde mich damit aber nochmal beschäftigen.
>
> Zumindest können die sogar mit der Levenshtein-Distanz suchen. Nett...
Geht auch ohne Sever, ganz normal in einer Java-Anwendung. Und der Index
läßt sich, wenn gewünscht, mittels RAMDirectory im Arbeitsspeicher anlegen.
Gruß Roland
Stefan Matthias Aust
> Naja, und was, wenn es z.B. ein Dokument mit 10.000 Seiten ist. Die willst
> du doch nicht erst in den Client lutschen und dann festzustellen, dass nur
> Seite 666 (jaaa!), das Gewünsche enthält.
Ich würde aus jeder Seite eine eigene Ressource machen...
>>Vielleicht 2 MB an Daten? Eigentlich lächerlich wenig... Vielleicht
>>sollte man einfach alles laden und dann im Client suchen :)
>
> Wie jetzt, insgesamt? Menno, sag das doch gleich :) Ja, rein in den Client
> mit den 2 MB und Feierabend. Oder meinetwegen auch in der DB, relational,
> falls es mal 100 MB sind. Also wegen 2 MB würd ich mir nicht die VT-Option
> von Oracle an die Backe nageln!
2 MB über eine dünne Leitung laden ist aber auch nicht so prall. Sagen
wir intranet mit 10 MBit - da braucht das dann vielleicht 4sek. Zu
lange, würde ich sagen. Und wenn ich etwas ändere, muss ich den Berg
Daten wieder zurückschaufeln? Hm, dann doch lieber die
Datenbank-Lösung. Ich denke, ich muss mal spicken, wie genau Lucene es
schafft, nach Wortfolgen zu suchen...
Jetzt ist mir das ganze jedenfalls wesentlich klarer, danke für's zuhören :)
Jochen Theodorou
[...]
Ich hab es jetzt nicht probiert, aber gab es da nicht auch noch LIKE?
Ist aber glaube ich nicht sonderlich performant, aber vielleicht einen
Test Wert.
Sowas wie "SELECT * FROM TextTable WHERE text LIKE '%Auto%'" sucht dann
alle Vorkommen des Wortes auto im Text. Das findet auch 'Autofahrer',
'Autolenkrad' usw. mit NOT kann man das auch verbinden, AND und OR sind
auch möglich. Nur eine Ähnlichkeitssuche wird es damit wohl nicht geben
und die Gross-/Kleinschreibung ist relevant.
Gruss theo
Stefan Matthias Aust
>> Zumindest können die sogar mit der Levenshtein-Distanz suchen. Nett...
>
> Geht auch ohne Sever, ganz normal in einer Java-Anwendung. Und der Index
> läßt sich, wenn gewünscht, mittels RAMDirectory im Arbeitsspeicher anlegen.
Ich glaube wir missverstehen uns hier. Natürlich ist der Algorithmus
auch außerhalb von Lucene einsetzbar... ich habe ihn ja auch als kleines
Javaprogrämmchen eben selbst implementiert. Die hatten mich nur auf
eine Idee gebracht, weil ich annahm, das wäre zu aufwendig und hatte das
überhaupt nicht in Erwägung gezogen.
Steffen Ramlow
> Stefan Matthias Aust schrieb:
> [...]
>
> Ich hab es jetzt nicht probiert, aber gab es da nicht auch noch LIKE?
> Ist aber glaube ich nicht sonderlich performant, aber vielleicht einen
> Test Wert.
Solange die Spalte indiziert ist und der Wildcard nicht am Anfang steht,
wird ein Index i.A. genutzt, es ist also i.A. schnell.
> mit NOT kann man das auch verbinden,
Dann wird es schwierig mit dem Index :)
> Nur eine Ähnlichkeitssuche wird es
> damit wohl nicht geben
Doch, viele DBs haben hierfür Funktionen, z.B. SOUNDEX. Aber dann wird's
immer ein FTS, also langsam, wenn die Tabelle groß genug ist.
> und die Gross-/Kleinschreibung ist relevant.
Das hängt davon ab, welche DB und wie man seine Daten organisiert.
Jochen Theodorou
> Jochen Theodorou wrote:
>
>>Stefan Matthias Aust schrieb:
>>[...]
>>
>>Ich hab es jetzt nicht probiert, aber gab es da nicht auch noch LIKE?
>>Ist aber glaube ich nicht sonderlich performant, aber vielleicht einen
>>Test Wert.
>
> Solange die Spalte indiziert ist und der Wildcard nicht am Anfang steht,
> wird ein Index i.A. genutzt, es ist also i.A. schnell.
kann sein dass ich LIKE falsch verstanden habe... aber wenn ich was
suche, was mitten im Text stehen kann, dann ist der Wildcard doch am
Anfang, oder?
Gruss theo
Steffen Ramlow
Am Anfang, kein Index nutzbar: %Bla
Nicht am Anfang, Index ggf. nutzbar: Blu%Bla oder Miau% oder Hu%Mu%Ma
Frank Buss
> Lasst mich laut nachdenken: Ein potentieller Kunde sagt "baue mir eine
> Volltextsuche". Ich erinnere mich an Tenary Search Trees und auch
> Lucent, doch er sagt "kein spezieller Server, du hast nur eine
> Datenbank". Also Fat Client. Was eigenes? Wie am besten?
MySQL soll Volltextsuche beherrschen, müsstest vielleicht mal auf der
Webseite nachlesen, ob das schon was für dich ist.
--
Frank Buß, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Stefan Matthias Aust
> Doch, viele DBs haben hierfür Funktionen, z.B. SOUNDEX.
Soundex funktioniert nur im englischen leidlich, ansonsten braucht man
andere Algorithmen.
Ach ja, und das mysql einen Volltext-Index bilden kann, ist mir bewusst,
doch mysql ist keine Option.
Steffen Ramlow
> Steffen Ramlow wrote:
>
>> Doch, viele DBs haben hierfür Funktionen, z.B. SOUNDEX.
>
> Soundex funktioniert nur im englischen leidlich, ansonsten braucht man
> andere Algorithmen.
>
> Ach ja, und das mysql einen Volltext-Index bilden kann, ist mir
> bewusst, doch mysql ist keine Option.
Denn rück' doch endlich mal raus, welche DB es ist, Oracle? Wenn ja, und die
Mengen gering bleiben und die Box genug Power und RAM hat, schreib einfach
entsprechende PL/SQL-Funktionen.
Marco Schmidt
[...]
>Fehlt was? Geht das besser? Gibt es etwas fertiges? Alternativen?
Mir war auch als erstes die Volltextsuche von MySQL eingefallen
<http://www.mysql.com/doc/en/Fulltext_Search.html>. Von den
Profidatenbanken erwarte ich mal, daß die Ähnliches im Programm haben.
Aber zum Eigenbau.
Da der Begriff in diesem Thread noch nicht gefallen ist: invertierter
Index. Für jedes Wort speichert man, in welchen Ressourcen es
vorkommt. Quasi Deine Tabelle WORDS, aber weniger redundant. Bewegt
man sich außerhalb der Datenbank, kann man dafür eigene
Datenstrukturen benutzen, die etwas effizienter sind. Denn Deine
Tabelle wäre ja voller Wiederholungen:
WORDS
...
geht 10
geht 15
geht 17
geht 19
...
Für komplexere Suchanfragen speichert man für jedes Wort Ressource und
Position im Dokument. Also:
WORDLIST
id int(10)
word varchar(100)
WORDS
word_id int references WORDLIST
res_id int references RESOURCES
position int
Damit kannst Du dann auch eine NEAR-Operation implementieren, indem
abs(position1 - position2) <= schwellwert sind.
Erst mit Positionen werden auch Phrasen mit zwei oder mehr Wörtern
auffindbar.
Außerdem ließe sich so besser gewichten. Kommt ein Wort am Anfang des
Dokuments vor, ist es evtl. wichtiger als irgendwo im Mittelteil.
Du hast schon das Weglassen von kleinen und häufig benutzten Worten
als "Optimierung" genannt. Spart einerseits, andrerseits findet man so
gewisse Sachen nicht (etwa "to be or not to be").
Auch möglich:
* Groß- und Kleinschreibung ignorieren
* Stemming (Worte auf Wortgruppen abbilden, dann werden bei suchen
nach gehen auch gehend, gehende, gehender, gehendes etc. gefunden).
* Soundex (oder etwas Alternatives für deutsch)
* Falls Deine Ressourcen Textattribute besitzen, kannst Du diese
ebenfalls in eine Gewichtung einfließen lassen. Etwas, das bei HTML
strong, b, em, h1, title etc. ist, wird dann als wichtiger angesehen.
Das könnte man dann durch eine Spalte modifier / importance / quality
in WORDS einfließen lassen.
Gruß,
Marco
--
Bitte nur in der Newsgroup antworten, nicht per Email!
de.comp.lang.java Homepage: http://www.dclj.de/
FAQ: http://www.faqs.org/faqs/de/comp-lang-java/faq/
Meine Java-Seiten: http://www.geocities.com/marcoschmidt.geo/java.html
Steffen Ramlow
> Stefan Matthias Aust:
>
> [...]
>
>> Fehlt was? Geht das besser? Gibt es etwas fertiges? Alternativen?
>
> Mir war auch als erstes die Volltextsuche von MySQL eingefallen
> <http://www.mysql.com/doc/en/Fulltext_Search.html>.
Hm, gar nicht mal schlecht!
Von den
> Profidatenbanken erwarte ich mal, daß die Ähnliches im Programm haben.
>
> Aber zum Eigenbau.
>
> Da der Begriff in diesem Thread noch nicht gefallen ist: invertierter
> Index. Für jedes Wort speichert man, in welchen Ressourcen es
> vorkommt. Quasi Deine Tabelle WORDS, aber weniger redundant. Bewegt
> man sich außerhalb der Datenbank, kann man dafür eigene
> Datenstrukturen benutzen, die etwas effizienter sind. Denn Deine
> Tabelle wäre ja voller Wiederholungen:
Nun ja, das spart zwar Platz, jedoch ist die Suche langsamer, weil
zusätzliche Tabelle.
Wie immer das Spiel: Normalisierung vs. Performanz.