Brevet FR3045857A1 (20170623)
REVENDICATIONS1. Procédé de classement, par un dispositif informatique dit de classement (101), d'un ensemble (E) d'éléments stockés dans un espace de stockage, chaque élément comprenant une 5 clé de classement (Ki) associée à une valeur de donnée (VALI), ledit procédé de classement comprenant : - une première étape de classement (E30) dans une structure (S) de données informatique de pointeurs vers lesdits éléments stockés dans l'espace de stockage, cette première étape de classement comprenant pour chaque élément : 10 o une étape d'obtention (E32) d'une valeur de hachage en appliquant une fonction de hachage à la dé de classement de l'élément; o une étape de détermination (E33), à partir d'un nombre prédéterminé m de bits consécutifs extraits de la valeur de hachage, d'un indice de position d'un pointeur vers l'élément dans la structure de données informatique ; et 15 o une étape d'insertion (E34) dudit pointeur dans la structure de données informatique à l'indice de position ainsi déterminé ; et - une deuxième étape de classement (E40) comprenant, pour chaque indice de position de la structure de données informatique associé à une pluralité de pointeurs, un classement de ces pointeurs entre eux en appliquant une première relation d'ordre prédéfinie aux clés de 20 classement des éléments informatiques vers lesquels pointent ces pointeurs.\n<CLM>\1\tProcédé de classement selon la revendication 1 dans lequel les m bits consécutifs extraits de la valeur de hachage correspondent aux m bits de poids forts de cette valeur de hachage. 25\n<CLM>\1\tProcédé de classement selon la revendication 1 ou 2 dans lequel la première relation d'ordre prédéfinie (0) appliquée aux clés de classement vérifie les règles suivantes : - une clé de classement A est strictement inférieure à une clé de classement B si la valeur de hachage de la dé de classement A est strictement inférieure à la valeur de hachage de la clé 30 de classement B ; si les valeurs de hachage de la clé de classement A et de la clé de classement B sont égales, la clé de classement A est strictement inférieure à la clé de classement B si la clé de classement A est strictement inférieure à la clé de classement B conformément à une deuxième relation d'ordre prédéfinie ; 35 - la clé de classement A est égale à la clé de classement B si et seulement si les clés de classement A et B sont égales conformément à la deuxième relation d'ordre. 3045857 21\n<CLM>\1\tProcédé de classement selon l'une quelconque des revendications 1 à 3 dans lequel l'étape d'application (E32) d'une fonction de hachage à la clé de classement comprend : - l'application d'une première fonction de hachage à la clé de classement résultant en un entier codé sur un nombre prédéterminé n de bits ; puis - l'application d'une seconde fonction de hachage audit entier résultant en la valeur de hachage.\n<CLM>\1\tProcédé de classement selon l'une quelconque des revendications 1 à 4 comprenant en outre une troisième étape de classement (E60) des éléments dans un fichier informatique (F) en parcourant séquentiellement la structure de données informatique.\n<CLM>\1\tProcédé de classement selon l'une quelconque des revendications 1 à 5 dans lequel le nombre m dépend de la taille de l'espace de stockage dans lequel sont stockés lesdits éléments.\n<CLM>\1\tProcédé de classement selon l'une quelconque des revendications 1 à 6 dans lequel 15 le nombre m est modifié dynamiquement au cours du procédé de classement.\n<CLM>\1\tProcédé de classement selon l'une quelconque des revendications 1 à 7 dans lequel la deuxième étape de classement est mise en oeuvre : - après insertion d'un pointeur dans la structure de données informatique à un indice de position 20 déjà associé à au moins un autre pointeur précédemment inséré ; ou - après avoir inséré dans la structure de données tous les pointeurs vers les éléments stockés dans l'espace de stockage ; ou - périodiquement. 25\n<CLM>\1\tProgramme d'ordinateur comportant des instructions pour l'exécution des étapes du procédé de classement selon l'une quelconque des revendications 1 à 8 lorsque ledit programme est exécuté par un ordinateur.\n<CLM>\1\tSupport d'enregistrement lisible par un ordinateur sur lequel est enregistré un 30 programme d'ordinateur comprenant des instructions pour l'exécution des étapes du procédé de classement selon l'une quelconque des revendications 1 à\n<CLM>\1\t11. Dispositif informatique de classement (101) d'un ensemble d'éléments stockés dans un espace de stockage, chaque élément comprenant une clé de classement associée à une 35 valeur de donnée, ledit dispositif de classement comprenant : - un premier module de classement (101B), configuré pour classer dans une structure de données informatique des pointeurs vers lesdits éléments stockés dans l'espace de stockage, 3045857 22 ce premier module de classement comprenant une pluralité de modules activés pour chaque élément et comprenant : o un module d'obtention (101B-1), configuré pour obtenir une valeur de hachage en appliquant une fonction de hachage à la clé de classement de l'élément; 5 o un module de détermination (101B-2), configuré pour déterminer à partir d'un nombre prédéterminé m de bits consécutifs extraits de la valeur de hachage, d'un indice de position d'un pointeur vers l'élément dans la structure de données informatique ; et o un module d'insertion (101B-3), configuré pour inséré ledit pointeur dans la structure de données informatique à l'indice de position ainsi déterminé ; et 10 - un deuxième module de classement (101C) configuré pour, pour chaque indice de position de la structure de données informatique associé à une pluralité de pointeurs, classer ces pointeurs entre eux en appliquant une première relation d'ordre prédéfinie aux clés de classement des éléments informatiques vers lesquels pointent ces pointeurs.\n<CLM>\1\tDispositif informatique de classement selon la revendication 11 comprenant en outre un troisième module de classement (101D) configuré pour classer dans un fichier informatique lesdits éléments en parcourant séquentiellement ladite structure de données informatique.\n<CLM>\1\tDispositif informatique de traitement (102) d'éléments comprenant chacun une clé de classement et une valeur de donnée, ledit dispositif informatique de traitement comprenant : - un module d'obtention (102A) configuré pour obtenir en provenance d'une pluralité de dispositifs de classement selon la revendication 12, une pluralité de fichiers informatiques comprenant des éléments classés ; - un module de regroupement (102B) configuré pour extraire et regrouper les éléments classés dans chaque fichier informatique comprenant une même clé de classement destinée à être traitée par le dispositif informatique de traitement, en utilisant une fonction de hachage identique à la fonction de hachage et la première relation d'ordre prédéfinie utilisées par chacun des dispositifs de classement.\n<CLM>\1\tSystème informatique (100) comprenant : - une pluralité de dispositifs informatiques de classement (101) selon la revendication 12 aptes à classer des ensembles d'éléments distincts ; et - des dispositifs informatiques de traitement (102) selon la revendication 13 aptes à traiter ces ensembles d'éléments. 3045857 23\n<CLM>\1\tSystème informatique selon la revendication 14 dans lequel les premiers modules de classement d'au moins deux dispositifs informatiques de classement utilisent des nombres m distincts. 5