[PHP] Mehrere ähnliche Wörter finden

M

Mr. Snoot

Gast
Hio,

kann mir jemand einen Tipp geben, wie ich bei einer Suche nach mehreren Wörtern (stehen direkt hintereinander) ähnliche Treffer finden kann?

Für einzelne Wörter ist das kein Problem, bei mehreren fallen mir nur sehr aufwendige Möglichkeiten ein. Ich habe es zwar erfolgreich geschaft, aber die Suche dauert einfach nen Tick zu lange.

Generell geh ich so vor, dass ich den Levenshteinwert des Suchbegriffs mit allen Wörtern der zu durchsuchenden Datei ermittle. Je nach Länge des Begriffs darf dieser Wert größer oder kleiner sein, damit er als Alternative in Frage kommt. Bei einem einzelnen Wort als Suchbegriff kann ich das einfach mit einer foreach-Schleife abarbeiten, die Suche geht ruckzuck.

Wie geh ich bei mehreren Begriffen vor? Ich hab zwar paar Ideen, die sind aber alle sehr aufwendig, da zu viele Levenshteinvergleiche durchgeführt werden müssen.

  • Ich könnte den ersten Suchbegriff mit dem ersten Wort der Textdatei vergleichen, ist der Levenshteinwert ok, überprüfe ich den zweiten Suchbegriff mit dem zweiten Wort usw.
    Ist der Levenshteinwert zu groß, breche ich ab, gehe ein Wort weiter und vergleiche den ersten Suchbegriff mit dem zweiten Wort der Textdatei, den zweiten Suchbegriff mit dem dritten Wort usw.
    Passen bspw. alle drei Suchbegriffe mit den Worten 1, 2, 3 überein, beginnt der nächste Suchvorgang mit Suchbegriff eins und Wort vier, ...
    ------------------------------------------------------------
  • Meine jetzige Lösung: bilde mit den Wörtern der Textdatei Strings, die aus so vielen Wörtern bestehen, wie der Suchbegriff. Aus dem Text "Heute ist ein schöner Tag" erzeuge ich bei 2 Suchbegriffen bspw. die Strings "Heute ist", "ist ein", "ein schöner" und "schöner Tag". Diese Strings kann ich dann nacheinander "einfach" wieder mit dem Suchstring vergleichen.

    Aber so bekomme ich natürlich viel zu viele Strings, was mir die Suche ausbremst
Ich habe keine Ahnung, wie man das sonst angehen könnte.
 

MQ6

Lt. Junior Grade
Dabei seit
Dez. 2006
Beiträge
399
Für was genau brauchst du das denn, wenn ich fragen darf?
Ein Anwendungsgebiet erschließt sich mir jetzt nicht auf den ersten Blick.

Vielleicht kommt jemand ja auf eine elegantere Lösung, wenn der Kontext etwas beschrieben wird.
 
M

Mr. Snoot

Gast
Ganz einfach: wenn jemand etwas sucht und nichts findet (entweder weil vertippt oder weils die Wörter nicht gibt), sollen Alternativen genannt werden. Im Moment jedoch nur für direkt hintereinanderstehende Wörter (weil das nahezu 100% der bisherigen Suchanfragen mit mehreren Wörtern abdecken würde).

Außer Möglichkeiten, für einzelne Wörter Vorschläge zu generieren, finde ich weit und breit nichts.


edit: ich habe so das Gefühl, dass es außer mir niemanden interessiert, sowas zu realisieren!? In keinem Forum hat jemand ne Idee :confused_alt:
 
Zuletzt bearbeitet:

MQ6

Lt. Junior Grade
Dabei seit
Dez. 2006
Beiträge
399
Bin auch noch am Nachdenken. Hab mal ziemlich viel mit Levenshteinwerten gerechnet, als wir falsch geschriebene Vornamen finden mussten. Melde mich ggf...
 

muckelzwerg

Lt. Junior Grade
Dabei seit
Mai 2006
Beiträge
460
Ich versteh die Aufgabe noch nicht ganz.
Die L.Distanz kann nur direkt ermittelt werden, indem zwei Worte verglichen werden.
Man kann also nicht den "Levenshtein-Wert" speichern und dann einfach einen Zahlenvergleich machen.
Wenn Du also nach mehrere Worten suchst, steigt die Komplexität linear mit der Suchwortanzahl.
Du kannst dann doch entweder versuchen die Vergleichsfunktion zu verbessern, den Suchalgorithmus zu
optimieren (macht bei linearen Problemen ja noch Sinn) oder "was anderes" machen.
Dein Ansatz würde die Vorschläge aus den durchsuchten Dateien ermitteln.
Ist das denn wirklich gewollt? Das typische "meinten sie ..." bei Suchmaschinen sollte doch eher auf eine
Menge von gesammelten Vorschlägen zurückgreifen. Diese Menge sollte im Verhältnis zu den zu
durchsuchenden Dateien sehr klein sein, was das Ganze beschleunigen würde.
Und dann könnte man versuchen die potentiellen Vorschläge noch nach ihrem Abstand "irgendwie zu ordnen",
so dass man frühzeitig abbrechen kann, etc.

Wenn die Vorschläge wirklich aus der Datei kommen sollen, dann kannst Du probieren, ob es
Gesetzte gibt, die zwischen den L.Abständen gelten. Evtl. kann man die Distanzen zwischen den
Suchbegriffen errechnen und verwenden um zu entscheiden ob man ein weiteres Wort prüft.
Vermutlich muss man dafür irgendwie einen Transformationsvektor ermitteln, der den Wortübergang beschreibt.
Also in der Art "SWort1 hatte Abstand x, SWort2 hat von SWort1 den Abstand y, schlaueFunktion(x, y) ergibt prüfe SWort2 nicht".

-- -- muckelzwerg
 
M

Mr. Snoot

Gast
Man kann also nicht den "Levenshtein-Wert" speichern und dann einfach einen Zahlenvergleich machen.
Das wäre aber die Lösung :)


Ich hatte schon überlegt, Alternativen von bereits gesuchten Wörtern auszugeben, aber da bekomme ich meiner Meinung nach keine guten Ergebnisse. Zum einen habe ich dazu zu wenig Suchabfragen, um einen ordentlichen Alternativindex zu erstellen, zum anderen gibt es zu wenig zu durchsuchende Inhalte, als dass gesammelte Vorschläge auch wirklich brauchbare Ergebnisse liefern.

Darum möchte ich mich eben auf Vertipper und "falsche" Worte konzentrieren, weil ich anhand der Logfiles sehe, dass ich da einiges rausholen kann. Eine schlaue Funktion, die bspw. den Kontext der Wörter erkennt, um dahingehend unnötige Vergleiche einzusparen, wäre vielleicht noch ne Lösung, aber mit Sicherheit viel zu viel Aufwand (es sei denn man heißt Google ;)).


Wahrscheinlich ist meine jetzige Lösung schon viel zu overpowered für die Seite, ich denk mir nur, dass sowas doch elegant möglich sein muss.
 

muckelzwerg

Lt. Junior Grade
Dabei seit
Mai 2006
Beiträge
460
Was mir nicht so ganz klar ist:
Wie wird denn eigentlich gesucht?
Der Benutzer (sind doch Benutzereingaben?) tippt seine Worte ein und verknüpft sie mit "AND",
bzw. passiert das implizit.
Soll jetzt der exakte Ausruck gesucht werden? Also der Effekt der Anführungszeichen bei Google,
oder sollen die Begriffe einzeln gesucht und dann beim Ranking der Ergebnisse entsprechend "vermischt"
(karthesisches produkt) werden.
Wenn Du den genauen String suchen willst, dann kannst Du doch aus allen Worten ein einzelnes neues machen, und nach diesem ganz gewöhnlich suchen. Also die Worte im Zieltext immer so bilden, wie Du es
beschrieben hast. Da Du in jedem Schritt ein (echtes) Wort "vorrückst", sind das genausoviele Vergleiche, wie
bei der Suche nach einem einzelnen (nichtzusammengesetzten) Wort.
Evtl. musst Du dann noch ein paar Features einbauen um Sonderzeichen zu behandeln. Also der L.Distanzfunktion beibringen z.B. Kommas, Punkte und Leerzeichen als gleichwertig zu betrachten etc.
(sollte in der Funktion schneller sein, als pauschal in jedem Zielwort eine Ersetzung zu machen)

-- -- muckelzwerg
 
M

Mr. Snoot

Gast
Es handelt sich um Benutzereingaben, diese werden immer mit UND verknüpft. Gesucht werden kann mit "" oder ohne (wobei vernünftige Alternativen im Moment nur bei ""-Suchen kommen, weil hier noch nicht nach einer Suche mit "" und ohne differenziert wird).


Jetzt wo du's aber sagst, hatte ich wohl dauernd einen Denkfehler. Ich bin davon ausgegangen, dass ich bei x Suchbegriffen x-mal so viele Vergleiche machen muss; in Wirklichkeit werdens aber sogar weniger (und zwar um Anzahl Wörter in Textdatei - Anzahl Suchbegriffe + 1).

D.h. meine Bremse sitzt nicht hinten bei der Levenshteinfunktion, sondern schon vorne beim Einlesen der Textdatei.

Dann ist mein Problem aber weiterhin, wie ich immer um ein Wort vorrücke, dabei aber x Wörter vergleichen kann!? Die Textdatei wird so eingelesen, dass alle Sonder-/Satz-/usw.-zeichen rausfliegen, ich habe also alle Wörter in einer langen Reihe.

Ich müsste als bei x Suchbegriffen in meinem Wortstring immer x Wörter bis vor das x. Leerzeichen vergleichen und dann in einer Schleife immer das jeweils erste Wort löschen.

------
edit
------

So, sieht eigentlich nicht kürzer aus, geht aber wesentlich flotter. Bei 3 Wörtern hat die Suche bisher zwischen 2 und 3 Sekunden gedauert. Jetzt nur noch 0,5 s :)

Neu: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Alt:

• Textdatei als String einlesen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .• Textdatei als Array einlesen
• Anzahl x der Suchbegriffe ermitteln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • Anzahl x der Suchbegriffe ermitteln
• Ermittle String von strpos 0 bis vor das x. Leerzeichen . . . . . . . . . . . . . . . . . . . . • Erzeuge String mit x Wörtern von array[0] bis array[x-1]
• levenshtein(String, Suchbegriff) . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .. . • String in neues Array speichern
• Lösche das 1. Wort + 1. Leerzeichen im String . . . . . . . . . . . . . . . . . . . . . . . .. . • Lösche 1. Schlüssel im Array
• Nächste Runde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . • Nächste Runde
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . ...
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . • levenshtein(neues Array, Suchbegriff)
 
Zuletzt bearbeitet:
Top