trouver le texte le plus proche d'un autre

trouver le texte le plus proche d'un autre - PHP - Programmation

Marsh Posté le 10-11-2011 à 23:07:25    

Bonsoir,
J'ai mis un site en place pour mon club avec une possibilité d'éditer les articles en ligne, et un versionning des articles.
Donc pour un article, je possède toutes ses versions dans l'historique, et tous les auteurs.
Jusqu'à présent, j'affichais en bas de l'article le dernier auteur qui avait édité l'article, mais voilà, un accent corrigé, et pouf, le voilà "propriétaire" de l'article, et cela ne rend pas tout le monde heureux.
 
Alors j'aurai voulu mettre en place un code qui comparer la dernière version de l'article avec les précédentes, et déterminer qui est l'auteur qui à rédiger le plus grand pourcentage de l'article.
 
Je sais qu'il existe des comparaisons pour l'anglais de sonorité de mot coumme soundex(), mais déjà c'est en anglais, et en plus, ce ne sont que des mots. Là, on peut imaginer que quelqu'un rajoute 3 lignes en plein milieu de l'article.
 
J'ai pensé à la distance de Levenshtein, mais ça marche que sur des chaines de moins de 255 caractères.
J'ai pensé à similar_text(), mais il semblerait qu'il est très long à calculer, et si j'ai 10 versions de l'article, et que je dois calculer donc 10 valeurs de similar_text, ça risque de faire un time out très rapidement.
 
Un autre soucis, est que la base de donnée est tout en UTF8, et donc je ne sais pas si ces fonctions sont compatibles avec ça...
 
Qu'en pensez vous, et que proposez vous ?
 
Merci de vos avis !
 
PS : le site est sur FREE, ce qui implique certaine contrainte.

Reply

Marsh Posté le 10-11-2011 à 23:07:25   

Reply

Marsh Posté le 16-11-2011 à 20:18:23    

Sur les logiciels de version du genre git ou svn, ca se fait ligne par ligne.
A chaque ligne correspond un auteur, le dernier a l'avoir modifie.
Tu peux faire ca, en te disant que l'auteur qui a modifie le plus de ligne dans l'article correspond a l'auteur principal de l'article.
Ca devrait donner de bons resultats, a part si un auteur fait une correction orthographique tres severe d'un article mal ecrit, ou effectivement le correcteur prendra la place de l'auteur sur pas mal de lignes...
 
A noter que si l'article ne saute jamais de lignes, tu peux toujours segmenter les affectations d'auteurs par un nombre arbitraire de caracteres.
Le seul point un peu complique, c'est de gerer les insertions de textes, ou les affectations se retrouveront toutes decalees du nombre de caracteres a gerer. C'est chiant mais pas insurmontable.


Message édité par Pascal le nain le 16-11-2011 à 20:22:49
Reply

Marsh Posté le 17-11-2011 à 10:18:28    

Autre solution : calculer le % de corrélation entre la version précédente de l'article et la version modifiée via l'algorithme LSA : http://fr.wikipedia.org/wiki/Analy [...] ue_latente
 
Pas besoin de calculer la SVD, tu t'arrêtes à la matrice des corrélations. Pour la lemnisation, tu peux utiliser la BD en GPL, Lexique3 : http://www.lexique.org/telLexique.php
 
Je m'en sers dans mon logiciel de help-desk Astres (cf ma signature) pour identifier automatiquement les 10 tickets d'incidents identiques, similaires ou corrélées ;) C'est assez efficace...


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
Reply

Marsh Posté le 17-11-2011 à 21:56:39    

Merci Pascal de ta réponse.
 
J’ai pour l’instant tenté de calculer le similar_text() entre la dernière version et toutes les versions précédentes, et classer suivant ce chiffre, ça marche bien tant que l’on ajoute du contenu, mais dès  que l’on en efface…
 
J’ai pensé alors un truc comme celui que tu me proposes, mais à l’échelle d’un mot, mais sur le papier, je n’ai pas réussi. Considérons si tu veux bien ces deux cas ensembles :
 
Imaginons que l’auteur 1 écrivent :
 
 

Code :
  1. Le
  2. Joli
  3. Petit
  4. Chaperon
  5. Rouge
  6. Dans
  7. Le
  8. bois
  9. Vert


 
Et que l’auteur 2 viennent modifier cela en
 

Code :
  1. Le
  2. Petit
  3. Chaperon
  4. Rouge
  5. Et
  6. Vert
  7. Dans
  8. Les
  9. Jardins
  10. Rouges

 
 
J’ai deux liste de mots avec des mots répété, avec à la fois des insertions, suppression et modification, et les trois en même temps, je ne suis pas capable de voir ce qui a été inséré, supprimé, ou modifié  (si j’ai la garantie qu’il y en a que un des trois, ok, c’est facile, c’est quand il y a les 3 en même temps que je ne vois pas comment faire) avec une algorithme. L’œil identifie des groupes de mots qui lui donne une intuition, mais l’algorithme….  Et le même problème va se poser si l’on procède par tranche de 100 caractères par exemple. (on ne peut pas faire par ligne, car en HTML, la notion de ligne varie suivant la taille de l’écran, ou alors c’est que une ligne fait un paragraphe complet.
 
En même temps, il est vrai que suivant les modifications que l’on fait avec SVN, et que l’on utilise le comparateur d’éclipse, on voit bien qu’il perd les pédales si l’on va trop loin.
 
Pour mettre en place ta proposition, je me dis qu’il faudrait commencer par faire plutôt un algorithme qui cherche les plus grandes chaines communes en premier lieu, et partir de ce résultat pour imaginer les modifications, mais la complexité d’un tel algorithme va vite monter, puisqu’il va falloir prendre toutes les tailles de chaines de 1 à N, prendre tous les sous chaines possibles de cette taille, et chercher leurs occurrences dans la nouvelle chaine, puis choisir un certain nombre de résultat de manière à couvrir le maximum de caractère (ce qui n’implique pas que tout les résultats les plus grands soient les meilleurs pour ça), et à partir de là, on suppose que ces morceaux les plus grands sont de la même origine, et que ce qui a autour à été modifié, supprimé ou ajouté.
 
J’utilise CKEditor comme zone de saisie, et il y a un bouton précédent et suivant. Je me suis dit que je pourrai récupérer cette liste pour reconstruire les modifications…  … mais si l’utilisateur coupe et colle le contenu de l’article, cette liste le déclarera comme l’unique auteur…
 
J’ai pensé à utiliser coté "base de donnée" le full-text ( http://dev.mysql.com/doc/refman/5. [...] earch.html ) ...
 
Rufo, merci aussi, il est trop tard pour que je me penchez sur ta proposition, mais ça semble intéressant. Je reviens en parler une fois que j'ai lu tout tes liens !

Reply

Marsh Posté le 18-11-2011 à 00:07:36    

naeco a écrit :

J’ai pensé alors un truc comme celui que tu me proposes, mais à l’échelle d’un mot, mais sur le papier, je n’ai pas réussi.


 
Effectivement, je vois le probleme.
Une solution serait de considerer qu'un block de mots est le meme que dans la derniere version a partir d'une certaine taille.
Ainsi dans ton exemple, le premier "Vert" sera un mot completement different du deuxieme "Vert".
On parcourt les deux textes, et des qu'un mot differe, le block s'arrete, et on passe en zone "nouvelle", jusqua trouver une sequence suffisament longue qui corresponde a la suite du texte original.
 
Mais avant de prendre une decision, je te suggere de lire les liens que t'a envoye rufo :
 
 

rufo a écrit :

Autre solution : calculer le % de corrélation entre la version précédente de l'article et la version modifiée via l'algorithme LSA : http://fr.wikipedia.org/wiki/Analy [...] ue_latente
 
Pas besoin de calculer la SVD, tu t'arrêtes à la matrice des corrélations. Pour la lemnisation, tu peux utiliser la BD en GPL, Lexique3 : http://www.lexique.org/telLexique.php
 
Je m'en sers dans mon logiciel de help-desk Astres (cf ma signature) pour identifier automatiquement les 10 tickets d'incidents identiques, similaires ou corrélées ;) C'est assez efficace...


 
C'est tres interessant, je ne connaissais pas.
Dans cette methode, l'ordre des mots, ainsi que le nombre n'a pas d'importance. Par conséquent, si je modifie beaucoup un texte, en doublant sa taille, mais en gardant les memes termes en proportions egales, la nouvelle version sera jugee equivalente a l'originale.
Ce n'est pas la methode exactement ideale, mais on peut sans doute s'en inspirer pour concocter une methode "maison", qui n'isole pas de son calcul le nombre de mots.
En fonction du "score de difference", tu peux decider qu'un article est a 10% d'un auteur A, 30% d'un auteur B, etc, sans retenir ce qu'ils ont chacun modifie.


Message édité par Pascal le nain le 18-11-2011 à 00:40:18
Reply

Marsh Posté le 18-11-2011 à 09:58:19    

Si effectivement l'ordre des mots n'est aps pris en compte dans mon algo, le nb d'occurrences, si. Tu verra qu'à un moment, le calcul d'un tdf-idf est appliqué à chaque valeur de la matrice termes/documents : http://fr.wikipedia.org/wiki/TF-IDF
 
Et t'avouera que remplacer la phrase "le chaperon rouge et vert" par "le chaperon vert et rouge" ne change rien au SENS de la phrase. Faut pas oublier que mon algo est SEMANTIQUE, pas simplement textuelle ;)
 
Du coup, si tu rajoutes des mots en retire ou en change dans la nouvelle version, le % de corrélation entre cette version et sa précédente va diminuer.


Message édité par rufo le 18-11-2011 à 09:59:27

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
Reply

Marsh Posté le 18-11-2011 à 22:53:25    

En effet, j'avoue ^^
 
C'est puissant ton truc rufo ! Je vais essayer de le mettre en place pour voir.
 
Merci de votre aide, je reviendrai faire un point de ce que ça aura donné dans quelques temps  :)

Reply

Marsh Posté le 18-11-2011 à 23:06:51    

[:drap] (les tu c'est pour moi)....
Je pensais que dans un français grossier, effectivement, l'ordre d'occurence des termes autour de "et" n'est pas important, c'est le cas de la majorité des acception ;Alors que dans un français spécialisé comme la description d'une carrosserie, on peut avoir une qualification des terme selon leur ordre d'occurence dans l'expression ; Ainsi une carrosserie rouge et verte, peut-être d'intérieur rouge et d'extérieur vert ; Ici intérieur et extérieur seraient des contextes tacites ; Ce qui peut ce spécifier par des axiomes dans la description.
Donc, ça dépend. Plus tu sera grossier, moins tu aura besoin d'analyse en sémantique. contrairement, à des description spécialisé.
Oui ?


Message édité par Profil supprimé le 18-11-2011 à 23:12:00
Reply

Marsh Posté le 19-11-2011 à 18:49:18    

Oui, je vois l'idée. Merci :)

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed