Reconnaissance approximative de mots - Page 1

Je voudrais faire une fonction qui servirait à reconnaitre des mots à peu près identiques. Par "à peu près", j'entend quelques lettres en plus ou en moins (singulier / pluriel, masculin / féminin par exemple), éventuellement des inversions de lettres (faute de frappe par exemple), des lettres remplacées ("e" au lieu de "é" ou "è" par exemple).

Pour ça, il faudrait une fonction qui à partir d'un mot génere "quelque chose", je sais pas encore quoi : soit une sorte de hash, soit une autre chaine, peu importe (c'est justement le but de ce topic), de façon à ce que deux mots proches une fois passés sous cette fonction donnent le même résultat, ou bien des résultats qu'on puisse associer facilement.

Par exemple, prenons quelques couples de mots "à peu près identiques" : balle/balles, étiré/étirer, attentif/attentive, etc... Il faudrait que la fonction ressorte pour "balle" et "balles" le même résultat, ou bien deux résultats qui nous permettront facilement de dire que "balle" et "balles" sont à peu près identiques. Idem avec les autres couples.

J'ai quelques idées en tête mais aucune ne me semble vraiment performante, et je ne suis même pas sûr de la meilleure forme pour le résultat de la fonction, celui sur lequel les comparaisons seront faites.

En esperant que la question soit compréhensible (ce dont je doute, j'ai l'impression de ne pas avoir été très clair ^^), y a-t-il des algorithmes connus pour ce genre de choses, ou bien l'un d'entre vous a-t-il en tête une solution efficace ?

Pour comparer 2 mots, tu peux parcourir les mots lettre par lettre et comparer:
* Si les lettres sont identiques, c'est bon, prochain caractère.
* Si un mot contient 12 et l'autre 21, compte une inversion, avance de 2 caractères.
* Si un mot contient 123 et l'autre 231, compte 2 inversions, avance de 3 caractères.
* Si un mot contient 123 et l'autre 312, compte 2 inversions, avance de 3 caractères.
* Si un mot contient 123 et l'autre 321, compte une inversion, avance de 3 caractères.
* Si un mot contient la lettre d'avant et pas l'autre, compte un dédoublement, avance dans le mot contenant le dédoublement seulement.
* Si un mot contient 12 et l'autre 2 seulement, compte une insertion, avance de 2 et 1 caractère respectivement.
* Compte une lettre différente et passe au prochain caractère.
(Cet algorithme n'est pas parfait, évidemment, il y a sans doûte de la marge pour faire mieux.) Dans le cas le plus simple, inversion==dédoublement==insertion==lettre différente=:erreur. Tu peux ensuite attribuer des poids aux erreurs.

Maintenant, si tu veux en faire une forme canonique à des fins de hachage, ça devient déjà plus compliqué.

Vertyos :
Pour ça, il faudrait une fonction qui à partir d'un mot génere "quelque chose", je sais pas encore quoi : soit une sorte de hash, soit une autre chaine, peu importe

Le but est de savoir si un mot donné est ou non présent dans un dictionnaire. Le dictionnaire est énorme, et en MySQL, donc bien sûr hors de question de s'amuser à extraire les mots un par un pour les tester : c'est pour ça qu'il faut une valeur à rechercher, et non pas faire des comparaisons longues comme celle que tu as proposé (qui marcherait surement, mais qui prendrait un temps fou).

< Cathode > le dico est dans la base déjà
< Cathode > l'extraire pr le lire intégralement... voilà quoi
< nitro > je vois pas trop comment tu peux faire autrement
< Cathode > faudrait une fonction qui renvoie un hash
< Cathode > qui diffère "un tout petit peu"
< Cathode > si la chaine diffère "un tout petit peu"
< nitro > ça s'appelle pas un hash alors
< Cathode > comme ça on peut chercher toutes les entrées entre hash-10 et hash+10 par exemple
< Cathode > ué bon on s'en fout du terme exact j'y connais rien moi

A priori, ceux avec qui j'en ai parlé sur IRC seraient tous pour une sorte de clé numerique generée en fonction du mot, reste à retrouver une fonction donc la clé ne diffère pas beaucoup entre deux mots qui ont une inversion de lettre, ou une lettre en plus/moins, etc...

hmmm. franchement, je vois la solution pas tres loin, mais tres facile a atteindre
peut etre en faisant des XOR bourrins ds l'algo de trasformation

Si ton dictionnaire est trié par ordre alphabétique, ces comparaisons ne sont pas aussi longues que ça à faire, surtout si tu élimines au bout de 2 ou 3 erreurs.

Mouais bon ok merci mais c'est pas ce que je cherche.
SELECT * FROM `dico`... "pas si long à faire que ça", bah je sais pas ce qu'il te faut...

oops, je voulais dire, *pas tres facile*

v3R7y0S le 1337 il utilise des termes comme h4sH juste opur se la peter

franchement je vois mal comment y arriver sachant qu'il peut y avoir un nombre indetermine de chaines proches les unes des autres, tu as pense a faire un graphe ?

C'est pas pr me la peter golio, j'utilisais "hash" pour désigner une valeur generée qui devrait permettre de rechercher un élement parmis un gros ensemble... Bon alors c'est pas tout à fait exact mais c'est quand même proche...

Heu non pas pensé graphe, tu peux préciser ? Sinon l'idée qu'à peu près tout le monde a, c'est de faire effectivement un hash de plusieurs façons différente, et en faire une sorte de moyenne.

(ma 2e phrase etait evidemment de l'humour, tout le monde l'aura remarque)

le probleme du hash c'est qu'il est pas cense generer des valeurs qui te diront si un mot est proche d'un autre :\

Pour le graphe, ca peut faire lourd, mais ca permettrait de savoir *directement* tous les mots proches d'un noeud a une lettre pres, et ainsi de suite si tu reussis a associer tous les noeuds selon leur rapprochement. explication de merde spotted
Tu me suis ?

liquid
: (ma 2e phrase etait evidemment de l'humour, tout le monde l'aura remarque)

Hmm nan j'avais pas vu le smiley

[cite]le probleme du hash c'est qu'il est pas cense generer des valeurs qui te diront si un mot est proche d'un autre :[/cite]
Heu ouais c'est précisement pour ça que c'est pas un hash, mais un truc qui s'en approche (ayant pour principale différence de servir à déterminer si le mot est proche d'un autre ^^)

Pour le graphe, ca peut faire lourd, mais ca permettrait de savoir *directement* tous les mots proches d'un noeud a une lettre pres, et ainsi de suite si tu reussis a associer tous les noeuds selon leur rapprochement. explication de merde spotted
Tu me suis ?

Oula oui mais ça m'a l'air vraiment bourrin pour le coup

c la solution la plus efficace, mais ca depend si tu es limite en vitesse/memoire parce que la generation du graphe (vide) peut ramer

Pour répondre à Kevin à propos du dictionnaire trié lexicographiquement, si une petite différence est justement dans les premières lettres ça fout tout par terre.

Et liquid, le concept de ta 2è phrase était ©

meuh

une fonction de hashage n'est pas inappropriée. Si cette fonction illustre le fait que deux mots sont proches par le fait que leur hach est proche, il suffira de se donner une "marge" de tolérance de valeur de hachage.

une idée comme ca : remplacer la chaîne de caractère l1,l2,l3,l4,...,ln par
l₁-l₂ , l₂-l₃ , l₃-l₄ ,... , l_n-1-l_n , l_n-l₁

et tu applique la méthode de Kevin, mais tu n'a plus a t'occuper des interversions simples.
mais en y regardant de plus pres, ca apporte d'autres pb...

nan mais de tte façon *une* valeur de hash ne conviendra jamais bien à ce genre de pbs, sauf si tu acceptes un taux d'erreur non nul ou si tu acceptes d'avoir à l'arrivée une portion non négligeable de l'ensemble des mots de départ... (distance à n dimensions, comment veux tu hasher une boule tridimensionnelle sans séparer les 3 composantes ?)

ça doit être assez délicat comme pb, même si tu te contentes de regarder par exemple la suppression d'une lettre (dans un sens ou dans l'autre) et que tu regardes la clôture d'ordre n (par exemple pour n=2, acceprtr vs accepter)

Il doit y avoir des heuristiques qui simplifient énormément, genre si aucun mot ne possèdait 2 fois la même lettre (ou version plus light, un mot possède un ensemble de lettres qui le caractérise assez précisément -- malheureusement, c moyennement vrai en français)

pas bete en effet d'utiliser des heuristiaues

Tu peux utiliser la "distance" entre deux chaines de caractères, c'est à dire le nombre minimal d'opérations élémentaires pour transformer la chaine A en la chaine B. (par opération élémentaire j'entend ajout/remplacement/deletion d'une lettre)

cherche à "string distance" par exemple, ou "string proximity"
http://acm.uva.es/p/v5/526.html

ou aussi à "string edit distance"
http://www.pnylab.com/pny/papers/sed/main.html

Ça souffre du même problème que mon algorithme.

En français : http://talana.linguist.jussieu.fr/taln99/ps/A39/A39.pdf (partie modeles de corrections d'erreurs)


(Kevin : je ne sais pas je n'ai pas regardé en détail)

Pas besoin de regarder en détail. Toutes ces distances répondent au même problème que mon algorithme "maison": ayant en entrée 2 chaînes A et B, connaître leur grade de ressemblance. Cela implique mesurer la distance du mot entré avec chaque mot du dictionnaire, et il ne veut/peut pas le faire.

Oui, la difficulté est d'appliquer la transformation sur chaque mot au moment de l'enregistrement, de façon à ne plus avoir qu'une recherche à faire : les mots enregistrés ne pourront pas être extraits à nouveau pour une comparaison évoluée (lettre par lettre ou autre).

oups g lu trop vite

Ça veut dire quoi pour toi "énorme" ? Combien de mots environ ?

Je sais pas exactement, mais je voudrais faire un truc qui ne faiblisse pas si le nombre de mots devient trop important. Si tu prends yAronet comme exemple, ça dépasse les 200000 mots.

oki.
(au passage si ça interesse quelqu'un, je dois avoir qq part un dico de ~390000 mots (FR) : il me semble que c le dico officiel du scrable, ou qq chose comme ça.)

Vertyos > L'algorithme soundex (implémenté pour la langue française) conviendrait peut-être à ce que tu veux faire

Soundex est quand-même très vague...

Pollux
: nan mais de tte façon *une* valeur de hash ne conviendra jamais bien à ce genre de pbs, sauf si tu acceptes un taux d'erreur non nul ou si tu acceptes d'avoir à l'arrivée une portion non négligeable de l'ensemble des mots de départ... (distance à n dimensions, comment veux tu hasher une boule tridimensionnelle sans séparer les 3 composantes ?)

toutafé. Et à mon avis, il est plus dur de trouver une fonction qui donne la même valeur pour deux mots proches, plutôt qu'une fonction qui donne deux valeurs aussi proches que les deux mots.
Et a propos des dimensions, il faut effectivement les garder. c'est d'ailleurs ce que j'ai "essayé" de faire.

ça doit être assez délicat comme pb, même si tu te contentes de regarder par exemple la suppression d'une lettre (dans un sens ou dans l'autre) et que tu regardes la clôture d'ordre n (par exemple pour n=2, acceprtr vs accepter)

Il doit y avoir des heuristiques qui simplifient énormément, genre si aucun mot ne possèdait 2 fois la même lettre (ou version plus light, un mot possède un ensemble de lettres qui le caractérise assez précisément -- malheureusement, c moyennement vrai en français)

c sur, c vraiment pas simple comme pb.

mais question, Vertyos : ces valeurs ("hash"), elles seront générées à la volée (lors de la comparaison), ou stockée ds ta base ?

faudrait que je demande à mes profs en fait, ce sont des info-matheux, ils doivent avoir qq references utiles.

hibOu
: toutafé. Et à mon avis, il est plus dur de trouver une fonction qui donne la même valeur pour deux mots proches, plutôt qu'une fonction qui donne deux valeurs aussi proches que les deux mots.

Euh, c'est même pas que ce serait dur, c que ça serait mathématiquement impossible (tu as la transitivité pour les hash : si H(x)=H(y)=H(z), alors H(x)=H(z) ; alors que x proche y proche z =/> x proche z)

mais question, Vertyos : ces valeurs ("hash"), elles seront générées à la volée (lors de la comparaison), ou stockée ds ta base ?

Plutôt stockées dans la base je pense...