"Meinten Sie: ..."

Webdesign & Technik PHP
1

Hallo liebe Community,

Jeder kennt die Funktion “Meinten Sie:” von Google. Sie schaut ob die Eingabe mit anderen Begriffen zu denen es wesentlich mehr Ergebnisse gibt nahezu übereinstimmt.

Solch eine Funktion benötige ich nun auch. Stellt ein Nutzer eine Frage die nicht in der Datenbank vorhanden ist wird geschaut ob die Frage starke Ähnlichkeit mit einer Frage besitzt, die bereits in der Datenbank vorhanden ist.

Leider konnte ich nichts finden.

Kennt jemand ein Code-Schnipsel auf Basis des Phonetic algorithm oder der Levenshtein-Distanz?

Liebe Grüße

MaxT :wink:

2

Naja, diese Funktion kann man ja nur für einzelne Wörter nutzen, sonst hätte das auch nicht viel Sinn. Du müsstest halt die Frage in Wörter zerlegen und dann suchen, wo die meisten der Wörter vorkommen. Und höchstens dann könnte man noch Levenstein einbauen.

3

Wie wirkt sich diese Methode eigentlich auf die Bearbeitungszeit aus?

4

Diese Levenshtein-basierten Suchvorschläge sind sehr arbeitsaufwändig, aber die meisten Datenbanksysteme haben so etwas ähnliches schon mehr oder weniger implementiert.

PostgreSQL zB:
postgresql.org/docs/8.3/stat … match.html

MySQL hat momentan keine levenshtein-Implementation, nur Soundex, was aber nicht wirklich für sowas geeignet ist…

5

Hallo liebe Community,

habe mir Soundex einmal angeschaut, leider vergleicht es nur die Ausprache (und das auch noch im Englischen), daher ist es wie du bereits sagtest ungeeignet.

Wie kann ich dennoch eine Eingabe mit den Einträgen in der Datenbank vergleichen?

Das Ganze ohne Datenbank sieht aktuell wie folgt aus:

[code]<?php
// eingegebenes falsch geschriebenes Wort
$input = ‘Aingabe’;

// Wörterarray als Vergleichsquelle
$words = array(‘Eintrag’,‘Eingabe’,‘Input’,‘Eintragung’);

// noch keine kürzeste Distanz gefunden
$shortest = -1;

// durch die Wortliste gehen, um das ähnlichste Wort zu finden
foreach ($words as $word) {

// berechne die Distanz zwischen Inputwort und aktuellem Wort
$lev = levenshtein($input, $word);

// auf einen exakten Treffer prüfen
if ($lev == 0) {

  // das nächste Wort ist das Wort selbst (exakter Treffer)
  $closest = $word;
  $shortest = 0;

  // Schleife beenden, da wir einen exakten Treffer gefunden haben
  break;

}

// Wenn die Distanz kleiner ist als die nächste gefundene kleinste Distanz
// ODER wenn ein nächstkleineres Wort noch nicht gefunden wurde
if ($lev <= $shortest || $shortest < 0) {
// setze den nächstliegenden Treffer und die kürzestes Distanz
$closest = $word;
$shortest = $lev;
}
}

echo “Eingegebenes Wort: $input\n”;
if ($shortest == 0) {
echo “Exakter Treffer gefunden: $closest\n”;
} else {
echo “Meinten Sie: $closest?\n”;
}

// Ausgabe des Status der für den Befehl hinterlegt ist
if ($closest == “Eintrag”) {echo “Der Befehl wird nicht bestätigt.”;}
if ($closest == “Eingabe”) {echo “Der Befehl wird bestätigt.”;}
if ($closest == “Input”) {echo “Der Befehl ist gesperrt.”;}
if ($closest == “Eintragung”) {echo “Der Befehl wird bereits verwendet.”;}

?>
[/code]

Dies müsste nun mit einer Datenbank umgesetzt werden. Natürlich liesen sich die Einträge der Datenbank in einen Array lesen und man könnte das obige Script soweit verwenden allerdings ist das vermutlich nicht sehr effizient.

Liebe Grüße

MaxT :wink:

6

Nunja, was Goggle da anbietet, hilft mir lediglich zu erkennen, wenn
ich mich mal vertippt habe.
Ansonsten, wenn dem nicht so ist, was meistens der Fall ist, ist der
Tip auch nicht hilfreich, eher ein Lacher, wie auch einige der
ausgegebenen Ergebnisse, die in der Schreibweise oft auch sehr
tolerant sind, so daß man bei speziellen Anfragen eben auch mal
sehr viele Nieten mit Dingen bekommt, die nicht relevant sind, ob
man das nun meinte oder nicht ;o)

Von daher stellt sich die Frage, ob sich der Aufwand bei einer solchen
Trefferquote lohnt. Oben genannter Tippfehler fällt meist auch auf,
wenn keine Ergebnisse kommen oder auch nur solche, die offenbar
einen Tippfehler enthalten.

Daß ein Programm erkennen kann, was ich wirklich meine oder
will, scheint mir utopisch zu sein - zumindest nach meiner
Erfahrung mit Programmen, die das zu raten versuchen ;o)

Es ist jedenfalls eine knifflige Sache bei sowas, das richtige Gewicht
zwischen Behinderung und Hilfe zu finden, mit seiner Fehlertoleranz
stellt Google selbst oft schon eine Behinderung des eigenen
Dienstes dar. Und da kommt mit ‘Meinten Sie: …’ eigentlich auch
keine Verbesserung bei heraus - man kommt allenfalls ins
philosophische Grübeln darüber, was man wirklich will oder meint -
und wer weiß das letztlich schon selbst und möchte auch noch
dauernd drauf hingewiesen werden? ;o)

7

Da gebe ich dir absolut recht Hoffmann. Was Google oder andere Suchmaschinen gelegentlich als Alternativen zu dem gewählten Suchbegriff anbieten ist absoluter…

Für einen solchen Zweck ist die Funktion in meinem Fall auch nicht gedacht. Es geht um eine Eingabe in ein Befehlsfenster, bei dieser Eingabe kann es häufig zu Rechtschreib- oder Syntaxfehler kommen, außerdem gibt es für einen Befehl viele minimal abweichende Varianten. Dadurch soll die Anzahl der hinterlegten Befehle in der Datenbank gesenkt werden.

Nur leider weis ich nicht ganz wie sich dies mit einem Datenbanksystem umsetzen lässt.

Liebe Grüße

MaxT :wink:

8

seufz - und warum teilst du uns nicht von Anfang an mit, was du wirklich vor hast …?
Dann könnte man gleich in die richtige Richtung überlegen.

Dann suchst du m.E. eher einen vernünftigen Parser, der diese Befehle analysieren und ggf. die verschiedenen Schreibweisen in eine einheitliche Form bringen kann.

9

Entschuldigung, ich wollte doch nur Mühe ersparen, die Mutation kann ich mir selbst herleiten, mir fehlt lediglich etwas der Ansatz für das Grundgerüst.

Ich weis eben nicht wie ich obiges PHP-Programm sauber mit einer Datenbank umsetze. Ich würde das Ganze mit Wenn-Abfragen bis oben hin “vollstopfen”. :neutral_face:

10

Mit phonetischen Ansätzen wirst du da aber vermutlich nicht weit kommen - eben weil die sich auf die Aussprache beziehen, und die zu betrachten ist bei „Befehlen“ im Computer-Sinne nun mal wenig sinnvoll.

Ob Levenshtein weiterhelfen kann, kommt auch stark darauf an, wie die Befehle aufgebaut sind.

Edit: Was du m.E. brauchst, ist eine Art von Normalisierung.

Wenn du Leute pre Freitext-Eingabe fragen willst, was ihr Lieblingstier ist, um daraus eine Statistik zu erstellen - dann wirst du Antworten wie „Hund“, „Hunde“, „ein Hund“ bekommen. Natürlich willst du die aber alle als ein Tier zählen, weil sie das ja auch sind - also „normalisierst“ du alle diese Antworten auf „Hund“.

Wie das in deinem Fall umzusetzen wäre, kann dir immer noch niemand sagen - weil du immer noch keine genaueren Infos lieferst, wie deine „Befehle“ denn nun aussehen, und wo die Abweichungen in der Schreibweise liegen können.
Wenn bspw. die Parameter in flexibler Reihenfolge angegeben werden können, wie man das z.B. von shell-Kommandos kennt - dann wäre die erste Normalisierung, diese in eine vorgegebene Reihenfolge umzusortieren.
Wenn es verschiedene Notationen für ein und den selben Parameter gibt, bspw. “-d” und “–directory” für die Angabe eines Verzeichnisnamens - dann wäre auch das auf eine Schreibweise zu normalisieren.

Oder ggf. musst du einen anderen Ansatz wählen - Eingaben nicht als Freitext machen lassen, sondern die Befehle bspw. über ein Formular „zusammenklicken“ lassen. Dabei kannst du dann gezielt vorgeben, wie das Format letztendlich aussehen wird.

11

Effizient lösen lässt sich das nur in der Datenbank. Allerdings kannst du hier keine Änderungen am Datenbanksystem vornehmen.

12

Leider, habe ein Levenshtein-Plugin für MySQL gefunden.

Habe es geschafft, verfüge nun über das Grundgerüst und werde es ausarbeiten. Wenn ich darf werde ich mich in ein paar Tagen mit meinem Script und ausführlichen Informationen zu dem Vorhaben wieder melden und erfragen ob sich die Performance mit den hier zur Verfügung stehenden Möglichkeiten weiter optimieren lässt.

Ich bedanke mich herzlich bei allen die sich an diesem Thema beteiligt haben. :slight_smile:

Liebe Grüße

MaxT :wink: