Mesurer la similarité de deux chaînes de caractères (Distance de Levenshtein en PowerShell)

Ah, les chaînes de caractères ! Ces suites de lettres, chiffres et symboles qui peuplent nos codes et nos vies de développeurs. Qu’elles contiennent des mots, des phrases, ou même de simples caractères, leur manipulation est au cœur de presque tout ce que nous faisons en programmation.

Mais comment savoir à quel point deux chaînes de caractères se ressemblent ? C’est là qu’intervient notre super-héros du jour : la distance de Levenshtein. (Modèle qui retourne une valeur égale au nombre minimal de caractères qu’il faut supprimer, insérer ou remplacer pour passer d’une chaîne à l’autre)

Un peu comme un baromètre de la similarité, cette technique nous dit combien de modifications il faut pour passer de la chaîne A à la chaîne B. Pratique, n’est-ce pas ?

Dans cet article, on va plonger tête première dans l’univers fascinant de la distance de Levenshtein et on va coder tout ça en PowerShell.

Pourquoi PowerShell, vous demandez ? Parce que c’est comme le couteau suisse de la programmation : ça coupe, ça visse, ça mesure, et surtout, ça scripte avec une élégance remarquable 🙂

La fonction de calcul de la distance de Levenshtein en PowerShell

On va reprendre la formule ci-dessous :

Directement le code de la fonction de calcul de la distance de Levenshtein en PowerShell et on détaille ça ensuite :

function Get-LevenshteinDistance {
    param (
        [Parameter(Mandatory)]
        [string]$String1,
        [Parameter(Mandatory)]
        [string]$String2
    )

    $length1 = $String1.Length
    $length2 = $String2.Length

    # Initialisation du tableau précédent avec des valeurs de 0 à la longueur de $String2.
    # Cela représente le coût initial pour transformer une chaîne vide en la sous-chaîne de $String2 jusqu'à chaque position.
    $prevRow = 0..$length2
    
    # Crée un nouveau tableau pour stocker les calculs de la ligne actuelle.
    $currentRow = New-Object int[] ($length2 + 1)

    for ($i = 1; $i -le $length1; $i++) {
        # Définit le premier élément de la ligne actuelle, ce qui représente le coût de suppression de tous les caractères jusqu'à $i dans $String1.
        $currentRow[0] = $i
        for ($j = 1; $j -le $length2; $j++) {
            # Calcul du coût de substitution. Si les caractères actuels sont identiques, le coût est 0. Sinon, le coût est 1.
            if ($String1[$i - 1] -eq $String2[$j - 1]) {
                $cost = 0
            }
            else {
                $cost = 1
            }

            # Calcul des coûts pour les opérations de suppression, insertion, et substitution.
            # Le coût pour chaque opération est calculé par rapport aux valeurs précédemment calculées et stockées dans $prevRow et $currentRow.
            $insert = $currentRow[$j - 1] + 1
            $delete = $prevRow[$j] + 1
            $substitute = $prevRow[$j - 1] + $cost

            # Le coût minimum parmi les trois opérations est sélectionné et stocké dans la ligne actuelle.
            $currentRow[$j] = [Math]::Min($insert, [Math]::Min($delete, $substitute))
        }

        # Échange les lignes pour la prochaine itération, la ligne actuelle devient la ligne précédente et vice-versa.
        $tempRow = $prevRow
        $prevRow = $currentRow
        $currentRow = $tempRow
    }

    # La dernière valeur calculée dans $prevRow correspond à la distance de Levenshtein entre les deux chaînes.
    return $prevRow[$length2]
}

Initialisation

1. Déclaration de la fonction et paramètres : La fonction Get-LevenshteinDistance prend deux chaînes de caractères en entrée, $String1 et $String2.
2. Cas de base : Si l’une des chaînes est vide, la distance de Levenshtein est simplement la longueur de l’autre chaîne, car cela représenterait le nombre d’insertions nécessaires pour passer d’une chaîne vide à la chaîne non vide.

Préparation des tableaux

3. Initialisation des tableaux :
   • $prevRow est initialisé avec des valeurs allant de 0 à la longueur de $String2. Ceci représente le « coût » initial pour transformer une chaîne vide en toutes les sous-chaînes possibles de $String2.
   • $currentRow est un tableau destiné à contenir les calculs pour chaque caractère de $String1 au fur et à mesure qu’ils sont effectués.

Calcul de la distance

4. Boucle principale sur $String1 : Pour chaque caractère dans $String1 (indexé par $i), nous allons calculer le « coût » pour le transformer en chaque sous-chaîne de $String2.
5. Initialisation de la première cellule de $currentRow : La première cellule de $currentRow est toujours définie à $i, ce qui représente le coût de suppression de tous les caractères précédents dans $String1 pour obtenir une chaîne vide.
6. Boucle secondaire sur $String2 : Pour chaque caractère dans $String2 (indexé par $j), nous calculons le coût minimal pour transformer la sous-chaîne de $String1 jusqu’à $i en la sous-chaîne de $String2 jusqu’à $j. Les calculs sont basés sur les opérations de suppression, insertion et substitution :
   • Insertion : Le coût d’insertion est calculé en prenant la valeur actuelle de $currentRow[$j - 1] et en ajoutant 1.
   • Suppression : Le coût de suppression est obtenu en prenant la valeur de $prevRow[$j] et en ajoutant 1.
   • Substitution : Le coût de substitution est calculé en prenant $prevRow[$j - 1] et en ajoutant $cost, qui est 0 si les caractères actuels sont identiques, sinon 1.
7. Sélection du coût minimal : Pour chaque paire de caractères, nous sélectionnons l’opération (insertion, suppression, substitution) qui a le coût minimal et mettons à jour $currentRow[$j] avec cette valeur.

Mise à jour pour la prochaine itération

8. Échange des rôles de $prevRow et $currentRow : Après avoir calculé tous les coûts pour les caractères actuels de $String1, $prevRow est mis à jour pour être $currentRow (les résultats de l’itération actuelle deviennent la base pour la prochaine itération), et $currentRow est réinitialisé en utilisant $tempRow (ce qui était $prevRow avant la mise à jour) pour les nouveaux calculs.

Conclusion

9. Retour de la distance de Levenshtein : Une fois toutes les itérations complétées, la dernière valeur de $prevRow à l’indice correspondant à la longueur de $String2 représente la distance de Levenshtein entre les deux chaînes.

Tester le calcul de la distance de Levenshtein

$string1 = "Vélo"
$string2 = "Maison"

$distance = Get-LevenshteinDistance -String1 $string1 -String2 $string2
Write-Host "La distance de Levenshtein est de $distance"

Résultat

$string1 = "Maisons"
$string2 = "Maison"

$distance = Get-LevenshteinDistance -String1 $string1 -String2 $string2
Write-Host "La distance de Levenshtein est de $distance"

Résultat

La fonction de calcul de similarité en pourcentage

Maintenant qu’on peut récupérer la distance entre deux chaînes de caractères on peut transformer ça en un pourcentage de similarité avec la formule suivante :

Comme la première fonction, la code puis le détail :

function Get-SimilarityPercentage {
    param (
        [Parameter(Mandatory)]
        $String1,
        [Parameter(Mandatory)]
        $String2
    )

    # Gérer le cas où l'un des arguments est vide.
    if (-not $String1 -and -not $String2) {
        # Les deux chaînes sont vides, considérées comme identiques.
        return 100
    }
    elseif (-not $String1 -or -not $String2) {
        # L'une des chaînes est vide et l'autre non, considérées comme totalement différentes.
        return 0
    }

    # Calculer la distance de Levenshtein si aucune des chaînes n'est vide.
    $distance = Get-LevenshteinDistance -String1 $String1 -String2 $String2

    # Déterminer la longueur maximale entre les deux chaînes.
    $maxLength = [Math]::Max($String1.Length, $String2.Length)

    # Calculer le pourcentage de similarité.
    $similarity = (1 - $distance / $maxLength) * 100

    # Retourner le pourcentage de similarité.
    return [math]::Round($similarity, 2)
}

Définition et Paramètres

La fonction commence par définir ses paramètres d’entrée, qui sont deux chaînes de caractères ($String1 et $String2). Ces chaînes représentent les textes à comparer.

Gestion des Cas Spéciaux

La fonction vérifie ensuite si l’une des chaînes est vide. Si c’est le cas, la similarité est immédiatement déterminée comme 0% si l’autre chaîne n’est pas vide, car une chaîne vide et une chaîne non vide ne peuvent pas être similaires. Si les deux chaînes sont vides, elles sont considérées comme identiques, donc la similarité est de 100%.

Calcul de la Distance de Levenshtein

La fonction calcule ensuite la distance de Levenshtein entre les deux chaînes en appelant une fonction auxiliaire, Get-LevenshteinDistance, qui doit être définie ailleurs dans le script ou le module. Cette distance représente le nombre minimal d’opérations requises pour transformer une chaîne en l’autre.

Calcul du Pourcentage de Similarité

Le pourcentage de similarité est calculé en soustrayant le rapport entre la distance de Levenshtein et la longueur maximale des deux chaînes de 1, puis en multipliant le résultat par 100 pour obtenir un pourcentage. La longueur maximale est utilisée comme dénominateur pour normaliser le score de similarité sur une échelle de 0 à 100, où 100 signifie que les chaînes sont identiques et 0 qu’elles sont totalement différentes.

Retour du Résultat

Finalement, la fonction retourne le pourcentage de similarité calculé. Ce résultat peut être utilisé pour évaluer à quel point deux chaînes de caractères sont similaires selon la métrique de la distance de Levenshtein.

Tester le calcul de pourcentage de similarité

$string1 = "Vélo"
$string2 = "Maison"

$similarityPercentage = Get-SimilarityPercentage -String1 $string1 -String2 $string2
Write-Output "Le pourcentage de similitude est de $similarityPercentage%"

Résultat

$string1 = "Maisons"
$string2 = "Maison"

$similarityPercentage = Get-SimilarityPercentage -String1 $string1 -String2 $string2
Write-Output "Le pourcentage de similitude est de $similarityPercentage%"

Résultat

Conclusion

Donc avons maintenant deux fonctions qui peuvent être utilisés pour retourner la distance de Levenshtein ainsi qu’un pourcentage de similarité.

Article un peu technique mais pour un réelle valeur ! ces fonctions vous aiderons dans de nombreux cas concrets de votre quotidien d’administrateur 😉

Pour ma part je vous présente ceci aujourd’hui car j’ai justement eu besoin de ce modèle de Levenshtein pour comparer des noms de machines venant de plusieurs sources de données mais qui peuvent ne pas être écrit exactement pareil dans ces différentes sources.

A+ les techies !