FR 2125433 A1 19720929 FR 7204756 A 19720211 75 04756 1 2125433 La présente invention se rapporte au classement d'enregistrements de données au moyen d'un dispositif de traitement de données et elle concerne plus particulièrement le classement d'un fichier d'enregistrements. Ce classement consiste à ordon-5 ner à la commande d'un calculateur, leé enregistrements d'un fichier suivant une succession binaire qui correspond à l'ordre de leurs indicatifs. Le terme "classement" doit être considéré aussi bien comme désignant une mise en ordre dans le sens direct qu'une mise en ordre dans le sens inverse. Si par exemple les indi-10 catifs sont les lettres de l'alphabet, le classement peut s'effectuer dans l'ordre alphabétique ou dans l'ordre inverse. Il existe en effet des cas où il est préférable de classer les données dans l'ordre inverse plutôt que dans l'ordre direct. Le procédé habituel de classement en direct des enregis-15 trements de données est appelé "interclassement^'. En général, les enregistrements sont manipulés avec leurs indicatifs. Mais dans certains cas, les indicatifs seuls sont classés et sont associés ensuite à leurs enregistrements respectifs. Selon ce procédé, les indicatifs, ou codes de commandes, sur lesquels 20 repose le classement, sont lus dans l'enregistrement et combinés avec les adresses d'enregistrements, appelées quelquefois étiquettes, de manière à constituer des enregistrements d'indicatifs. Ce sont ces enregistrements d'indicatifs qui sont classés et qui constituent ensuite un index permettant de retrouver 25 ultérieurement les enregistrements de données dans l'ordrë voulu. Ces procédés sont décrits plus en détail dans la publication "Sorting Technique" numéro C 20-1639-0, édité par International Business machines Corporation, 1965. Dans le premier cas, une opération ou un programme d'inter-30 classement comporte les deux phases, ou sous-programme, ci-après : Une première phase de formation de séries au cours de laquelle un groupe d'enregistrements de données est lu dans la mémoire interne de l'unité de traitement."Cette dernière ordonne le groupe par "classement en mémoire interne", par exemple selon les 35 procédés de comparaison ou de valorisation d'indicatifs. Le groupe est ensuite enregistré dans tine-mémoire de réserve sous forme d'une série ordonnée. Le processus est répété avec le groupe suivant qui est enregistré dans une autre partie de la mémoire de réserve et ainsi de suite jusqu'à ce que tous les enregistrements du 40 fichier soient classés en série. TJne seconde phase d'interclassement au cours de laquelle les séries ordonnées sont lues dans la mémoire de réserve par l'unité centrale de traitement qui, par classement en mémoire interne, interclasse les séries suivant l'ordre des indicatifs.En général, le 45 nombre des séries ordonnées dépasse la capacité de classement en mémoire interne et l'unité centrale doit procéder à plusieurs "passes " pour rassembler toutes les séries ordonnées en une seule. Les séries entièrement interclassées constituent le fichier final dans lequel les enregistrements de données sont dans l'ordre. 50 Dans le cas où seuls les indicatifs sont ordonnés, le prin cipe de l'interclassement reste le même. que Ces deux formes d'interclassement présentent l'inconvénient/ la phase d'interclassement des séries prend du temps, particulièrement lorsque de nombreuses passes sont nécessaires. 55 La présente invention concerne un procédé perfectionné se lon lequel il est possible de classer un fichier dont le nombre d'enregistrements dépasse la capacité interne du dispositif. Le 72 04756 a 2125433 classement est effectué par un calculateur numérique qui comporte une unité de mémoire, une unité arithmétique, un dispositif de commande, une unité de sortie et un fichier d'entrée d'enregistrements de données identifiés chacun par un indicatif à plusieurs 5 caractères. Le procédé selon l'invention consiste à lire les enregistrements du fichier et à examiner la valeur des caractères de leurs indicatifs au moyen du dispositif de commande, de manière à produire un premier groupe de signaux qui représentent la distri-10 bution des valeurs d'indicatifs des enregistrements du fichier ; à enregistrer ce premier groupe de signaux dans l'unité de mémoire ; à traiter ce premier groupe de signaux par le dispositif de commande et à en déduire un second groupe de signaux qui représentent les valeurs limites des caractères d'un index et à définir 15 ainsi des secteurs de l'étendue totale des valeurs d'indicatifs, de manière que, selon la distribution de ces derniers, chaque section contienne le même nombre d'enregistrements ; à enregistrer dans l'unité de mémoire le second groupe de signaux représentant les secteurs ; à comparer, au moyen .du dispositif de com-20 mande, les caractères d'indicatifs de chaque enregistrement avec l'index, de manière à déterminer le secteur auquel appartient chaque indicatif ; à identifier chaque indicatif par l'une de plusieurs étiquettes de désignation indiquant le secteur f et à classer les indicatifs dans chaque secteur identifié par une 25 étiquette de désignation, en fonction des valeurs de ces indicatifs, de manière que le classement de ces derniers dans chaque secteur forme un fichier ordonné terminé. L'invention concerne également un dispositif de traitement de données qui comporte une unité de traitement, une mémoire inter 30 ne qui conserve les données traitées par l'unité de traitement ainsi que les instructions de programme correspondantes, une mémoire de réserve destinée à fournir à la mémoire interne des données qui doivent -être traitées et à en recevoir les données trai tées, et un dispositif d'entrée qui conserve un certain nombre d'enregistrements non classés comportant chacun un indicatif d'identification. Le dispositif destiné à classer les enregistrements en fonction des valeurs de leurs indicatifs respectifs comporte : un dispositif qui transfère au moins une partie des indicatifs du dispositif d'entrée à la mémoire interne ; un dispositif qui commande l'unité det,! traitement de manière qu'elle traite cette partie d'indicatif et qu'elle calcule et enregistre dans la mémoire interne une représentation de la distribution des 11 04756 2125433 valeurs de tous les indicatifs ; un dispositif qui commande l'unité de traitement, de manière, qu'en fonction de cette représentation, elle introduise dans la mémoire interne un index constitué par la succession ordonnée de secteurs de valeurs d'indi-5 catifs dont le nombre est estimé de manière à être à peu près le même dans chaque secteur ; un dispositif qui compare la valeur- de chaque indicatif avec l'index et qui produit un indice du secteur d'index auquel correspond l'indicatif; un dispositif qui place tous les indicatifs et leur indice correspondant 10 dans la mémoire de réserve ; un dispositif qui vtransfère à la mémoire interne tous les indicatifs portant le même indice ; et un dispositif qui commande l'unité de traitement de manière qu'elle classe tous les indicatifs du même indice contenus simultanément dans la mémoire interne. 15 Selon un mode de réalisation, le classement en direct, par une unité de traitement, d'un fichier d'enregistrement de données dans lequel chaque enregistrement est identifié par un indicatif, comporte les phases suivantes , estimation et mémorisation de la distribution des enregistrements de données dans le 20 fichier en fonction de leurs indicatifs j formation et mémorisation d'un index qui divise l'étendue totale maximale des valeurs d'indicatifs en secteurs consécutifs dont les valeurs limites, en fonction de l'estimation de la distribution drenregistrementi sont telles qu'à peu prè^ le même nombre déterminé d'enregistrements 25 se situe dans chaque secteur ; détermination du secteur correspondant à chaque enregistrement de données, par rapport à l'index mémorisé, suivie de la mémorisation des informations d'identification ; classement, en fonction de l'ordre des indicatifs, de chaque groupe constitué par ceux des indicatifs d'un même sec-30 teur, ainsi qu'ils ont été déterminés à partir des informations d'identification mémorisées, les groupes étant classés dans un ordre qui correspond à l'ordre des valeurs limites d'indicatifs. Les enregistrements de données sont ainsi rassemblés en un fichier ordonné. 35 De même que selon le procédé courant d'interclassement, il est possible de classer des enregistrements de données avec leurs indicatifs ou de ne classer que ces derniers. Il est 11 04756 4 2125433 également possible de classer les indicatifs avec une partie seulement des enregistrements de données. Dans tous les cas, le classement effectué de cette manière permet de faire une économie appréciable de temps par rapport à l'interclassement, 5 particulièrement en raison de la suppression de la phase d'interclassement des séries avec ses passes successives. L'invention sera décrite plus en détail en regard des dessins annexés à titre d'exemple nullement limitatif et sur lesquels : 10 la figure 1 représente schématiquement un dispositif de trai tement de données destiné à procéder à l'opération de classement, la figure 2 représente schématiquement la disposition logique du dispositif de travail de la figure 1 î les figures 3a à 3g montrent schématiquement la manière se-15 Ion laquelle l'estimation est effectuée. Selon le présent procédé, le classement par l'unité centrale de traitement s'effectue de la manière suivante : L'unité centrale lit les indicatifs des enregistrements de données des fichiers dans sa mémoire interne et produit une es-20 timation de la distribution de ces enregistrements en fonction de leurs indicatifs. L'unité de traitement enregistre l'estimation, de préférence mais pas nécessairement, dans sa mémoire interne en vue de son utilisation immédiate. L'unité centrale de traitement produit un index et l'en-25 registre dans sa mémoire interne ou dans la mémoire de réserve. L'index est produit de manière que l'étendue totale maximale des valeurs d'indicatifs soit divisée en secteurs consécutifs dont les valeurs limites sont telles que, selon l'estimation de la distribution des enregistrements, chaque secteur contienne à peu près 30 le même nombre prédéterminé d'enregistrements. L'unité centrale s'assure de l'index du secteur correspondant à chaque enregistrement en fonction de son indicatif, après quoi cet indicatif est enregistré dans une mémoire de réserve avec l'information d'identificateur qui indique que l'en-35 registrement se situe dans ce secteur. L'unité centrale de traitement classe chaque groupe d'indicatifs d'un même secteur, ainsi que déterminé dans la mémoire de Il Ui/ou V 2V2h4i3 réserve précitée, et en fonction de l'ordre des indicatifs. Les groupes sont classés dans un ordre qui correspond à l'ordre des valeurs limites de leurs indicatifs. Enfin, lorsque l'unité centrale de traitement a terminé 5 le classement de chaque groupe, elle inscrit les indicatifs classés de chaque groupe sous forme d'un fichier ordonné. Le nombre prédéterminé d'enregistrements de données que contient chaque secteur correspond de préférence au nombre maximal d'enregistrements qui peuvent être classés par l'unité 10 de traitement^par classement par mémoire interne. C'est-à-dire que la capacité de la mémoire interne doit être suffisante pour conserver tous les enregistrements qui doivent être classés à un moment donné, pour fournir l'espace de travail nécessaire selon le procédé de classement interne choisi et pour 15 mémoriser le programme ou sous-programme de classement. Si l'estimation de la distribution est exacte, chaque secteur d'enregistrement de données, ou d'indicatifs s'ils sont seuls classés, se situe juste dans la capacité de classement en mémoire interne de l'unité de traitement. 20 L'estimation peut s'effectuer selon un certain nombre de procédés, différents. Par exemple, la distribution d'un échantillon représentatif des enregistrements de données dans le fichier peut être déterminée ou estimée et l'estimation peut être basée sur cette distribution, par exemple selon un échantillonnage à 25 intervalles fixes. Il est possible aussi que les indicatifs de tous les enregistrements du fichier soient lus et.que leur distribution soit estimée selon un procédé d'approximation bien connu," par exemple par échantillonnage aléatoire. Selon un procédé d'estimation particulièrement avantageux, 30 l'unité de traitement de données prélève tour à tour chacun des indicatifs ou chacun des indicatifs de l'échantillon si l'estimation s'effectue sur un échantillon. Elle détermine ensuite les caractères, ou le groupe de caractères, le plus significatif de l'indicatif. Avec certaines structures de fichier, il est ocmmode 35 et plus rapide de considérer simultanément des groupes de caractères plutôt que des caractères isolés. L'unité de traitement examine ensuite le contenu d'un compteur destiné à compter le 72 04756 2125433 nombre d'indicatifs dans un caractère ou groupe de caractères le plus significatif, afin de s'assurer si le contenu du compteur a déjà atteint une valeur prédéterminée inférieure au nombre d'indicatifs sur lesquels l'unité centrale peut procéder 5 au classement en mémoire interne. Si le contenu du compteur n'a pas atteint la valeur prédéterminée, l'unité de traitement lui ajoute une unité de manière à compter l'indicatif et recommence l'opération sur l'indicatif suivant jusqu'à ce qu'ils aient tous été examinés. Si le contenu du compteur a atteint la valeur 10 prédéterminée, l'unité de traitement détermine le caractère ou groupe de caractères, le plus significatif suivant de l'indicatif, examine le contenu d'un compteur destiné à compter le nombre des indicatifs dont les deux caractères ou groupes de caractères sont le premier et le second plus significatifs, de 15 manière à" déterminer si le contenu du compteur a déjà atteint une valeur prédéterminée qui est également inférieure au nombre des indicatifs sur lesquels l'unité centrale peut procéder au classement en mémoire interne. Si le contenu du compteur n'a pas atteint cette valeur, l'unité de traitement lui ajoute une unité 20 de manière à compter l'indicatif et recommence l'ensemble du processus sur l'indicatif suivant jusqu'à ce qu'ils aient été tous examinés et que le contenu du compteur ait atteint sa valeur. L'unité de traitement détermine ensuite le caractère ou groupe de caractères le plus significatif suivant en plus de ceux men-25 tionnés précédemment, et avec un autre compteur, tant que le contenu d'un compteur n'a pas atteint une valeur prédéterminée. Ce contenu est augmenté d'une unité afin de compter l'indicatif et le processus recommence au début sur l'indicatif suivant, et ainsi de suite. 30 Ce procédé constitue un "comptage par embranchements successifs" car, lorsque le contenu de l'un quelconque des compteurs atteint la valeur prédéterminée, la présence d'un. autre indicatif introduit un embranchement de ce compteur vers un autre. Si le compteur précédent comptait les indicatifs dont 35 seuls les premiers "n" caractères les plus significatifs étaient des caractères déterminés, le nouveau compteur ne compte que les indicatifs comportant ces caractères déterminés et le caractère, 72 04756 7 2125433 ou groupe de caractères, le plus significatif suivant qui est le même que celui de l'indicatif qui a provoqué l'embranchement vers le nouveau compteur. Ce nouveau compteur est donc plus sélectif que le précédent. 5 II en résulte que si l'indicatif suivant comporte les mêmes "n" premiers caractères les plus significatifs, mais que le caractère, ou groupe de caractères, plus significatif suivant diffère de celui de l'indicatif qui a provoqué l'embranchement vers le nouveau compteur, un autre embranchement est emprunté 10 vers un autre compteur qui compte 1'indicatifs suivant . A partir d'un même compteur, plusieurs embranchements peuvent donc diverger vers des compteurs correspondants, à partir desquels d'autres embranchements peuvent diverger à leur tour formant ainsi un "arbre de nofe'l". 15 A la fin du processus d'estimation, les compteurs qui ont été utilisés contiennent les nombres d'indicatifs. Bien entendu, tout compteur qui aiguille vers un autre compteur contient la valeur prédéterminée lorsque sa capacité a été dépassée.Ainsi qu'il ressortira par la suite, ces nombres d'indicatifs mémorisés dans 20 les compteurs représentent une estimation de leur distribution. Pour toute distribution donnée, la précision de l'estimation dépend des valeurs prédéterminées de dépassement permises aux compteurs, la réduction de ces valeurs, avec l'augmentation résultante du nombre des compteurs nécessaires, augmente la 25 précision de l'estimation. •Selon le procédé d'estimation par caractère qui vient d'être décrit, le compteur qui est utilisé lorsqu'un autre compteur d.épasse sa capacité ne compte que les indicatifs dont les "n + 1" caractères les plus significatifs sont les mêmes que ceux 30 de l'indicatif qui a aiguillé vers le nouveau compteur. Il est cependant possible de diviser l'étendue des caractères qui peuvent se présenter dans les secteurs. Le nombre maximal d'embranchements qui peuvent diverger à partir d'un compteur lorsqu'il dépasse sa capacité est donc réduit et le nombre maximal de 35 compteurs est alors moins important. La précision du processus d'estimation en est réduit, mais peut néanmoins être satisfaisante dans certaines applications. Le même principe peut également 72 Ô4756 8 2125433 être adopté dans le processus d'estimation de groupes de caractères mentionnée précédemment. Après avoir procédé à l'estimation de la manière décrite ci-dessus, l'unité de traitement de données peut alors produire 5 l'index. Pour ce faire, elle sélectionne d'abord ceux des compteurs dont le contenu n'a pas été augmenté jusqu'à leur valeur prédéterminée au cours de la procédure d'estimation, c'est-à-dire ceux des compteurs qui ne donnent naissance à aucun embranchement. Ii'unité de traitement augmente ensuite le contenu de 10 chacun de ces compteurs d'une quantité à peu près égale au nombre d'indicatifs supplémentaires qui devraient être ajoutés si le contenu du compteur ne comportait pas une valeur supérieure ou prédéterminée, s'il n'existait aucun compteur moins sélectif et si les indicatifs comptés réellement par chacun, des compteurs 15 moins sélectifs étaient supposés être également distribués entre le ou les compteurs situés sur des embranchements partant du compteur moins sélectif. l'unité de traitement additionne ensuite les nombres d'indicatifs augmentés de chaque compteur sélectionné dans un ordre qui est le même que l'ordre des caractères 20 significatifs des indicatifs comptés par le compteur, jusqu'à ce que le nombre de ces indicatifs, représenté par la somme des nombres, soit proche de la capacité de classement en mémoire interne de l'unité de traitement. Cette dernière met ensuite en mémoire une indication du ou des caractères significatifs, 25 représentés par le dernier nombre additionné, ce ou ces caractères représentant l'une des valeurs limites de chacun de deux secteurs consécutifs. Ces opérations sont répétées jusqu'à ce que l'étendue totale maximale des valeurs d'indicatifs soit divisée en secteurs consécutifs. 30 L'index est donc produit et il peut être mémorisé, soit dans la mémoire interne en vue de son utilisation immédiate, soit dans la mémoire de réserve. Dans ce dernier cas, il est normalement mémorisé sous une forme fragmentée. L'opération suivante consiste à rapporter chacun des indi-35 catifs à l'index de manière à déterminer le secteur auquel il appartient. Cette opération peut s'effectuer en une seule passe pour chaque indicatif, mais dans certains cas, il est préférable 72 04756 9 2125433 d'effectuer plusieurs passes dont la première consiste à comparer l'indicatif à la partie de l'index qui ne détermine qu'approximativement le secteur, c'est-à-dire d'une manière approchée. la précision de l'opération de comparaison est augmentée progressi-5 vement au cours des passes suivantes. L'information d'identification, c'est-à-dire le secteur correspondant à chaque enregistrement, est mémorisée et la manière selon laquelle cette mise en mémoire est effectuée a une influence considérable|sur la vitesse à laquelle l'opération de 10 classement est effectuée. Un procédé consiste à mémoriser l'enregistrement de données lui-même (ou seulement son indicatif) dans une mémoire de réserve et à enregistrer sa position avec l'information d'identification de secteur dans ce quijconstitue un plan de mémoire. Si la mémoire de réserve est constituée par 15 une unité de disques magnétiques, chaque cylindre de l'unité de disque peut comporter son propre plan de mémoire ainsi que les plans d'enchaînement des différents cylindres. Ce procédé conduit à un enchaînement, ou liaison indirecte des enregistrements de données ou d'indicatifs dans chacun des secteurs. Au 20 cours de la présente description, les enregistrements de données, ou seulement d'indicatifs, situés dans l'un quelconque des secteurs seront dans certains cas appelés "godets". Du fait qu'une estimation seulement, c'est-à-dire l'op->-posé d'une analyse précise, de la distribution des enregistrements 25 a été faite, il est possible que le nombre d'enregistrements ou d'indicatifs de l'un quelconque des secteurs, c'est-à-dire le nombre d'indicatifs d'un groupe comportant un identificateur de secteur commun, dépasse le nombre prédéterminé d'une quantité 30 suffisante pour être supérieur à la capacité de classement en mémoire interne de l'unité centrale. Si cela se produit, le dispositif de traitement de données applique un procédé de dépassement selon lequel l'unité centrale classe dans le groupe un nombre d'indicatifs égal à sa capacité de classement en mémoire 35 interne et ceux des indicatifs du groupe qui, en fonction de leur ordre et du sens de classement (direct ou inverse) doivent être classés avant que les autres indicatifs du groupe soient 72 04756 io 2125433 lus dans la mémoire interne de l'unité centrale. La détermination consiste à lire ce nombre d'indicatifs du groupe dans la mémoire interne, à détecter dans cette mémoire l'indicatif supérieur ou l'indicatif inférieur, à comparer tour à 5 tour chacun des autres indicatifs du groupe avec l'indicatif supérieur ou l'indicatif inférieur de la mémoire interne et, en fonction du résultat, à reclasser l'indicatif dans la mémoire avec les autres, après quoi les indicatifs résultants dans la mémoire interne sont classés et inscrits en un fichier de sor-10 tie. Cette opération est répétée autant de fois qu'il est nécessaire pour classer tous les indicatifs du groupe, seuls ceux d'entre eux qui n'ont pas été classés précédemment étant classés pendant chaque opération ultérieure. Le procédé de' dépassement consiste donc à classer les 15 parties supérieures ou inférieures (en fonction du sens du classement) du groupe d'indicatifs chargés dans la mémoire interne, à classer les indicatifs dans cette partie et à répéter l'opération sur la partie suivante du groupe jusqu'à ce que tous les indicatifs du groupe soient classés. Des dépassements de n'im-20 porte quelle valeur peuvent être traités, bien qu'il soit préférable d'éviter les dépassements importants dont le traitement est particulièrement coûteux en temps. Si le dépassement excède la capacité de classement de mémoire interne de l'unité centrale de moins de 50 un procédé 25 différent prenant moins de temps peut être appliqué. Selon ce procédé, le dispositif de traitement de données calcule le nombre d'indicatifs en excès sur la capacité de classement' en mémoire interne de l'unité centrale, ce qui implique que le nombre de réel d'indicatifs/ chaque groupe soit .compté. Le dispositif 30 de traitement lit ensuite dans la mémoire interne deux fois plus d'indicatifs dans le groupe que le nombre calculé d'indicatifs en excès. Il divise les indicatifs dans la mémoire en deux'sous-groupes de dimension égale dont l'un contient ceux des indicatifs qui, en raison de leurs valeurs d'indicatifs, doivent être classés 35 avant ceux de l'autre sôus-groupe (autrement dit l'un des sous-groupes contient les indicatifs inférieurs à tous les indicatifs 72 04756 11 2125433 de l'autre sous-groupe), le dispositif de traitement extrait de la mémoire les indicatifs de l'autre sous-groupe et les remplace par ceux des indicatifs du groupe qui n'ont pas été lus précédemment dans la mémoire. Il classe les indicatifs dans la 5 mémoire jusqu'à ce que tous ceux de l'un des sous-groupes soient classés et les inscrit dans un fichier de sortie, il lit dans la mémoire les indicatifs qui en ont été extraits précédemment et il continue à classer les indicatifs dans la mémoire jusqu'à, ce que tous les autres indicatifs du groupe soient classés. 10 Dans certains cas, il peut se produire qyie deux ou plu sieurs enregistrements dé données à classer ont le même indicatif et qu'en outre, ils doivent rester dans la même séquence. Dans ce cas, les indicatifs de ces enregistrements peuvent être "prolongés" afin d'identifier la séquence et l'opération de 15 classement est effectuée de manière que ces enregistrements . soient classés en fonction de l'ordre de leurs indicatifs "prolongés". Dans les cas où il est probable que des fichiers successifs d'enregistrement présentent la même distribution d'in-20 dicatifs, il "peut être possible de classer un second fichier à partir de l'index préparé pendant le classement du premier. Cela réduit évidemment de manière considérable le temps total du classement. Le dispositif de traitement de données destiné à effectuer 25 le classement selon l'invention peut être d'un type absolument courant. Par exemple, le calculateur Honeywell, série 200,peut, avec un programme de classement qui commande les circuits, mettre en oeuvre le procédé décrit. Le programme de classement peut être enregistré sur bande magnétique ou sur disque magnétique 30 sous forme de signaux qui représentent les séquences d'instructions qui doivent être exécutées par la partie commande de l'unité centrale. Un tel dispositif comporte un dispositif d'entrée, une unité centrale de traitement avec sa mémoire interne, une unité 35 arithmétique et une partie commande, me mémoire de réserve, un dispositif de sortie et un programme qui dirige la partie commande de manière qu'elle conditionne l'unité centrale qui classe les 72 04756 12 2125433 enregistrements de la manière décrite. Au lieu d'être commandées par programme enregistré, les opérations peuvent être dirigées par un programme partiellement ou complètement câblé. A titre d'exemple, le classement d'enregistrement selon 5 l'invention sera maintenant décrit en regard des dessins annexés. la figure 1 illustre schématiquement le dispositif de traitement de données. Il sera supposé à titre d'exemple que ce dispositif consiste en un calculateur numérique électronique, particulièrement le calculateur Honeywell série 200, qui exé-10 cute l'opération de classement sous la commande d'un programme. le calculateur comporte un dispositif d'entrée 1 qui est supposé être une unité de bande magnétique, une unité centrale de traitement 2, un dispositif de travail 3 qui constitue une mémoire de réserve qui sera supposée être une unité de dis-15 que magnétique et un dispositif de sortie 4 qui sera supposé être une unité de bande magnétique . l'unité centrale de traitement 2 comporte une partie commande 5, une mémoire interne 6 et une unité arithmétique 7. les connexions entre ces différents éléments et permettant la circulation des instructions et des 20 informations sont représentées schématiquement. Le dispositif est commandé, dans son opération de classement, par le programme de calculateur qui est enregistré sur une unité de disque magnétique (non représentée). Ce programme est transféré à la mémoire interne afin d'être exécuté par la par-25 tie commande 5. Le programme consiste en séquence de signaux représentant les instructions qui doivent être interprétées et exécutées par la partie commande 5. En général, les enregistrements qui doivent être classés dans un ordre correspondant à l'ordre de leurs indicatifs sont 30 fournis au dispositif sous la forme d'un fichier d'entrée enregistré sur bande magnétique (non représentée). A la commande du programme et au moyen du dispositif d'entrée 1, le dispositif de traitement lit ce fichier et, après en avoir classé les enregistrements, il les enregistre au moyen du dispositif de sortie 35 4 sous forme d'un fichier de sortie ordonné sur une autre bande magnétique (non représenté). L'opération de classement sera décrite dans ses grandes lignes d'abord et plus en détail ensuite. L'organigramme 72 04756 2125433 I montre clairement que la première phase consiste à "déterminer les valeurs initiales" c'est-à-dire à déterminer manuellement les niveaux d'opération du dispositif, en fonction des caractéristiques globales supposées du fichier d'entrée, en introduisant 5 par exemple des paramètres provenant de cartes de contrôle. Dans l'exemple présent, l'unité de traitement détermine à partir de là, les valeurs prédéterminées des contenus des compteurs et une valeur de dimension de "godets" à utiliser. Ces valeurs, en plus d'autres paramètres qui peuvent être nécessaires, sont mémorisées 10 dans des zones appropriées de la mémoire, ou dans des registres de l'unité de traitement. Ainsi que mentionné précédemment, la valeur de comptage détermine le nombre d'articles comptés dans chaque secteur avant de descendre au secteur immédiatement inférieur. La dimension des godets correspond à la capacité dis-15 ponible en tores, divisée par la longueur de l'article. Cette valeur peut être sous estimée de manière à réduire la possibilité de dépasser la capacité de classement interne de l'unité de traitement, c'est-à-dire le dépassement au moment du classement des articles dans les godets. 20 Pendant la phase suivante, le dispositif d'entrée 1 (fi gure 1) lit, à la commande du programme, le fichier d'entrée par l'intermédiaire de l'unité centrale 2, dans le dispositif de travail 5 où. il est écrit sous forme d'un "fichier de travail" (non représenté). 25 II faut noter que le fichier de travail comporte des espa ces appropriés destinés à la mise en place, ainsi qu'il sera décrit par la suite. Pendant l'opération de lecture, le programme dirige l'unité centrale de traitement de manière qu'elle estime la distribution des enregistrements en fonction de leurs indi-30 catifs. Cette estimation est enregistrée dans la mémoire interne 6. 72 Û47S6 14 2125433 ORGANIGRAMME 1 D^teradnation des valeurs initiales Lecture fichier d'entrée ^timation distribution des indicatifs Ecriture du fichier de travail Formation index ïTIi Exécution processus de dépassement Lecture fichier de travail Déterriination godet et étiquette d'indicatif Ecriture fichier de travail Lecture fichier de tra vail par godets Classement interne Ecriture fichier de sortie ÏÏH ARRET 72 04756 2125433 Ainsi que le montre l'organigramme 1, lorsque les enregistrements de données du fichier d'entrée ont été lus et que l'estimation a été faite, le programme ordonne à l'unité centrale de traitement de former un index qui, en fonction de l'estimation 5 de la distribution des enregistrements, divise l'étendue globale maximale des valeurs d'indicatifs en secteurs consécutifs dont les valeurs limites sont telles que chaque secteur contient approximati vement le même nombre prédéterminé d'enregistrements. Ce nombre prédéterminé est choisi égal au nombre maximum que l'unité centrale N 10 peut classer par classement en mémoire interne. L'index produit est enregistré dane la mémoire interne 6. Lorsque la formation d'index est terminée, le programme donne l'ordre à l'unité centrale de traitement de lire dans sa mémoire interne les enregistrements de données du fichier de travail, c'est-à-dire dans le dispositif de 15 travail 3» et de comparer chaque indicatif à l'index de manière à déterminer le secteur correspondant à chaque indicatif. L'enregistrement est alors associé (organigramme 1) à cette information d'identificateur, indiquant le groupe ou le sous-groupe auquel il appartient. L'enregistrement de données est ensuite mémo-20 risé à nouveau dans le dispositif de travail 3, avec l'information d'identificateur supplémentaire. Les enregistrements qui appartiennent au même secteur sont effectivement reliés par un identificateur de secteur commun, de manière à former un "godet" ainsi que mentionné précédemment. 25 La liaison mentionnée ci-dessus apparaît mieux sur la figure 2 qui montre schématiquement quatre cylindres de l'unité de disque magnétique constituant le dispositif de travail 3. Une partie de chaque cylindre est réservée à un plan 8, c'est-à-dire à une zone de mémoire qui, lorsque chaque enregistrement est mémo-30 risé sur ce cylindre, reçoit l'adresse de l'enregistrement (par exemple l'adresse des enregistrements 9 et 10) sur ce cylindre et également l'information d'identification de secteur spécifiant le godet auquel appartient cet enregistrement. Les plans servent donc à relier les enregistrements de chaque secteur ou les enregistre- • 35 ments que contient chaque godet. Les plans eux-mêmes sont reliés d'une manière similaire dans les cas où les enregistrements d'un godet sont distribués ou répartis entre plusieurs cylindres, ce qui 72 04756 16 2125433 est souvent le cas. Il faut noter bien entendu que, grâce à cette disposition d'indexage, les enregistrements appartenant au même godet peuvent être groupés de manière à réduire l1attente dans la suite du fonctionnement du dispositif. 5 A la fin de l'opération d'étiquetage, le dispositif de travail 3 contient an fichier de travail comportant un certain nombre de godets, ces godets contenant chacun un groupe d'enregistrements reliés indirectement et appartenant au même secteur. A la phase suivante, le programme ordonne à l'unité centrale 10 de lire les enregistrements du fichier de travail godet par godet, dans sa mémoire interne où les enregistrements de chaque godet sont classés tour à tour. L*ordre dans lequel les godets sont lus dans la mémoire de l'unité de traitement est déterminé par l'ordre des valeurs limites d'indicatifs car l'objet du classement consiste 15 à produire un fichier de sortie dans lequel les enregistrements de données sont dans un ordre correspondant à l'ordre de leurs indicatifs d'identification, lorsque les enregistrements de chaque godet sont lus dans la mémoire, l'unité de traitement détermine si la capacité de classement en mémoire interne a été dépassée et, si 20 c'est le cas, elle détermine si cette capacité a été dépassée de plus de 50 fo. Si l'unité de traitement n'a pas dépassé sa capacité de classement en mémoire interne, lorsque le godet a été lu dans la mémoire, l'unité centrale de traitement classe les enregistrements de données par classement en mémoire interne, par exemple par com-25 paraison. Après le classement, les enregistrements de données sont mémorisés sur la bande magnétique par le dispositif de sortie 4, sous forme d'une partie du fichier de sortie. Les enregistrements du godet suivant, déterminé en fonction de l'ordre des valeurs limites d'indicatifs, sont ensuite classés et ainsi de suite jus-30 qu'à ce que tous les godets soient classés. Si le contenu de l'un des godets dépasse la capacité de classement en mémoire interne de l'unité centrale, un ou deux processus de dépassemenVCorganigramme 1) sont exécutés. Le processus est choisi suivant que le dépassement est supérieur de plus ou a 35 moins 50 fi/la capacité de classement en mémoire interne. Si ce dépassement est inférieur à 50 $, un processus de dépassement moins 72 04756 17 2125433 coûteux en temps n'est appliqué que si le dépassement est supérieur à ce pourcentage. .Après avoir décrit dans ses grandes lignes l'opération de classement, chaque partie en sera maintenant décrite en détail en 5 commençant par l'estimation de la distribution des indicatifs. Ainsi que mentionné précédemment, l'estimation est effectuée, dans l'exemple présent, par embranchements successifs. L'explication de ce processus d'estimation est plus facile si les indicatifs sont supposés consister en lettres de l'alphabet, la signifi-10 cation des caractères décroissant de la gaucher vers la droite. Chaque indicatif est supposé comporter cinq caractères. Il sera également supposé que ces indicatifs doivent être classés dans l'ordre alphabétique plutôt que dans l'ordre inverse. Ainsi que le montre la figure 3a, le premier indicatif à 15 examiner est ACTIF. Le caractère le plus significatif de cet indicatif est la lettre A. Cet indicatif est compté par un compteur affecté au comptage des seuls indicatifs dont le caractère"le plus significatif est la lettre A. Ce compteur est représenté sur la figure 3a par un carré à l'intérieur duquel est inscrit son con-20 tenu. La figure 3b montre que le second indicatif examiné est APPUI. Le caractère le plus significatif est encore' la lettre A. Cet indicatif est donc encore compté par le compteur de la figure 3a dont le contenu passe à deux. 25 La figure 3c montre que le troisième indicatif examiné est APLAT. Le caractère le plus significatif de cet indicatif est encore A. Mais il est supposé que ce compteur ne peut pas compter au delà de deux, c'est-à-dire qu'il arrive au dépassement si son contenu dépasse deux. Un nouveau compteur est donc nécessaire pour compter l'indicatif Aplat. Ce compteur est plus sélectif que le 30 premier en ce qu'il ne compte que les indicatifs dont les deux caractères les plus significatifs sont respectivement A et P. La figure montre que le troisième indicatif fait passer à un le contenu de ce compteur. Le fait que le compteur A est en dépassement, est représenté par un cercle. 35 La figure 3d montre que le quatrième indicatif examiné est ACCES. Le compteur A a dépassé et il n'y a pas encore de compteur destiné à compter A et C comme premier et second caractères plus 72 04756 2125433 significatifs. Un nouveau compteur doit donc être attribué et son contenu passe à un. Du fait que l'indicatif suivant examiné est ACIDE, ainsi que le montre la figure 3e, le contenu de ce nouveau compteur passe à deux. 5 l'indicatif suivant examiné est ACIER, ainsi que le montre la figure 3f» qui provoque le dépassement du compteur AC. Un nouveau compteur est donc désigné pour compter les indicatifs dont les trois caractères les plus significatifs sont respectivement ACI. le contenu de ce nouveau compteur passe à un. 10 Enfin , le dernier indicatif examiné est BANDE. Du fait qu'il n'existe pas de compteur destiné à compter les indicatifs dont le caractère le plus significatif est B, il en est désigné un dont le contenu passe à un. Cet exemple montre la manière selon laquelle les embranche-15 ments successifs s'effectuent dans la mémoire interne à la commande du programme pendant le processus d'estimation. Il faut noter, en raison des références ultérieures, que ce comptage comporte un certain nombre de niveaux, à savoir quatre dans le cas particulier représenté sur la figure 3g. 20 En pratique, la valeur de dépassement des compteurs est de beaucoup supérieure à deux. Il faut également noter qu'en pratique, les compteurs affectés ne sont pas des dispositifs discrets de mémorisation, mais plutôt des positions de mémoire qui peuvent être choisies au hasard dans la mémoire interne. 25 la manière dont l'unité centrale de traitement procède à cette opération d'estimation sera maintenant décrite plus en détail en regard de l'organigramme 2. 72 04756 19 2125433 Sortie 72 04756 » 2125433 Quand un enregistrement est introduit dans l'unité centrale de traitement, cette dernière positionne ce qui sera appelé un "interrogateur d'indicatif", dans une position décalée d'un caractère à gauche du caractère de gauche, ou caractère le plus signi-5 ficatif de l'indicatif. En même temps, l'unité centrale met en place ce qui sera appelé un "interrogateur de structure de comptage" destiné à examiner, s'il y a lieu, la structure du comptage déjà présent dans la mémoire interne. Ainsi que le montre l'organigramme 2, l'interrogateur de structure de comptage est placé au 10 noeud d'origine des embranchements. Cela signifie qu'il est positionné de manière à examiner une position de mémoire qui corres-pont au premier embranchement, c'est-à-dire que, sur les figures 3a à 3g» l'interrogateur est positionné de manière à examiner les cercles correspondants les plus élevés. 15 Ainsi qu'il ressort clairement de la position de l'entrée dans le processus représenté par 1*organigramme 2, l'interrogateur d'indicatif est déplacé d'une position de caractère vers la droite de manière à lire la position du caractère le plus significatif de l'indicatif, après quoi l'interrogateur de structure de comptage 20 vérifie si le noeud d'origine contient une entrée correspondant à un comptage, à un aiguilleur, ou ni à l'un ni à l'autre, et correspondant à l'indicatif partiel (c'est-à-dire l'indicatif partiel A sur les figures 3a à 3f et l'indicatif partiel B sur la figure 3g) qui est lu par l'interrogateur d'indicatif. Le terme 25 "aiguilleur" désigne un indicateur d'entrée (c'est-à-dire une adresse) qui est déterminé lorsqu'un compteur a dépassé et qu'il aiguille vers un autre compteur (entrée de comptage) disposé un embranchement plus bas. Ces opérations effectuées par l'unité centrale de traitement ressortent mieux de l'examen des figures 3a 30 à 3g et de l'organigramme 2,ensemble. La figure 3a montre que l'interrogateur d'indicatif lit "A" et l'interrogateur de structure de comptage vérifie que le noeud d'origine contient une entrée d'indicatifs partiels "A", (le premier niveau d'embranchement au-dessous de l'origine est 35 agencé de manière à contenir des entrées de comptage jusqu'à ce qu'elles débordent et elles sont alors remplacées par des aiguilleur^. L'opération suivante effectuée consiste à vérifier si la 72 04756 2125433 valeur de dépassement a été atteinte. Dans cet exemple, cette valeur n'a pas été atteinte et un "un" est ajouté au comptage des A, ce qui termine les opérations concernant l'indicatif ACTIF. Sur la figure 3b, l'interrogateur d'indicatif lit à nouveau 5 "A" lorsqu'il a été déplacé d'un caractère vers la droite, l'interrogateur de structure de comptage trouve encore que le noeud d'origine contient une entrée de comptage correspondant aux indicatifs partiels "A". Une autre opération est donc effectuée afin de vérifier si la valeur de dépassement a été atteinte. Dans cet 10 exemple, elle ne l'a pas été et un autre "un" est ajouté au comptage des "A" terminant ainsi les opérations concernant cet indica- _ tif. Sur la figure 3c, lorsque l'opération de vérification de dépassement est effectuée, il est constaté que la valeur de dépassement a été atteinte, le comptage des "A" est donc remplacé par 15 un aiguilleur vers un nouveau compteur, (entrée de comptage), l'interrogateur d'indicatif est alors déplacé d'un caractère vers la droite, et il lit le caractère "P"'. Au cours de la phase suivante, une entrée de comptage est attribuée à l'indicatif partiel "AP", ce qui termine les opérations concernant l'indicatif AP1AT. 20 l'indicatif suivant est ACCES, ainsi que le montre la figure 3d, et il provoque le déroulement de phases différentes. C'est-à-dire qu'au moment où il examine le noeud d'origine, l'interrogateur de structure de comptage trouve un aiguilleur correspondant aux indicatifs partiels "A" (cet aiguilleur a été produit lorsque 25 le comptage "A" a dépassé). En conséquence, l'interrogateur de structure de comptage est déplacé afin d'examiner l'embranchement désigné par l'aiguilleur, c'est-à-dire qu'il est déplacé de manière à examiner l'embranchement "A", l'interrogateur d'indicatif est également déplacé d'un caractère vers la droite et il lit le 30 caractère "C". l'unité centrale de traitement vérifie ensuite si le noeud "A" contient une entrée de comptage, un aiguilleur, ou ni l'un ni l'autre, correspondant à l'indicatif partiel "AC". Il ne ' trouve évidemment ni l'un ni l'autre et une entrée de comptage est déterminée pour l'indicatif partiel "AC", ce qui termine les 35 opérations concernant cet indicatif. l'indicatif suivant sur la figure 3e est ACIDE et l'interrogateur de structure de comptage trouve à nouveau un aiguilleur 72 04756 22 2125433 pour les indicatifs partiels A. L'interrogateur de stucture de comptage est donc déplacé à nouveau afin d1examiner l'embranchement "A" et l'interrogateur d'indicatif est déplacé également d'un caractère vers la droite où il lit le caractère "0". L'unité cen-5 traie de traitement vérifie ensuite si l'embranchement "A" comporte une entrée de comptage correspondant à l'indicatif partiel AC. Elle vérifie ensuite si la valeur de dépassement a été atteinte. Dans cet exemple ce n'est pas le cas, et un autre, "un" est ajouté au comptage des "AC" ce qui termine les opérations concernant l'indi-10 catif ACIDE. Ainsi que le montre la figure 3f» l'indicatif suivant est ACIER, et le processus est le même que celui qui vient d'être décrit à propos de l'indicatif ACIDE , à la différence près qu'il est constaté que la valeur d^dépassement a été atteinte dans le comptage des AC. L'entrée de comptage AC est alors remplacée par 15 un aiguilleur vers une nouvelle entrée de comptage. L'interrogateur d'indicatif est alors déplacé d'un caractère vers la droite,où il lit le caractère "I" et un comptage est' formé pour l'indicatif partiel "ACI", ce qui termine les opérations concernant l'indicatif ACIER. 20 Enfin, l'indicatif BARDE est maintenant reçu ainsi que le montre la figure 3g, et l'interrogateur d'indicatif lit l'indicatif partiel "B". L'interrogateur de structure de comptage vérifie si le noeud d'origine contient une entrée de comptage pour cet . indicatif partiel. Du fait que cette entrée existe, l'opération 25 de vérification de dépassement est effectuée et, puisqu'il est constaté que la valeur de dépassement n'a pas été atteinte, un "un" est ajouté au comptage des "B". Lorsque tous les indicatifs ont été soumis à ces opérations, la mémoire interne contient des positions de mémorisation qui 30 désignent un nombre de comptages de dépassement et des entrées de comptage qui désignent un nombre de comptages partiels, chacun de ces comptages représentant des indicatifs qui contiennent des indicatifs partiels déterminés. La phase suivante consiste à produire un index à partir de ces comptages. 72 04756 23 2125433 OKGAhIGRAKIHE 72 04756 2125433 la manière selon laquelle un index est formé, sera maintenant décrite en regard de l'organigramme 3. La description du processus de formation d'index est considérablement facilitée si l,on considère d1abord un exemple et, pour cette raison, la forma-5 tion d'un index à partir de la structure d'embranchement de la figure 3g sera décrite. La première phase du processus de formation d'index consiste à positionner l'interrogateur de structure de comptage de manière qu'il examine le noeud d'origine de la représentation par embranchements enregistrée de la mémoire in-10 terne, afin de vérifier q'il consiste en une entrée de comptage ou en un aiguilleur, (ce qui peut se faire par l'examen de certaines positions d'éléments binaires dans la position de mémoire spécifiée). La figure 3g montre que l'interrogateur de structure de comptage trouve deux aiguilleurs. L'adresse duvpremier aiguilleur 15 de la séquence de classement (c'est-à-dire l'aiguilleur désigné par A) est mémorisée dans une file d'attente. L'autre aiguilleur B est ignoré à cet étage. L'interrogateur de structure de comptage est ensuite déplacé de manière à examiner l'embranchement désigné par le premier ai-20 guilleur, c'est-à-dire qu'il est descendu pour examiner le niveau 2. En outre, la valeur de dépassement distribuée, (si elle existe), est calculée. Cet élément peut être ignoré pour le moment car, à cet état du fonctionnement,il est nul. En- outre, le comptage total courant S est également nul. L'interrogateur de structure de 25 comptage trouve deux aiguilleurs à l'embranchement du niveau 2 qu'il examine. L'adresse du premier aiguilleur de la séquence de classement (c'est-à-dire l'aiguilleur AC) est mémorisée dans la file d'attente et l'autre aiguilleur désigné par AP est ignoré. l'interrogateur de structure de.comptage est ensuite dé-30 placé de manière à examiner l'embranchement désigné par l'aiguilleur AC, c'est-à-dire qu'il est descendu afin d'examiner le niveau 3. En outre, le dépassement distribué est calculé. Ce terme est défini comme le nombre d'indicatifs supplémentaires que chaque compteur d'un niveau quelconque aurait compté si les comp-35 teurs ne comportaient pas de valeur de dépassement, s'il n'y avait aucun compteur moins sélectif et si les indicatifs réellement comptés par chacun de ces compteurs moins sélectifs avaient été 72 04756 25 2125433 distribués également entre le où les compteurs aiguillés à partir de ce compteur. Dans le présent exemple, ce terme est égal à xin car le compteur "A" comporte une valeur de dépassement égale à 2 et deux embranchements. Un total égal à l'unité est donc mémorisé comme comptage total courant T. lorsque 1*interrogateur de structure de comptage examine en-suitè le noeud désigné par l'aiguilleur AC, il trouve encore un aiguilleur, l'adresse de ce dernier, désignée par ACI, est mémorisée dans la file d'attente. l'interrogateur de. structure de comptageXest ensuite déplacé de manière à examiner l'embranchement désigné par l'aiguilleur ACI,_ c'est-à-dire qu'il est descendu afin-d'examiner le niveau 4. En outre, la valeur de dépassement distribuée additionnelle est calculée. Il est visible qu'elle est égale à deux car il faut supposer que tous les indicatifs qui ont provoqué le dépassement du compteur AC étaient des indicatifs "AGI". Cette valeur est mise en mémoire et porte à trois le comptage total courant T. l'interrogateur de structure de comptage constate que l'embranchement au niveau 4- qu'il examine comporte une entrée de comptage égale à un. Cette valeur est ajoutée au contenu mémorisé faisant passer à quatre le comptage total courant T. la phase suivante consiste à comparer cette valeur de quatre avec la dimension voulue du godet, c'est-à-dire la zone de mémoire destinée au nombre d'enregistrements de chaque secteur consécutif. Afin de simplifier la description, il sera supposé initialement que là dimension prévue du godet est également 4. Dans ce cas, l'interrogateur de structure de comptage vérifie s'il existe un autre embranchement à partir du noeud AC et constate qu'il n'y en a pas. Il vérifie ensuite s'il existe un noeud plus élevé et constate qu'il en existe un, à savoir le noeud "A". Ensuite, l'adresse de l'aiguilleur vers ce noeud, avec la valeur de dépassement distribuée associée, égale à l'unité, est extraite de la file d'attente. l'interrogateur de structure de comptage constate'qu'il existe un embranchement à partir du noeud A et il est déplacé afin d'examiner cet embranchement, le comptage total courant T qui est encore égal à 4 est ajouté à la valeur de dépassement distribué qui vient d'être extraite et qui ^est égale à l'unité, ce qui porte à cinq le .comptage total courant. n 647 M 2125433 Lorsqu'il examine l'embranchement précité, l'interrogateur de structure de comptage constate que le noeud examiné est une entrée de comptage, à savoir le comptage 11AP". La valeur qu'il contient est alors ajoutée au comptage total courant ï qui passe 5 à six. Cela dépasse la dimension prévue du godet. Par conséquent, l'indicatif partiel correspondant au dernier comptage à ajouter, c'est-à-dire l'indicatif partiel AP est conservé dans une partie de la mémoire interne. Cet indicatif partiel constitue une partie de l'index car il est évident qu'il constitue l'une des valeurs 10 limites mentionnées, précédemment des secteurs, ou godets. En d'autres termes, tous les indicatifs partiels au-dessous de AP, c'est-à-dire les indicatifs partiels précédents tels que AC et ACI sont, en fonction de l'index, groupés ensemble dans le même godet tandis que tous les indicatifs AP et au-dessus sont placés dans un ou plu-15 sieurs autres groupes. Le processus de formation d'index se poursuit de la manière décrite ci-^après afin de déterminer combien de ces autres groupes sont nécessaires. La phase suivante consiste à soustraire du comptage total courant T, égal à six, sa valeur précédente, c'est-à-dire cinq, 20 ce qui donne une nouvelle valeur égale à un de ce comptage total courant. L'interrogateur de structure de comptage vérifie ensuite s'il existe une autre branche après le noeud "A" et constate qu'il en existe une. Il vérifie ensuite s'il existe un noeud supérieur et trouve qu'il en existe un, à savoir le noeud- d'origine. L'adresse 25 de l'aiguilleur du noeud d'origine est extraite de la file d'attente avec la valeur de dépassement distribuée associée qui est égale à zéro. L'interrogateur de structure de comptage constate qu'il existe une autre branche à partir du noeud d'origine, à savoir l'embranchement vers le oompteur "B" et-il est déplacé de manière à 30 examiner cet embranchement. En ce faisant, il trouve un comptage d'une unité. Cette valeur est ajoutée au comptage du total courant T égal à un ce qui donne un nouveau comptage total oourant égal à deux. Ce nombre est inférieur à la dimension prévue du godet. Il est alors déterminé qu'il n'existe aucun autre embranchement à 35 partir du noeud d'origine et qu'il n'exixte aucun noeud supérieur. Par conséquent, l'ensemble des embranchements successifs ont été soumis à la formation d'index et l'opération est terminée. 72 04756 27 2125433 Afin de mieux faire comprendre le principe du processus de formation d'index, il va être examiné maintenant ce qui se serait produit si la dimension prévue du godet avait été deux . au lieu de quatre. La procédure aurait été la même jusque, et y 5 compris, l'addition du comptage "AGI" égal à un au comptage total à trois. Après la comparaison suivante avec la dimension prévue du godet, l'indicatif ACI est mémorisé dans une partie de la mémoire interne, comme une partie de l'index. La valeur précédente du comptage total courant, à savoir 10 trois, est ensuite soustraite ce qui donne un noùyeau comptage total courant T égal à un. L'interrogateur de structure de comptage aurait alors constaté qu'il n'y a pas d'autres embranchement partant du noeud "AC" mais qu'il éxiste un noeud supérieur, à savoir le noeud "A". L'adresse de ce noeud et la valeur de dépassement 15 distribuée qui est nulle,auraient été extraits de la file d'attente Comme il existe un autre embranchement partant de ee noeud, à savoir l'embranchement vers le comptage "AP", l'interrogateur de structure de comptage aurait été déplacé afin d'examiner cet embranchement. Il aurait trouvé un comptage d'une unité qui aurait 20 été ajoutée au comptage total courant T qui serait passé à deux. Du fait que cette valeur est égale à la dimension prévue du godet, l'indicatif partiel "AP" n'est pas maintenu comme partie de l'index. Du fait qu'il constate qu'il n'existe aucune autre branche partant du noeud "A",' l'interrogateur de structure de comptage 25 est déplacé de manière à examiner l'embranchement vers le comptage "B" où il trouve un comptage d'une unité.Cela augmente le comptage total courant T jusqu'à trois et l'indicatif partiel B est donc maintenu dans la mémoire interne comme une partie de l'index. L'index divise donc effectivement les indicatifs en trois 30 secteurs ou en trois godets, à savoir un godet qui contient les indicatifs partiels jusqu'à ACI, un godet qui contient les indicatifs partiels de ACI jusqu'à B et un godet qui contient les indicatifs partiels B et au-dessus. L'examen des indicatifs réels montre que le premier godet contient deux indicatifs (ACTIF et ACCES) 35 le second contient quatre indicatifs (APPUI, APLAT, ACIDE et ACIER) et le troisième contient un indicatif (BAKDS). Une opération de dépassement devra donc avoir lieu pendant le classement du second godet. 72 04756 28 2125433 Les deux processus différents de dépassement seront maintenant décrits en commençant par celui appliqué lorsque le nombre d'enregistrements de donnéeô contenus dans un godet dépasse de plus de 50 la capacité de classement en mémoire interne de l'unité centrale. Cette description sera faite en regard de ^organigramme 4. 72 04756 29 2125433 Sortie 72 04756 2125433 Au cours de la première phase, le contenu du godet est lu par l'unité centrale de traitement jusqu'à ce que le nombre maximal d'enregistrements qui peuvent être classés par classement en mémoire interne soit enregistré dans la mémoire. Au lieu 5 de classer ensuite les enregistrements, ce qui serait fait en l'absence de dépassement, l'indicatif le plus élevé (c'est-à-dire le dernier dans l'ordre alphabétique ou celui qui porte le numéro le plus élevé) contenu dans la mémoire interne est déterminé. Tous les enregistrements qui restent dans le godet sont alors lus tour 10 à tour dans la mémoire et leurs indicatifs sont comparés avec l'indicatif le plus élevé enregistré dans la mémoire interne. Si l'indicatif de l'enregistrement de données introduit est supérieur, il est ignoré. Si au contraire, il est inférieur, cet enregistrement remplace celui d'indicatif plus élevé se trouvant déjà dans la 15 mémoire. le processus ci-dessus se poursuit jusqu'à ce que tous les enregistrements du godet complet soient lus. l'indicatif le plus élevé de la mémoire est ensuite enregistré. Pendant ce temps, les enregistrements enregistrés dans la mémoire sont classés par clas-20 sement en mémoire interne et deviennent disponibles pour être écrits dans le fichier de sortie. le godet est ensuite lu à nouveau (ainsi qu'il apparaît sur l'organigramme 1) et l'opération suivante est répétée. Tous ceux des enregistrements dont l'indicatif est inférieur à l'indicatif 25 le plus élevé enregistré sont ignorés car ils ont déjà été classés, le lot suivant d'enregistrements de données est donc classé. Ce processus est répété autant de fois qu'il est nécessaire pour classer l'ensemble du godet. 72 04756 31 2125433 ORGANIGRAMME 5 72 04756 32 , 2125433 L'organigramme 5 illustre une procédure de dépassement moins coûteuse en temps qui est appliquée si le nombre des enregistrements d'un godet dépasse de moins de 50 $ la capacité de classement en mémoire interne de l'unité de traitement. 5 la première phase consiste à calculer le nombre d'enregis trements de données en excès. Le double de ce nombre est ensuite lu dans le godet par la mémoire interne. Il est évident que cela remplirait la mémoire interne si l'excès était réellement de 50 fo. Les enregistrements de la mémoire interne sont ensuite divi-10 ses en deux sous-groupes d'égales dimensions, les enregistrements de l'un des sous-groupes comportant tous des indicatifs qui sont inférieurs aux indicatifs de l'autre sous-groupe. L'autre sous-groupe dTenregistrements est alors effacé et son indicatif le plus bas est mémorisé. Les autres enregistrements de données sont ensuite 15 lus dans la mémoire interne. Les enregistrements de données qui se trouvent maintenant dans la mémoire interne sont classés par classement en mémoire interne et sont ensuite écrits dans le fichier de sortie. Ensuite, le sous-groupe d'enregistrement effacé est lu à nouveau dans la 20 mémoire interne, de manière à remplacer ceux qui viennent d'être classés, ce qui s'effectue en relisant à nouveau une partie du godet,, ainsi qu'il ressort de l'organigramme 1. Le classement en mémoire interne est effectué sur ces enregistrements, après quoi ils sont écrits dans le fichier de sortie, ce qui termine les opé-25 rations concernant ce godet. Afin d'éviter de surcharger inutilement la description par les choses qui sont connues des spécialistes, un diagramme général a été donné, suivi d'une description fonctionnelle de chaque bloc et de l'identification spécifique des éléments qu'il représente. 30 D'autres informations sur la manière dont sont constitués les différents équipements ainsi que la programmation y afférent , peuvent se trouver dans les textes des Brevets et publications ci-après : 200 , , "Series/Programmers ' Reference Manual Models 200/1200/ 2200/4200", publié par Honeywell Incorporation le 10 novembre 35 1966, N° d'ordre 139, Copyright 1968. "Honeywell Sériés 200 M0D1 (MSR) Data Management Subsystem", publié par Honeywell Incorporation le 3 décembre 1968, Copyright 72 04756 33 2125433 1968, 1969, 1970 par Honeywell Incorporation, Copyright 1971 par Honeywell Information Systems Inc. Les brevets des Etats-Unis d'Amérique N0 3 331 056 et 3 323 110. 5 "Sorting Techniques - C20-1639, International Business Machines, Data Processing Division, White Plains, ffew-York (1965). . Volume 1 Fondamental Algorithms, The Art of Computer Pro-gramming par Donald E. Knuth, Addison-Wesley, Publishing Company, Copyright 1968. 10 II va de soi que de nombreuses modifications peuvent être apportées au procédé décrit et représenté sans sortir du cadre de • l'invention. Par exemple, ainsi qu'il a été mentionné, le procédé selon la présente invention peut être appliqué au classement d'enregistrements en n'utilisant que leurs .indicatifs, ou à partir d'un 15 index d'enregistrements d'indicatifs. Dans certaines applications où il n'est nécessaire de retrouver que peu d'enregistrements à la fois, ces derniers peuvent être situés par une recherche dans l'index des indicatifs classés. Cela évite d'avoir à lire l'enregistrement complet dans un groupe de mémoire pendant l'opération de 20 classsment et d'écrire ensuite les enregistrements classés dans un dispositif de sortie. 72 04756 34 2125433 REVENDICATIONS 1. Procédé de classement par un calculateur numérique comportant une unité de mémoire, une unité arithmétique, un dispositif de commande, une unité de sortie et un fichier d'entrée d'enregis- 5 trements de données identifiés chacun par un indicatif constitué par plusieurs caractères, procédé caractérisé en ce qu'il consiste essentiellement à lire lesdits enregistrements de données dans ledit fichier et à examiner la valeur des caractères de leurs indicatifs au moyen du dispositif de commande, de manière à produire 10 un premier groupe de signaux représentant la distribution desdites valeurs d'indicatifs desdits enregistrements de données dudit fichier, à mémoriser ledit premier groupe de signaux représentant ladite distribution d'indicatifs dans ladite unité de mémoire, à traiter ledit premier groupe de signaux par ledit dispositif de com-15 mande et à en déduire un second groupe de signaux représentant les valeurs limites des caractères d'un index afin de définir des secteurs consécutifs de l'étendue totale desdites valeurs d'indicatifs de manière qu'en fonction de ladite distribution d'indicatifs, chacun desdits secteurs contienne un nombre sensiblement égal d'en-20 registrements de données, à mémoriser ledit second groupe de signaux représentant lesdits secteurs dans ladite unité de mémoire, à comparer lesdits caractères d'indicatif de chacun desdits enregistrements de données avec ledit index, au moyen dudit dispositif de commande, de manière à déterminer à quel secteur appartient cha-25 que indicatif et à identifier chaque indicatif par l'une de plusieurs étiquettes de désignation indiquant le secteur et à classer, en fonction de leur valeur, les indicatifs dans chacun desdits secteurs identifiés par ladite étiquette de désignation, de manière que le classement de tous lesdits indicatifs dans lesdits secteurs 30 constitue un fichier classé complet. 2. Procédé selon la revendication 1, caractérisé en ce que ledit premier groupe de signaux est produit en fonction des indicatifs d'enregistrements de données d'un échantillonnage d'enregistrements sélectionnés à des intervalles fixés pendant l'exécution 35 de l'opération de lecture desdits enregistrements de données dudit fichier d'entrée. 72 04756 35 2125433 3. Procédé selon la revendication 1, caractérisé en ce que ledit premier groupe de signaux est produit à partir d'un certain nombre d'indicatifs sélectionnés par échantillonnage desdits enregistrements de données dudit fichier d'entrée, selon un procédé 5 d'approximation prédéterminé, pendant l'exécution de l'opération de lecture desdits enregistrements de données dudit fichier d'entrée.' 4. Procédé selon la revendication 1, caractérisé en ce que l'opération de production dudit premier groupe de signaux représente» tant ladite distribution consiste à examiner la valeur du caractère le plus significatif de l'indicatif lu, à conserver un comptage séparé du nombre d'indicatifs dans lesquels la valeur du caractère le plus significatif est différente, à augmenter le comptage d'une unité à chaque indicatif dont le caractère le plus significatif a 15 l'une desdites valeurs différentes, jusqu'à ce que ledit comptage ait atteint une valeur prédéterminée, à examiner la valeur du caractère le plus significatif suivant de chaque indicatif lu ensuite, ainsi que les caractères examinés précédemment chaque fois que l'un quelconque desdits comptages a atteint ladite valeur prédéterminée 20 et à exécuter répétitivement toutes les opérations précédentes pour chacun des caractères moins significatifs examinés ensuite dans les indicatifs qui sont lus ensuite successivement, de manière à former des comptages de caractères d'indicatifs d'une manière plus sélective, suivant une structure par embranchements successifs représen-25 tant ladite distribution d'indicatifs. "5. Procédé selon la revendication 4, caractérisé en ce que l'exécution répétitive des opérations cesse lorsque tous les indicatifs ont été examinés. 6. Procédé selon la revendication 4, caractérisé en ce que 30 ladite valeur prédéterminée est inférieure au nombre d'indicatifs qui peuvent être classés par ledit classement interne. 7. Procédé selon la revendication 5, caractérisé en ce que la production du second groupe de signaux représentant une étiquette d'indexage consiste à sélectionner lesdits comptages qui n'ont pas 35 été augmentés jusqu'à ladite valeur prédéterminée, à augmenter chaque comptage sélectionné d'une quantité égale à ladite valeur prédéterminée, divisée par le nombre de comptages associés à un 72 04756 36 2125433 comptage de caractères d'indicatifs moins sélectifs, de manière que le comptage desdits caractères d'indicatifs moins sélectifs soit distribué de manière sensiblement égale parmi lesdits comptages associés, à cumuler les comptages dans un ordre qui corres-5 pond à l'ordre desdits caractères significatifs jusqu'à ce que la somme cumulée soit proche du nombre d'indicatifs que ledit calculateur numérique peut classer par classement interne, à mémoriser le groupe de signaux représentant lesdits caractères significatifs dont les comptages viennent d'être cumulés et à exécuter répétiti-10 vement les opérations de cumulation et de mémorisation jusqu'à ce que toute 1*étendue des valeurs d'indicatifs représentée par lesdits caractères d'indicatifs sélectionnés soit divisée en plusieurs secteurs consécutifs formant des groupes successifs de signaux de représentation correspondant audit second groupe de 15 signaux. 8. Procédé selon la revendication 1, caractérisé en ce que chacun desdits indicatifs comporte plusieurs caractères, ladite opération de comparaison des indicatifs avec ledit index consistant à comparer un nombre prédéterminé desdits caractères d'indi- 20 catifs correspondant aux positions de caractères significatifs avec une partie dudit index, de manière à déterminer le secteur approximatif desdits Indicatifs et à effectuer ensuite des comparaisons entre les caractères de positions de caractères moins significatifs desdits indicatifs avec des parties différentes dudit index d'uné 25 manière selon laquelle la pré cis io^d es dit e s comparaisons augmente progressivement à chaque comparaison successive. 9. Procédé selon la revendication 1, caractérisé, en ce que l'opération d'identification de chaque indicatif consiste à écrire dans un fichier de sortie chacune desdites étiquettes de désigna- 30 tion avec une information définissant la position dudit enregistrement de données associé dans une zone prédéterminée dudit fichier de sortie. 72 04756 J7 2125433 1C, : /-«vitif 'n traite:-eut Ù8 données, caractérisé en ce au'ii, co-voor te une unit ; de traiic-mont de données, ur.e- mémoire der-rl^éa intcr-ie/à eoi^ervor les données pondant qu'elles sont traitées par ladite unité et des •instrucLions de trofiracmie de ladite unité, une mémoire de réserve qui fournit à ladite mémoire"interne les données qui doivent 3t.7C traitées et qui on reçoit -les données traitées et un dispositif d'entrée destiné a mémoriser plusieurs enregistrements non dansés et comportant chacun un Indicatif d*identification, le dispositif de classement desdits enregistrements en fonction des valeurs de leurs indicatifs respectifs comportant ur dispositif qui transfère au moins une partie desdits plusieurs indicatifs dudit. dispositif d'entrée à ladite mémoire interne, un dispositif qui commande ladite unité de traitement de manière qu'elle traite ladite partie d'indicatifs et" calcule une représentation de la distribution des valeurs d.:e tous les indicatifs et mémorise .'ladite représenta tiot/dans ladite mémoire interne, un dispositif qui commande ladite unité de traitement de manière qu'elle produire un index en fonction de .'Ladite représentation et qu'elle mémorise ledit index dans ladite mémoire in-tsi-ne, ledit index étant constitué-par une-succession ordonnée do secteurs do valeurs desdits indicatifs? le nombre des indicatifs étant estimé de manière à ûtre à peu "près le raÔme dans chaque secteur, un dispositif qui compare la valeur de chacun desdits indicatifs avec lc:-d ti; index et qui produit un indice correspondant du secteur d auquel correspond ledit indicatif, un dispositif oui sonorise tous les indicatifs et leurs indices respectifs dans ladite -canotre de réserve, un dispositif qui transfère tous les ir lien tifs de ".ame inalue à ladite mémoire interne et u.n dispositif qui cor.. de ladite unité de traitement de manière "et le ni- - ,:e tous Ir-.'i's indicatifs de môme indice cox.sor 7 és si: -1 : a;;é::en t : • • s ladite mémoire interne, BAD ORIGINAL