Tester la distance d’édition iOS sur un Mac cloud

Pour proposer des corrections dans un champ de recherche, quelques dizaines de lignes suffisent souvent à calculer une distance d’édition. Pourtant, les caractères chinois, les accents combinés et les emoji peuvent facilement fausser le résultat. En plaçant les tests dans un répertoire de travail fixe sur un Mac cloud, les membres d’une équipe répartis sur plusieurs fuseaux horaires peuvent réutiliser les mêmes cas Swift. L’enjeu n’est pas de comparer la vitesse des machines, mais de définir précisément ce qui constitue « un caractère » et de plafonner le travail autorisé pour chaque comparaison.

Fixer le modèle de distance et la définition d’un caractère

Cet article utilise la distance de Levenshtein : une insertion, une suppression ou une substitution coûte une opération. La permutation de deux caractères adjacents ne compte pas comme une seule opération. La distance entre ab et ba vaut donc deux, et non un. Si la correction automatique doit prendre en charge les permutations, il faut changer d’algorithme, pas simplement modifier les résultats attendus.

Les chaînes sont décomposées en valeurs Swift Character, c’est-à-dire en grappes de graphèmes étendues. Un emoji représentant une famille peut contenir plusieurs valeurs scalaires Unicode, mais il participe à la comparaison comme un seul caractère. Selon la sémantique d’égalité des caractères de Swift, deux caractères accentués équivalents peuvent être égaux même si l’un est précomposé et l’autre décomposé.

La neutralisation de la casse, la conversion entre caractères pleine chasse et demi-chasse, ainsi que la suppression des accents ne relèvent pas de la fonction de distance. Si le produit exige ces règles, elles doivent être regroupées dans une couche de prétraitement distincte, tout en conservant le texte d’origine.

Une distance plus faible signifie seulement que le modèle d’opérations choisi demande moins de modifications. Elle ne traduit pas une proximité sémantique entre deux mots et ne peut pas servir directement de critère de rapprochement d’identités ou de décision de sécurité.

Implémenter des tableaux à deux lignes avec un budget de calcul

Sur le Mac cloud, vérifiez que la commande xcrun swift --version s’exécute, puis enregistrez le contenu suivant dans edit-distance.swift. L’implémentation ne conserve que la ligne précédente et la ligne courante. L’entrée la plus courte est placée en colonnes, ce qui évite de stocker toute la matrice.

Trois limites s’appliquent aux entrées : au maximum 16384 octets UTF-8 et 512 caractères par chaîne, et un produit des deux longueurs limité à 65536. Ces valeurs sont des exemples de budgets techniques, pas les conclusions d’un test de performances. En production, il faut les adapter au nombre de candidats et à l’objectif de latence des interactions.

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]
}

Le contrôle par division évite le dépassement d’entier qui pourrait se produire si l’on effectuait la multiplication avant de vérifier la limite. Les chaînes vides sont traitées avant cette division, ce qui élimine le risque de division par zéro. La limite en octets est vérifiée avant la construction des tableaux : elle empêche d’accepter une entrée trop volumineuse composée de peu de caractères mais de très nombreuses marques combinatoires, ce qu’une limite portant uniquement sur le nombre de caractères ne suffirait pas à bloquer.

Ajouter des tests d’acceptation directement exécutables

Ajoutez le code suivant à la fin du même fichier, puis lancez xcrun swift edit-distance.swift. Une fonction de vérification explicite déclenche l’échec du test, sans dépendre d’assertions susceptibles d’être désactivées selon la configuration d’optimisation.

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 {
}

Ces cas vérifient l’initialisation, les substitutions, le traitement des permutations et l’unité Unicode retenue. Le test de rejet pour dépassement du budget n’accepte que l’erreur prévue. Toute autre erreur continue de se propager : une interception trop large ne peut donc pas transformer à tort un échec en réussite.

Couvrir les combinaisons d’entrées par des tests de propriétés

Les cas fixes détectent les erreurs connues. Les tests combinatoires permettent, eux, de repérer des défauts dans l’échange des lignes, l’initialisation des bords de la matrice ou le traitement des caractères répétés. Toujours avec a, b et un caractère chinois, générez toutes les chaînes de longueur inférieure ou égale à trois. Pour chaque paire, vérifiez que :

• La distance d’une chaîne à elle-même est nulle, et l’inversion des arguments ne change pas le résultat.
• La distance est supérieure ou égale à la valeur absolue de la différence des longueurs en caractères.
• La distance est inférieure ou égale à la plus grande des deux longueurs en caractères.

Vérifiez aussi l’inégalité triangulaire sur quelques triplets. Le respect de ces propriétés ne prouve pas que l’algorithme est entièrement correct : ces tests doivent donc être associés à des cas dont le résultat est connu. Pour les entrées qui dépassent le budget, il ne faut ni exiger une distance en retour ni les inclure dans ces comparaisons de propriétés.

Tester séparément la couche de prétraitement

Si la recherche ignore la casse, vérifiez d’abord séparément la sortie du prétraitement, puis la distance entre les sorties obtenues. N’appelez pas de conversions dépendant des paramètres régionaux courants dans la boucle de programmation dynamique. Sinon, une même paire de mots pourrait produire des résultats différents selon l’environnement, et chaque cellule supporterait à nouveau le coût de conversion.

Intégrer les tests au pipeline et limiter le travail total

Versionnez le script avec le code de l’application et exécutez-le avant les tests unitaires. Un code de sortie non nul doit bloquer les étapes suivantes. Consignez l’identifiant du commit source, la version de Swift et le cas en échec. Il n’est pas nécessaire de fixer des seuils à la milliseconde sur le temps écoulé réel : les variations de charge liées aux tâches partageant la machine rendraient ces seuils bruyants.

Un budget par comparaison ne garantit pas un budget pour l’ensemble d’une requête de recherche. Réduisez d’abord l’ensemble des candidats selon leur catégorie métier ou leur écart de longueur, puis limitez leur nombre. Si l’annulation doit être prise en charge, vérifiez son état entre deux candidats. La fonction de distance synchrone ne s’interrompt pas automatiquement lorsque la tâche qui l’englobe est annulée.

Avant la mise en production, précisez quatre points : la politique pour les entrées vides, l’affichage des erreurs de dépassement, le budget total des candidats et la version du prétraitement. Un dépassement doit être explicitement signalé comme « non calculé », jamais déguisé en une distance très élevée. Le classement des résultats ne confondra ainsi pas une mesure de protection des ressources avec un indice de dissemblance entre les textes.

Questions fréquentes