Dédoublonnage des données lors d'une migration

Lors de la migration d'un système d'information vers un autre, on est souvent tenté de se lancer dans une opération d'amélioration de la qualité. Bien qu'il s'agisse d'un projet en soi, cela peut être le « bon moment », pour autant que l'on dispose des ressources nécessaires pour le faire. Ressources humaines, évidemment, mais il faut aussi disposer d'assez de temps que pour pouvoir mettre en place une méthodologie à même de nous garantir une amélioration de la qualité.

Cette année quelques étudiants se sont lancés dans cette aventure pour leurs travaux de fin d'études avec la migration de catalogues de bibliothèque. Et un problème particulier s'est rapidement posé avec la présence de doublons dans les listes d'autorité. Les catalogues sont les endroits rêvés pour mesurer la créativité de l'esprit humain pour ne pas respecter les règles ;-)

Ainsi, dans un catalogue de bibliothèque, nous aurons une liste d'éditeurs par exemple, et en fonction de la créativité des catalographes, mais aussi de la quantité de personnes impliquées dans la gestion de ces éditeurs, nous trouverons des variantes plus ou moins nombreuses :

• Ed. O'Reilly ;
• Editions O'Reilly ;
• O'Reilly ;
• E. O'Reilly ;
• etc.

L'idéal serait donc de pouvoir trouver tout les doublons, et de les remplacer par la forme correcte. Mais comment trouver tout ces doublons ? Sans ordinateur, la tâche est fastidieuse :

1. parcourir la liste d'autorité ;
2. établir une liste des doublons ;
3. faire le choix de la forme « correcte » ;
4. effectuer les remplacements nécessaires.

Face à ce genre de situations, mon premier réflexe est souvent de déterminer ce que je peux informatiser, voire même automatiser. Dans le cas présent, ce serait idéal de pouvoir obtenir une liste des « éventuels doublons », donc, des expressions suffisamment proches que pour nous mettre la puce à l'oreille. Dans le cas présent, l'informatique nous offre plusieurs techniques :

• un algorithme permettant de calculer la distance de Levenshtein, c'est-à-dire le nombre d'opérations élémentaires pour passer un mot M à un mot P ; sur base de cet algorithme, nous allons donc pouvoir comparer chaque entrée de la liste d'autorité avec le reste de cette dernière, et conserver les éléments dont la distance de Levenshtein est peu importe (ce seuil est évidemment à paramétrer comme la taille des mailles d'un filet) ; évidemment, cet algorithme est disponible sur le CPAN : Text::Levenshtein pour une version en Perl, et Text::LevenshteinXS pour une version en C ;
• d'autres techniques, dérivées de la précédente, existent ; par exemple employer l'algorithme se cachant derrière agrep, un grep permettant de faire des approximations dans la recherce de chaînes de caractères ; un module Perl existe qui reproduit ce comportement : String::Approx (il s'agit ici aussi d'un module XS, donc basé sur du C).

Donc, les techniques existent, « y a plus qu'à » … faire une recherche sur le CPAN, par exemple avec le mot clé « group » ou « similarity », ce qui m'a permis de décrouvrir String::Similarity::Group qui s'appuie sur String::Similarity, lequel s'appuie sur un algorithme différent mais faisant sensiblement la même chose que les techniques expliquées ci-dessus. Bref, une fois encore le CPAN m'économise du temps, et me permet de mettre en place un prototype rapidement (sans ce module, j'aurais mettre en place la création des groupes, ce qui n'est certes pas compliqué, mais qui apporte son lot de réflexions).

Voici le prototype en question :

#!/usr/bin/env perl

use strict;
use warnings;

use Spreadsheet::Read;
use Spreadsheet::Write;
use String::Similarity::Group qw( :all );
use Getopt::Long;

my $config = { threshold => "0.75", };

GetOptions( $config, "input=s", "output=s", "column=s", "sheet=s", "threshold=s" );

die _usage() unless _valid($config);
my $values = _build_values( $config->{input}, $config->{sheet}, $config->{column} );
my @groups = groups( $config->{threshold}, $values );

_save_groups( $config->{output}, \@groups );

sub _usage {
    return
"Usage: $0 --input file.xls --output output.xls --column 4 --sheet 1 --threshold '0.75'\n";
}

sub _valid {
    my $config = shift;

    if (    exists $config->{input}
        and exists $config->{output}
        and exists $config->{sheet}
        and exists $config->{column} )
    {
        return 1;
    }
    else {
        return 0;
    }
}

sub _build_values {
    my ( $file, $sheet_n, $col ) = @_;

    my @values;
    my $data  = ReadData($file);
    my $sheet = $data->[$sheet_n];

    for my $row ( 1 .. $sheet->{maxrow} ) {
        push @values, $sheet->{cell}[$col][$row];
    }

    return \@values;
}

sub _save_groups {
    my $output = shift;
    my $groups = shift;

    my $sheetname = '001';

    my $xls = Spreadsheet::Write->new(
        file   => $output,
        format => 'xls',
        sheet  => $sheetname++,
    );

    foreach my $group ( @{$groups} ) {
        foreach my $row ( @{$group} ) {
            $xls->addrow($row);
        }
        $xls->addsheet( 'group_' . $sheetname++ );
    }
}

Ce script en ligne de commande accepte les arguments suivants :

• input : cela permet de donner le nom du fichier Excel (ou n'importe quel format géré par Spreadsheet::Read, donc OpenOffice.org Calc et CSV viennent s'ajouter à la liste) ;
• output : cela permet de spécifier le nom du fichier Excel qui contiendra les groupes. J'ai pris la convention de créer autant de feuilles de calcul qu'il n'y a de groupes, et de mettre les candidats doublons dans une feuille de calcul ;
• sheet : cela permet de spécifier le numéro de la feuille de calcul contenant les données à analyser ;
• column : cela permet de spécifier le numéro de la colonne contenant les données à analyser.
• threshold : il s'agit du seuil de similitude à partir duquel String::Similarity::Group commence à regrouper les élements. C'est donc à partir de ce paramètre que nous allons pouvoir agir sur la taille des mailles de notre filet.

Le reste du script est juste le liant permettant de faire travailler ces différents modules ensemble.

Voilà, j'ai donc maintenant à ma disposition un outil permettant de mettre en évidence des candidats doublons, il faut évidement encore choisir soi-même quelle est la forme correcte, mais la partie consistant à analyser les données a été facilité et n'a pris que quelques minutes.