Discussion :

[Benjamin Delespierre]

Bonjour à tous,

Aujourd'hui, j'ai eu besoin d'un algo pour trouver le mot le plus proche dans une liste. Vu que ça existait pas et que je n'arrivais pas à le faire simplement avec array_map ou array_walk, j'ai codé une fonction que voici:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function array_find_closest ($needle, $haystack, $approx = 3) {
	if (($offset = array_search($needle, $haystack)) !== false)
		return $haystack[$offset];
 
	foreach ($haystack as $item) {
		$lev = levenshtein($needle, $item);
 
		// if needle is completely different
		if ($lev >= strlen($item))
			continue;
 
		// if word is 'too' different
		if ($lev > $approx)
			continue;
 
		$guess[$item] = $lev;
	}
 
	if (empty($guess))
		return false;
 
	asort($guess);
	return key($guess);
};

La fonction retourne false si aucune correspondance n'a été trouvée.

Note: le troisième paramètre vous permet de déterminer la 'distance' maximum acceptable. Il représente le nombre maximum de caractère différents, à ajouter ou à soustraire pour trouver une correspondance.

Attention: cette fonction utilise l'algorithme de levenshtein pour déterminer les correspondances possibles, cet algo est assez lourd et rends la fonction assez gourmande.

Usage:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
$colors = array('orange', 'blue', 'yellow', 'pink', 'black', 'white');
 
var_dump( array_find_closest('blu', $colors) ); // 'blue'
var_dump( array_find_closest('P1nk', $colors) ); // 'pink'
var_dump( array_find_closest('color is black', $colors) ); // false (trop de différences)
 
var_dump( array_find_closest('Bl4cK', $colors) ); // 'black'
var_dump( array_find_closest('Bl4cK', $colors, 2) ); // false (il faut changer 3 caractère pour arriver à 'black' mais 2 seulement sont autorisés)

Voilà, si quelqu'un à des idées pour réduire la complexité ou améliorer en quoi que ce soit, les remarques sont les bienvenues.

[stealth35]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function array_find_closest($needle, $haystack, $approx = 3)
{
    if (in_array($needle, $haystack)) {
        return $needle;
    }
 
    $distances = array();
 
    foreach ($haystack as $word) {
        $distance = levenshtein($needle, $word);
        if ($distance <= $approx) {
            $distances[$word] = $distance;
        }
    }
 
    asort($distances);
 
    return $distances ? key($distances) : false;
}

pas grand chose

[Benjamin Delespierre]

Pourquoi avoir viré cette sécurité ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
		// if needle is completely different
		if ($lev >= strlen($item))
			continue;

[stealth35]

Pourquoi avoir viré cette sécurité ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
		// if needle is completely different
		if ($lev >= strlen($item))
			continue;

on la déjà avec $approx

[Benjamin Delespierre]

Je l'avais mis pour éviter ce cas de figure:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function array_find_closest($needle, $haystack, $approx = 3)
{
    if (in_array($needle, $haystack)) {
        return $needle;
    }
 
    $distances = array();
 
    foreach ($haystack as $word) {
        $distance = levenshtein($needle, $word);
        if ($distance <= $approx) {
            $distances[$word] = $distance;
        }
    }
 
    asort($distances);
 
    return $distances ? key($distances) : false;
}
 
$haystack = array('defghi', 'abc');
$needle = 'ghi';
 
var_dump( array_find_closest($needle, $haystack) ); // 'abc'

[stealth35]

oui bien joué

[Benjamin Delespierre]

Donc voici une version un poil mieux:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function array_find_closest($needle, array $haystack, $approx = 3) {
    if (in_array($needle, $haystack)) {
        return $needle;
    }
 
    $distances = array();
    foreach ($haystack as $word) {
        $distance = levenshtein($needle, $word);
        if ($distance >= strlen($word))
                continue;
        if ($distance <= $approx)
            $distances[$word] = $distance;
    }
 
    asort($distances);
    return $distances ? key($distances) : false;
}

merci à Stealth

[yakotey]

Donc voici une version un poil mieux:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function array_find_closest($needle, array $haystack, $approx = 3) {
    if (in_array($needle, $haystack)) {
        return $needle;
    }
 
    $distances = array();
    foreach ($haystack as $word) {
        $distance = levenshtein($needle, $word);
        if ($distance >= strlen($word))
                continue;
        if ($distance <= $approx)
            $distances[$word] = $distance;
    }
 
    asort($distances);
    return $distances ? key($distances) : false;
}

merci à Stealth

Bjr,

C'est bizarre, mais lorsqu'on rajoute le mot "zombie" à la fin du tableau dictionnaire des mots, et que l'on recherche "zo" ou "zom" on a pas le résultat escompté.

BR

[Benjamin Delespierre]

Ta recherche n'est pas assez proche, le nombre de caractère différents est supérieur à $approx.

Ex:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
$haystack = array(
	'ghoul',
	'orc',
	'goblin',
	'salad-shaped-pork',
	'zombie',
);
 
$needles = array(
	'zo',
	'zom',
	'zomb',
);
 
foreach ($needles as $needle)
	var_dump( array_find_closest($needle, $haystack) );

Résutlats:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
boolean false // 'zo' est différent de zombie de 'zombie' de 4 caractères, donc 1 de trop
string 'zombie' (length=6) // 'zom' est différent de 'zombie' de 3 caractères, ça passe
string 'zombie' (length=6) // etc.

Normalement, cette fonction doit être utilisée pour des recherches ou seuls quelques caractères sont différents par exemple entre "Ferrari" et "ferari".
Donc si tu veux faire une recherche plus 'lâche', tu dois modifier le paramètre $approx