Platz Punkte, wo ein Wort falsch geschrieben ist

Question

Ich bin ein Web-App in PHP zu schaffen, wo Menschen versuchen können Wörter übersetzen sie für die Schule lernen müssen.

Zum Beispiel, jemand braucht das niederländische Wort ‚weer‘ auf ‚Wetter‘ in Englisch, zu übersetzen, aber leider tippt er, ‚ob‘. Weil er fast das richtige Wort eingegeben haben, möchte ich ihm eine zweite Chance geben, mit Punkten ‚.‘ an den Orten, an denen er einen Fehler gemacht:

Language A:   weer
Language B:   weather
Input:        whether
Output:       w..ther

Oder zum Beispiel

Language A:   fout
Language B:   mistake
Input:        mitake
Output:       mi.take

Oder:

Language A:   echt
Language B:   genuine
Input:        genuinely
Output:       genuinely (almost good, shorten the word a little bit)

Aber, wenn der Eingang unterscheidet mich zu sehr von der gewünschten Übersetzung, ich will nicht, Ausgabe erhalten wie ........

ich über Levenshtein Entfernung gehörte, und ich denke, dass ich einen Algorithmus benötigen, die viel wie, dass man ist, aber ich weiß nicht, wie man Platz Punkte auf dem richtigen Ort statt Echo, wie viele Operationen durchgeführt werden soll.

Also, wie kann ich das falsch geschriebene Wort mit Punkten auf den Plätzen zurück, wo jemand einen Fehler gemacht?

Answer 1

Nehmen Sie sich zuerst einen Blick auf die Levenshtein Algorithmus auf wikipedia . Dann gehen Sie auf und Blick auf die Beispiele und die resultierende Matrix d auf der Artikelseite:

                *k*     *i*     *t*     *t*     *e*     *n*
        >0       1       2       3       4       5       6 
*s*      1      >1       2       3       4       5       6 
*i*      2       2      >1       2       3       4       5 
*t*      3       3       2      >1       2       3       4 
*t*      4       4       3       2      >1       2       3 
*i*      5       5       4       3       2      >2       3 
*n*      6       6       5       4       3       3      >2 
*g*      7       7       6       5       4       4      >3 

ist der Abstand an der unteren rechten Ecke der Matrix, d [m, n] zu finden. Aber von dort ist jetzt möglich, die minimalen Schritten nach oben links von der Matrix, d [1, 1] folgen Backtrack. Man geht einfach links, oben links, oder bei jedem Schritt nach oben je nachdem, was dem Weg minimiert. In dem obigen Beispiel würden Sie den Pfad durch die ‚>‘ Zeichen markiert finden:

  s i t t i n g      k i t t e n
0 1 1 1 1 2 2 3    0 1 1 1 1 2 2 3
  ^       ^   ^      ^       ^   ^
  changes in the distance, replace by dots

Jetzt können Sie auf dem minimalen Weg finden, an welchen Stellen d [i, j] die Abstandsänderungen (markiert durch ^ im Beispiel oben), und für diese Buchstaben setzten Sie in dem ersten (oder zweiten) Wort eines Punkt an Position i (bzw. j respectively).

Ergebnis:

  s i t t i n g      k i t t e n
  ^       ^   ^      ^       ^   ^
  . i t t . n .      . i t t . n . 

Answer 2

Die Terminologie Sie suchen, wird „Edit-Distanz“ bezeichnet. Mit so etwas wie Levenshtein Abstand wird Ihnen die Anzahl der Operationen benötigt, um eine Zeichenfolge in das andere zu transformieren (Einfügungen, Löschungen, Ersetzungen, etc).

Hier ist eine Liste von anderen "Bearbeitung Abstand" Algorithmen .

Wenn Sie sich entscheiden, dass ein Wort ist „nahe genug“ (das heißt es nicht mehr als einen bestimmten Schwellenwert der Änderungen erforderlich), können Sie zeigen, wo die Bearbeitungen (durch zeigt Punkte) auftreten müssen.

So wie Sie wissen, wo die Punkte setzen?

Das Interessante an dem „Levenshtein Abstand“ ist verwendet es eine M x N-Matrix mit einem Wort auf jeder Achse (siehe die Probenmatrix in Levenshtein Artikel ). Sobald Sie die Matrix erstellen, können Sie die Buchstaben benötigen „zusätzliche Änderungen“ als korrekt bestimmen. Das ist, wo Sie die Punkte setzen. Wenn der Brief erfordert „keine zusätzlichen Änderungen,“ drucken Sie einfach den Brief. Ziemlich cool.

Answer 3

Ich glaube, Sie brauchen ein mehrstufiger Prozess nicht nur Levenshtein zu tun. Zuerst würde ich überprüfen, ob das eingegebene Wort eine Form des Zielwortes ist. Das wäre Ihr drittes Beispiel fangen und auch keine Sorgen um Punkte hinzuzufügen. Sie können auch diesen Schritt zu fangen Synonyme verwenden. Der nächste Schritt ist die Längendifferenz der beiden Strings zu überprüfen.

Wenn die Differenz 0 ist, können Sie einen Brief für Brief Vergleich tun, um die Punkte zu platzieren. Wenn Sie nicht alle Punkte zeigen wollen, dann sollten Sie eine Anzahl von Punkten halten gelegt und einmal über die Grenze eine Fehlermeldung angezeigt. (Leider, das war falsch)

Wenn die Differenz zeigt die Eingabe länger benötigen Sie einen Brief überprüfen löschen sein würde, das Problem beheben. Hier können Sie Levenshtein verwenden, um zu sehen, wie nahe sie sind, wenn sie zu weit zeigen, sind davon entfernt Ihre Fehlermeldung, wenn es in Reichweite ist, müssen Sie die Schritte Levenshtein in umgekehrter Richtung tun, und die Änderungen markieren irgendwie. Nicht sicher, wie Sie wollen zeigen, dass ein Brief Bedarf gelöscht werden.

Wenn die Differenz zeigt die Eingabe kürzer Sie verwenden Levenshtein Abstand tun können, um zu sehen, ob die beiden Worte nahe genug sind oder die Fehler zeigen. Dann machen Sie die Schritte in umgekehrter Reihenfolge wieder Zugabe von Punkten für Einfügungen und Punkte für Substitutionen.

Eigentlich sind die letzten beiden Schritte können in einer Funktion kombiniert werden, dass verläuft durch den Algorithmus und erinnert sich der Einsatz löschen oder die Substitution und ändert die Ausgabe entsprechend.