iOS-Editierdistanz auf einem Cloud-Mac zuverlässig testen

Wenn ein Suchfeld bei Tippfehlern passende Vorschläge liefern soll, lässt sich die Editierdistanz oft mit wenigen Dutzend Zeilen Code berechnen. Bei chinesischen Zeichen, kombinierenden Akzenten und Emojis entstehen dabei jedoch leicht falsche Ergebnisse. Liegen die Tests in einem festen Arbeitsverzeichnis auf einem Cloud-Mac, können Teammitglieder über Zeitzonen hinweg dieselben Swift-Testfälle verwenden. Entscheidend ist nicht, wie schnell der Rechner arbeitet, sondern was genau als „ein Zeichen“ gilt und wie viel Rechenaufwand eine einzelne Vergleichsoperation höchstens verursachen darf.

Distanzmodell und Zeichenbegriff festlegen

Dieser Artikel verwendet die Levenshtein-Distanz: Einfügen, Löschen und Ersetzen zählen jeweils als eine Operation; das Vertauschen benachbarter Zeichen zählt nicht als einzelne Operation. Die Distanz von ab zu ba beträgt deshalb zwei, nicht eins. Soll eine Autokorrektur Vertauschungen unterstützen, muss der Algorithmus ausgetauscht werden. Nur die erwarteten Testergebnisse anzupassen, reicht nicht.

Zeichenketten werden in Swift-Character-Werte zerlegt, also in erweiterte Graphemcluster. Ein Familien-Emoji kann aus mehreren Unicode-Skalarwerten bestehen, geht aber als ein Zeichen in den Vergleich ein. Äquivalente Akzentzeichen in vorkomponierter und zerlegter Form können nach Swifts Gleichheitssemantik für Zeichen gleich sein.

Die Vereinheitlichung von Groß- und Kleinschreibung, die Umwandlung zwischen vollbreiten und halbbreiten Zeichen sowie das Entfernen von Akzenten gehören nicht zur Distanzfunktion. Benötigt das Produkt solche Regeln, sollten sie in einer eigenen Vorverarbeitungsschicht umgesetzt werden. Der Originaltext muss dabei ebenfalls erhalten bleiben.

Eine kleinere Distanz bedeutet lediglich, dass im gewählten Operationsmodell weniger Änderungen nötig sind. Sie sagt nichts über die semantische Ähnlichkeit zweier Wörter aus und darf nicht unmittelbar als Grundlage für Identitätsabgleiche oder Sicherheitsentscheidungen dienen.

Rollierende Arrays mit Rechenbudget implementieren

Prüfen Sie auf dem Cloud-Mac, ob sich xcrun swift --version ausführen lässt, und speichern Sie den folgenden Inhalt als edit-distance.swift. Die Implementierung hält nur die vorherige und die aktuelle Zeile vor. Die kürzere Eingabe wird den Spalten zugeordnet, sodass nicht die gesamte Matrix gespeichert werden muss.

Für die Eingaben gelten drei Grenzen: höchstens 16384 UTF-8-Bytes und 512 Zeichen pro Zeichenkette sowie höchstens 65536 für das Produkt der beiden Zeichenlängen. Diese Werte sind beispielhafte technische Budgets, keine Ergebnisse eines Leistungstests. Im Produktivbetrieb sollten sie an die Zahl der Kandidaten und die angestrebte Reaktionszeit angepasst werden.

enum DistanceError: Error {
    case inputLimit
    case workLimit
}

func distance(_ lhs: String, _ rhs: String) throws -> Int {
    guard lhs.utf8.count <= 16_384,
          rhs.utf8.count <= 16_384 else {
        throw DistanceError.inputLimit
    }

    let a = Array(lhs)
    let b = Array(rhs)
    guard a.count <= 512, b.count <= 512 else {
        throw DistanceError.inputLimit
    }

    if a.isEmpty { return b.count }
    if b.isEmpty { return a.count }

    guard a.count <= 65_536 / b.count else {
        throw DistanceError.workLimit
    }

    let columns = a.count <= b.count ? a : b
    let rows = a.count <= b.count ? b : a
    var previous = Array(0...columns.count)
    var current = Array(repeating: 0, count: columns.count + 1)

    for i in rows.indices {
        current[0] = i + 1
        for j in columns.indices {
            let substitution = previous[j]
                + (rows[i] == columns[j] ? 0 : 1)
            current[j + 1] = min(
                previous[j + 1] + 1,
                min(current[j] + 1, substitution)
            )
        }
        swap(&previous, &current)
    }
    return previous[columns.count]
}

Die Prüfung per Division vermeidet einen Ganzzahlüberlauf, der auftreten könnte, wenn erst multipliziert und anschließend geprüft würde. Bei einer leeren Zeichenkette kehrt die Funktion vor der Division zurück, sodass keine Division durch null möglich ist. Die Byte-Grenze wird vor dem Aufbau der Arrays geprüft. So werden übergroße Eingaben auch dann abgefangen, wenn wenige Zeichen sehr viele kombinierende Zeichen enthalten und eine reine Begrenzung der Zeichenzahl nicht ausreichen würde.

Direkt ausführbare Abnahmetests ergänzen

Hängen Sie den folgenden Code an dieselbe Datei an und führen Sie anschließend xcrun swift edit-distance.swift aus. Eine explizite Prüffunktion löst bei einem Fehlschlag einen Fehler aus; der Test verlässt sich damit nicht auf Assertions, die je nach Optimierungskonfiguration deaktiviert sein können.

func require(_ condition: Bool) {
    if !condition { fatalError("Distance contract failed") }
}

let fixtures: [(String, String, Int)] = [
    ("", "", 0),
    ("", "构建", 2),
    ("kitten", "sitting", 3),
    ("构建", "构件", 1),
    ("ab", "ba", 2),
    ("\u{00E9}", "e\u{0301}", 0),
    ("👨‍👩‍👧‍👦", "", 1)
]

for (a, b, expected) in fixtures {
    let forward = try distance(a, b)
    let backward = try distance(b, a)
    require(forward == expected)
    require(backward == expected)
}

do {
    _ = try distance(
        String(repeating: "a", count: 257),
        String(repeating: "b", count: 257)
    )
    fatalError("Expected work limit")
} catch DistanceError.workLimit {
}

Diese Testfälle prüfen die Initialisierung, Ersetzungen, die Semantik von Vertauschungen und die verwendete Unicode-Einheit. Der Test für die Budgetüberschreitung akzeptiert ausschließlich den dafür vorgesehenen Fehler. Andere Fehler werden weitergereicht und können nicht durch einen pauschalen Catch-Block fälschlich als bestandener Test gewertet werden.

Zeichenkombinationen mit Eigenschaftstests abdecken

Feste Testfälle decken bekannte Fehler auf. Kombinatorische Tests eignen sich dagegen besonders dafür, Fehler beim Zeilentausch, bei der Randinitialisierung und im Umgang mit wiederholten Zeichen zu finden. Erzeugen Sie aus a, b und einem chinesischen Zeichen alle kurzen Zeichenketten mit höchstens drei Zeichen. Prüfen Sie für jedes Paar:

• Die Distanz einer Zeichenkette zu sich selbst ist null; beim Vertauschen der Argumente bleibt das Ergebnis gleich.
• Die Distanz ist mindestens so groß wie der Betrag der Differenz der Zeichenlängen.
• Die Distanz ist höchstens so groß wie die größere der beiden Zeichenlängen.

Prüfen Sie zusätzlich für einige Tripel die Dreiecksungleichung. Dass diese Eigenschaften erfüllt sind, beweist nicht die vollständige Korrektheit des Algorithmus. Deshalb müssen sie zusammen mit Fällen geprüft werden, deren Ergebnis bekannt ist. Für Eingaben außerhalb des Budgets darf weder die Rückgabe einer Distanz verlangt werden, noch dürfen sie in diese Eigenschaftsvergleiche eingehen.

Vorverarbeitung separat testen

Ignoriert die Suche Groß- und Kleinschreibung, prüfen Sie zunächst separat das Ergebnis der Vorverarbeitung und anschließend die Distanz zwischen den vorverarbeiteten Zeichenketten. Rufen Sie innerhalb der dynamischen Programmierung keine Umwandlungen auf, die von den aktuellen Regionseinstellungen abhängen. Sonst kann dasselbe Wortpaar je nach Umgebung unterschiedliche Ergebnisse liefern, und die Umwandlungskosten fallen in jeder Zelle erneut an.

In die Pipeline einbinden und den Gesamtaufwand begrenzen

Versionieren Sie das Skript zusammen mit dem Anwendungscode und führen Sie es vor den Unit-Tests aus. Ein Exit-Code ungleich null muss die nachfolgenden Schritte blockieren. Protokollieren Sie die Commit-Kennung des Quellcodes, die Swift-Version und den fehlgeschlagenen Testfall. Millisekundengenaue Schwellenwerte auf Basis der verstrichenen Echtzeit sind dafür nicht erforderlich; wechselnde Auslastung durch parallel laufende Aufgaben würde solche Schwellenwerte unnötig störanfällig machen.

Ein Budget pro Vergleich ist noch kein Budget für die gesamte Suchanfrage. Grenzen Sie die Kandidaten zunächst nach fachlicher Kategorie oder Längendifferenz ein und begrenzen Sie anschließend ihre Anzahl. Soll ein Abbruch möglich sein, prüfen Sie den Abbruchstatus zwischen den Kandidaten. Die synchrone Distanzfunktion wird nicht automatisch unterbrochen, wenn die umgebende Task abgebrochen wird.

Vor dem Produktivstart müssen vier Punkte feststehen: der Umgang mit leeren Eingaben, die Anzeige von Grenzwertüberschreitungen, das Gesamtbudget für Kandidaten und die Version der Vorverarbeitung. Eine Überschreitung muss ausdrücklich als „nicht berechnet“ zurückgegeben werden und darf nicht als sehr große Distanz getarnt sein. So verwechselt die Suchrangfolge Maßnahmen zum Ressourcenschutz nicht mit einem Hinweis auf unähnliche Texte.

Häufig gestellte Fragen