A la chasse aux (faux) doublons

[renaud26]

Bonjour à toutes et tous,

Suite à une refonte de 3 BDD en une, je me trouve avec le problème suivant, dans une table "produits".

nom
voiture 4 roues
Voiture quatre roues

Qui sont des faux doublons. Que je voudrais pouvoir détecter.
J'ai lu le passionnant article sur le sujet : http://sqlpro.developpez.com/cours/doublons/ et tenté de m'en inspirer, sans succès. Les requêtes plantent ou ne retournent rien.

Pourtant, je pensais que :

Code :

1
2
3
4
5
6
7
8
 
SELECT *
FROM   produits T1
WHERE  EXISTS
   (SELECT *
    FROM  produits T2
    WHERE  T1.id <> T2.id
      AND  T1.nom LIKE '%T2.nom%')

pourrait retourner quelque chose...mais nada.
Je voudrais une requête qui ratisse "large" et tant pis si elle me retourne des doublons qui n'en sont pas.
Sans doute faudrait-il utiliser des expressions rationnelles, mais je n'y comprends quant à leur utilisation dans mySQL.
Pensez-vous que cela soit possible ?

[Benjamin Delespierre]

L'article m'a l'air très intéressant, j'y jetterai un coup d'oeil à l'occasion.

Une solution (beaucoup) moins propre pour la détection des doublons pourrait être un algorithme 0(n*m) sur l'ensemble des produits (assez lourd donc) qui calculerait (par exemple) la distance Levenshtein et afficherai un rendu trié par distance et donc serait capable de "repérer" les faux doublons. Un tel script de sanitize n'est sûrement pas la solution la plus élégante mais c'est la seule chose que j'ai imaginé compte tenu de ma faible expérience...

Par exemple, la distance entre "voiture 4 roues" et "Voiture quatre roues" est de 7 (6 en minuscule):

Code :

1
2
3
4
5
6
 
$a = 'voiture 4 roues';
$b = 'Voiture quatre roues';
 
var_dump(levenshtein($a, $b));
var_dump(levenshtein(strtolower($a),strtolower($b)));

En d'autres termes, cet algorithme permettra de reconnaitre des chaines "proches".

[renaud26]

Bonjour et merci de ta réponse.
Ma foi...je vais tenter le coup, la table ne comprend que 500 lignes.
Et puis ce n'est à faire qu'une fois...
Ensuite, je reviens pour donner le résultat.

[Benjamin Delespierre]

Je viens de voir d'autres fonction qui peuvent t'intéresser:
- similar_text calcule les caractères similaires entre deux chaines
- soundex calcule une clé identique pour deux chaines ayant les mêmes phonèmes ("voiture" et "voature" par exemple - ne fonctionne pas avec des chiffres)

A voir si ça peut servir.

[renaud26]

Oui, je viens de lire la doc à ce propos. Mais il semblerait que ces fonctions soient moins précises que levenshtein.
Par contre, je me trouve comme un âne : comment je fais, au niveau de ma requête, ou de son traitement, pour déterminer qu'il y a suspicion de doublon ?

[Benjamin Delespierre]

Tu le fais pas, c'est ça le hic. Il faut que tu réccupères toutes tes dénominations produits et que tu fasse tourner l'algo dessus.

Voici un skeleton si ça peut t'aider:

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
<?php
 
define("MAX_STR_DIFF", 7);
define("IGNORE_FROM_LEV", 7);
 
$pdo = new PDO("mysql:dbname=testbase;host=127.0.0.1", "root", "");
 
$query = "SELECT `prod_name` AS `name` FROM `ma_db`.`products`";
if ($stmt = $pdo->query($query)) {
 
  $names = array_map(function ($item) { return $item['name']; }, $stmt->fetchAll(PDO::FETCH_ASSOC));
  $res = array();
 
  foreach ($names as $a) {
    foreach ($names as $b) {
		if (abs(strlen($a) - strlen($b)) > MAX_STR_DIFF) continue;
		$lev = levenshtein(strtolower($a), strtolower($b));
		if (!isset($res[$lev][]) $res[$lev] = array();
		$res[$lev][] = array($a, $b);
	}
  }
 
  echo "<table>";
  echo "<thead><tr><th>Lev</th><th>Left</th><th>Right</th>";
 
  foreach ($res as $lev => $strings) {
 
	if ($lev > IGNORE_FROM_LEV) break;
 
	siwtch ($lev) {
		case 0: $bgcolor = 'red'; break;
		case ($lev > 0 && $lev <= 5): $bgcolor = 'orange'; break;
		case ($lev > 5 && $lev <= 10): $bgcolor = 'blue'; break;
		default: $bgcolor = 'green'; break;
	}
 
	foreach ($strings as $pieces)
	{
		list($left, $right) = $pieces;
		echo "<tr><td style=\"background-color: $bgcolor;\">$lev</td><td>$left</td><td>$right</td></tr>";
	}
  }
 
  echo "</table>";
 
}
else {
  die("Query error";
}

Pas de commentaire, c'est fait à l'arrache pour aider. Je ne l'ai même pas fait tourner.
Un mot d'explication, le principe est le suivant:
- on récupère toutes les noms produits
- pour chaque nom, on le vérifie en regard de tous les autres
- si les deux chaines à comparer sont de taille trop différente (défini par le paramètre MAX_STR_DIFF) on ignore et on considère donc qu'il ne s'agit pas d'un doublon
- on récupère la distance Levenshtein qu'on place dans l'indice correspondant du tableau de résultats
- ensuite on passe sur le tableau de résultat (ordonné par distance de Levenshtein) et pour chaque distance on affiche toutes les chaines droite et gauche correspondantes
- pour eviter que le tableau produit ne soit trop long, on spécifie un paramètre IGNORE_FROM_LEV qui permet d'ignorer les entrées dont la distance est supérieure à la valeur du paramètre.

A toi de me dire si ça te va. Si tu mets de valeurs trop grandes dans les deux paramètres, tu vas te retrouver avec un tableau de 250000 pour un jeu de 500 produits: prudence avec la pondération.

[renaud26]

Merci d'avoir pris le temps de coder cet exemple.
Malheureusement, il ne fonctionne pas.
Si je mets les params à 4, tous les produits sont retournés.
Si je mets 5, j'ai un "out of memory".

Je vais gratter encore du côté de la requête proprement dite.
Si quelqu'un a une autre idée, je suis toujours preneur...