nicht angemeldet
2 Strings PROZENTUAL vergleichen...
Hi Leute,
ich habe folgendes Problem:
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.
Wie mache ich das? Weiß das jemand?
Vielen Dank
Kevin
-
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.
Wie genau definierst Du "80%"? Wenn 80% der Buchstaben von String A an derselben Stelle in String B stehen? Wenn die ersten 80% der Strings identisch sind? Welche dieser Strings wären für Dich in diesem Sinne "gleich":
"test" und "teste"
"atest" und "test"
"ablubbtesttesttesttesttesttesttesttesttestablubb" und "testtesttesttesttesttesttesttesttest" ?Das mußt Du erst mal festlegen.
-
Ok, ich werde es versuchen, 80% zu definieren, aber zuerst möchte ich die 80% doch besser auf 65% runtersetzen.
So nun zu meiner Definition:
Zwischenschritt: Die Variable RechenUmInProzent enthält die minimale Anzahl an Zeichen, die ersetzt, eingefügt oder gelöscht werden müssen um den String 1 nach String 2 umzusetzen.
Prozent: 65%, bzw. 80% sind, wenn 20% der Zeichen (Zwischenschritt) von der Gesamtanzahl der Zeichen des Strings ersetzt, eingefügt oder gelöscht werden müssen.
Ich hoffe, das ist nicht all zu kompliziert formuliert. Aber du wolltest schließlich eine Definition von 80, bzw. 60%.
Also: Das Javascript soll "Zwischenschritt" berechnen.
Vielen Dank für Eure Mühe
Kevin
-
Sorry, aber ich muss nochmal was hinzufügen.
In deinem Fall Mulder würden also alle 3 Beispielstrings die Bedingungen erfüllen, und wären innerhalb von 65%.
Kevin
-
Moin hier! :)
Ok, ich werde es versuchen, 80% zu definieren, aber zuerst möchte ich die 80% doch besser auf 65% runtersetzen.
Irrelevant: Wenn du herausfindest, wieviel % des einen mit dem anderen String identisch sind, dann kannst du die Grenze selbst setzen.
Zwischenschritt: Die Variable RechenUmInProzent enthält die minimale Anzahl an Zeichen, die ersetzt, eingefügt oder gelöscht werden müssen um den String 1 nach String 2 umzusetzen.
Du willst also beliebige Variantionen des Strings erlauben: Zwischen jedem vorhandenen Zeichen können beliebig viele andere Zeichen stehen, jedes vorhandene Zeichen kann auch gelöscht werden, um Übereinstimmung zu erhalten.
Das ist eine äußerst komplexe Aufgabe!
Vielleicht klappts mit einem regulären Ausdruck.
Mal angenommen, du willst den String "defgh" auf Ähnlichkeit testen, dann sollte der zweite String ungefähr so aussehen:
/.*d?.*e?.*f?.*g?.*h?.*/
Vorher, dazwischen, und hinterher beliebig viele (auch kein) Zeichen (das bedeutet '.*'), und die vorhandenen Zeichen können, müssen aber nicht vorkommen (das bedeutet das Fragezeichen dahinter).Wenn du die möglichen Ersetzungen feststellen willst, mußt du die einzelnen Bestandteile in Klammern setzen und auswerten:
/(.*)(d?)(.*)(e?)(.*)(f?)(.*)(g?)(.*)(h?)(.*)/Und diesen Ausdruck vergleichst du dann mit dem zweiten String, und erhälst in den "passenden" Variablen die Information, ob kein oder mehrere Zeichengefunden wurden, die dazwischenpassen.
Du hast allerdings keinerlei Garantie, daß du ein Veränderungsminimum erhälst. Vielleicht findest du im Laufe der Tests heraus, daß es besser ist, den regulären Ausdruck nicht-gierig zu machen. Das sähe dann so aus:
/(.*?)(d?)(.*?)(e?)(.*?)(f?)(.*?)(g?)(.*?)(h?)(.*?)/Letztendlich laufen alle regulären Ausdrücke aber auf eines hinaus: Du verwendest die regulären Ausdrücke von Javascript </selfhtml/javascript/objekte/regexp.htm>. Die Informationen der Klammern fragst du mit RegExp.$1 etc. ab und stellst so fest, ob im zweiten String Zeichen vorhanden waren, die im ersten nicht drinwaren (bei allen Klammern mit *.?), bzw. ob die geforderten Buchstaben enthalten waren (bei Klammern mit x?). Du hast übrigens Glück: Die erste Art von Klammern hat die ungeraden Zahlen, die zweite Art von Klammern die geraden Zahlen in der Ergebnisvariablen.
Ich fürchte nur, in Javascript ist nach neun Klammern Schluß, und bei Wörtern mit mehr als vier Buchstaben mußt du dir was anderes ausdenken.
Du kannst natürlich auch nachforschen, ob es irgendwo einen Ähnlichkeitsalgorithmus gibt, der Strings auf die von dir gewünschte Weise vergleicht und ein Ergebnis auswirft.
Vielleicht solltest du aber doch nicht mit Javascript zu Werke gehen, sondern mit PHP. Das kennt nämlich viele passende Funktionen, um Strings auf Ähnlichkeit zu vergleichen. Unter anderem passen die Funktionen "levenshtein" und "similar_text", welche vermutlich genau das tun, was du willst. Darüber hinaus gibts noch die Funktionen "soundex" und "metaphone", welche Identitäten über die Aussprache feststellen können.
http://www.selfphp.info/funktionsreferenz/string_funktionen/levenshtein.php
- Sven Rautenberg
-
Moment mal, Jungs.
Das kann doch alles so megaschwierig nicht sein.
Manche Seiten bieten doch z.B., wenn man dort nach einem Link sucht, alternative Links mit ähnlichem Namen an.
Mein Server ist leider nicht php-fähig, aber ich habe jetzt mal dazu eine Frage:
Wie kann ich einen Text-php-Code (also keine generierte Grafik) in meine HTML-Seite, also per HTML-Befehle einfügen? Geht das irgendwie? Denn dann könnt ich ja diese Suchroutine über ein externes php-Skript laufen lassen.
Kevin
-
N'abend!
Moment mal, Jungs.
Das kann doch alles so megaschwierig nicht sein.Doch, das ist - jedenfalls programmtechnisch - ziemlich schwierig. Ein Programm kann ganz prima einen String 1:1 mit einem anderen String vergleichen. Wenn auch nur ein Byte unterschiedlich ist, wird es das feststellen und melden - ob die Strings dadurch aber "ähnlich" sind, kann das Programm so einfach nicht sagen.
Manche Seiten bieten doch z.B., wenn man dort nach einem Link sucht, alternative Links mit ähnlichem Namen an.
Tja, diese Seiten müssen aber wohl nicht auf Javascript zurückgreifen. Ich persönlich halte Javascript für extrem ungeeignet, um die Aufgabe zu erfüllen, die Ähnlichkeit von Links zu prüfen. Javascript ist nicht gerade die schnellste Sprache, und hat auch nicht unbedingt die besten vorgefertigten Funktionen für sowas. PHP hätte genau das, was du brauchst...
Mein Server ist leider nicht php-fähig, aber ich habe jetzt mal dazu eine Frage:
Das ist sehr schade für dein Problem.
Wie kann ich einen Text-php-Code (also keine generierte Grafik) in meine HTML-Seite, also per HTML-Befehle einfügen? Geht das irgendwie? Denn dann könnt ich ja diese Suchroutine über ein externes php-Skript laufen lassen.
Das hängt alles von a) deiner Webseite bzw. den Möglichkeiten des Webspaces, b) evtl. von der Art, die Seite zu programmieren und c) vom externen Skript ab.
Dazu solltest du aber mal etwas ausführlicher erzählen, was genau du nun eigentlich willst - bitte im umfassenden Maßstab. Bislang ist nur bekannt, daß du zwei ähnliche Strings vergleichen willst. Was in den Strings drinsteht, ist unbekannt, also können Lösungen nur allgemein sein - möglicherweise ist ja eine Optimierung drin, wenn die Aufgabe spezieller ist. Wenn du beispielsweise herausfinden willst, ob es den Link "www.einlink.de" in der Liste gibt, oder welche anderen Links es gibt, die ähnlich sind, dann könnte man den Link auch einfach auseinandernehmen und nach Einzelteilen suchen, oder stückchenweise nach Einzelteilen (also: enthalten andere Links "einlink"? "einlin"? "inlink"? ...). Trotzdem ist das Problem (welches gerade in Javascript zu ziemlich langen Laufzeiten führen kann), daß du nicht einen Vergleich hast, sondern je nach Stringlänge hunderte Vergleiche mit immer neuen Variationen durchführen mußt.
Wenn du nur bis zu einer gewissen Ähnlichkeit vergleichen willst, dann ließe sich auch auf dieser Basis sicherlich etwas optimieren. Konkreter wird's aber wirklich nur mit mehr Informationen. Und vielleicht bietet sich ja noch ein ganz anderer Ansatz als der, den du bislang wählen willst, indem man z.B. die Datenstrukturen entsprechend optimiert oder die Aufgabenstellung verändert.
- Sven Rautenberg
-
Hi Sven, und alle andern,
hier ist mein Quelltext (ist für eine Fehlerseite, d.h. wenn man eine falsche URL eingibt, erscheint per .htaccess diese Seite hier und die gibt ähnliche Links, die in einem Array gespeichert sind, aus):
[...]
<br><br><span class="topic">Fehler!!!</span><br><br><br>
<strong>Die von Ihnen angeforderte Seite
<script language="javascript">
var CheckArray = new Array("C:\Eigene Dateien\Server-Backups\01-04-2002\jugend\new\error.html","Helena");
var CheckString;
var count = 0;
var percent_of_conformity = 0;
var Aussage = window.location.pathname;
var Suche = Aussage.lastIndexOf("/");
if (Suche == 0) {
Suche = Aussage.lastIndexOf("\");
}
var Link = Aussage.substr(Suche+1,Aussage.length);
if (Link != "error.html") {
document.write(Link);
}
</script>
konnte nicht gefunden werden.</strong><br><br>
Bitte überprüfen Sie die korrekte Schreibweise, oder/und versuchen Sie es erneut.<br><br><br><br>
<strong>Verwandte Links:</strong><br><br>
<script language="javascript">
for(var e = 0; e <= 1; e++) {
CheckString = CheckArray[e];
longest_string_length = (Aussage.length > CheckString.length) ? Aussage.length : CheckString.length;
percent_of_conformity = 0;
for(i = 0; i < longest_string_length; i++) {
if(Aussage.substr(i,1) == CheckString.substr(i,1)){
percent_of_conformity++;
}
}
percent_of_conformity = parseInt((percent_of_conformity/longest_string_length)*10000)/100;
if (percent_of_conformity > 65) {
count++;
document.writeln("<a href="" + CheckString + "">" + CheckString + "</a><br>");
}
}
if (count == 0) {
document.writeln("Keine Übereinstimmungen");
}
</script>
<br><br><br><br>
[...]Ich hoffe, ihr versteht jetzt, warum ich Eure Hilfe brauche.
Tausend Dank
Kevin
-
Moin nochmal!
hier ist mein Quelltext (ist für eine Fehlerseite, d.h. wenn man eine falsche URL eingibt, erscheint per .htaccess diese Seite hier und die gibt ähnliche Links, die in einem Array gespeichert sind, aus):
Dazu fallen mir zwei Dinge ein:
1. Es gibt ein Apache-Modul namens "mod_speling". Das versucht, kleine Tippfehler (ein Zeichen falsch, zuviel oder weggelassen) zu korrigieren und eine passende Seite auszugeben. Bei mehreren Alternativen wird eine Auswahlliste angezeigt. Du solltest schauen, ob das Modul auch bei deinem Webserver installiert und benutzbar ist - spart dir nämlich eine ganze Menge Arbeit.
2. Wenn es um URLs geht, dann fallen mir im Grunde zwei typische Tippfehlermöglichkeiten ein:
a) Falsche Groß/Kleinschreibung.
b) Falsche Dateiendung (.htm statt .html z.B.)Das bedeutet, du hat, bevor du dich auch nur irgendwie um Ähnlichkeiten kümmern mußt, schon mal zwei Ansätze, die möglicherweise erfolgversprechender sind. Denn wenn eine komplett großgeschriebene URL nicht existiert, sondern kleingeschrieben werden muß, dann würde praktisch garkeine Ähnlichkeit festgestellt werden, weil alle Buchstaben ausgetauscht werden müßten - jedenfalls, wenn man die Ähnlichkeit falsch auffaßt und große und kleine Buchstaben als "unterschiedlich" definiert.
Ganz grundsätzlich würde ich dein Problem aber keinesfalls mit Javascript lösen wollen!
Warum nicht? Erstens hast du mit Javascript nur die Informationen, welche du explizit ins Skript schreibst. Wenn du also eine Liste der verfügbaren Dateien haben willst, mußt du die extra in ein Array eintragen - und das Array aktuell halten! Jede Änderung in den Verzeichnissen erfordert eine Änderung im Array. Das ist bei einer kleinen Site (10 Seiten) nicht aufwendig, aber bei einer großen Site (denke da auch an die Ladezeit für die Fehlerseite). Bei einer kleinen Site brauchst du aber nicht diese aufwendige Fehlerbehandlung - da reicht es aus, einfach die vorhandene Navigation anzubieten, mit der man auf jede beliebige Seite gelangen kann. Und falls innerhalb der Site fehlerhafte Links sind, müssen die natürlich repariert werden (dazu die LÖogfiles auswerten). Bei einer großen Site hingegen wird das Javascript möglicherweise ewig vergleichen - da ist der User schon dreimal weiter, wenn er einfach die Navigation benutzt. Mit serverseitigen Skripten könntest du einfach eine Liste der Dateien einlesen, die aktuell vorhanden sind, und dann vergleichen - in PHP sogar mit den passenden Funktionen levenshtein() oder similar_text().
Zweitens könntest du auf dem Server (wenn du es denn könntest) eben mit mod_speling oder schlauen anderen Methoden (z.B. mittels mod_rewrite) solange an der URL rumändern, bis eine passende Seite gefunden wird. Taktik z.B.: wenn /pfad1/pfad2/seite1.html nicht gefunden wird, dann wird auf /pfad1/pfad2/index.html zurückgegriffen, ansonsten auf /pfad1/index.html, und notfalls auf /index.html.
Drittens: Du könntest natürlich auch versuchen, eine Site-interne Suchmaschine zu füttern, und aus den Begriffen der URL passende Suchbegriffe bilden.
Ich weiß schon, daß dich das alles nicht weiterbringt, will es aber trotzdem gesagt haben - die Antwort kommt schließlich ins Archiv.
Was bleibt als Javascript-Lösungsmöglichkeit:
Nutze zuerst nach Möglichkeit die Merkmale deiner URLs, die eindeutig und einheitlich sind.Wenn alle URLs nur Kleinbuchstaben verwenden, dann konvertiere die eingegebene URL vor jedem anderen Vergleich erst in Kleinbuchstaben - vielleicht ist das schon der Fehler gewesen, und du erhälst dadurch einen eindeutigen Treffer.
Wenn du immer .html verwendest, prüfe, ob das in der eingegebenen URL auch verwendet wurde, ansonsten korrigiere und prüfe, ob diese neue URL existiert.
Trenne den Dateinamen hinten ab und prüfe, ob in dem angeforderten Verzeichnis Dateien existieren, welche mit dem Dateinamen oder einem Teil davon vorne anfangen. Wenn also seite1.html gewünscht wurde, aber nicht existiert, dann prüfe, ob seite1*, seite*, seit*, sei*, se* oder s* existieren. Prüfe auch, ob *seite1*, *seite*... existieren (also vorne Zeichen fehlen). Logisch, daß mit fortscheitender Verfremdung die Übereinstimmung immer weniger werden sollte. :)
Bedenke bei all den Methoden aber eines: Ein Computer kann nur anhand gewisser Regeln Übereinstimmungen feststellen - er kann aber niemals Übereinstimmungen _erkennen_, so wie es ein Mensch kann. Uns ist auf den ersten Blick klar, daß /begrüßung/willkommen.html und /begruessung/hallo.htm irgendwie ähnlich sind. Vor allem, wenn wir die restlichen Dateien und deren Inhalt kennen, aber keine andere als die hallo.htm eine Begrüßung enthält, und willkommen.html garnicht existiert. Der Computer aber "sieht" nichts.
Insofern halte ich deine Herangehensweise für Overkill und nicht zweckdienlich zugleich.
Overkill, weil du versuchst, den Computer mit menschlicher Intelligenz zu versehen (und das mit Javascript - die Quadratur des Kreises ist leichter als das ;) ).
Nicht zweckdienlich, weil das mögliche Resultat nicht besser sein muß, als einfach eine Liste aller im angesprochenen Verzeichnis vorhandenen Dateien auszugeben, wenn die konkrete Datei nicht gefunden wurde.
Wenn du die gewünschte URL nach deinen Dateinamenskonventionen (also immer .html, immer kleingeschrieben) umgewandelt hast und keinen Treffer findest (den könntest du dann per Link, oder noch besser: Direkt per Weiterleitung ausgeben), dann ist alles weitere nur Voodoo.
Mag sein, daß ich das zu pessimistisch sehe, aber ich erwarte in der Regel von einer 404-Seite nicht, daß sie mittels Javascript errät, was ich wollte. Schlimm genug, daß sie überhaupt erscheint, aber dann ist das Vorhandensein der Sitenavigation wichtiger, als die möglichen Links. Meistens verlasse ich solche Seiten auch wieder mit dem "Zurück"-Button, weil ich dann doch lieber dort weitermache, wo ich hergekommen bin.
- Sven Rautenberg
-
-
-
-
-
Prozent: 65%, bzw. 80% sind, wenn 20% der Zeichen (Zwischenschritt) von der Gesamtanzahl der Zeichen des Strings ersetzt, eingefügt oder gelöscht werden müssen.
Vielleicht verrätst Du uns mal, wozu Du das überhaupt brauchst, vielleicht gibt es ja noch eine einfacher umsetzbare Formel.
Ich habe mal eine (zugegeben nicht perfekte) Fuzzy-Vergleichsroutine geschrieben, die so vorging, um die Ähnlichkeit von String A und String B zu bewerten:1. Loope über die Buchstaben von String A. Sei A[i] der i-te Buchstabe von A.
2. Wenn A[i] == B[i], erhöhe Score um 1.00.
3. Wenn A[i] == B[i-1] oder A[i] == B[i+1], erhöhe Score um 0.50.
3b. (evtl.) Wenn A[i] == B[i-2] oder ..., erhöhe Score um 0.25.
4. Andernfalls verringere Score um 0.50.Am Ende steht dann eine Summe, die die Ähnlichkeit von A und B beschreibt (an den Werten muß man noch tunen, bei mir waren die am Ende so bei +0.35 und +0.56).
So kann man z.B. erreichen, daß eine Suche nach "Stetoskp" auch "Stethoskop" findet etc.
(Das war in Cold Fusion, wo es keine nativen Fuzzy-Funktionen gibt. :-)
-
-
-
Hallo.
Ausgehend von der Länge des längsten Strings, wird an jeder Position überprüft, ob die Zeichen der beiden Strings gleich sind oder nich:
<script type="text/javascript">
<!--
original_string = window.prompt("original_string","the quick brown fox jumps over the lazy dog").split("");
string_to_check = window.prompt("string_to_check","The Quick Brown Fox Jumps Over The Lazy Dog").split("");
percent_of_conformity = 0;
longest_string_length = (original_string.length > string_to_check.length) ? original_string.length : string_to_check.length;
for(i = 0; i < longest_string_length; i++){if(original_string[i] == string_to_check[i]){percent_of_conformity++}}
percent_of_conformity = parseInt((percent_of_conformity/longest_string_length)*10000)/100;
window.alert(percent_of_conformity + "% Übereinstimmung");
if(percent_of_conformity > 80){window.alert(string_to_check.join(""))}
//-->
</script>Gruß
Norbert-
Wow, das klappt ja nahezu perfekt!
Großartig, vielen Dank Norbert.
Beim Einbinden in mein Skript habe ich nur noch irgendwie für mich unerklärliche Probleme. Mein Skript sieht folgendermaßen aus:
var CheckArray = new Array("blabla","test");
var CheckString;
var percent_of_conformity = 0
for(var e = 0; e <= 1; e++) {
CheckString = CheckArray[e];
percent_of_conformity = 0;
longest_string_length = (Aussage.length > CheckString.length) ? Aussage.length : CheckString.length;
for(i = 0; i < longest_string_length; i++) {
if(Aussage[i] == CheckString[i]){
percent_of_conformity++;
}
}
percent_of_conformity = parseInt((percent_of_conformity/longest_string_length)*10000)/100;
if (percent_of_conformity > 65) {
document.writeln("<a href="" + CheckString + "">" + CheckString + "</a><br>");
}
}Bei diesem Skript werden bei mir jetzt aber alle Arrays von CheckArray ausgelesen, und nicht nur die, die 65% mit dem Aussage-String übereinstimmen. Als Ergebnis kommt immer 100% raus, warum? Wo ist der Fehler in dem Skript? Was habe ich falsch gemacht?
Vielen Dank für Eure Hilfe
Kevin
-
-
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