Génération de mots similaires
Génération de mots similaires - Algo - Programmation
Marsh Posté le 24-04-2006 à 17:01:52
ça te suffit pas ça : http://dev.mysql.com/doc/refman/5. [...] nsion.html
Marsh Posté le 24-04-2006 à 17:43:05
J'avais mis mysql comme sgbd à titre informatif mais je ne veux pas être dépendant d'un sgbd (de toute manière, je suis en mysql < 4 donc c'est mort). Mon post concerne uniquement l'aspect algorithmie...
Message édité par rufo le 24-04-2006 à 17:43:40
Marsh Posté le 24-04-2006 à 17:55:11
Reply
Marsh Posté le 24-04-2006 à 18:15:18
| nargy a écrit : utilise l'algo de levenstein pour comparer la distance entre deux chaînes |
dans la mesure où chaque mot généré ne contient qu'une des modifs citées précédemment, je en pense pas que levenstein va m'aider beaucoup...
edit : je viens d'effectuer le test -> ça varie entre 0 et 2.
0 -> mot exact
1 -> substitution d'une lettre par une autre
2 -> ajout d'une lettre
Donc, c'est pas probant.
Message édité par rufo le 24-04-2006 à 18:19:21
Marsh Posté le 24-04-2006 à 19:22:46
> Donc, c'est pas probant.
- c'est à dire? de toutes façons, ce n'est pas une recherche exacte qu'il faut, mais une recherche pondérée, tu peut ajouter lenvenstein pour pondérer les résultats.
aussi, comparaison trigraphe.
Marsh Posté le 25-04-2006 à 11:08:13
| nargy a écrit : > Donc, c'est pas probant. |
c'est quoi la comparaison trigraphe? Je viens de regarder sur google mais je tombe surtout sur des sites qui parlent de l'opérateur de comparaison (en langage C, C++...)
Marsh Posté le 25-04-2006 à 11:50:51
Comparer les lettres trois par trois, avec toutes les combinaisons possibles.
Ça fonctionne relativement bien pour de nombreuses typos.
Marsh Posté le 25-04-2006 à 11:52:50
| nargy a écrit : Comparer les lettres trois par trois, avec toutes les combinaisons possibles. |
Je visualise pas complètement ce que fait l'algo. Il prend quoi en entrée et il donne quoi en sortie? Merci 
Marsh Posté le 25-04-2006 à 12:05:43
il prends deux chaines en entrée, renvoie un booléen.
pour chaque trio de caractère de la première chaîne, il compare si ce trio correspond à une combinaison du trio de la deuxième chaîne.
genre:
1ère chaine: abcd
il compare <<abc>> avec les 3 premiers caractères de la 2ème, combinaisons: abc, acb, bac, bca, cab, cba
puis il compare <<bcd>> avec les 3 derniers caractères de la 2ème
Il retourne Faux s'il ne trouve pas de combinaison possible pour un trio.
Marsh Posté le 25-04-2006 à 12:26:11
Ok, j'ai compris. Mais je pense que cet algo est utile pour savoir dans quelle mesure 2 chaînes (distinctes) se ressemblent. Or, dans mon cas, forcément elles se ressemblent puisque ma 2ième chaîne est générée à partir de la première mais ayant subi une petite modif (ajout/suppression/remplacement d'un caractère). Donc, ça va me retourner vrai uniquement pour les chaînes auxquelles j'ai juste fait une premutation de 2 caractères adjacents 
C'est donc pas ça qu'il me faut (je sais, je suis difficile!:D).
Ce dont j'ai besoin, c'est virer qq mots similaires qui seraient un peu trop "bizarres" (cf "dans" -> je veux garder "dasn" et virer "dzns" ). Il faut donc trouver des propriétés linguistiques + ou - communes aux langues qui utilisent notre alphabet. Dans le pire des cas, je peux au moins me limiter au fr/en (l'allemand a des mots bien trop bizarres! 
)...
Marsh Posté le 25-04-2006 à 12:28:00
> cf "dans" -> je veux garder "dasn" et virer "dzns"
ben, oui, exactement ce que fait le trigraphe.
Marsh Posté le 25-04-2006 à 12:35:18
si je te propose trigraphe et levenstein, c'est parceque j'ai lu sur un site universitaire (lequel?) le résumé d'une thèse dans laquelle ils avaient comparé de nombreuses méthodes (dont soundex1&2, metaphone, et d'autres plus exotiques...) pour comparer des chaînes avec des typos, et ces deux méthodes combinées donnaient les meilleurs résultats pour toutes les langues.
Marsh Posté le 25-04-2006 à 12:37:43
| nargy a écrit : > cf "dans" -> je veux garder "dasn" et virer "dzns" |
oops, oui, mauvais exemple.
ex : "calculateur" -> je veux garder aussi "callculateur". Là, ton algo va me le virer. A moins que vu qu'il va trouver certaines permutations, il va me renvoyer vrai?
Message édité par rufo le 25-04-2006 à 12:38:29
Marsh Posté le 25-04-2006 à 12:43:53
| nargy a écrit : si je te propose trigraphe et levenstein, c'est parceque j'ai lu sur un site universitaire (lequel?) le résumé d'une thèse dans laquelle ils avaient comparé de nombreuses méthodes (dont soundex1&2, metaphone, et d'autres plus exotiques...) pour comparer des chaînes avec des typos, et ces deux méthodes combinées donnaient les meilleurs résultats pour toutes les langues. |
t'aurais le lien de cette thèse par hasard? Ca m'intéresserait 
Je suis déjà allé sur un site universitaire français lire qq thèses (je les ai lues en diagonales, hein, parce qu'elles sont longues en général)... J'ai testé aussi avec soundex et similar_text mais bof, ça reste toujours au niveau du caractère et non au niveau de l'ordre des lettres dans le mot avec la prise en compte des enchainements voyelles/consonnes.
ex : en fr/en, on n'a pas de mots avec "ywz" à la suite ou "dzn" (pas à ma connaissance en tout cas). Je pense aussi à d'autres règles : un mot ne peut pas commencer par 3 consonnes à la suite (ie 3 voyelles?).
Message édité par rufo le 25-04-2006 à 12:46:25
Marsh Posté le 25-04-2006 à 13:19:36
> ex : "calculateur" -> je veux garder aussi "callculateur". Là, ton algo va me le virer. A moins que vu qu'il va trouver certaines permutations, il va me renvoyer vrai?
- c'est pourquoi le trigraphe est combiné avec levenstein. Par exemple lorsque le trigraphe retourne vrai, distance<=1, pour éviter d'avoir une dégradation de la pondération levenshtein lors de multiples erreurs de frappes.
Note que trigraphe et levenshtein fonctionne de la même manière avec voyelles et consonnes, et quelque soit la langue.
Exemples:
distance("dans","dzns" )=1 // tombe en levenshtein
distance("dans","dnas" )=0 // tombe en trigraphe
distance("calculateur","callculateur" )=1 // tombe en trigraphe
Un autre algo souvent utilisé, comme avec soundex, où les doubles lettres ne sont pas comptés:
distance("calculateur","callculateur" )=0 // tombe en soundex
distance("calculateur","caliculateur" )=1 // tombe en lenvenshtein
Les doubles lettres sont retirées avant d'executer d'autres algorithmes (problème avec le ``LL`` espagnol).
Note aussi que dans la thèse que j'ai lu, ils avaient comparé aussi un algo proche de celui que tu décrit au début, avec pondération par distance des touches sur le clavier, mais avaient éliminé la solution car trop complexe à mettre en oeuvre pour trop peu de précision supplémentaire par rapport à levenshtein.
> t'aurais le lien de cette thèse par hasard?
- j'ai déjà essayé de la retrouver sans succès.
Note enfin, que tous ces algos pondèrent les typos, celà n'empêche que tu peut pondérer aussi par la distance sémantique, en utilisant un dictionnaire de synonymes.
Exemple de dictionnaire de synonymes avec pondération:
http://elsap1.unicaen.fr/cgi-bin/cherches.cgi
Un autre lien interessant à ce propos, avec des stats faites à partir de l'internet, mais que tu connais probablement:
http://labs.google.com/sets
Il y a des chercheurs qui ont réussi aussi à extraire des infos d'une page web, et de poser des question à l'ordinateur. Ils ne donnent pas l'algo qu'ils utilisent (désolé, je me souviens plus ni du nom de la méthode, ni du site), mais fournissent quelques exemples:
- lecture d'un article de news
- question: qui est le président des états unis?
- réponse: george bush
Marsh Posté le 25-04-2006 à 16:19:33
| nargy a écrit : > ex : "calculateur" -> je veux garder aussi "callculateur". Là, ton algo va me le virer. A moins que vu qu'il va trouver certaines permutations, il va me renvoyer vrai? |
je vois : donc pour filtrer, j'applique successivement sur chaque mot généré levenshtein, soundex et trigraphe et je garde le mot s'il obtient 0 à l'une des 3 fonctions.
pour http://labs.google.com/sets , ça utiliserait pas l'algo de l'étudiant israëlien ou australien que Google a acheté à grands frais y'a pas longtemps?
Marsh Posté le 25-04-2006 à 16:41:40
une petite précision pour l'algo du trigraphe : il compare les permutations de 3 lettres du mot1 avec 3 lettres du mot2 en respectant la position, je veux dire par là :
- si je prends les 3 premières lettres (1, 2, 3) du mot1 et que je génère les permutations, je vais les comparer aux 3 premières lettres du mot2
- si je prends les lettres 2, 3, 4 du mot1 et que je génère les permutations, je vais les comparer aux lettres 2,3,4 du mot2.
Au final, l'algo du trigraphe retourne vrai si pour chaque trigraphe du mot1, j'ai trouvé une permutation à la même position dans mot2, c'est bien ça?
Par ailleurs, est-ce-que le mot1 doit toujours être le plus court (si mot1 et mot2 sont de tailles différentes)? Merci de ton aide
Message édité par rufo le 25-04-2006 à 18:29:04
Marsh Posté le 25-04-2006 à 19:03:24
> je vois : donc pour filtrer, j'applique successivement sur chaque mot généré levenshtein, soundex et trigraphe et je garde le mot s'il obtient 0 à l'une des 3 fonctions.
- en gros, mais pour bien faire, développer un algo séparé.
> étudiant israélien / australien
- aucune idée, ça fait un moment (qq années) que Google Sets est en place...
> Au final, l'algo du trigraphe retourne vrai si pour chaque trigraphe du mot1, j'ai trouvé une permutation à la même position dans mot2, c'est bien ça?
- oui, c'est l'algo de base. tu peut le mixer avec levenshtein. je n'ai jamais vu l'algo, car comme je t'ai dit c'est ce que j'ai lu dans un résumé de thèse. si tu as des problèmes à l'implémenter, je peut t'aider, c'est interessant comme algo.
L'algo du trigraphe suppose que taille(mot1)=taille(mot2)+/-1. Le plus interessant est de mixer les algos dont on a parlé avec Boyler-Moore (recherche sous-chaîne dans chaîne). Balaise, et interessant.
Marsh Posté le 26-04-2006 à 10:58:48
Au fait, levenshtein, je me demande si c'est très utile? Car à part le mot exact, il va toujours renvoyer un nb > 0 donc il va toujours tomber, non?
Après qq tests, mon filtre trigraphe/soundex/lenshtein n'est pas tip top. Je pense qu'il faut que je pré-traite mes mos en virant les doublements de lettres et les accents comme préconisé dans la thèse dont tu m'as parlé.
Je vais aussi chercher à récupérer + d'infos sur cet algo du trigraphe, quitte à créer un nouveau topic sur ce forum.
Marsh Posté le 26-04-2006 à 11:36:12
bah.. levenshtein te permet de pondérer les résultats. Si l'utilisateur ne fait pas une fôte, les résultats corrects apparaissent en haut de liste.
S'il en fait une, tant pis pour lui, il devra regarder vers la fin de la liste.
Si les résultats sont plus nombreux avec une syntaxe différente tu peut proposer cette syntaxe, comme le fait google.
> Après qq tests, mon filtre trigraphe/soundex/lenshtein n'est pas tip top. Je pense qu'il faut que je pré-traite mes mos en virant les doublements de lettres et les accents comme préconisé dans la thèse dont tu m'as parlé.
- à mon avis il faudrait coder un algo modifié de levenshtein avec trigraphe, il y a des sources en C/C++/Java/etc.. de levenshtein sur wikipedia, notamment la version linéaire. Si j'ai du temps je me penche dessus.
> Je vais aussi chercher à récupérer + d'infos sur cet algo du trigraphe, quitte à créer un nouveau topic sur ce forum.
- si tu veux, mais il n'y a pas grand chose à en dire de plus. C'est une simple comparaison par trio de lettres, qui permet intuitivement de considérer égales des chaînes qui comportent des dislexies.
Marsh Posté le 26-04-2006 à 11:49:52
J'ai trouvé ça en fouillant sur wikipedia:
http://en.wikipedia.org/wiki/N-gram
ça parle de généralisation de trigraphes, qu'ils appelent trigrammes, ça doit être le nom officiel et donc c'est pour ça qu'on a rien trouvé en cherchant trigraphe. Comme quoi...
Toujours en fouinant sur wikipedia, un projet sourceforge:
http://sourceforge.net/projects/dedupe/
Algo pour rechercher une sous-chaîne dans une chaîne avec levenshtein:
http://en.wikipedia.org/wiki/Bitap_algorithm
edit: malheureusement le code présenté n'est pas complet
Message édité par nargy le 26-04-2006 à 12:05:41
Marsh Posté le 26-04-2006 à 12:05:13
Je suis aussi sur wikipedia 
Je suis en train de creuser l'ago de viterbi :
http://fr.wikipedia.org/wiki/Algorithme_de_Viterbi
et la distance de Hamming (je l'avais oublié celui-à), mais je pense que ça se rapporche de ce que fait levenshtein...
http://fr.wikipedia.org/wiki/Distance_de_Hamming
Pour le trigraph (nom en) qui s'appelle trigramme (nom fr), je m'en suis rendu compte en surfant sur un site de linguistique.
Message édité par rufo le 26-04-2006 à 12:06:48
Marsh Posté le 26-04-2006 à 12:18:12
viterbi, c'est pour un réseau neuronal, ça s'applique plus dans les domaines de l'audio ou de la vidéo...
distance de Hamming: levenshtein est beaucoup plus interessant
il y a ça qui est interessant pour un levenshtein efficace:
http://en.wikipedia.org/wiki/Levenshtein_automaton
dommage qu'il n'y ait pas plus de description
Il y a ça aussi pour rechercher à l'aide de levenshtein:
http://en.wikipedia.org/wiki/Metric_trees
ça a l'air interessant, surtout avec levenshtein, et les Vp-trees doivent pouvoir se combiner avec les n-grammes et les calculs de cosinus (produit scalaire de N-grammes, généralisation: http://en.wikipedia.org/wiki/Dot_product ).
Message édité par nargy le 26-04-2006 à 12:27:16
Marsh Posté le 26-04-2006 à 12:30:02
Ah voilà ce dont je te parlais, un module Perl avec trigram+levenshtein:
http://search.cpan.org/~tareka/Str [...] Trigram.pm
edit: c'est plutot trigram+hamming
Message édité par nargy le 26-04-2006 à 12:31:54
Marsh Posté le 26-04-2006 à 15:21:44
pourtant, l'exemple donné pour l'algo de viterbi s'approche assez bien de ce que je cherche à faire.
Marsh Posté le 27-04-2006 à 16:35:16
Pour pouvoir utiliser l'algo de viterbi, il faut connaître la proba d'avoir telle lettre quand on connaît la lettre précédente dnas une langue donnée. J'ai donc fait une petite moulinette qui m'analyse des textes. J'ai analysé 3 textes :
- le premier était composé de news de Yahoo (économie, politique, santé, sciences...mais pas de sport ou people), d'articles du Monde, de textes de Maupassant et d'un article technique sur les CD-R.
- les 2 autres étaient 2 bouquins de Bernard Werber.
Grosso modo, j'ai à chaque fois le même ordre de grandeur. J'ai mis 3 chiffres après la virgule histoire de ne pas avoir 0 à cause d'un arrondi. Voici le résultat :
|
Marsh Posté le 28-04-2006 à 08:12:53
remarque que c'est interessant, mais je trouve que c'est pas vraiment précis. Peut être faudrait-il faire plus de stats avec l'avant dernière lettre.
Peut tu extraire de tes stats, le mot le plus probable commençant par A, B, C, D etc... je suis curieux de voir le résultat?
Marsh Posté le 28-04-2006 à 08:13:48
Reply
Marsh Posté le 28-04-2006 à 14:03:25
| nargy a écrit : (tu t'arrête d'ajouter des lettre quand la proba est trop faible) |
en l'occurence, mes stats, c'est pas pour ajouter des lettres ça serait plutôt virer des mots dont la proba de l'enchaînement des lettres et trop faible...(genre le mot "dzns" ).
Pour la précision, qu'est ce qui te fait dire que mes stats sont pas précises? Si t'en a des plus précises effectuées lors d'une thèse linguistique, je suis prenneur. Mais faut pas oublier que ces stats dépendent de la nature du texte. Avec une nouvelle du Maupassant, on va avoir beaucoup de "z" précédés d'un "e" car il utilise pas mal le "vous" (-> "avez" ). Pareil dans les articles du Monde. Sur mon article traitant des Cds, je vais avoir pas mal de "d" précédés d'un "c" alors que normalement, c'est pas possible en fr. Donc, c'est bien de mener l'analyse sur plusieurs types de textes (littéraires, techniques, poétiques, courants, familliers...).
Marsh Posté le 28-04-2006 à 22:20:05
- ha non non c'est pas ça que je voulais dire
- tes stats sont assez précises pour ce que tu veux faire, je voyait pas ça comme ça
- c'est juste que par curiosité, j'aurais aimé connaître quel était d'après l'ordinateur, le mot le plus probable commençant par 'A', même si ce mot n'existe pas dans la langue française
- comme tu as des stats, tu as la possibilité de faire ça, mais tu n'a peut être pas le temps
- j'avais vu à la télé une chercheuse en liguistique qui faisait la même chose, ou presque, avec des mots, et représentait en 3D les probabilités, c'était très interessant de comparer les auteurs, et de suivre leurs évolutions
Marsh Posté le 29-04-2006 à 11:35:30
| nargy a écrit : - ha non non c'est pas ça que je voulais dire |
Par contre, je ne suis pas sûr qu'avec ce genre de stats on puisse reconstruire des mots de la langue française. On risquerait d'agglutiner les lettres en prenant les plus fortes probas et on risquerait d'avoir des mots à rallonge qui n'existent pas au final. Cela dit, combiné à un algo génétique, ça pourrait donner une population (ou chaque individu représente un mot) qui évolurait petit à petit vers des mots existants Si j'ai le temps, j'essaierai...
Marsh Posté le 29-04-2006 à 13:14:34
> On risquerait d'agglutiner les lettres en prenant les plus fortes probas
- ouais voilà! avec des stats sur l'avant dernière lettre, et les autres, on pourrait avoir le mot le plus long jusqu'à répétition.
- l'algo génétique: excellent
Sujets relatifs:
- script qui scan des rep avec html et qui remplace des mots
- les développeurs utilisent-ils des outils de génération auto de codes
- [Résolu] Un compteur de mots dans Word
- [reglé]sauter une ligne lors de la generation pdf
- Génération d'un mail avec pièce jointe en PHP
- Génération d'un chiffre aléatoire à partir d'une loi gaussienne
- cryptage des mots de passe pour oracle
- [C++ débutant] Génération d'instances dynamique (?)
- Etendre XDoclet pour la génération du BusinessDelegate
- internal error during packaging generation
Marsh Posté le 24-04-2006 à 16:46:13
Je suis en train d'écrire un algo permettant d'étendre une recherche via des mots clés afin de contourner le pb de recherches infructueuses du fait qu'il y a des fautes d'orthographe ou de frappe dans une base de données (ici, Mysql).
ex : l'utilisateur recherche tous les enregistrements contenant le mot "plate-forme". Il va donc rater les enregistrements contenant "plate forme" ou "plateforme".
Par ailleurs, je cherche autant que possible à ne pas créer un algo trop spécifique aux caractéristiques d'une langue. Je préfèrerait qu'il soit assez généraliste (ou alors paramétrable).
Pour l'instant, voilà ce que sait faire mon algo qui prend en paramètre un mot :
- remplacer 1 lettre du mot par une autre lettre. Cette autre lettre appartient à l'ensemble des lettres voisines (sur le clavier) de la lettre à remplacer. -> ici, j'ai un paramétrage pour indiquer sur quel clavier on travaille.
- inverser l'ordre de 2 lettres adjacentes.
- supprimer une lettre du mot.
- rajouter une lettre après la lettre courante du mot sur laquelle on travaille. Pareil, la lettre ajoutée appartient à l'ensemble des lettres voisines (sur le clavier) de la lettre après laquelle on effectue cet ajout. En plus, je traite le cas du doublement de frappe de la lettre (ex : appel -> apppel) et de l'ajout du " " et du "-".
En sortie de cet algo, j'ai une liste contenant tous les nouveaux mots générés à partir du mot donné en entrée. Le pb, c'est que pour un mot, même court, je me retrouve à la fin avec pas mal de possibilités. J'aimerais pouvoir en éliminer qq uns qui sont "bidons".
ex : le mot "dans" va me donner entre autre "dzns" (faute de frappe) ou "dasn". Je veux garder "dasn" (faute de frappe classique) mais supprimer "dzns" (faute de frappe trop visible, l'utilisateur aura probablement corrigé lors de la rédaction de son texte dans la BD).
J'ai donc mis en place 2 filtres :
- suppression des mots générés ayant plus de x consonnes (j'ai mis 4)
- suppression des mots générés ayant plus de x voyelles (j'ai aussi mis 4)
Est-ce que vous connaitriez d'autre filtres "intelligents" que je pourrais mettre en place qui ne nécessiteraient pas la mise en place d'un dico? Merci
Message édité par rufo le 25-04-2006 à 12:39:57