PHP
PHP / MySql

Recherche
 
ManuelPHP.com

join
<<<
levenshtein localeconv
>>>

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 .

<< levenshtein >>
join Chaînes de caractères (Strings) localeconv





Google

Services webmasters

Les manuels
 

ManuelPHP.com © 2003-2012 Tigersun - Crédits
Webmaster Site Internet - Télécharger des Logiciels - Programme TV - Entraide Informatique - Agence de Communication
2018-09-20