nicht angemeldet
Hallo,
Ich möchte zwei Strings prozentual vergleichen. Und wenn der eine String 80% mit dem anderen String übereinstimmt, soll er angezeigt werden, wenn nicht, dann eben nicht.
Ich hab' so etwas ähnliches einmal mit Delphi geschrieben, und zwar hat es mir Verbesserungsvorschläge gesucht, wenn die Rechtschreibkorrektur einen Fehler gefunden hat (ähnlich wie bei großen Textverarbeitungsprogrammen wie Word). Dabei ging ich so vor:
Ich habe mir überlegt, was ein Mensch alles für fehler machen kann. Dabei bin ich zu folgendem Ergebnis gekommen: Der Mensch kann
- einen Buchstaben zu viel einfügen. Beispiel: "Fehrler"
- einen Buchstaben auslassen. Beispiel: "Feler"
- zwei aufeinanderfolgende Buchstaben vertauschen. Beispiel: "Fheler"
- einen falschen Buchstaben schreiben. Beispiel: "Vehler"
Die ersten beiden Fälle sind genau entgegengesetzt und können daher als gleich betrachtet werden: Wenn das Wort "Fehrler" mit dem richtigen Wort "Fehler" verglichen wird, kann man sagen, dass im Wort "Fehrler" ein r zu viel geschrieben wurde, man könnte aber genauso gut sagen, dass im Wort "Fehler" ein r ausgelassen wurde.
Dann habe ich eine Funktion geschrieben, die als Parameter zwei Wörter übergeben bekommt, nämlich das falsch geschriebene Wort und das Vergleichswort. Diese Funktion ermittelt zu erst, wie lange das falsch geschriebene Wort ist und multipliziert diesen Wert mit einer festen Konstante (bei dir wären dass 35%, also 0.35). Damit weis die Funktion, wie viele der oben genannten Unterschiede zwischen den beiden Wörtern erlaubt sind. Die anzahl dieser Unterschiede wird in einem imaginären Unterschiedswert gespeichert, der zu Anfang 0 ist.
Die Funktion vergleicht nun die länge der beiden Wörter, um zu ermitteln, welches Wort das längere und welches das kürzere ist. Falls der Längenunterschied größer ist als die erlaubte Anzahl von Fehlern, wird abgebrochen.
Anschließend werden für beide Wörter je ein Zähler initialisiert, der immer angibt, an welcher Position im Wort (d.h. beim wie vielten Buchstaben) sich das Programm momentan befindet. Diese beiden Zähler werden auf den ersten Buchstaben gesetzt (bei Delphi ist das 1, bei JavaScript wäre das 0).
Jetzt kommt eine Schleife, in der jeder einzelne Buchstabe mehr oder weniger der Reihe nach durchlaufen wird, bis der Zähler des kürzeren Wortes größer ist, als die länge des kürzeren Wortes, d.h. bis das kürzere Wort abgearbeitet ist. Diese Schleife läuft folgendermaßen ab:
-
Es werden die durch die jeweiligen Zähler angegebenen Buchstaben der beiden Wörter verglichen. Ist hier kein Unterschied, so werden beide Zähler um eins erhöt und es wird mit dem nächsten Schleifendurchlauf fortgefahren.
-
Falls die verglichenen Buchstaben unterschiedlich sind, wird der imaginäre Unterschiedswert zwischen den beiden Wörter um eins erhöht und folgendes überprüft:
- Stimmt der aktuelle Buchstabe des kürzeren Wortes mit dem nächsten Buchstaben des längeren Wortes und stimmt der nächste Buchstabe des kürzeren Wortes mit dem übernächsten Buchstaben des längeren Wortes überein? -> In diesem Fall wurde im kürzeren Wort ein Buchstabe ausgelassen oder es wurde im längeren Wort ein Buchstabe zu viel geschrieben. Der Zähler des kürzeren Wortes wird um 2, der Zähler des längeren Wortes um 3 erhöht und es wird mit dem nächsten Schleifendurchlauf fortgefahren. (hier wird davon ausgegangen, dass ein zu viel geschriebener Buchstabe nur im längeren Wort vorkommen, bzw. ein ausgelassener Buchstabe nur im kürzeren Wort "vorkommen" kann, was ja auch am wahrscheinlichsten ist.)
- Stimmt der nächste Buchstabe des kürzeren Wortes mit dem aktuellen Buchstaben des längeren Wortes überein und stimmt der aktuelle Buchstabe des kürzeren Wortes mit dem nächsten Buchstaben des längeren Wortes überein? -> In diesem Fall wurden zwei aufeinanderfolgende Buchstaben vertauscht. Die Zähler beider Wörter werden um 2 erhöht und es wird mit dem nächsten Schleifendurchlauf fortgefahren.
- Traf keine der bisher genannten Bedingungen zu, so wurde schlicht ein falscher Buchstabe eingegeben. Der Zähler beider Wörter wird um eins erhöht und es wird mit dem nächsten Schleifendurchlauf forgefahren.
Zwischendrin wird immer wieder überprüft, ob die Anzahl der bisher gefundenen Fehler die Anzahl der zulässigen Fehler nicht überschreitet. Sobald die Anzahl der zulässigen Fehler überschritten wird, wird abgebrochen.
Die Funktion sieht im (ObjectPascal-)Quelltext folgendermaßen aus. Auch wenn es eine andere Programmiersprache ist, sollte es relativ leicht verständlich sein, da nur primitive Anweisungen verwendet wurden. Falls der Grenzwert überschritten wurde, wird -1 zurückgegeben, ansonsten wird die Anzahl der gefundenen Fehler (also der imaginäre Unterschiedswert) zurückgegeben.
function vergleicheWoerter(wort1,wort2: string): integer; // in wort1 muss das falsch geschriebene Wort übergeben werden, in wort2 muss das vergleichswort übergeben werden var laenge1, laenge2, laengenunterschied, zspeicher2: integer; zspeicher: string; pos1,pos2: integer; vergleichmax: integer; begin laenge1 := length(wort1); laenge2 := length(wort2); vergleichmax := Round(laenge1*minrichtigAnteil); if vergleichmax = 0 then vergleichmax := 1;
laengenunterschied := laenge1 - laenge2; if (laengenunterschied > vergleichmax) or (laengenunterschied < -vergleichmax) then begin Result := -1; exit; end;
Result := 0;
if laengenunterschied < 0 then begin zspeicher := wort1; wort1 := wort2; wort2 := zspeicher;
zspeicher2 := laenge1; laenge1 := laenge2; laenge2 := zspeicher2;
laengenunterschied := -laengenunterschied; end;
pos1 := 1; pos2 := 1;
while pos2 <= laenge2 do begin if wort1[pos1] <> wort2[pos2] then begin Result := Result + 1; if Result > vergleichmax then begin Result := -1; exit; end;
if (laengenunterschied > 0) and // falls ein wort länger ist als das andere und nicht bereits genug fehlende buchstaben gefunden wurden (wort1[pos1+1] = wort2[pos2]) and // und falls der nächste buchstabe (immer vorhanden) übereinstimmen würde ((pos2 = laenge2) or (wort1[pos1+2] = wort2[pos2+1])) then // und falls der übernächste buchstabe des längeren wortes (sofern vorhanden) mit dem nächsten des kürzeren wortes übereinstimmen würde: begin // wort1 enthält einen buchstaben zu viel pos1 := pos1 + 1; // einen buchstaben überspringen laengenunterschied := laengenunterschied - 1; end else if (pos2 <= laenge2-1) and // falls noch mindestens ein buchstabe danach kommt (wort1[pos1+1] = wort2[pos2]) and (wort1[pos1] = wort2[pos2+1]) then // und falls zwei aufeinanderfolgende buchstaben vertauscht wurden: begin // es wurden zwei aufeinanderfolgende Buchstaben vertauscht. pos1 := pos1 + 1; pos2 := pos2 + 1; end; end;
pos1 := pos1 + 1; pos2 := pos2 + 1; end;
Result := Result + laenge1 - pos1 + 1; if Result > vergleichmax then Result := -1; end;
Robert