[PHP 5.0] Trouver l'occurence la plus proche dans un tableau

[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 :

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 :

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 :

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 :

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

[stealth35]

Envoyé par Benjamin Delespierre

Pourquoi avoir viré cette sécurité ?

Code :

on la déjà avec $approx

[Benjamin Delespierre]

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

Code :

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 :

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]

Envoyé par Benjamin Delespierre

Donc voici une version un poil mieux:

Code :

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 :

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 :

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