Bonjour,

j'ai un petit problème de "doublon" à résoudre et je sais pas trop comment m'y prendre :
En gros je vais avoir d'un côté en base de donnée une liste de Nom Prenom et de l'autre je vais avoir une entrée texte avec des Nom et Prénom et je dois arriver à dire si ces entrées existent déjà en base et le test doit pouvoir détecter des choses comme :

Bernard Dupont / Dupont Bernard
Bernard Dupont / Dupond B
Bernard Dupont / M. Dupont Bernard

ect ect... Existe t'il des projets déjà existant sur le sujet ? J'ai du mal à trouver les bons mot clefs sur google et je n'ai rien trouvé de concluant pour le moment.

Le problème à l'air assez classique mais au final si on veut faire un truc solide c'est plus complexe que ça en à l'air

Ca ne me parait pas completement evident de faire un truc comme ca. Il faut aussi faire attention au faux positifs. Il y a certainement beaucoup de bernard dupont different.

exactement, genre pouvoir gérer des frères ou conjoint (même nom de famille)

et "M. Dupont Bernard" ca pourrait etre un mec qui utilise son deuxieme prenom.

Dans un cas comme "Bernard Dupont / Dupont Bernard", tu as des problemes de prenom qui sont aussi des noms. J'ai un ami qui s'appelle Pierre Mathieu et qui a rencontrer un mec qui s'appelle Mathieu Pierre.

Dans un cas comme "Bernard Dupont / Dupond B", tu as carrement changer l'orthographe alors fusionner automatiquement ca m'a l'air casse cou.

Dans theadvisor [1], on utilise la distance de Levenshtein[2] pour decider si les titres de deux articles sont similaires ou non. On utilise d'abors un filtre a base de hashage mot par mot pour detecter des candidats. Et on confirme avec les dates de publications. Bref, on utilise pas un critere unique.

[1] http://theadvisor.osu.edu
[2] http://en.wikipedia.org/wiki/Levenshtein_distance

Dans un cas comme "Bernard Dupont / Dupond B", tu as carrement changer l'orthographe alors fusionner automatiquement ca m'a l'air casse cou.

Non la c'est moi qui ai tapé comme un sale mais du coup >la distance de Levenshtein peut être sympa dans le cas d'une >faute de frappe...

Dans le pire des cas on peut imaginer qu'on demande à l'utilisateur de confirmer parmis une liste (restreinte à quelques choix pertinents) de candidat si son entrée ne match pas avec la base de donnée.

L'inversion semble être le seul cas relativement simple. Le cas "classique" du "Bernard Dupont / Dupond B" semble un peu plus galère...

Mais ton lien vers Wikipedia et ton commentaire m'ont fait regarder le projet sous un autre angle et je vais sûrement orienter mes recherches sur d'autres points de similarité que les auteurs (genre le titre) et voir si des algorithmes comme celui que tu m'a présenté s'en sortent bien

par curiosite, c'est quoi comme base de donnee que tu essaye de nettoyer?

Si tu veux faire une recherche sur la base avec la distance de Damerau-leveinstein, l'algo présenté par Wikipédia tel quel est très mauvais.
Il faut utiliser un trie et adapter l'algo pour avoir des perfs correctes. Grâce à ce trie tu pourra faire une fonction:
words search(baseword, maxdist)

qui va te renvoyer les id des mots(nom et prenons confondus) dont la distance est inférieure à maxdist, triés de la plus petite à la plus grande distance.

Ensuite tu fais
l1 = search(Nom, maxdist)
l2 = search(Premon, maxdist)

et tu cherches dans l1 et l2 l'id commun tel que la distance soit la plus petite.
Cet algo devrait gérer la plupart des cas.

Si tu veux gérer le cas Dupond B une solution serait d'étendre la distance de Damerau-Leveinstein pour accepter une transformation X****** -> X avec un cout fixe. A tester.

Là je suis surpris, tout le monde a pas ce genre de connaissance. On peut effectivement utiliser un trie ou un automate pour ce genre d'opération.

Tu t'y connais bien en correction orthographique hyru?

@godrik c'est une bdd interne sensé gérer des articles de recherche (via un bibtex), mais il y a des gros soucis de doublon apparemment (notamment à cause des noms/prénoms). mais au final je pense qu'au lieu de chercher des noms/prénoms similaires pour les détecter il vaut mieux se baser sur d'autres critères moins dangereux comme le titre

Sinon j'ai trouvé ce lien la un peu partout, vous en pensez quoi ? http://www.seoblack-inside.com/script-php-calcul-similaire-comparaison-mots/

_skip
J'avais fait un correcteur orthographique en distance Damerau-Leveinstein à base de Patricia Trie.
L'objectif était que ça retourne une liste des corrections possibles à une distance inférieure à un seuil donné, le plus rapidement possible donc en pré-compilant le dico pour avoir le Patricia trie sur un bloc mémoire contigu. J'ai encore le svn du projet d'ailleurs:
https://subversion.assembla.com/svn/text-mining-project/

Je crois que les BTree font encore mieux mais je me suis pas trop renseigné dessus.

dark_drow
L'article que tu as donné est assez bourrin mais devrai bien marcher si tu te sens pas implémenter un trie et que tu ne veut pas gérer les fautes de frappe.

C'est exactement ce qui m'intéresse en fait. Je serai curieux de jeter un oeil à ton code car je pensais à un truc similaire. Et aussi je voudrai considérer certaines transformations comme des "demi erreurs".

Ainsi si on veut corriger "cercle" on aurait

cercle : 0
cerclé : 0.5
cerclu : 1
cercler : 1

En considérant que "e -> é" est pas une faute aussi grave que "e -> u".

Si tu veux voir le code le principal est dans trunk/PatriciaTrie. Le reste c'est les main des exécutables principalement.
L'algo de recherche est dans PatriciaTrieFinder.h, méthode findDistance.
Les demi-erreur devraient être facile à gérer. Il y a un moment dans la fonction une variable replaceCost qui est mise à 0 ou 1. Pour gérer les demi-erreur il faudrait la mettre à 0.5 si c'est le cas, en faisant un traitement plus fin que word[i - 1] == currWord[offset_trie].

Et au fait en relisant le README je vois qu'on parle d'une badAlloc n'y prête pas attention c'était l'executable de référence fourni par le prof qui badAllocait sur des requêtes de grosses distances pas le notre.