Forum général.cherche-logiciel Détecter des lignes presque identiques

Posté par  .
Étiquettes : aucune
7
20
mar.
2011

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  . É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  . É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  . É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  . É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  . Évalué à 2.

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

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