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...

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).

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.

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

 
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...

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

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

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

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?

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

Trop fort la calculette en ligne.

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.

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"

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

trop naïf.

cad ?

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

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 :-).

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

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.

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.