levenshtein

(PHP 4 >= 4.0.1, PHP 5)

levenshteinCalcule la distance Levenshtein entre deux chaînes

Description

int levenshtein ( string $str1 , string $str2 )
int levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del )

La distance Levenshtein est définie comme le nombre minimal de caractères qu'il faut remplacer, insérer ou modifier pour transformer la chaîne str1 en str2. La complexité de l'algorithme est en O(m*n), où n et m sont les tailles respectives de str1 et str2 : c'est plutôt bien, en comparaison de similar_text(), qui est en O(max(n,m)**3), mais cela reste très coûteux.

Dans sa forme la plus simple, levenshtein() va prendre uniquement deux chaînes de caractères comme paramètres, et calculer simplement le nombre d'insertions, de remplacements et d'effacements nécessaires pour transformer str1 en str2.

La deuxième variante de la fonction prend trois paramètres supplémentaires qui représentent les coûts d'insertions, de remplacements et d'effacements. C'est une version plus générale de la première fonction, mais qui est un peu moins efficace.

Liste de paramètres

str1

Une des chaînes à évaluer.

str2

Une des chaînes à évaluer.

cost_ins

Définit le coût de l'insertion.

cost_rep

Définit le coût du remplacement.

cost_del

Définit le coût de l'effacement.

Valeurs de retour

Retourne la distance Levenshtein entre deux chaînes de caractères. Elle retournera -1 si l'un des deux arguments contient plus de 255 caractères.

Exemples

Exemple #1 Exemple avec levenshtein()

<?php
// mot mal orthographié
$input = 'carrrot';

// tableau de mots à vérifier
$words  = array('apple','pineapple','banana','orange',
				'radish','carrot','pea','bean','potato');

// aucune distance de trouvée pour le moment
$shortest = -1;

// boucle sur les des mots pour trouver le plus près
foreach ($words as $word) {

	// calcule la distance avec le mot mis en entrée,
	// et le mot courant
	$lev = levenshtein($input, $word);

	// cherche une correspondance exacte
	if ($lev == 0) {

		// le mot le plus près est celui-ci (correspondance exacte)
		$closest = $word;
		$shortest = 0;

		// on sort de la boucle ; nous avons trouvé une correspondance exacte
		break;
	}

	// Si la distance est plus petite que la prochaine distance trouvée
	// OU, si le prochain mot le plus près n'a pas encore été trouvé
	if ($lev <= $shortest || $shortest < 0) {
		// définition du mot le plus près ainsi que la distance
		$closest  = $word;
		$shortest = $lev;
	}
}

echo "Mot entré : $input\n";
if ($shortest == 0) {
	echo "Correspondance exacte trouvée : $closest\n";
} else {
	echo "Vous voulez dire : $closest ?\n";
}

?>

L'exemple ci-dessus va afficher :

Mot entré : carrrot
Vous voulez dire : carrot ?

Voir aussi

LoadingChargement en cours