cybton.com
Über uns | Jobs | Werbung | Sitemap | AGB | Impressum | Hilfe ?
 Kostenlos anmelden)
wichtigWir suchen PHP-Entwickler/innen (Freelancer oder Vollzeit)
Forum
Aktuellste Beiträge
Forenregeln

Community
BB-Codes
Tags
Chat
Suche (Web)
Wer ist online?
Top-User

Basar


Statistik
Mitglieder gesamt: 69394
Mitglieder online: 1
Gäste online: 1
mehr...

Anzeige
Forum » Forum: Website & Webprogrammierung » Thread: Such-Algorithmen für Texte in Datenbank

Thread: Such-Algorithmen für Texte in Datenbank

Seite 1 von 212

24.02.2008 10:46 Uhr

 

Status: offline
Hallo.

Heute wieder zu einer Theorie-Stunde mit mir  :lol: 

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:
PHP:
1
2
3
4
5
6
words
id int(11)
word varchar(255)
 
primary index auf id
unique index auf word
PHP:
1
2
3
4
5
connector
word_id int(11)
text_id int(11)
 
primary index über word_id + text_id
Und dazu dann eben die Tabelle mit den Texten:
PHP:
1
2
3
4
5
texts
id int(11)
text mediumtext
 
primary key über id
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  :glad: 
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  :lol: 
Ich nehme auch gerne Links mit Tutorials / Erklärungen zu solchen Dingen entgegen, wenn ihr da etwas findet.
2 mal bearbeitet
24.02.2008 11:00 Uhr

 

Status: offline
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.
___________________________
:)
24.02.2008 11:12 Uhr

 

bmk
Moderator
Status: offline
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 ;-)
___________________________
Let's code responsibly...
Webcrawler -- Portal für Dirigenten -- Musikverein Königstetten
24.02.2008 11:50 Uhr

 

Status: offline
hmm
bmk hat folgendes geschrieben:
Zitat:
Du speicherst also nicht zu jedem Text die enthaltenen Stems, sondern umgekehrt zu jedem Stem die Texte, in denen der vorkommt.

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  :conf: 

Der Rest ist mir so im groben klar  :tongue: 

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  :tongue: 

LG Jens

EDIT:
Das sieht noch gut aus (bin gerade dabei es zu lesen):
http://www.phpbar.de/w/Volltextsuche
1 mal bearbeitet
___________________________
Meine Homepage:
http://thewebwar.cybton.com/
24.02.2008 12:12 Uhr

 

Status: offline
Zitat:
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.


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):
Zitat:
words
id - word
1 hallo
2 spiel
3 lern


Zitat:
connector
word_id text_id
1 2
1 30
2 30
2 35
3 10


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?

Zitat:
* Die Verwaltung des Stem-Index ist mühsam: Man muss bei jeder Änderung eines Textes zuerst die vorherigen

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  :glad: 

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  :lol: 
24.02.2008 14:03 Uhr

 

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

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?
___________________________
Visit my Blog, URL Shorter
24.02.2008 17:09 Uhr

 

bmk
Moderator
Status: offline
Zitat von thewebwar:
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?

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.

Zitat von zombie3456:
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.

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:  :lol: 
Deutscher Stemmer für PHP: http://ahecht.bochmann.de/prog.porter-stemmer-deutsch.shtml

Zitat von sim4000:
Das Problem ist nur, das mein Datenbankmodell mit innoDB Arbeitet

Was genau hat die verwendete Datenbank-Engine mit dem Problem zu tun...??
___________________________
Let's code responsibly...
Webcrawler -- Portal für Dirigenten -- Musikverein Königstetten
24.02.2008 17:17 Uhr

 

Status: offline
Zitat:
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.
24.02.2008 17:27 Uhr

 

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

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...
___________________________
Visit my Blog, URL Shorter
24.02.2008 17:48 Uhr

 

bmk
Moderator
Status: offline
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.
___________________________
Let's code responsibly...
Webcrawler -- Portal für Dirigenten -- Musikverein Königstetten
Seite 1 von 212
Ähnliche Threads Forum Ähnlichkeitsgrad
 [gelöst] [PHP]+[MySQL] - Zeichen ersetzen nach DB-Auslesen Website & Webprogrammierung 1
 Suche: Event-Script mit Städteverzeichniss, Umkreissuche etc. Website & Webprogrammierung 1
 MySQL: 2 Datensätze auslesen, zwischen denen 1 bestimmter Wert ist Website & Webprogrammierung 1
 Access Control Website & Webprogrammierung 1
 Datenbankgestützer Counter: unbekannter Fehler Website & Webprogrammierung 1
 [PHP/MYSQL] Zeitgesteuert auf Datenbank zugreifen Website & Webprogrammierung 1
 [gelöst]Problem mit MySQL-Datenbankabfrage Website & Webprogrammierung 1
nach obennach oben

Copyright © 2014 cybton-network

Google
Partner: #Musik - Dein Internetradio - nexem. - .wir machen news
ANEXIA - PHP Entwicklung - Web-Entwicklung - Fritz!Box Anrufmonitor für Mac OS - Rolladen, Markisen und Jalousien in Stuttgart - Rolladen in Stuttgart - SMSjobs