8.127 Chaînes de caractères (Strings)
8 Référence des fonctions
Manuel PHP
. Introduction
. Pré-requis
. Installation
. Constantes pré-définies
. Voir aussi
. addcslashes
. addslashes
. bin2hex
. chop
. chr
. chunk_split
. convert_cyr_string
. convert_uudecode
. convert_uuencode
. count_chars
. crc32
. crypt
. echo
. explode
. fprintf
. get_html_translation_table
. hebrev
. hebrevc
. html_entity_decode
. htmlentities
. htmlspecialchars_decode
. htmlspecialchars
. implode
. join
->levenshtein
. localeconv
. ltrim
. md5_file
. md5
. metaphone
. money_format
. nl_langinfo
. nl2br
. number_format
. ord
. parse_str
. print
. printf
. quoted_printable_decode
. quotemeta
. rtrim
. setlocale
. sha1_file
. sha1
. similar_text
. soundex
. sprintf
. sscanf
. str_ireplace
. str_pad
. str_repeat
. str_replace
. str_rot13
. str_shuffle
. str_split
. str_word_count
. strcasecmp
. strchr
. strcmp
. strcoll
. strcspn
. strip_tags
. stripcslashes
. stripos
. stripslashes
. stristr
. strlen
. strnatcasecmp
. strnatcmp
. strncasecmp
. strncmp
. strpbrk
. strpos
. strrchr
. strrev
. strripos
. strrpos
. strspn
. strstr
. strtok
. strtolower
. strtoupper
. strtr
. substr_compare
. substr_count
. substr_replace
. substr
. trim
. ucfirst
. ucwords
. vfprintf
. vprintf
. vsprintf
. wordwrap
|
8.127.30 levenshtein()
Calcule la distance Levenshtein entre deux chaînes
[ Exemples avec levenshtein ] PHP 3 >= 3.0.17, PHP 4 >= 4.0.1, PHP 5
int
levenshtein (
string
str1
,
string
str2
,
int
cost_ins
,
int
cost_rep
,
int
cost_del
)
levenshtein
calcule 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.
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.
| 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éfinission 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";
}
?>
|
Voir aussi
soundex
,
similar_text
et
metaphone
.
|
