Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
878 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  algo tolérance orthographique

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

algo tolérance orthographique

n°490388
dweis
Posté le 18-08-2003 à 16:27:58  profilanswer
 

J'ai une base de donnée avec 1.000.000 de mots
L'utilisateur doit pouvoir faire des recherches dans parmis ces mots.
Premier problème : fautes d'orthographe, il faut pouvoir reconnaitre un mot s'il est mal orthographié. Bon pour ça, j'ai testé un peu de soundex/phonex ça a l'air de donner un résultat satisfaisant
Mon vrai problème est le suivant : faute de frappe.
Je voudrais donc que si la personne tappe "appatrement", et bien ça trouve "appartement".
Vous me direz il y a bien les fonctions levenshtein et similar_text de php qui sont faites pour ça. Mais le problème c'est qu'elles sont inutilisables puisqu'il faudrait faire 1.000.000 d'appels à ces fonctions pour chaque recherche !
Il faut donc trouver quelque chose qui permette de tout précalculer ou qui soit vraiment simple et je ne vois pas du tout.
Pourtant google (http://www.google.fr/search?q=appatrement&ie=UTF-8&oe=UTF-8&hl=fr&meta) ou allocine (http://www.allocine.fr/recherche/default.html?motcle=appatrement) font ça sans problème alors doit y avoir des algos performants pour ce genre de problème.
 
Donc si vous avez des pistes...

mood
Publicité
Posté le 18-08-2003 à 16:27:58  profilanswer
 

n°490409
os2
Posté le 18-08-2003 à 16:46:59  profilanswer
 

dis où ta pogné ta base de 1 000 000 de mot, ça m'intéresse


---------------
Borland rulez: http://pages.infinit.net/borland
n°490981
rufo
Pas me confondre avec Lycos!
Posté le 19-08-2003 à 10:58:24  profilanswer
 

os2 a écrit :

dis où ta pogné ta base de 1 000 000 de mot, ça m'intéresse


 
la langue française dois avoir aux alentours de 52000 mots je crois...:??: Mais bon, il y a peut-être toutes les conjugaisons des verbes et les accords des mots + les masculins/féminins...
 
Pour ton pb, t'as qu'a rajouter pour chaque un champ "soundex" et un champ "levenshtein" (voire un champ "similar_text" ) et tu index tes mots sur ces derniers champs...(c'est une idée comme ça).

n°491011
Krueger
tout salaire demande dutravail
Posté le 19-08-2003 à 11:13:13  profilanswer
 

[:drapo]
Personnellement je pense à avoir un moyen de calculer une distance entre deux mots, la distance nulle étant l'égalité stricte. Après il peut y avoir différents critères qui accroissent ou non la distance comme la permutation ou le remplacement de lettres. Reste que pour implémenter ça je n'en ai aucune idée. Néanmoins c'est une piste que je propose. :hello:


---------------
"Colère et intolérance sont les ennemis d'une bonne compréhension." Gandhi
n°491018
nraynaud
lol
Posté le 19-08-2003 à 11:14:52  profilanswer
 

tu le fais à l'envers, à partir de la saisie tu génère les mots qui sont à une distance de 1 de la saisie et tu fais le requête pour chaque, puis une distance de 2 puis de 3 ... puis tu t'arrêtes car 3 fautes dans le même mot, il faut pas se foutre de la gueule du monde. plus sérieusement, plus la distance augmente et plus le nombre de mots générés est grand.
 
Le seul truc que je connaisse sur la question (que je ne connais que par hasard) :  
http://cristal.inria.fr/~xleroy/software.html#agrep


---------------
trainoo.com, c'est fini
n°491024
rufo
Pas me confondre avec Lycos!
Posté le 19-08-2003 à 11:17:11  profilanswer
 

Krueger a écrit :

[:drapo]
Personnellement je pense à avoir un moyen de calculer une distance entre deux mots, la distance nulle étant l'égalité stricte. Après il peut y avoir différents critères qui accroissent ou non la distance comme la permutation ou le remplacement de lettres. Reste que pour implémenter ça je n'en ai aucune idée. Néanmoins c'est une piste que je propose. :hello:


 
Je pense pas que sont pb soit de calculer la distance entre 2 mots (php propose déjà qq fcts), mais plutôt que ce calcul se fasse très vite (parce que s'il doit tester 1000000 de mots pour chaque entrée, il est pas rendu). Avec du SQL, ça sera beaucoup plus rapide si les résultats des différentes méthodes de calcul proposées plus haut sont déjà stockés dans la bd. C'est vrai que normalement, tu ne stockes dans une bd que ce qui ne peut être calculé. Mais des fois, pour des questions de performances, je pense qu'on peux déroger à la règle...

n°491033
Krueger
tout salaire demande dutravail
Posté le 19-08-2003 à 11:18:55  profilanswer
 

nraynaud a écrit :

tu le fais à l'envers, à partir de la saisie tu génère les mots qui sont à une distance de 1 de la saisie et tu fais le requête pour chaque, puis une distance de 2 puis de 3 ... puis tu t'arrêtes car 3 fautes dans le même mot, il faut pas se foutre de la gueule du monde. plus sérieusement, plus la distance augmente et plus le nombre de mots générés est grand.
 
Le seul truc que je connaisse sur la question (que je ne connais que par hasard) :  
http://cristal.inria.fr/~xleroy/software.html#agrep


On a au moins un nom d'algorithme et une commande UNIX. :jap:


---------------
"Colère et intolérance sont les ennemis d'une bonne compréhension." Gandhi
n°491035
rufo
Pas me confondre avec Lycos!
Posté le 19-08-2003 à 11:19:22  profilanswer
 

nraynaud a écrit :

tu le fais à l'envers, à partir de la saisie tu génère les mots qui sont à une distance de 1 de la saisie et tu fais le requête pour chaque, puis une distance de 2 puis de 3 ... puis tu t'arrêtes car 3 fautes dans le même mot, il faut pas se foutre de la gueule du monde. plus sérieusement, plus la distance augmente et plus le nombre de mots générés est grand.
 
Le seul truc que je connaisse sur la question (que je ne connais que par hasard) :  
http://cristal.inria.fr/~xleroy/software.html#agrep


 
ce paramètre de la distance max serait effectivement bien pour paramètrer la requête sql ;)

n°491040
nraynaud
lol
Posté le 19-08-2003 à 11:21:46  profilanswer
 

rufo a écrit :


normalement, tu ne stockes dans une bd que ce qui ne peut être calculé. Mais des fois, pour des questions de performances, je pense qu'on peux déroger à la règle...

gni ? le processus de dénormalisation est un des plus important du développement. Car c'est aussi le plus casse-gueule.


---------------
trainoo.com, c'est fini
n°491048
nraynaud
lol
Posté le 19-08-2003 à 11:27:36  profilanswer
 

rufo a écrit :


ce paramètre de la distance max serait effectivement bien pour paramètrer la requête sql ;)

De toute façon ce pb est très vite réglé, s'il va au-delà de 3 je lui paye un paquet de cacahuète, même google avec 15000 PC sous linux fait pas mieux (et encore, il fait plutôt 2).
D'ailleur faudrait calculer le seuil où l'espace généré est suppérieur à 1.000.000 mots (parce qu'après on se la joue dans l'autre sens, minimum de la distance), mais pour des mots de 10 lettres par exemple, il doit pas être très grand.


---------------
trainoo.com, c'est fini
mood
Publicité
Posté le 19-08-2003 à 11:27:36  profilanswer
 

n°491155
chaica
Posté le 19-08-2003 à 14:04:41  profilanswer
 

nraynaud a écrit :

De toute façon ce pb est très vite réglé, s'il va au-delà de 3 je lui paye un paquet de cacahuète, même google avec 15000 PC sous linux fait pas mieux (et encore, il fait plutôt 2).
D'ailleur faudrait calculer le seuil où l'espace généré est suppérieur à 1.000.000 mots (parce qu'après on se la joue dans l'autre sens, minimum de la distance), mais pour des mots de 10 lettres par exemple, il doit pas être très grand.


 
HS : t'as vu où que google tournait avec 15000 pcs, ma dernière source dit 8000. Mais tu dis peut être ça au hasard?

n°491164
nraynaud
lol
Posté le 19-08-2003 à 14:14:08  profilanswer
 

chaica a écrit :


HS : t'as vu où que google tournait avec 15000 pcs, ma dernière source dit 8000. Mais tu dis peut être ça au hasard?

http://linuxfr.org/comments/256344.html


---------------
trainoo.com, c'est fini
n°491242
Krueger
tout salaire demande dutravail
Posté le 19-08-2003 à 15:07:16  profilanswer
 


Trop fort la calculette en ligne. :)


---------------
"Colère et intolérance sont les ennemis d'une bonne compréhension." Gandhi
n°491684
dweis
Posté le 19-08-2003 à 20:47:01  profilanswer
 

nraynaud a écrit :

tu le fais à l'envers, à partir de la saisie tu génère les mots qui sont à une distance de 1 de la saisie et tu fais le requête pour chaque, puis une distance de 2 puis de 3 ... puis tu t'arrêtes car 3 fautes dans le même mot, il faut pas se foutre de la gueule du monde. plus sérieusement, plus la distance augmente et plus le nombre de mots générés est grand.


mouais générer automatiquement toutes les fautes possibles, à mon avis même avec 2 ou 3 fautes ça fait vite qques centaires (voir milliers) de possibilités

n°491698
nraynaud
lol
Posté le 19-08-2003 à 20:55:37  profilanswer
 

dweis a écrit :


mouais générer automatiquement toutes les fautes possibles, à mon avis même avec 2 ou 3 fautes ça fait vite qques centaires (voir milliers) de possibilités

et ? t'es pas responsable de l'orthographe des utilisateurs. Plus j'y pense et plus je me dit qu'une distance de 2 c'est déjà suffisant pour bien des cas.


---------------
trainoo.com, c'est fini
n°491699
dweis
Posté le 19-08-2003 à 20:55:55  profilanswer
 

sinon idée sympas qu'on m'a proposé (mais qui ne marche que pour des inversion de lettres, par pour des insertions ou des oublis) : on prend les lettres du mot et on les classes par ordre alphabétique en supprimant tous les double. il suffit alors de comparer les codes obtenus
ainsi "appartement" donne "aemprt"
et "appatrement" donne également "aemprt"

n°491700
dweis
Posté le 19-08-2003 à 20:56:45  profilanswer
 

nraynaud a écrit :

et ? t'es pas responsable de l'orthographe des utilisateurs. Plus j'y pense et plus je me dit qu'une distance de 2 c'est déjà suffisant pour bien des cas.


en fait ce qui m'intéresse plus c'est de trouver un algo efficace pour ce genre de problème. après le mettre en pratique c'est plus pour le fun ;)

n°491711
nraynaud
lol
Posté le 19-08-2003 à 21:05:29  profilanswer
 

dweis a écrit :

sinon idée sympas qu'on m'a proposé (mais qui ne marche que pour des inversion de lettres, par pour des insertions ou des oublis) : on prend les lettres du mot et on les classes par ordre alphabétique en supprimant tous les double. il suffit alors de comparer les codes obtenus
ainsi "appartement" donne "aemprt"
et "appatrement" donne également "aemprt"

trop naïf.


---------------
trainoo.com, c'est fini
n°491742
dweis
Posté le 19-08-2003 à 21:27:18  profilanswer
 

cad ?

n°491801
MagicBuzz
Posté le 19-08-2003 à 22:06:45  profilanswer
 

-- Edit : effacé, après tests, c'est pas convainquant :D --


Message édité par MagicBuzz le 19-08-2003 à 22:10:59
n°491825
nraynaud
lol
Posté le 19-08-2003 à 22:18:49  profilanswer
 

tu vas laisser de côté toute une classe de fautes courantes donc tu n'auras pas d'efficacité.
 
Par contre, tu peux tester : virer l'ordre (en triant) et les les lettres doublées et ensuite te concentrer sur les ajouts et les ommissions de lettres, tu réduit un peu l'espace de recherche (tu vires le pb le plus facile, les permutations et une toute petite partie des ommissions et insertions : les lettres multiples), sans trop le déformer je pense.
 
En particulier, tu peux raisonnablement penser qu'en français, les pb de consonnes doubles sont les plus courrants :-).


---------------
trainoo.com, c'est fini
n°491849
MagicBuzz
Posté le 19-08-2003 à 22:38:42  profilanswer
 

une idée pour replacer le truc du "aemprt"...
 
change systématiquement :
 
les "en/an" en "en" par exemple
les "s[consonne]" en "s"
les "s[voyelle]" en "z"
les "ss" en "s"
les "un[consonne ou espace]/ein[consonne ou espace]/ain[consonne ou espace]/in[consonne ou espace]" en "un"
les "c[consonne ou u ou espace]" en q
les "c[voyelle sauf u]" en "s"
les "k" en "q"
les "g[voyelle sauf u et o]" en "j"
les "h" en ""
les "ph" en "f"
etc.
 
Faut faire du phonétique quoi...
 
et... ignore systématiquement la dernière lettre, le s, le l, et autres sont très souvent muets en fin de mot.
 
Comme ça, tu vas pouvoir trapper les mots mal orthographiés en plus des inversions de lettres. par contre, tu risque de très vite te retrouver avec des doublons...
 
Avec ce système, si le gars tapes :
 
q, tu retrouve cul, puisque : cu => q et l disparaît
aurtaugraffe => ortografe => aefgort
orthographe => ortografe => aefgort
=> Tu le retrouve dons aussi
 
Par contre, cette faute de frappe "dons" que j'ai laissé volontairement, bah tu la retrouvera pas... c'est donc pas parfait ;)


Message édité par MagicBuzz le 19-08-2003 à 22:43:17
n°492638
nraynaud
lol
Posté le 20-08-2003 à 17:17:43  profilanswer
 

MagicBuzz a écrit :


Faut faire du phonétique quoi...

Le phonétique, il sait faire (soundex et autre conneries), c'est même peu complexe , c'est les fautes de frappes (qui peuvent donner des trucs imprononçables ou changer la pronomciation) son pb actuel.


---------------
trainoo.com, c'est fini
n°492939
MagicBuzz
Posté le 21-08-2003 à 00:37:44  profilanswer
 

Faut combiner les deux.
 
Sinon, soundex, c'est bien, mais à moins que MySQL ait une implémentation en français, sous Oracle c'est de la prononciation anglaise. Donc tu auras des résultats approximatifs.
 
En anglais "no" et "know" se prononcent "pareil". Hors en français, pas du tout. Par contre, "no" et "nos" se prononce pareil en français... Mais pas en anglais.
 
A partir de là, soundex est fortement déconseillé pour une appli non anglophone, à moins qu'il existe une implémentation pour ton pays. T'as pas le choix faut te taper l'algo de phonétique à la main.
 
Et combiné avec l'autre algo, tu trappes facilement les fautes de phonétiques et inversions de lettres. Par contre, evidement, si le gars "glisse" et ajoute une lettre qui n'a rien avoir avec le mot, bah tu détectera rien. A ce moment, il doit exister d'autres algos, mais qui à mon avis sont trop complexes pour être gérés au niveau SQL.

n°492944
the real m​oins moins
Posté le 21-08-2003 à 01:18:16  profilanswer
 

[:blueflag]


---------------
Hey toi, tu veux acheter des minifigurines Lego, non ?
mood
Publicité
Posté le   profilanswer
 


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  algo tolérance orthographique

 

Sujets relatifs
[ALGO] Générateur grille mots croisés[ALGO] TCP/IP Fletcher 16 bit.
algo pour trouver tous les chemins...algo glouton
Question methode c++ (algo)[ASP/Algo] Nombre en Français
[RESOLU][ALGO]Comment fonctionne le tracking par mail ?Algo de Hashage/Signature
changer un entier en double ? ou bien mon algo est mauvais ...helpalgo de graph
Plus de sujets relatifs à : algo tolérance orthographique


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR