Bonjour,
Je voudrais ouvrir une discussion au sujet d'un problème qui a été posé dans une école d'ingénieur il y a quelques semaines. J'ai actuellement un stagiaire qui terminera ses études en juin 2019, il m'a alors donné l'énoncé. Cependant... j'ai un peu de mal à m'y mettre.
Imaginons un très gros fichiers ARCHIVES qui contiennent les archives de familles dans un département, certaines remontant jusqu'au XVI siècle. Un million de personnes y sont enregistrées, chacune d'elle respectant la structure de données suivantes :
- un identifiant unique [donc une clé],
- le nom de la personne, lequel peut être composé de plusieurs mots séparés par un blanc,
- les prénoms de la personne, séparés par un blanc (pas de tiret comme par exemple Jean-Luc),
- les identifiants de la mère et du père, par défaut 0 s'ils ne sont pas connus.
Ainsi, ce fichier ARCHIVES permet de dresser des arbres généalogiques. Ce fichier est réputé ne contenir aucune erreur d'orthographe ou de saisie. Cependant, l'ordre des prénoms n'est pas garanti. De même, les mots composant le nom peuvent être intervertis.
Propriétés de ARCHIVES :
- En moyenne, la profondeur des généalogies est 5 générations ,
- En moyenne, chaque personne a 4 enfants.
C'est alors que la Préfecture envoie une liste de 18000 personnes, NOTABLES, structuré comme suit :
- identifiant unique,
- nom de la personne, pouvant être composé de plusieurs mots, alors séparés par un blanc,
- prénoms, avec la même propriété/contrainte que le nom.
Propriétés de NOTABLES :
- En moyenne, le nom de chaque personne est composé de 2 noms, le maximum répertorié est 6,
- Quant aux prénoms, la moyenne est de 3 par personne, le maximum étant de 6.
Les identifiants des deux fichiers sont indépendants.
Les fichiers ARCHIVES et NOTABLES peuvent être stockés en mémoire.
Voici donc ma propre réflexion :Citation:
Arrivent donc les questions :
1) La Préfecture demande d'identifier les personnes du fichier NOTABLES dans ARCHIVES, en insistant sur la nécessité que les noms et prénoms doivent correspondre en nombre et ordre des mots. Par exemple Louis Georges DU VALNEUF n'est pas la même personne que Georges Louis DU VALNEUF.
2) Même question, mais l'ordre des prénoms des personnes peut être quelconque dans les deux fichiers. Il est donc possible qu'il y ait des homonymies.
Dans les deux questions, concevoir un algorithme rapide et performant qui permette de marquer les personnes de NOTABLES qui seraient identifiées dans ARCHIVES.
Chercher 18 000 personnes et balayer un fichier de 1 000 000 personnes par deux boucles imbriquées, cela me semble très naïf et surtout désastreux : cela représente quand même 18 milliards de recherche, nombre très élevé.
Je suppose qu'il y a donc un travail de préparation, comme par exemple trier une fois pour toutes les deux fichiers, puisque l'énoncé n'indique pas qu'il y ait le moindre tri. Le tri s'effectue sur le nom puis les prénoms. Les noms les plus courts sont placés avant les plus longs, si les premiers constituent les lettres des derniers, par exemple : DE MARIA est placé avant DE MARIANT. Si les noms sont identiques, les prénoms constituent le second discriminant.
Mais là, ça coince pour moi : existe-t-il un moyen de trier 1 000 000 de personnes "rapidement" ? Comme il est dit que ce fichier peut-être placé en mémoire, je me dis que la solution réside là. J'ai bien un algorithme à proposer qui procède à un balayage unique et simultané des deux fichiers.
De même, les clés d'identification ne servent nullement ici, bien qu'elles puissent être employées à marquer les personnes qui sont présentes dans les deux fichiers.
Merci par avance de vos remarques, critiques, observations, conseils... :)
