Thread: Such-Algorithmen für Texte in Datenbank

Hallo.

Heute wieder zu einer Theorie-Stunde mit mir   

Es soll diesmal die Frage gestellt werden, wie man möglichst mächtige Suchalgorithmen unabhängig von dem guten MATCH AGAINST und dem natürlich super langsamen LIKE '%string%' aufbaut.

Sollten gute Vorschläge kommen, dann kann es auch sein, dass so etwas in die cybton-Suche eingebaut wird, damit man diese endlich wieder verwenden kann.

In einem anderen Eintrag habe ich schon folgende Theorie über die einfachste Art eines Algorithmus geschrieben:

Zitat Beginn

Die einfachste Technik für solche eine eigene Suche, wäre es wahrscheinlich, sich einfach 2 weitere Tabellen anzulegen:Und dazu dann eben die Tabelle mit den Texten:Dann müsste man bei einer Suche die Tabelle words auslesen und danach die Texte aus texts zu den gefunden Wörtern über die connector Tabelle suchen.

Aber genau dazu gibt es ja MATCH AGAINST von MySQL   
Wenn man allerdings mächtigere Suchen bauen will, sollte man solche Theorien in großem Maße erstellen können.

Zitat Ende

(leider funktioniert quote wohl nicht mehr, wenn ein code dazwischen steht)

Stimmt diese Theorie überhaupt?
Was für andere Theorien fallen euch noch ein?
Wie könnte man diese Theorie weiter ausbauen, um sie leistungsfähiger zu machen?

Ich geh jetzt erstmal Fahrrad fahren und werde dann auch noch Google ein wenig mit meinen Problemen quälen   
Ich nehme auch gerne Links mit Tutorials / Erklärungen zu solchen Dingen entgegen, wenn ihr da etwas findet.

Hallo,
ich würde aber auf keinen Fall nur nach den Key-Words suchen, sondern auch eine eventuell optionale Suche die den Inhalt durchsucht anbieten.
Mit freundlichen Grüßen,
Alex.

Also... *tieflufthol*

Das erste Stichwort wäre mal "Stemming". Damit bezeichnet man einen Algorithmus, der dir aus so Wörtern wie "suche", "suchst", "suchen" oder "suchend" den gemeinsamen Wortstamm "such" liefert. Einen PHP-Stemmer für Deutsch findest du im Internet, hab grad keinen Link parat.

Das zweite Stichwort wäre "umgekehrter Index". Du speicherst also nicht zu jedem Text die enthaltenen Stems, sondern umgekehrt zu jedem Stem die Texte, in denen der vorkommt.

Ist das einmal gemacht, geht eine Suchanfrage ziemlich schnell:
* Suchbegriff ebenfalls stemmen
* Alle Texte ausgeben, die diesen Stem enthalten
Und das war's auch schon.

Vorteile:
* Wahnsinnig schnelle Suchanfragen
* Kleinere Datenbasis: die Volltext-Indices fallen weg, es werden mehrere einzelne Worte zu einem einzigen Stem zusammengefasst (siehe oben)
* Man kann selbst bestimmen, welche Worte (nicht) in den Index kommen: Bei MySQL wird zB alles unter 4 Zeichen Wortlänge gar nicht Indiziert. Mit "PHP" wird man also nie auch nur irgendetwas finden.

Nachteile:
* Die Verwaltung des Stem-Index ist mühsam: Man muss bei jeder Änderung eines Textes zuerst die vorherigen Stems aus der Tabelle austragen und danach den neuen Text wieder hinzufügen.
* Die Abfrage von kombinierten Wörtern oder Wortgruppen muss extra implementiert werden
* Über die Reihung der Suchergebnisse muss man sich extra Gedanken machen: Kommen einfach jene zu erst, die die meisten Treffer haben? Oder schafft man es irgendwie, zu unterscheiden, ob der Suchbegriff irgendwo mitten im Text oder in einem Threadtitel vorgekommen ist?

So viel zur grauen Theorie. Als Anstoß einer Diskussion sollte es jedenfalls mal Reichen ;-)

hmm
bmk hat folgendes geschrieben:

Dann muss ich ja also eine Tabelle haben, in der schon die Stems drinnen stehen.
Muss ich die dann einmal alle per Hand dort eintragen?
das wäre doch viel zu viel Aufwand   

Der Rest ist mir so im groben klar   

Dieser Stemmer ist aber glaube ich für Englisch:
http://tartarus.org/~martin/PorterStemmer/
=> PHP
http://tartarus.org/~martin/PorterStemmer/php.txt

Hier ist etwas zu deutschen STemmer, aber leider keine PHP Implementation:
http://snowball.tartarus.org/algorithms/german/stemmer.html

hier ist noch eine Stopwprd List, welche ganz hilfreich sein könnte:
http://snowball.tartarus.org/algorithms/german/stop.txt

Ich werde mich mal weiter auf die Suche machen und gegebenen Falls noch mehr posten   

LG Jens

EDIT:
Das sieht noch gut aus (bin gerade dabei es zu lesen):
http://www.phpbar.de/w/Volltextsuche

Das klingt so ähnlich wie meine Theorie. Ich habe ja auch eine Tabelle mit dem Wort (unique) + ID und dann eine Tabelle, in der steht, in welchem Text dieses Wort vorkommt.

Praktisch (mit Stemming):




Das heißt dann, dass in Text 2 "hallo" vorkommt, in Text 30 "hallo" und z.B. "spielen" in Text 35 z.B. "spielt" und in Text 10 dann noch soetwas wie "lerne!". Soweit richtig verstanden?


Der erste Nachteil scheint mir kein besonders großer Nachteil zu sein. Über eine Klasse ist das schnell gelöst. Zumindest war das beim Tag-System auf cybton kein großes Problem und bei einem Text sind es ja nur mehr Wörter.

Der Porter Stemmer (laut wikipedia sehr bekannt) scheint ja ganz einfach zu verwenden sein. Eine PHP Implementierung für die englische Sprache gibt es hier: http://tartarus.org/~martin/PorterStemmer/php.txt
Und eine Erklärung für die Verwendung für Deutsch hier: http://snowball.tartarus.org/algorithms/german/stemmer.html

Hier gibt es eine Implementierung für alle Sprachen, für die man aber C-Quelltexte auf dem Zielsystem kompilieren muss: http://pecl.php.net/package/stem

Aber irgendwie kommt mir dieser Stemmer Algorithmus komisch vor. Liegt aber wahrscheinlich daran, dass die gefundenen Stämme am Ende nicht der richtigen Rechtschreibung (vgl. libraries und library => librari) entsprechen.
Ich schaue mir nach dem Essen mal die anderen Algorithmen an, die ich auf einer anderen Seite noch gesehen habe.

Das ist auf jeden Fall alles sehr interessant. Stark, was man mit dem PC inzwischen auch bei Sprache schon machen kann   

Ist die Technik mit einem Wortindex und den Texten, in welchen die Wörter vorkommen dazu, eigentlich die einzige Möglichkeit, eine gute Suche in Datenbanken anzulegen?
Bei Google stoße ich da immer wieder auf einen Grover's Algorithmus, aber das schlagen mich die Formeln fast um und ich weiß nicht mal, ob der für Zahlen oder Texte ist   

Moin.
Da jetzt ja alle im Such Wahnsinn sind, wollte ich auch mal mein glück versuchen.   

Das Problem ist nur, das mein Datenbankmodell mit innoDB Arbeitet, da ich mit Foreign Keys arbeite.
Wie kann man das denn in innoDB am elegantesten lösen?

Nein, das ganze ist ja ein fortlaufender Prozess, bei dem man mit einer völlig leeren Tabelle beginng. Man startet mit dem ersten Text, bildet die Stems und dann muss man halt nachschaun: Ist der Stem bereits in der Tabelle, fügt man nur noch die Verknüpfung zwischen Stem und Text ein, ansonsten muss man halt zuerst noch dem Stem selbst eintragen.


Ja, das ist genau das, wovon ich auch spreche. Nur dass halt die Begriffe zuerst gestemmt werden sollten, sonst findest du nur jene Texte, die genau "sucht" beinhalten, wäührend "suchte" oder "suchst" nicht gefunden wird.

Hab inzwischen auch den Link wieder gefunden:   
Deutscher Stemmer für PHP: http://ahecht.bochmann.de/prog.porter-stemmer-deutsch.shtml


Was genau hat die verwendete Datenbank-Engine mit dem Problem zu tun...??

Mmhh als er mich per ICQ fragte, wusste ich nichts von diesem Post und habe ihm gesagt, dass InnoDB keinen Fulltext Index unterstützt.

Bei genau diesem Thema stört die Engine wahrscheinlich nicht.

Genau wie Brati sagte.
Hab leider vergessen in meinem Post zu erwähnen, das es um "Match Against" ging. sry.   

Ich wollte wissen, ob man das auch mit innoDB lösen kann, ohne einen Index erstellen zu müssen. Weil das wäre für meine kleine Seite etwas übertrieben...

Du hast prinzipiell drei Möglichkeiten:
a) Du baust das hier nach, worüber wir hier gerade sprechen. Machst dir also praktisch deinen eigenen Fulltext-Index.
b) Wenn's nur ne kleine Seite ist, tut's eine LIKE-Abfrage vermutlich eh
c) Du lagerst die Textspalten auf zusätzliche MyISAM-Tabellen aus.