Salut,
Je dois identifier des doublons dans une très longue liste de noms en tenant compte d'éventuelles fautes de frappes et d'autres éléments rendant la simple utilisation de la commande uniq inutile.
J'imagine qu'il y a une application pour ça :D (c'est quand même assez banal comme besoin et trivial à coder), mais je ne trouve rien, une idée ?
Au fait le programme en question dois prendre en charge l'unicode la liste étant internationale.
# un bon algo
Posté par NeoX . Évalué à 2.
il va te falloir un bon algo pour detecter 2 mots differents, d'un seul meme mot tapé 2x avec une faute de frappe.
en effet, comment tu sais si ces deux lignes sont les memes avec une coquille, ou deux differentes ?
Dupond Martin
Dupont Martin
pour le reste je penses que sort -u permettra de classer le fichier et de ne garder que les lignes uniques.
ensuite il te faudra le lire à la main, pour detecter les fautes de frappes ou les coquilles
[^] # Re: un bon algo
Posté par Tonton Benoit . Évalué à 3.
Pour sort -u je le fais déjà, mais je suis loin d'être infaillible (et j'avoue qu'au bout de quelques milliers de lignes je n'ai plus les yeux en face des trous) Un algo de détection de lignes proches ne sera jamais parfait c'est pour ça que ça passera par mon contrôle final (et j'ai d'autres éléments que juste les noms pour décider si c'est une faute ou pas), et je sais bien que le fichier ne sera jamais "parfait" j'essaye juste de l'approprir un peu avant de mettre tout ça dans une base de donnéeq.
[^] # Re: un bon algo
Posté par openbar . Évalué à 3.
Une solution bourrine est de comparer la distance de levenshtein http://fr.wikipedia.org/wiki/Distance_de_Levenshtein entre chaque paire de lignes ( complexite n2 * complexite de chaque comparaison ) et de regarder a la main les plus faibles scores, tu decides quand t'arretes de regarder.. Par contre faut que tu le code toi meme.. en python ca devrait pas prendre plus de 10 minutes. http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance
[^] # Re: un bon algo
Posté par Tonton Benoit . Évalué à 3.
C'est un peu ce que je pensais faire "à la rache", mais je m'etonne que cela n'a pas déjà été fait.
[^] # Re: un bon algo
Posté par JoeltheLion (site web personnel) . Évalué à 1.
ça a probablement déjà été fait, mais tu passeras plus de temps à le chercher qu'à le refaire en python ou équivalent :)
[^] # Re: un bon algo
Posté par phoenix (site web personnel) . Évalué à 4.
Sinon je peux te conseiller mon site http://www.shadoware.org/post/2010/06/06/Calcul-de-la-Distance où j'effectue la même chose mais entre deux fichier (cela marche mieux sur ce qui est texte). L'algo est à base de compression, et un programme permet de comparer deux fichiers tar.
Rien n'empêche d'adapter le programme pour une autre utilisation ou de s'en inspirer.
[^] # Re: un bon algo
Posté par jiyuu . Évalué à 2.
Sinon pour une solution en O(log n) il existe les Bk tree [0]. Il y a un lien pour une implementation en python sur la page wikipedia et le lien pour l'implementation en common lisp contient un jolie graphique expliquant le principe.
[0] La page wikipedia est un plutot vide. Une meilleur explication en anglais se trouve ici
# google refine
Posté par Stéphane Gully (site web personnel) . Évalué à 3.
Essaye peut-être avec google refine, si je me rappel bien ça peut dédoubler des termes semblables.
# unique ?
Posté par eric gerbier (site web personnel) . Évalué à 1.
le projet unique (http://unique.sourceforge.net/) pourrait peut-être aider (je ne l'ai pas essayé)
# Distance de Levenshtein
Posté par khivapia . Évalué à 2.
Si je ne me gourre pas, c'est la notion mathématique que tu cherches : c'est une "distance d'édition", un truc qui mesure le degré de différence entre deux textes, le nombre minimal d'éditions, suppressions et insertions qu'il faut pour passer d'une chaîne de caractère à une autre.
http://en.wikipedia.org/wiki/Levenshtein_distance
En plus il y a des packages python qui sont tout prêt pour ça, notamment packagés sous debian.
[^] # Re: Distance de Levenshtein
Posté par Tonton Benoit . Évalué à 3.
Finalement je suis parti sur cette solution, mais en ruby qui dispose aussi d'un module tout prêt.
Merci à tous !
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.