komplexere Suchfunktion

[mustang]

Hallo Leute,

ich hätte mal einige Fragen / Überlegungen zum Thema Suchfunktion mit PHP und MySQL.
Ich habe bereits das Forum durchsucht und auch Google zu Rate gezogen, stoße aber immer wieder nur auf Lösungsansätze, die bei %LIKE% aufhören, oder sich mit dem Vorschlagen von Suchworten mit Hilfe von Javascript beschäftigen. Mir geht es um einen Schritt weiter zu einer komplexeren Suchfunktion.

Grundsätzliches:
Ich arbeite also mit PHP und MySQL und habe eine Datenbankstruktur, die ähnlich einem Blog aufgebaut ist. Zur Vereinfachung eine Tabelle mit Blogeinträgen mit ID, Inhalt, Autor, Datum, Kategorie.

Zur Suche:
Mit ist bekannt, wie man mit LIKE arbeitet (% und so weiter).
Für mehrere Suchwörter würde ich den String vorher mit explode zerlegen und durchlaufen lassen. Im Weiteren will ich darauf nicht mehr weiter eingehen und beziehe mich deswegen nur auf ein Suchwort.


Das Problem:
Mit LIKE bekomme ich lediglich Ergebnisse geliefert, in denen das Suchwort komplett vorkommt. Zum Beispiel: Suchwort = "Hohlkopf". Dann bekomme ich Einträge mit "Hohlkopfkrankheit" & "Großhohlkopf". Leider nicht "Hohlköpfe" oder "Kopf". Dieses Problem möchte ich gerne lösen.

Der Lösungsansatz:
Die Idee ist das Suchwort selber noch einmal zu zerlegen. Mein Ansatz war dabei mit LIKE nach allen Kombinationen aus dem Suchwort bis zu einer Länge von 4 Buchstaben (also minimale Übereinstimmung) zu suchen und entsprechend Punkte zu vergeben.
Das bedeutet für das Beispiel Hohlkopf, dass ich nach den folgenden Substrings suche (for-Schleife, LIKE %SUBSTRING%):

Hohlkopf
Hohlkop
Hohlko
Hohlk
Hohl
ohlkopf
ohlkop
ohlko
ohlk
hlkopf
hlkop
hlko
lkopf
lkop
kopf

In einer temporären Tabelle werden jedem Ergebnis Punkte für das Vorkommen eines Substrings vergeben.
Dafür habe ich mir folgende Berechnung ausgedacht:
Bei einem Begriff mit 8 Buchstaben gibt es 15 verschiedene Kombinationen. Die Anzahl der Kombinationen folgt der Reihe der Dreieckszahlen (1, 3, 6, 10, 15, 21, 28, ...) ab einer Anzahl von 4 Buchstaben des Suchwortes.
100 ist die maximal-Anzahl an Punkten, die vergeben werden soll, wenn das Suchwort komplett vorkommt.
Ich vergebe für jeden gefundenen Substring 100/(Anzahl der Buchstaben) an Punkten. Für Hohlkopf wären das also 12,5 Punkte für jeden gefundenen Substring. Wenn der Begriff komplett vorkommt, macht das in der Summe 100 Punkte.
Wenn nur "Hohl" & "Kopf" vorkommt, ergibt das in der Summe 2*12,5 = 25 Punkte. Also auch so ein Eintrag würde gefunden.
Die Beiträge würden anschließend in der Reihenfolge der Anzahl der Punkte ausgegeben werden.

Weiteres Problem an der ganzen Sache ist allerdings, dass die Anzahl der Query's sehr schnell zunimmt. Bei 100 Blogeinträgen und 4 zu durchsuchenden Feldern und einem Suchwort mit 8 Buchstaben ergeben sich 15*4*100 = 6000 Querys (wenn ich für jeden Substring und jedes Feld ein einzelnes Query machen würde - zur Vereinfachung der Rechnung). Das erscheint mir für die Datenbank nicht gerade optimal.

Verbesserung:
Die nächste Überlegung war also die Anzahl der Substrings zu verkleinern und nur nach den kleinsten Kombinationen und dem Suchwort zu suchen:

Hohlkopf
Hohl
ohlk
hlko
lkop
kopf

Dabei komme ich dann auf 2400 Querys (100 Beiträge, 4 Felder, 8 Buchstaben).
Das Erscheint mir immer noch sehr viel.

Fragen

• Was meint ihr zu diesem Ansatz eine Suche zu programmieren?
• Ist das überhaupt ein Ansatz, der eurer Meinung nach mit weiteren Optimierungen erfolgreich sein könnte (vorallem bezüglich der Query-Anzahl)?
• Habt ihr andere Dinge, die man beachten sollte, verbessern könnte, oder ganz andere Ansätze, wie ihr eure eigene individuelle Suche für eure Website programmiert habt?
• Eine Veränderung mit MATCH AGAINST habe ich schon in Betracht gezogen, aber diese Funktion findet auch keine Substrings. Hat damit jemand damit Erfahrungen gemacht?

Vielen Dank schön mal im Vorraus. Ich würde mich sehr freuen, wenn man eine gemeinsame Lösung erarbeiten könnte.

edit:
Eine Variante wäre außerdem, dass man, wenn ein Substring gefunden wurde, in diesem Baum nicht mehr weiter nach unten geht. Also wenn "Hohlko" gefunden wurde, soll nicht mehr nach "Hohlk" gesucht werden. Das dürfte die Anzahl der Querys um ein vielfaches verkleinern.

 

[Tronjer]

Wie wäre es hiermit?
https://jqueryui.com/autocomplete/

 

[mustang]

Ich dachte das Script ist nur für die Autovervollständigung mit vorher angegebenen Listen. Das Skript durchsucht doch keine Datenbank, oder?
edit: Ich suche außerdem eigentlich nach einer PHP Lösung...

 

[Tronjer]

Das ist eine PHP-Lösung. ;)

Das Script sendet einen Ajax-Request an eine PHP-Datei, welche die DB-Queries ausführt und liefert das Ergebnis an den Client zurück.

Schau mal in die Doku.

 

[scbawik]

Das ist eine PHP-Lösung. ;)

Das Script sendet einen Ajax-Request an eine PHP-Datei, welche die DB-Queries ausführt und liefert das Ergebnis an den Client zurück.

Schau mal in die Doku.

Das Problem scheint aber die Abfrage selbst zu sein? Daher wird Auto-Complete nichts bringen.

 

[maria1]

Einfach mal googeln, ist ganz easy...
Demo: http://kodesmart.com/wp-tut-files/livesearch/
Tutorial: http://kodesmart.com/kode/live-search-with-jquery-php-and-mysql

Grüße

 

[mustang]

Das Problem scheint aber die Abfrage selbst zu sein? Daher wird Auto-Complete nichts bringen.

Richtig. Mir geht es nicht um eine Autocomplete funktion, wie ich es oben schon geschrieben hatte. Beide Scripts (von maria1 und auch von Trojaner) suchen lediglich ganze Wörter mit Hilfe von LIKE %SUCHWORT%. Man wird also nie verwandte Suchbegriffe finden und genau darum geht es mir ja.
Außerdem möchte ich vorerst eine reine PHP-Lösung haben, um die Website barrierefrei zu halten. Also sprich: Formularfeld - absenden - Ergebnisse anzeigen.
Ich wollte mich eben mit der eigentlichen Abfrage beschäftigen und diese optimieren.

 

[scbawik]

Richtig. Mir geht es nicht um eine Autocomplete funktion, wie ich es oben schon geschrieben hatte. Beide Scripts (von maria1 und auch von Trojaner) suchen lediglich ganze Wörter mit Hilfe von LIKE %SUCHWORT%. Man wird also nie verwandte Suchbegriffe finden und genau darum geht es mir ja.
Außerdem möchte ich vorerst eine reine PHP-Lösung haben, um die Website barrierefrei zu halten. Also sprich: Formularfeld - absenden - Ergebnisse anzeigen.
Ich wollte mich eben mit der eigentlichen Abfrage beschäftigen und diese optimieren.

Such mal nach "MySQL SOUNDEX" bzw. "SOUNDS LIKE".

Eine ähnlich performante und intelligente Such-Engine wie Google sie hat, darfst du dir natürlich nicht erwarten.

Wenn dir das nicht reicht, musst du dich eben daran machen, einen eigenen Algorithmus zu schreiben, wie du es ohnehin schon begonnen hast.

 

[mustang]

Wenn dir das nicht reicht, musst du dich eben daran machen, einen eigenen Algorithmus zu schreiben, wie du es ohnehin schon begonnen hast.

Genau das ist die Idee :-) Deswegen hatte ich das hier ins Forum geschrieben, einschließlich meiner Überlegungen. Ich hatte gehofft, dass es dazu Verbesserungen, Ideen oder Kommentare dazu gibt, wie man das optimieren könnte und so weiter, sodass am Ende vielleicht eine gute Lösung herauskommt, die auch andere Leute nutzen können. :-)

 

[mustang]

hm ok schade, ich hatte gehofft, dass da jemand mitarbeitet...

Mich würde außerdem interessieren, wie die Suchfunktionen im Web an sich funktionieren. Bzw. als Beispiel einfach die Suche dieses Forums. Werden tatsächlich alle Beiträge und Themen bei der Eingabe eines Suchbegriffes durchsucht? Ich könnte mir vorstellen, dass das etwas viele Datenbankabfragen sind. Wie wird das gemacht?