Algo de levenshtein: creation de groupe

Bonjour à tous,

voila, je programme en java (mais pas grave ca :D ) et je suis confronté à un GROS probleme:

J'ai un tableau de données (une suite de mots). Je souhaite mettre au point des groupes de mots proches orthographiquement.

Exemple:
Bonjour
Bonjor
Bonjoure


J'utilise pour ca la distance de livenshtein pour savoir si un mot est proche de l'autre. Je mets dans le meme groupe des mots dont la distance =1.

Masi mon algo ne focntionne pas crrectement car dans l'exemple, j'obtiens plusieurs groupes alors que ca devrait etre le meme.
Ainsi:
d(bonjour,bonjor) = 1
d(bonjour,bonjoure) = 1
d(bonjor,bonjoure) = 2

donc je dis "meme groupe" car meme si d(bonjor,bonjoure) =2, on peut passer de l'in à l'autre via un intermediare dont la distance = 1
d(bonjor,bonjour) = 1 --> d(bonjour,bonjoure) = 1 et donc
bonjor,bonjoure appartienne au meme groupe


Comment puis-je faire pour grouper des mots? d'avance merci

Citation:

---

Envoyé par Terminator

Comment puis-je faire pour grouper des mots? d'avance merci

---

Tu peux modifier ta fonction de distance pour permettre 2 ajouts/suppressions/echange avec un coût de 1 unité.

Ou plus simplement tu n'a qu'a diviser le résultat de ton calcul par 2 et arrondir. :roll:

Merci pour le reponse,

oui et non ... ou plutot non :D

Au fait, je veux mettre dans le meme groupe tous les mots dont on piusse (avec ou sans intermediaire) arriver avec une distance de 1 ou plus (si intermediaire)
Ainsi, si il y a 4 intermediaires, on peut accepter que les 2 mots soient dans meme groupe si la distance d'intermediaire à intermediaire = 1

Je sais, c compliqué à expliquer (et donc à me lire), mais je peux donner un exemple si vous souhaitez.

D'avance merci

Citation:

---

Envoyé par Terminator

Je sais, c compliqué à expliquer (et donc à me lire), mais je peux donner un exemple si vous souhaitez.

---

Non, c'est bon, j'ai capté. En fait tu veux trouver le plus court chemin dans un graphe, avec comme mesure de distance le Max() des valeurs des arcs.

Bref de la theorie des graphes... Un sujet que je vais laisser aux experts du forum. :aie:

Citation:

---

Envoyé par Terminator

Merci pour le reponse,

oui et non ... ou plutot non :D

Au fait, je veux mettre dans le meme groupe tous les mots dont on piusse (avec ou sans intermediaire) arriver avec une distance de 1 ou plus (si intermediaire)
Ainsi, si il y a 4 intermediaires, on peut accepter que les 2 mots soient dans meme groupe si la distance d'intermediaire à intermediaire = 1

Je sais, c compliqué à expliquer (et donc à me lire), mais je peux donner un exemple si vous souhaitez.

D'avance merci

---

J'espere que tu n'as pas un dictionnaire trop complet, sinon tout va se retrouver dans la meme classe.

Un algo possible:

Admettons que tu as deja classe une serie de mots en classe et que tu veilles voir l'effet qu'a ajouter un mot (au debut, tu as simplement un ensemble vide de classe).

Pour chaque classe, tu compares le mot a ajouter avec les mots de la classe. Des qu'il y en a un pour lequel la distance est 1, tu sais que tu doit ajouter le mot a la classe.

Si apres avoir parcouru toutes les classes, il faut ajouter le mot a plusieurs classes, ca veut dire qu'il faut fusionner ces classes.

S'il ne faut ajouter le mot a aucune classe, il forme une classe a lui tout seul.

Dans le pire cas, tu as N*(N-1)/2 comparaisons. Il est facile de voir qu'on ne peut pas faire mieux (si on ne fait pas N*(N-1)/2 comparaisons, il y a deux mots qu'on n'a pas compare, on peut construire le cas ou c'est justement les deux seuls mots qui avaient a faire partie de la meme classe) si on se limite a des comparaisons 2 a 2.

non non, ce n'ai pas une histoire de graphe!!

Jean-Marc.Bourguet: c'est +/- ca :D (mais comme j'ai pas tout compris à 100%, je peux pas dire que c'est excactement ca :( )

Pour faire plus simple, voici un exemple concret:

Liste de mots:

Code:

---

[Bonjour, nous, bonjoure, aventure, bonjur]

---

A ce jour, je fonctionne comme suit:
Je donne un numero(etiquette) à chaque:

Code:

---

1 2 3

[Bonjour, nous, bonjoure, aventure, bonjur] reprectivement [0,1,2,3,4]

---

Ensuite, je parcours un à un et je regarde la distance:
pour Bonjour, ca donne en distance
[0,x,1,x,1]
(lire: entre "bonjour" et "bonjour" la distance est de 0, le x signifie different de 0 ou 1)

Je crée en parallele un liste
[liste0,liste1,liste2, liste3, liste4]
chaque liste contient par defaut l'etiquette initiale

Code:

---

[{0},{1},{2},{3},{4}]

---

Je mets en plus dans les liste les etiquettes où la distance est =1.

Donc, une fois le premier element analysé, on aura

Code:

---

[{0,2,4},{1},{2},{3},{4}]

---

On passe alors au deuxieme elmeent ="nous" que nous comparons à ses successeurs (et jamais à ces precedents, pour gagner du tps)
ensuite au 3me, 4eme,...

A la fin, les listes sont:

Code:

---

[{0,2,4},{1},{2},{3},{4}]

---

De cette liste nous pouvons dire:

Code:

---

1 2 3

groupe 1 = Bonjour = bonjoure= bonjur groupe 2 =nous groupe 3 =aventure

---

Pour l'instant, j'ai aps encore implementé, c'est que la logique qui a été faite, j'aimerais savoir si cela vous semble bons?
Mon dico est assez grand (4millions de records dont de nombreux redondants)
En effet, je risque d'avoir des soucis de creations de groupes (surtout si les mots sont petits), mais ce n'est pas tres tres grave.

Pour tout dire, mon but premier est de corriger des encodages qui ont été fait à la main, certains mots sont donc tres proches
Exemple: alexandre et alecandre lorsque quelqu'un entre des noms
Je souhaite donc creer des groupes avec un ensemble de noms +/- identique et reperer le noms exacte pour constituer une liste de noms exactes.

A partir de cette liste, je remplacerai les noms mal orthographiés par les valeurs exactes.

D'avance merci pour votre lecture

Hio,

Je crois qu'il vaudrait mieux aller chercher du côté des soundex, qui gèrent la phonétique du mot, sinon tu vas devoir mettre de très nombreuses exception à ton calcul de distance, au point que ça ne voudra plus dire grand chose d'autre que "c'est la différence que j'ai décidé d'utiliser", avec un rapport assez lointain avec l'algorithme d'origine. :)