[PostgreSQL] identification de chaines ressemblantes

J’ai un problème qui me paraît pas si compliqué mais dont je n’arrive pas à me dépétrer. Comme il est assez intéressant et susceptible d'être utile à d'autres, je vous le soumets :

J’ai deux tables (j’utilise PostgreSQL) :

CREATE TABLE a
(
id_alphanum varchar(70) NOT NULL,
CONSTRAINT pk_a PRIMARY KEY (id_alphanum)
) ;

CREATE TABLE b
(
id_num varchar(30) NOT NULL,
id_alphanum(70),
CONSTRAINT pk_b PRIMARY KEY (id_num)
) ;

Les identifiants alphanumériques sont des descripteurs de lieux, par exemple ‘ruederivoli’.
Comme les concepteurs de la table a et de la table b ne sont pas les mêmes, les id_alphanum ne coïncident pas alors qu’ils décrivent les mêmes objets. Par exemple, ‘rue de Rivoli’ (avec espace, lettres capitales et article) vs. ‘ruerivoli’ (minimaliste).

Mon problème est d’identifier, en vue d’une mise à jour, les id_alphanum de la table b avec ceux de la table a. J’ai déjà écrit une fonction distance_mots(varchar,varchar) qui me retourne la distance entre deux mots : zéro si ce sont les mêmes mots et +1 à chaque opération ajout de caractère/suppression (c’est la distance de Levenshtein pour ceux que ça intéresse).

Je cherche à produire une requête qui m’affiche tous les a.id_alphanum avec en regard le b.id_alphanum le plus proche.
Je m’empatouille avec les GROUP BY, les MIN etc, mais je n'arrive pas à ce résultat. Si vous avez une idée de génie, je suis preneur.

Merci à la communauté


Sakalam

Les différences sont uniquement des espaces en plus ? Ou tu as d'autres types de différences ?

edit : j'ai relu ton message que j'avais lu très vite. Si tu as déjà ta fonction de "rapprochement" il faut que tu fasse une jointure entre les deux tables. La condition de jointure pourrait être fonction de la distance de levenstein maxi de tes deux noms.

exemple :

Code:

---

1 2 3 4 5

select a.id_alphanum, b.id_alphanum from a inner join b on distance_mots(a.id_alphanum, b.id_alphanum ) < 2

---

Cette requête retournera les id_alphanum de a qui ont dans b une distance inférieure a 2.

Les différences peuvent être n'importe quoi : des articles rajoutés (par exemple 'place concorde' doit concorder avec 'place de la concorde'), des majuscules/minuscules, des lettres accentuées ou pas.

Mais les différences sont relativement "bien" gérées par la fonction que j'ai écrite

distance_mots('placeconcorde','Place de la Concorde') retourne 9
distance_mots('placeconcorde','Place de la Madeleine') retourne 15

Mais il faut que je mette ensemble cette fonction avec des MIN etc. pour mettre en face de chacun des id_alphanum de la table a, l'id_alphanum de la table b le plus proche.

edit : Merci ! moi-même j'ai répondu avant ton edit (on n'en sort pas!). Ta méthode marche (en ramant un poil), mais je me demandais s'il n'y avait pas un moyen d'obtenir le minimum plutôt que ceux "assez proche" (cad distance<2 comme tu le suggères). En tous cas, j'ai une bonne base.

S.

voilà :

Code:

---

1 2 3 4 5 6

SELECT a.id_alphanum, b.id_alphanum FROM a INNER JOIN b ON distance_mots(a.id_alphanum,b.id_alphanum) = ( SELECT MIN(distance_mots(a.id_alphanum,b2.id_alphanum)) FROM b b2

---

edit : Attention cependant car :
- la distance de levenshtein peut rapprocher des choses que tu ne rapprocherais "logiquement" pas d'après les exemples que tu m'a montrés
- tu pourras avoir de multiples lignes de la table b rapprochées d'une seule ligne de la table a

Ceci doit te faciliter le travail pour la plupart des cas mais une grosse relecture doit être faite. Ou mieux analyser ton problème pour avoir des résultats automatiques plus fiables.

D'ailleurs pour compléter et avoir une approche qui colle plus à ta problématique, je viens de penser que seuls les noms propres doivent être utilisés pour rapprocher tes lieux grâce à la distance de Levenshtein.

Le mauvais exemple :

Code:

---

1 2	distance_mots("champsdemars", "champselysees") > 6

---

Code:

---

1 2	distance_mots("avenuedeschampselysees", "champselysees") > 9

---

Ici on voit de suite le problème que tu peux rencontrer.

Je te suggère donc de passer tes lieux à travers une fonction qui enlève tout ce qui relève des appelations de voie (place, avenue, rue, ...) ainsi que des articles (de, la, les, ...) avant de calculer la distance de Levenshtein.


Ca donnerait :

Code:

---

1 2	distance_mots("mars", "champselysees") > 11

---

Code:

---

1 2	distance_mots("champselysees", "champselysees") > 0

---

Tu me diras que les articles, s'ils sont collés aux noms du fait du manque d'espaces, seront impossible à sortir avec une fonction. Peut être ne retirer que les appellations de voierie.

A méditer...

Merci pour tes conseils.

Avec les données dont nous disposons, la distance de Levenshtein devrait suffire, mais effectivement pour des cas plus élaborés, je pense raffiner la fonction écrite.
J'ai pris bonne note que ta requête pouvait retourner plusieurs associations : toutes celles dont le calcul donne le minimum.

Merci pour ton aide

S.

Je te conseille tout de même de supprimer les appellations de voierie c'est très simple à réaliser (du replace en masse) et ça te donnera de suite de bien meilleurs résultats.

Bonne chance

Un collègue m'a suggéré quelque chose d'assez simple et efficace :

Code:

---

1 2 3 4 5

SELECT DISTINCT ON (a2) a.id_num AS a1, a.id_alphanum AS a2, b.id_alphanum AS b1,distance_mots(a.id_alphanum,b.id_alphanum) AS d FROM a,b ORDER BY a2,d ASC

---

On devrait toujours avoir un statisticien sous la main !

S.