Das Werkzeug String-Ähnlichkeit nimmt zwei Text-Strings, String A und String B, die standardmäßig kitten und sitting sind, und berechnet im Browser die Levenshtein-Bearbeitungsdistanz zwischen beiden. Bei jeder Taste rechnet das Ergebnis live neu: drei Statistik-Karten geben die Distanz, den Ähnlichkeits-Prozentsatz und die Operationenzahl aus, bei den Standardwerten 3, 57.1% und 7, und darunter eine Fortschrittsleiste und eine nummerierte, farbcodierte Editier-Skript-Liste, die jeden Schritt vom ersten bis zum letzten Zeichen aufführt. Alles ist ein Dynamic-Programming-Durchlauf im Browser über die beiden Strings: nichts wird irgendwo hingesendet, und an keiner Stelle findet ein Hochladen statt.
Was das Werkzeug nimmt und was es gibt
Die Eingabe ist zwei eingezeilige Textfelder nebeneinander, beschriftet String A und String B, in einer Monospace-Schrift, und es wird nichts weiter verlangt. Die Standardwerte sind kitten in A und sitting in B, und die gleichen zwei Wörter erscheinen als Platzhalter der Felder. Die Ausgabe ist drei Karten in einer Reihe: die Distanz als reiner Ganzzahlwert, die Ähnlichkeit als Prozentsatz mit einer Nachkommastelle, und die Operationenzahl als reiner Ganzzahlwert. Unter den Karten füllt sich eine Fortschrittsleiste auf denselben Prozentsatz, und eine scrollbare Liste gibt das komplette Editier-Skript aus, jede Zeile von 1 an nummeriert, jede Zeile nach ihrem Typ gefärbt: Ersetzung in Gelb, Einfügung in Blau, Löschung in Rot, und Treffer in der abgedunkelten Textfarbe. Es gibt keinen Knopf: Das Ergebnis rechnet neu, während du tippst, weil die ganze Rechnung ein Lesevorgang mit Memoisierung der beiden Feldwerte ist.
Wie die Distanz berechnet wird
Die Distanz ist die klassische Levenshtein-Distanz, gebaut mit einer Dynamic-Programming-Tabelle von (Länge von A + 1) mal (Länge von B + 1) Zellen. Jede Zelle nimmt das Minimum von drei Nachbarzellen plus einer Kosten: die Zelle darüber plus eins, das ist eine Löschung; die Zelle links plus eins, das ist eine Einfügung; und die Diagonale plus einer Kosten von null, wenn die beiden Zeichen gleich sind, und eins, wenn sie es nicht sind, das ist ein Treffer oder eine Ersetzung. Der Vergleich ist zeichenweise und unterscheidet Groß- und Kleinschreibung, also sind K und k verschiedene Zeichen. Für die Standardwerte, kitten gegen sitting, ist die Tabelle 7 mal 8, 56 Zellen, und die Zelle unten rechts liest 3: das k durch ein s ersetzen, das e durch ein i ersetzen, und das g einfügen. book gegen back ist 2, die beiden o-Positionen; flaw gegen lawn ist 2, die Löschung des f und die Einfügung des n am Ende.
Was die Operationsliste zeigt
Die Liste ist ein Rückweg durch die fertige Tabelle, vom unteren rechten Eck zurück zum oberen linken. Bei jedem Schritt bevorzugt der Weg einen Treffer, wenn die beiden aktuellen Zeichen gleich sind, dann eine Ersetzung, dann eine Einfügung, dann eine Löschung, und die gesammelten Schritte werden umgekehrt ausgegeben, vom ersten zum letzten. Dieser Weg ergibt ein gültiges minimales Editier-Skript, nicht das einzige: verschiedene gleich teure Entscheidungen bei einem Gleichstand gäben eine andere Liste gleicher Länge. Treffer stehen auch in der Liste, also ist die Operationenzahl die Länge des Skripts, nicht die Distanz. kitten gegen sitting gibt 7 Operationen für eine Distanz von 3 aus, die vier Treffer sind i, t, t und n; kitten gegen sich selbst gibt 6 Operationen, alle Treffer, für eine Distanz von 0; flaw gegen lawn gibt 5 aus, die zwei Edits plus drei Treffer.
Wie der Ähnlichkeits-Prozentsatz abgelesen wird
Der Prozentsatz ist die längere Länge minus die Distanz, geteilt durch die längere Länge, mal hundert, mit einer Nachkommastelle ausgegeben. Für die Standardwerte, 7 minus 3 durch 7, liest er 57.1%, was im gelben Band liegt: die Zahl und die Leiste werden bei 70 oder mehr grün, bei 40 oder mehr gelb, und unter 40 rot. Identische Strings lesen 100.0% bei Distanz 0. Eine einzelne Groß-Klein-Wendung, Kitten gegen kitten, ist eine Distanz von 1 über einer Länge von 6 und liest 83.3%. Ein Akzent zählt als ein Zeichenunterschied: café gegen cafe ist eine Distanz von 1 und liest 75.0%. Und ein Surrogatpaar zählt als zwei Einheiten, also ist das Smiley in a😀b gegen ab eine Distanz von 2 und liest 50.0%.
Wenn das Ergebnis leer ist
Wenn eines der beiden Felder nach dem Zuschneiden leer ist, ist das Ergebnis null und nichts unter den beiden Eingaben wird gerendert: keine Karten, keine Leiste, keine Liste. Leerzeichen innen oder an den Rändern werden nicht aus dem Vergleich entfernt, sie dienen nur zur Leere-Prüfung, also ist ein Leerzeichen am Ende eine Bearbeitung: key mit einem Leerzeichen am Ende gegen key ist eine Distanz von 1 und liest 75.0% über der Länge von 4. Gegen eine leere Zeichenkette ist die Distanz die ganze Länge der anderen Seite, deshalb berechnet abc gegen die leere Seite 3 und 0.0%, auch wenn die Seite es nicht anzeigt, solange das Feld leer bleibt.
Wie lang die Strings sein dürfen
Es gibt keine Längenbegrenzung im Code. Der Aufwand ist die Tabellengröße, (Länge von A + 1) mal (Länge von B + 1) Zellen, also wächst die Arbeit mit dem Produkt der beiden Längen: kitten gegen sitting sind 56 Zellen, zwei Strings à 1,000 Zeichen sind etwa eine Million Zellen, und zwei à 10,000 Zeichen sind etwa hundert Millionen, die die Seite berechnet, aber langsam. Die Eingaben sind eingezeilige Felder, also werden sehr lange Strings in einer Zeile eingegeben oder eingefügt.
Was es nicht ist
Das Werkzeug vergleicht, es transformiert den Text nicht: um die überflüssigen Leerzeichen und Zeilen vor dem Vergleich zu entfernen, nutzt man den Leerraum-Reiniger; um einen String von Ende zu Anfang zu kehren, macht das der Textumkehrer; und um Zeichen zu zählen, ohne einen zweiten String, macht das der Zeichenzähler und -Analyseur. Für den Einstieg in das Umkehr-Werkzeug sieh den Textumkehrer-Guide.