FR 2027736 A1 19701002 FR 6945785 A 19691230 69 45785 1 2027736 La présente invention concerne la recherche d'information et plus particulièrement un nouveau procédé et un nouveau dispositif à commande électronique pour engendrer des indexs lisibles en machine' à utiliser dans la recherche d'informations. 5 Actuellement les informations de toute sorte sont engendrées à une vites se sans cesse croissante. Il y a un inconvénient par le fait que l'on ne peut rechercher rapidement un bloc d'informations dans la masse d'informations dans laquelle il est enfoui. Bien que l'on ait réalisé beaucoup de travaux sur la recherche d'information, on n'a pas trouvé jusqu'ici de solutions, bien 10 que de nombreuses techniques de recherche d'information compliquées aient été conçues pour accéder à une source d'informations comprenant un grand nombre de documents ou d'enregistrements. □ans le domaine de la recherche d'information, l'invention concerne un dispositif permettant de commander une machine pour localiser des documents 15 indexés par des clefs. Tout type de clef disposé suivant une séquence ordonnée peut être traité grâce à cette invention, qui ne concerne pas le choix de la clef en elle-même. L'invention nécessite seulement que chaque clef soit associée à une indication de l'emplacement du bloc d'informations qu'elle représente. L'information d'emplacement peut être une adresse, un indicateur 20 associé ou peut être obtenue à partir de la clef elle-même par un moyen qui ne fait pas partie de l'invention. La présente invention concerne un algorithme qui permet d'améliorer la vitesse de recherche d'un index ordonné en engendrant un index comprimé à partir de l'index ordonné, de sorte que la recherche est ensuite réalisée dans 25 l'index comprimé par ordre hiéarchique. On connaît de nombreux procédés et moyens pour effectuer une recherche dans un index ordonné non comprimé. La recherche dans un index non comprimé est réalisée par des moyens électroniques avec des ordinateurs en utilisant des procédés d'accès spéciaux, des moyens de commande et des techniques utili-30 sant des catalogues. On pourra se référer au brevet français n° 1 412 027 déposé par la demanderesse en France le 24 Septembre 1964 et aux brevets américains n° 3 366 928, 3' 242 470 et 3-030 609. La recherche d'information dans un ordinateur est limitée d'un certain nombre de façons parmi lesquelles on peut citer la très grande capacité de 35 la mémoire nécessitée par les techniques de recherche et la nécessité de balayer un grand nombre d'entrées ayant un grand nombre de "multiplets" chacune (dans la suite de la description, ce terme sera employé pour désigner un élément d'information traité comme un tout, tel qu'un ensemble ie bits représentant un caractère) avant qu'un argument de recherche puis, ^re trouvé. Cette 40 opération prend du temps et elle est coûteuse pour la recherche dans un index 69 45785 2 2027736 très bng. Ce sont ces inconvénients que cherche à résoudre la présente invention. La présente invention permet de réduire le nombre de multiplets par entrée dans l'index exploré. Il-en résulte qu'il faut une capacité plus petite pour la mémoire et que la recherche est plus rapide étant donné qu'il y a 5 moins de multiplets qui doivent être détectés për là machine. Dans les techniques actuelles de recherche au moyen des ordinateurs électroniques, telles que celles décrites dans les brevets cités, il y a des clefs non comprimées qui accompagnent les enregistrements sur un disque ou tambour pour indexer l'information contenue dans l'enregistrement associé. La recher-10 che de l'enregistrement associé peut être réalisée, soit par la clef, soit -par l'adresse de l'enregistrement. Par exemple dans' les brevets américains, n° 3 350 693, 3 343 134, 3 344 402, 3 344 403 et 3 344 405, une clef non comprimée peut être indexée sur un disque d'enregistrement magnétique. Grâce à un dispositif électronique, une clef peut être balayée par un argument de 15 recherche pour trouver une condition d'égalité. Lorsqu'on a trouvé la condition d'égalité un indicateur (adresseï associé à la clef non comprimée respective est obtenu et utilisé pour rechercher l'enregistrement représenté par la clef, et qui peut se trouver quelque part sur le disque. Cet indicateur peut par exemple comprendre l'emplacement sur le disque ou autre dispositif 20 où est situé l'enregistrement. L'ordinateur peut ainsi accéder automatiquement à l'enregistrement adressé. Après avoir été localisé l'enregistrement peut être utilisé dans n'importe quel but. La présente invention concerne la compression d'un index classé, c'est-à-dire dans lequel les clefs sont disposées suivant un ordre déterminé, en 25 enlevant uniquement un type de redondance attribuable au classement. Les procédés de cette invehtion pour la suppression de la redondance dans des informations classées ne peuvent pas s'appliquer directement à des informations non classées. Les procédés de l'art antérieur ne s'intéressent pas à la suppression 30 de la redondance résultant du classement des clefs dahs l'index. Par suite les procédés de cette invention sont différents des techniques de compression de données et de suppression de redondance de l'art antérieur. On trouve des exemples d'autres types de techniques de compression dans les brevets américains n° 2 978 535, 3 225 333 concernant les signaux TV conver 35 tis en digils, dans le brevet américain n° 3 237 170 et le brevet français n° 1 346 327 déposé par la demanderesse en France le 24 Octobre 1962 concernant le comptage du nombre des désaccords entre les parties successives d'un signal de communication digital, dans le brevet américain n° 3 237 170 concernant ."'.s? codage de configurations de bits répétitives, 3 275 989 concernant les 40 commandes qui ne contiennent que la partie qui est changée par rapport à la 69 45785 3 2027736 commande précédente, dans le brevet n° 3 223 982 qui concerne l'utilisation de la partie modifiée d'une adresse par rapport à l'adresse antérieure, dans le brevet n° 3 278 907 qui concerne la compression dans le temps de signaux radars Doppler. 5 Les brevets cités concernent des techniques de compression de données qui sont réversibles. C'est-à-dire, elles permettent de comprimer les données» de les transmettre, et de reconstruire les données originales non comprimées à partir des données comprimées reçues. La réversibilité n'est pas une condition nécessaire dans la présente invention, car la fonction principale de 10 la compression d'index est l'accélération de la recherche et non la reconstruction de 1*index. Par conséquent, un objet de cette invention est de réaliser un procédé de compression de clefs et un système qui réduit la capacité de la mémoire nécessaire pour un index que l'on peut explorer à la machine, t5 Un autre objet de cette invention est de réaliser un système et un procé dé de compression de clefs qui permettent de traduire un index d'origine ordonné en une forme comprimée qui réduit fortement le nombre des multiplets qui doivent Stre balayés par la machine pendant une recherche. Ceci augmente la vitesse de recherche de la machine par rapport à la vitesse de recherche de 20 l'index d'origine non comprimé pour une même vitesse de lecture des multiplets dans la machine. Un objet plus particulier de cette invention est d'engendrer un index comprimé dans lequel chaque clef d'entrée se présente sous une forme comprimée. Chaque entrée comprimée a une longueur de multiplet qui ne dépend pas du tout 25 de la longueur de la clef non comprimée correspondante. Par exemple, une clef non comprimée qui comporte cent ou mille multiplets peut être représentée par une clef comprimée ayant un seul multiplet dans l'index comprimé. La valeur de la compression d'index dépend principalement du "resserement" de l'index c'est-à-dire de l'importance de la variation des critères de classement entre 30 les clefs non comprimées de l'index. L'invention nécessite comme entrée une séquence ordonnée de clefs non comprimées avec les repères associés des blocs de données représentés par ces clefs. Les repères peuvent être des indicateurs d'adresse placés à cfité de leur clef respective. Les clefs et leurs indicateurs associés peuvent être 35 assemblés et ordonnés d'une manière connue qui ne fait pas partie de la présente invention. Par suite, le signal d'entrée peut être une séquence ordonnée de clefs non comprimées suivies ou précédées par leurs indicateurs d'emplacement respectifs. L'invention utilise un dispositif de comparaison électronique pour compa-40 rer les clefs non comprimées (UK) adjacentes d^ns l'ordre choisi de l'index. 69 45785 4 2027736 Initialement les deux premières clefs sont comparées comme premier couple de clefs, ensuite les seconde et troisième clefs sont comparées comme second couple de clefs et les troisième et quatrième clefs comme quatrième couple etc... jusqu'à ce que chaque couple de clef dans l'index ait été comparé. Une clef 5 comprimée CK, est engendrée à partir de chaque comparaison d'un couple de clefs non comprimées. L'indicateur associé à une des clefs non comprimées dans un couple (de préférence avec la première clef non comprimée) est associé avec la clef comprimée engendrée à partir de ce couple, La comparaison est réalisée entre positions de multiplet de même ordre dans le couple de clefs non compri-10 mées et va de la position de de l'ordre le plus élevé jusqu'à la position d'ordre le plus élevé pour lesquelles la comparaison indique une différence, et qui peut être appelée position "différence1*. Dans la forme préférée de l'invention, la comparaison des multiplets d'un couple ne doit pas se poursuivre au-delà de la position "différence". Dans certains cas, ce peut aussi 15 être la position d'ordre le plus haut d'un couple ds clefs non comprimées. Un compteur électronique concerve la valeur du nombre de positions de multiplets pour lesquels l'égalité est détectée, appelée "valeur d'égalité". Cette valeur est conservée pour engendrer un champ d'emplacement de multiplets dans la clef comprimée en cours de formation. Cette valeur est aussi conservée pendant 20 la comparaison du couple suivant pour commander la formation de la clef comprimée suivante, suivant que la valeur d'égalité est égale, supérieure ou inférieur à la valeur d'égalité précédente. Cette relation classe la clef comprimée suivante en un de trois types de clef: décalage à droite, pas de décalage et décalage à gauche. La clef comprimée avec décalage à droite reçoit un ou 25 plusieurs mutliplets à partir d'une de deux clefs non comprimées dans le couple comparé, de préférence à partir de la seconde clef non comprimée du couple. La clef comprimée avec décalage à gauche ne doit pas avoir de multiplets transférés à partir d'une clef non comprimée. Une clef comprimée sans décalage n'a pas plus d'un multiplet K. obtenu à partir d'une des clefs non comprimées 30 du couple, de préférence la seconde clef non comprimée. Une séquence de clefs comprimées sans décalage comporte alternativement un multiplet K et pas de multiplet K etc... Le choix du fait qu'il y ait ou non un multiplet K dépend du fait que la clef comprimée antérieure adjacente n'a pas ou a au moins un multiplet K respectivement. Chaque clef comprimée doit aussi indiquer l'empla-35 cernent de ses multiplets K par rapport à la clef non comprimée à partir de laquelle elle est obtenue. Ceci peut être réalisé en attribuant à chaque clef comprimée deux champs comprenant un champ "de valeur des multiplets facteurs" et un champ "de valeur des multiplets K". Le champ de valeur des multiplets facteurs pour les clefs comprimées ayant K multiplets est le nombre de posi-4Q tions de multiplets ayant un ordre supérieur au multiplet K. dans la clef non 69 45785 5 2027736 comprimée à partir de laquelle les multiplets K sont obtenus. Pour les clefs comprimées n'ayant pas de multiplet K, le nombre des multiplets facteurs détermine la position du multiplet "différence" qui est à la valeur d'égalité plus 1. La valeur des multiplets K. est le nombre de multiplets K dans la clef 5 comprimée. Dans les clefs comprimées n'ayant pas de multiplet K ou de multiplet facteur, la non existence de chacun de ces multiplets est indiquée. Les nombres minimaux de multiplets K sont définis dans le paragraphe précédent. Tout nombre de multiplets supplémentaires provenant de la même clef non comprimée peut être transféré à une clef comprimée sous forme de 10 multiplets K dans 3 a mesure où les multiplets supplémentaires maintiennent le même ordre relatif que les multiplets K ont dans la clef non comprimée. Ces multiplets transférés supplémentaires auront des caractéristiques redondantes mais on peut accepter un degré de redondance dans certain cas. D'autres objets caractéristiques et avantages de la présente invention 15 ressortiront mieux de l'exposé qui suit, fait en référence aux dessins annexés à ce texte, qui représentent un mode de réalisation préféré de celle-ci. La figure 1 représente une première réalisation de l'invention. La figure 2A représente un montage pour un circuit de commande de mise en séquence et de branchement qui peut être utilisé dans le circuit de la 20 figure 1. Les figures 2B-1 et 2B-2 représentent les signaux d'horloge et un circuit d'horloge qui peuvent être utilisés dans la figure 2A. Les figures 2C-1 à 2N représentent une réalisation des circuits utilisés dans les commandes de mise en séquence et de branchement représentées sur 25 la figure 2A, Les figures 2Q-1 à 2Q-3 constituent un tableau de la séquence des signaux de commande représentant la chronologie des cycles pour une réalisation des signaux de commande engendrés pour la circulation des données sur la figure 1 avec le procédé représenté sur la .figure 3. 30 La figure 3 représente la disposition des figures 3A-3F. Les figures 3A-3F représentent un organigramme détaillé d'un procédé de l'invention qui peut être réalisé avec le circuit de la figure 1. La figure 4 aide à définir certaines caractéristiques fondamentales d'un cs'j'vte df? -lofs, non comorimies utilisé dans la présente invention. 35 La figure 5 aide à définir certaines caractéristiques fondamentales entre deux clefs non comprimées, adjacentes utilisées dans la présente invention. La figure 6A représente une réalisation d'un procédé de l'invention oui peut être réalisé avec le circuit de la figure 1. La figure 6B représente un autre procédé de l'invention qui peut être 40 réalisé avec le circuit de la figure 1.. 69 45785 6 2027736 La figure 7 représente le procédé de la figure 6A avec un blocage des index de clefs comprimées. Les figures 8A, B et C représentent des séquences de clefs non comprimées choisies à partir desquelles sont engendrées respectivement des clefs compri-5 mées du type à décalage à gauche, à décalage à droite et sans décalage. La figure 9 représente une séquence de clefs non comprimées choisie et une séquence de clefs comprimées engendrées à partir d'elle avec une compression de multiplets maximum. La figure 10 représente une séquence de clefs non comprimées choisie^ 10 et une séquence de clefs comprimées engendrée à partir d'elles dans laquelle chaque clef sans décalage comporte un multiplet K. ' La figure 11 représente un autre procédé de l'invention-qui peut être réalisée avec le circuit de la figure 1. Les figures 12A et 12B représentent des variantes de la présente inven- 15 tiori. La figure 12C représente un autre procédé pour la présente invention. La figure 13 représente un format d'enregistrement ou de communication pour une séquence de clefs non comprimées choisie. La figure 14A représente un format d'enregistrement ou de communication 20 pour une séquence de clefs comprimée engendrée. La figure 14B-E représente différents formats d'enregistrement pour des clefs comprimées. La figure 15 représente comment disposer les figures 15A à 15F. La figure 15A représente un organigramme détaillé pour une autre réalisa-25 tion de l'invention. La figure 15B constitue un tableau de la séquence des signaux de commande représentant la chronologie des cycles pour une autre réalisation des signaux de commande engendrés pour commander la circulation des données sur le circuit de la figure 1 avec le procédé représenté sur la figure 15. 30 Les figures 15C-F représentent des modifications aux circuits des figures 2C-2N pour une autre réalisation d'une commande de mise en séquence et de branchement pour engendrer la séquence des signaux de commande sur la figure 15E. L'aération "de formation des index comprimés" agit sur une chaîne d'entrée £ clefs d'index qui sont sous une forme normale non comprimée et sont dans Drdre choisi. Ils peuvent être disposés dans l'ordre croissant ou décroissant les clefs respectives peuvent avoir une longueur variable. Une information supplémentaire peut être ajoutée à chaque clef, par exemple une information associée et une adressa indicatrice qui peut localiser soit directement, soit 40 indirectement un enregistrement avec lequel la clef respective est associée. 69 45785 7 2027736 La figure 4 représente deux clefs adjacentes dans une chaîne d'index non comprimés choisis dans laquelle les clefs non comprimées (UK) x...x et y...y sont deux clefs successives quelconques dans la séquence choisie. Chaque clef est constituée de plusieurs multiplets (caractères). Les X et Y dans 5 les clefs non comprimées respectives représentent les positions de multiplets qui peuvent varier en nombre parmi les différentes clefs non comprimées. Les positions de multiplets dans une clef diffèrent en importance pendant l'opération de classement à partir de la position de multiplet la plus à gauche, qui est la plus significative à la position la plus à droite qui est la moins 10 significative. Les clefs sur la figure 4 sont représentées alignées suivant leur multiplet le plus à gauche qui est le multiplet le plus significatif dans cette invention ainsi que dans la séquence de classement. Les multiplets dans une clef diminuent d'importance au fur au mesure que leur position augmentent à partir du multiplet le plus à gauche dans une clef quelconque, du 15 point de vue de l'opération de cette invention. Le dispositif de la présente invention engendre des clefs comprimées CK en utilisant une séquence de comparaison entre toutes les clefs non comprimées adjacentes dans un index ou sous-index. Ainsi, une comparaison est réalisée entre le couple j-1 et le couple j suivie par une comparaison entre un 20 couple suivant j et j+1. Ainsi, chaque clef non comprimée sauf la première et la dernière dans l'index est la seconde clef non comprimée d'un couple de comparaison et ensuite la première clef non comprimée du couple de comparaison suivant. Chaque comparaison est réalisée entre les positions de multiplets ayant le même ordre, c'est-à-dire les multiplets X et Y les plus à gauche 25 sont comparés, les seconds multiplets les plus à gauche sont comparés etc... Il résultera de ces comparaisons de multiplets que l'on trouvera invariablement une inégalité 0, puisque chaque clef dans l'index diffère de toute autre clef. Par exemple, cette différence peut être trouvée dans les adresses avec des noms identiques dans un index. 30 Toute opération de comparaison des clefs non comprimées dans cette inven tion ne doit pas aller au-delà de la position du multiplet inégal la plus à gauche D. La position du multiplet inégal D peut être la position la plus à gauche ou cela peut être un autre multiplet. Si ce n'est pas le multiplet le plus à gauche, il a sur sa gauche des multiplets égaux E. Les positions 35 des multiplets moins significatifs à la droite de la position du multiplet inégal D sont appelées multiplets de bruit N puisqu'ils ne sont pas nécessaires à la formation des clefs comprimées» Ainsi, dans une comparaison de clefs non comprimées adjacentes telles que x...x et y...y, il est possible qu'aucune des positions de mutliplets 40 ou que toutes les positions sauf la position la moins significative soient 69 45785 a 2027736 des positions de multiplets égaux E. Avec la plupart des couples de clefs non comprimées, la position du multiplet différent la plus à gauche sera une position de multiplet entre la position la plus à gauche et la position la plus à droite dans la comparaison. 5 Souvent deux clefs comparées x...x et y...y auront des longueurs de multi plets différentes. Dans ce cas, le premier multiplet de la clef la plus longue au-delà de la position de multiplet la moins significative de la clef la plus courte est par définition une position de multiplets inégaux. Dans cette comparaison de multiplets indiquant une inégalité, onconsidère le multiplet de 10 la clef la plus longue comme supérieur à l'abssence de multiplet de la clef la plus courte. Chaque fois que cela se produit la clef la plus courte peut être supposée avoir à sa droite le multiplet d'ordre le plus bas dans la séquence de comparaison utilisée telle que le multiplet blanc. On suppose sur la figure 4 que l'on utilise pour la liste d'index non 15 comprimé un ordre croissant Si on utilise un ordre décroissant, les inégalités "supérieure à" et "inférieure à" seront inversées dans toute la description. La figure 4 représente une comparaison A entre UKx et UKy, qui ont des positions j-1 et j dans la séquence d'index ordonnée UK. Les positions de multiplets dont la comparaison donne une égalité sont identifiées par E^, la 20 position du multiplet inégal le plus significatif est D^, et les multiplets de bruit sont N,. A La figure 5 représente la comparaison suivante B entre UKy et UKz, qui constitue le couple suivant aux positions d'index j et j+1. La comparaison suivante B utilise la seconde clef non comprimée y...y 25 de la comparaison antérieure comme première clef non comprimée pour la comparaison suivante. Ainsi, sur la figure 5, la clef non comprimée y...y est la même clef non comprimée que y...y sur la figure 4 qui représente la comparaison précédent immédiatement A. La clef non comprimée z...z suit ainsi immédiatement la clef non comprimée y...y dans la séquence triée de clefs non compri-30 mées. Les indices A et B sur les figures 4 et 5 représentent deux comparaisons successives à partir desquelles E, D et N sont obtenus. L'invention concerne les positions de multiplets de différence D dans deux comparaisons adjacentes. Il y a trois possibilités dans cette relation 35 des comparaisons adjacentes, qui sont représentées sur la figure 5 par les Cas I, II, et III. Le premier cas I sur la figure 5 représente la position de différence D„ comme étant à la même position de multiplets que la position D de différence D. dans la comparaison de clefs non comprimées précédent immédia- A tement représentée sur la figure 4. Le Cas I D^ peut être appelé un cas sans 40 décalage par rapport à D. car D_ n'a pas décalé sa position de multiplets par A D 69 45785 9 2027736 rapport à D . a Le second Cas II sur la figure 5 représente la position de différence □g comme étant à une position de multiplet plus significative que la position de différence sur la figure 4, Le Cas II Dg peut être appelé un cas avec 5 décalage à gauche par rapport à Dft. Le troisième Cas III sur la figure 5 représente la position de différence Dg comme étant à une position de multiplet moins significative que la position de différence sur la figure 4. Le Cas III Dg peut être appelé un cas avec décalage à droite par rapport à D^. Comme la position de différence relative Og varie par rapport à la posi-10 tion de différence précédente le nombre de positions de multiplets égaux Eg variera en conséquence et le nombre de positions des multiplets de bruit Ng variera. Puisque la position de différence D est toujours à une position à la droite des positions des multiplets égaux, on a alors D=E+1. Chaque clef non comprimée dans une séquence d'index représente un bloc 15 de données. Chacun de ces blocs de données doit être représenté dans toute séquence engendrée de clefs comprimées CK. ièrns La j clef comprimée, représente l'article d'information représenté , .ième . _ ... par la j clef non comprimée j. Une comparaison de la clef non comprimée j avec la clef non comprimée îèrns 20 j+1 engendre la j clef comprimée en utilisant certaines informations obtenuœ à partir de la comparaison précédent immédiatement les clefs non comprimées j-1 et j. Le contenu de la clef comprimée dépend de l'information résultant de la comparaison immédiatement précédente dans laquelle l'information la plus importante est la position D déterminée pendant la comparaison immédia- 25 tement antérieure. Il peut aussi être nécessaire de savoir si les multiplets de la clef comprimée antérieure étaient nuls ou non. L'information de position D peut être donnée d'un certain nombre de façons par exemple par le nombre de multiplets à partir du multiplet le plus significatif dans la comparaison respective ou en déterminant le nombre de positions égales Eft pendant la même 30 comparaison puisque la position D est une position supérieure d'un multiplet ,a à la valeur E^. Dans le cas où le premier couple de clefs non comprimées est comparé, on suppose que des conditions zéro précèdent la première opération de comparaison. 35 La première comparaison dans une séquence d'index quelconque de clefs non comprimées UK pour engendrer des clefs comprimées débute de préférence avec une comparaison entre les deux premières clefs non comprimées dans la séquence ordonnée. Cette première comparaison est utilisée pour engendrer la première clef comprimée CK qui peut représenter le bloc d'information repré-40 senté par la première clef non comprimée. Ensuite une seconde comparaison 69 45785 10 2027736 des seconde et troisième clefs non comprimées et l'information résultant de la première comparaison sont•utilisées pour engendrer la seconde clef comprimée qui représentera alors l'article représenté par la seconde clef non comprimée. La troisième comparaison est réalisée entre les troisième et quatrième clefs 5 non comprimées dans la séquence jusqu'à ce que la fin de l'index non comprimé soit atteinte. Par suite chaque clef comprimée représente le bloc d'information représenté par la première clef non comprimée dans le couple à partir duquel la clef comprimée est engendrée. Le format de la clef comprimée minimum comporte un nombre minimum de mul-10 tiplets K obtenu à partir d'une des clefs non comprimées pendant une comparaison. Le format de la clef comprimée minimum prend un ou plusieurs multiplets K à partir d'une clef non comprimée avec décalage à droite, ne prend pas de multiplet K à partir d'une clef non comprimée avec décalage à gauche et prend soit des multiplets K un soit des multiplets K zéro à partir d'une clef non 15 comprimée sans décalage. Il est toujours possible d'avoir plus que le format de multiplets minimum pour une clef comprimée en y ajoutant plusieurs multiplets à partir de la clef non comprimée à partir de laquelle sont obtenus les multiplets K. tout en maintenant les positions relatives parmi les multiplets K. Une telle information est rendondante mais elle peut être utile dans certain 20 cas par exemple lorsque des parties de l'information sont erronées. Deux éléments supplémentaires d'information sont nécessaires avec.une clef comprimée en plus des multiplets K. afin d'utiliser correctement la clef comprimée pendant une opération de recherche. Un élément d'information localise chaque multiplet K. d'une clef comprimée par la valeur de la position du multi-25 plet par rapport au multiplet le plus significatif dans la clef non comprimée à partir dé laquelle le multiplet K est obtenu. Le second élément supplémentaire localise la fin de la clef comprimée. Dans cette réalisation ces deux éléments se présentent sous la forme de deux champs appelés: champ de longueur de facteur F et champ de longueur de clef 30 comprimée L. Ils font partie de chaque clef comprimée. Le format de la clef comprimée totale devient alors FLK. ou LFK suivant que l'on donne la préférence à F ou L pour apparaître en premier dans le format. La longueur en multiplets L d'une clef comprimée dépend de celui des trois cas représentés sur la figure 5 (pas de décalage, décalage à gauche ou décalage 35 à droite) dans lequel on se trouve pendant une comparaison particulière. Dans le second cas de la figure 5 (décalage à gauche) il n'apparaît pas de multiplet K dans la clef comprimée et L est nul. Dans le premier cas de la figure 5 (sans décalage), le nombre minimum de multiplets K est nul (L=0) ou égal a un (L=1) suivant que le cle-f ccnnrimée antérieure comporte un nombre de multiplets K. 40 non nul ou nul respectivement. Par suite si la position D continue à avoir 69 45785 11 2027736 la même valeur pendant une séquence ininterrompue de comparaisons les clefs comprimées sans multiplet K (L=0) alterneront avec les clefs comprimées avec un multiplet K (L=13 à cause de la relation avec la condition nulle ou non nulle des multiplets K. précédant immédiatement. Dans le troisième cas de la 5 figure 5 (avec décalage à droite) la clef comprimée aura un ou plusieurs multiplets K (L^O). Par suite dans le cas III. le champ K peut avoir un nombre \ variable de multiplets qui est égal au nombre de positions de multiplets après la position D. jusqu'à la position D,-,, ceci peut être défini d'un certain nom- A D bre de façonsi telles que L=Dg-D^=(Eg+1)-(E^+1)=Eg-EA. 10 Le facteur (F) d'une clef comprimée représente le nombre de positions de multiplets continus à partir et y compris le multiplet le plus significatif, qui ne sont pas des multiplets K dans la clef comprimée en cours mais qui é-taient précédemment représentés par des multiplets K dans l'index comprimé. L'indice B représente une valeur dans la clef comprimée en cours tandis que 15 l'indice A représente une valeur dans la clef comprimée immédiatement antérieure. Le facteur FQ dépend du fait que la clef non comprimée en cours n'a pas de décalage, a un décalage à gauche ou un décalage à droite comme décrit en se référant à la figure 5. De même Fg est influencé par le fait que L^ est nul ou non. 20 Pour les conditions des multiplets K minima, le champ F g a les valeurs suivantes, pour une clef comprimée sans décalage ou avec décalage à gauche, la valeur FD dépend du fait que la valeur L. sur la clef comprimée immédiatement B A antérieure est nulle ou non. Lorsque L^ est nul dans le cas où il n'y a pas de décalage, la valeur FQ est la même que la valeur EQ égale. Alors que L^ 25 n'est pas nul dans les cas sans décalage, Fg peut avoir une valeur quelconque à partir d'une valeur maximum de Eft+1 jusqu'à une valeur minimum de E0+1. Dans le cas avec décalage à gauche, indépendamment du fait que L=0, F0 peut avoir une valeur quelconque entre EA+1 à Eg+1. Mais si L=0 pour le cas avec décalage à droite, Fg+E^; et si L n'est pas égal à zéro, Fg=E^=1. 30 Un exemple des clefs comprimées avec des champs K minima est représenté dans le tableau I suivant: 69 45785 12 2027736 TABLEAU I UK CK E F L K Engelhard, Hans 11 0 12 Engelhard, L Engelhard, Ludwig 3 12-4 0 . English, Irvine J 9 3 7 Lish, J English, Jas J 1 10-2 0 Ericson, Oscar 1 1 1 s ■ Eskind, Ralph R. 2 2 1 P Esposito, Blas 1 3-2 .0 Evancie, Kenneth G 1 1 1 z Ezequelle, Jonathan A □ 2-1 0 Fahnestock & Co 2 0 - 3 Fam Famularo, Jos J 2 3 - q_ Farewell, Richd L 3 2 2 rr Farrar, Cari E 1 4-2 0 Feeney, Kermit 2 1 2 en Fennell, Lee T 2 3 0 Ferris, Harriet Akin, Mrs 8 2 7 rris, R Ferris, Raymond W 69 45785 13 2027736 Avec le cas I de la figure 5, on peut obtenir une simplification de fonctionnement en ayant un seul multiplet K, qui est le multiplet Dn, et L=1. Il D en résulte cependant une compression moins bonne pour un index ayant des séquences sans décalage, ce qui se produit souvent dans les index importants. Un exemple de clef comprimée utilisant cette opération est représenté par le tableau II suivant: TABLEAU II UK CK E F L K Engelhard, Hans 41 0 12 Engelhard, L Engelhard, Ludwig 3 4 D English, Irvine J S 3 7 Lish, J English, Jas J 1 2 0 Ericson, Oscar 1 1 1 - s Eskind, Ralph R 2 2 1 P Esposito, Blas 1 3 0 Evancie, Kenneth G 1 1 1 z Ezequelle, Jonathan A 0 1 0 . Fahnestock & Co 2 0 3 Fam Famularo, Jos J 2 2 1 r Farewell, Richd L 3 3 1 r Farrar, Cari E 1 2 D Feeney, Kermit 2 1 2 en Fennell, Lee T 2 3 - 1 r Ferris, Harriet Akin, Mrs 8 3 6 ris, R Ferris, Raymond W - 69 45785 14 2027736 En conséquence un index comprimé peut être représenté par le format FLK. Les valeurs de F et L peuvent être représentées par un multiplet chacune ou elles peuvent occuper une fraction de mutliplet par exemple un demi multiplet chacune. Si F et L occupent chacun un demi multiplet de 8 bits, elles peuvent 5 contenir chacune des valeurs allant de 0 à 15, on a trouvé que ceci est suffisant en pratique pour loger presque tous les index comprimés car le nombre moyen de multiplets K par clef comprimée a été trouvé inférieur à un dans les indexs importants. En général K diminue au fur et è mesure que les index augmentent car les index longs sont, généralement plus comprimés, c'est-à-dire» 10 plus redondants. Pour traiter des valeurs L supérieures à 15 multiplets et/ou des valeurs F supérieures à 15 multiplets» on peut utiliser un des codes à 4 bits pour chaque demi multiplet F et L pour étendre une clef comprimée à l'entrés de la clef comprimée suivante. Cette expansion réduira la valeur maximum de F 15 ou L à 14 pour une clef comprimée non étendue. La clef comprimée étendue indiquera une expansion soit de F soit de L ou les deux par mise en place du code d'expansion à 4 bits Ctel que 153 respectivement dans l'un ou l'autre des champs F ou L ou dans les deux champs. Si seul F a un code d'expansion, la clef comprimée étendue n'aura pas de multiplets K et son champ L est nul, par suite elle 20 a un multiplet de long. Si L a le code d'expansion la même clef comprimée a 14 multiplets K et le champ L dans, la clef comprimée étendue suivante indiquera combien il y a de multiplets K. en plus qui sont transportés avec la clef comprimée étendue et qui doivent être reliés au multiplet K dans l'entrée d'index immédiatement précédente. On peut utiliser de cette manière un. nombre quel-25 conque de clefs comprimées étendues pour loger une clef comprimée ayant une longueur quelconque des champs F ou L. Cependant, des clefs comprimées ayant plus de 14 multiplets K sont très rares dans les index connus. Des clefs comprimées ayant plus de 14 multiplets F sont plus courantes. Chacune de ces clefs comprimées étendue ajoute un seul multiplet pour les champs F et L supplémen-30 taires. Les multiplets IC mis en chaîne ne doivent pas provoquer de redondance dans le système. Il y a deux cas fondamentaux possibles pour déterminer l'obtention des multiplets K. dans les clefs comprimées d'un index. C'est-à-dire, les multiplets K peuvent être obtenus à partir de l'une ou l'autre des clefs non comprimées 35 dans un couple ccomparé. Dans le cas fondamental I, les multiplets K. sont ob- -tenus à partir des multiplets dans la première clef non comprimée du couple de clefs non comprimées comparées. Dans le cas fondamental II, les multiplets K sont obtenus à partir des multiplets dans la seconde clef non comprimée du couple de clefs non comprimées comparées. 40 Une fois que l'on a choisi entre les cas I ou II, toutes les clefs compri 69 45785 15 2027736 mées dans l'index doivent ensuite être obtenues en utilisant les régies appropriées au cas choisi. En général on a trouvé que le cas II est préférable au cas I, car les multiplets K obtenus à partir de la seconde clef non comprimée seront plus grands que les multiplets K. obtenus à partir de la première clef 5 non comprimée dans un couple comparé. Cette supériorité a un avantage dans les opérations de recherche. La plupart des index conduisent à une source d'informations plus' fondamentale, que l'index lui-même, bien que dans certains cas l'information soit directement ajoutée à l'index. Dans la plupart des cas l'information indexée est 10 trop importante pour quelle soit ajoutée de façon efficace à la clef non comprimée ou à la clef comprimée. En conséquence, il est nécessaire dans la plupart des cas d'ajouter à chaque clef, un article d'information supplémentaire qui conduira directement ou indirectement à l'information indexée. Un tel article d'information supplémentaire peut être l'adresse de l'in-15 formation nécessaire ou ce peut être l'adresse d'une autre adresse qui fait partie d'une chaîne d'adresses qui conduit à l'information indexée. Dans un tel cas, un indicateur serait ajouté à chaque clef. L'indicateur est une adresse qui peut être utilisée pour localiser l'information indexée ou pour localiser l'indicateur suivant dans une chaîne conduisant à l'information indexée. 20 II y a deux possibilités pour ajouter un indicateur à une clef comprimée. Ces deux possibilités peuvent être appelées possiblité I ou possiblité II. La possiblité I associe le premier indicateur de la clef non comprimée à la clef comprimée engendrée à partir de chaque couple comparé de clefs non comprimées. La possiblité II associe le second indicateur de la clef non comprimée 25 avec la clef comprimée engendrée à partir de chaque couple de clefs non comprimées comparées. Une fois que l'on a choisi entre les possibilités I et II, il est essentiel ensuite d'appliquer les régies concernant chaque possiblité. Pour faire le choix entre les deux possibilités on doit considérer qu'il y a un indicateur de plus qu'il y a de clefs comprimées réelles engendrées par 30 la comparaison entre les clefs non comprimées réelles. C'est-à-dire chaque clef non comprimée aura son indicateur et il y aura une clef comprimée de moins engendrée par rapport au nombre de couples de clefs non comprimées comparées. Cette différence entre le nombre de clefs comprimées réelles et les indicateurs réels peut être évitée en ajoutant une clef comprimée fictive au début ou à 35 la fin de l'index. La possiblité I nécessite une clef comprimée fictive initiale pour fournir à la première clef non comprimée l'indicateur. La possiblité II nécessite une clef comprimée fictive à la fin de l'index pour loger le dernier indicateur qui autrement ne peut pas l'être. On préfère utiliser la possiblité II car 40 la clef comprimée fictive ne peut être utilisée pour identifier la fin de l'in 69 45785 16 2027736 dex comprimé. Les clefs comprimées avec un nombre minimal ou supérieur de multiplets obtenus à partir de la clef non comprimée correspondante ont été décrites. La clef comprimée de dimension minimale éliminé toutes les redondances de mul-5 tiplets que l'on trouvent dans la liste triée de clefs non comprimées. Cependant. il a des cas pour lesquels il est souhaitable de conserver une certaine redondance. Par exemple, si on élimine tous les multiplets de bruit, et que tous les multiplets facteurs sont conservés, il reste une redondance suffisante pour effectuer la recherche de l'index comprimé partiellement sur la 10 même base que celle de l'index non comprimé correspondant. Le tableau suivant représente ce type de compression: TABLEAU III UK CK E E K Engelhard, Hans 11 12 Engelhard, L Engelhard, Ludwig 3 3 Eng English, Irvine J S 10 English, J English, Jas J 1 1 E Ericson, Oscar 1 2 Es Eskind, Ralph R 2 3 Esp Esposito, Blas 1 1 " E - - . Evancie, Kenneth G 1 • 2 Ez Ezequelle, Jonathan A 0 1 F Fahnestock & Co 2 3 Fam Famularo, Jos J 2 2 Fa Farewell, Richd L 3 4 . Farr Farrar, Cari E 1 1 F "Feeney, Kermit 2 3 Fen Fennell, Lee T 2 2 Fe Ferris, Harriet Akin, Mrs 6 a. - - Ferris, R Ferris, Raymond W 69 45785 17 2027736 10 Avec une clef comprimée du tableau III, un ou plusieurs multiplets supplémentaires (multiplets de bruitî peuvent être ajoutés à la droite des multiplets K. à partir de la clef non comprimée à partir de laquelle les multiplets K nécessaires sont obtenus. Le cas limite est atteint lorsque la clef comprimée comporte tous les multiplets de la clef non comprimée correspondante et qu'il n'y a pas de compression. Ou bien, les multiplets K minima et les multiplets de bruit N peuvent être conservés et les multiplets facteurs F éliminés. Ceci est différent de l'opération qui consiste à conserver le multiplet D et le multiplet N comme représenté dans le tableau IV suivant: TABLEAU IV UK CK E F L .K Engelhard, Hans 11 0 8 Ludwig 15 Engelhard, Ludwig 3 4 14 Lish, Irvine J English, Irvine J 9 3 11 Lish, Jas J English, Jas J 1 2 13 ricson, Oscar Ericson, Oscar 1 1 14 skind, Ralph R Eskind, Ralph R 2 2 12 posito, Blas 20 Esposito, Blas 1 3 17 vancie, Kenneth G Evancie, Kenneth G 1 1 20 zequelle, Jonathan A Ezequelle, Jonathan A 0 1 15 Fahnestock & Co Fahnestock & Co 2 0 13 mularo, Jos J Famularo, Jos J 2 2 15 rewell, Rochd L 25 Farewell, Richd L 3 3 11 rar. Cari E Farrar, Cari E 1 2 14 eeney, Kermit Feeney, Kermit 2 1 12 nnell, Lee T Fennell, Lee T 2 3 23 rris, Harriet Akin, Mrs Ferris, Harriet Akin, Mrs 8 3 9 Raymond, W 30 Ferris, Raymond W 69 45785 18 2027736 Une autre variante consiste à inclure avec des multiplets K. minima, au moins le multiplet de bruit le plus significatif en ajoutant au caractère supérieur suivant dans la séquence de comparaison utilisée. Ceci est particulièrement approprié lorsque les régies décrites pour le cas fondamental I sont uti-5 lisées puisqu'il en résulte-Une condition de supériorité pour les multiplets K ce qui est avantageux pour rechercher l'index comprimé. Dans le dernier cas, chaque fois que le premier multiplet de bruit est le caractère dé rang supérieur dans la séquence de comparaison, le multiplet de bruit suivant est aussi ajouté aux multiplets K car la valeur du caractère de rang le plus haut ne peut 10 être changée. Si un, multiplet de bruit ajouté est le caractère de rang le plus haut, le multiplet de bruit suivant est ajouté, jusqu'à ce qu'un multiplet de bruit ajouté ne soit pas le caractère de rang le plus haut dans la séquence de comparaison. Seul le dernier multiplet de bruit ajouté est augmenté à la valeur supérieure suivante dans la séquence de comparaison. Il est rare qu'il 15 faille plus d'un multiplet de bruit. Le tableau suivant représente un exemple de compression d'index utilisant le dernier type d'opération avec une séquence de comparaison décimale codée binaire dans laquelle le multiplet A suit la virgule (,): TABLEAU V L K 5 BOONA 0 2 SA 5 TH, RJ 2 OC 0 0 ? 20 UK B00N, CLYDÉ E' 0 BOONSTRA, PIET W 4 B005, DONALD • 3 BOOTH, RICHARD R 3 25 BOOTH, ROBERT A 7 BOOTH, RONALD 8 BOOTH, VERNON 6 BORCHLEWICZ, ROBERT J 2 30 BOYD, DARRELL C 9 45785 19 2027736 F = H des multiplets facteurs à partir de la gauche de la clef L = 14 des multiplets de la clef enregistrée dans cette entrée d'index. La figure 6A représente un organigramme qui décrit la succession des opérations dans un des procédés de cette invention. Dans cette figure, l'étape 5 de mise en route 10 restaure les registres maintenant les valeurs F. et L. A A à zéro. Ensuite l'étape 11 fait passer le système aux couples suivants de clefs non comprimées Y et Z qui sont les clefs j et j+1 respectivement représentées sur la figure 5. Initialement, ce sont les deux premières clefs dans un index non comprimé qui sont prises à partir du support d'emmagasinage tel qu'une 10 bande magnétique, un disque magnétique, une mémoire à noyau etc... Au cours de l'étape 12 est réalisé un test de fin d'index pour déterminer si l'étape 11 a atteint la fin de l'index non comprimé. La fin de l'index peut, être indiquée d'un certain nombre de manières par exemple, ce peut être indiqué par un caractère spécial, un enregistrement spécial, une combinaison particulière 15 de caractère, ou en détectant une valeur de multiplet invalide pour une clef non comprimée. Si on n'a pas atteint la fin d'index, l'étape de comparaison 13 est réalisée au cours de laquelle on doit trouver UK-Y inférieur à UK-Z puisque les clefs dans l'index non comprimé doivent être dans l'ordre fixé et que chaque 20 clef doit être unique dans l'index. En conséquence, si on trouve que UK-Y est égal ou supérieur à UK-Z, les clefs ne sont pas dans l'ordre choisi correct et une erreur est mise en évidence par l'étape 48a ou 48c, respectivement. Normalement il ne doit pas se produire une telle erreur, puisque l'opération de classement antérieure pour les clefs non comprimées doit avoir été réalisée 25 correctement. Le nombre des positions de multiplets égaux Eg est déterminé par l'étape de comparaison 13 et elles sont comptées par l'étape 14. En effet, l'étape 14 augmente la valeur Eg de un pour chaque égalité entre les multiplets Y et Z ayant des positions correspondantes Bt revient à l'étape 13 pour une comparaison des multiplets Y et Z suivants. Dès que l'on a détecté que le mul-30 tiplet Z est supérieur au multiplet Y, on passe à l'étape 16. La dernière valeur E0 obtenue par l'étape 14, avant de passer à l'étape 16 est emmagasinée comme valeur E„ correcte pour la clef comprimée en cours et définit l'empla-5 cernent DQ qui a une valeur supérieure d'un multiplet à la valeur Eg. La valeur E est emmagasinée dans un registre ou dans une position de mots qui lui est B 35 allouée. Ensuite, l'étape 16 est réalisée par un dispositif de soustraction mécanique ou électronique qui soustrait la valeur dans un registre Eft de la valeur dans un registre Eg et emmagasine le résultat de la soustraction dans un registre S. La valeur dans le registre S est alors comparée à zéro dans l'étape 17, 69 45785 20 2027736 qui trouve ra que S est inférieur à, égal à, ou supérieur à zéro. Ceci détermine si la position Dg a été décalée vers la gauche, n'a pas été décalée ou a été décalée vers la droite par rapport à la position D„ antérieure. Dans D le premier couple de clefs non comprimées dans un index, la position Dn est D 5 décalée vers la droite car on suppose que la position DQ antérieure est nulle. Suivant laquelle de ces trois déterminations est réalisée par l'étape 17, une branche différente 21, 22 ou 23 respectivement est sélectionnée. Les branches 22 et 23 conduisent d'abord à des étapes au cours de laquelle un test est réalisé pour voir si Lft est égal à zéro, et ensuite elles se séparent en deux 10 branches suivant que L^ est nul ou non. 11 en résulte cinq branches possibles. Différentes valeurs peuvent être engendrées pour LQ et F g sur deux branches différentes. Si S est inférieur à zéro, l'étape 30 est réalisée par laquelle un zéro est mis dans le registre Lg et qui emmagasine cette valeur Lg comme composante L de la clef comprimée en cours de formation. Ensuite on passe à 15 létape 31 au cours de laquelle la valeur dans le registre; Eg est incrémentée de un et est placée dans le registre Fn. La valeur Fn résultante est emmagasi- D D née comme composante F de la clef comprimée engendrée. Aucun multiplet K n'est engendré lorsque S est inférieur à zéro, et l'étape 43a suit l'étape 31 pour transférer l'indicateur UK-Y avec la clef comprimée engendrée. 20 L'étape 44 est exécutée avant l'étape 43a en préparation de l'itération suivante dans le procédé de la figure 6A, la valeur dans le registre E^ est - - P réattribuée comme valeur EA et la valeur dans le registre LQ est réattribuée comme valeur L^. Ensuite l'étape 11 est réintrduite qui provoque l'examen du couple suivant de clefs non comprimées. Ce couple suivant comprend la seconde 25 clef (UK-Z) du dernier couple A, qui devient la première clef (UK-Y) du couple suivant B et la clef comprimée après UK-Z du dernier couple devient UK-Z du couple suivant. De cette manière chaque couple suivant de clefs non comprimées UK-Y et UK-Z est obtenu lorsque l'étape 11 est réintroduite jusqu'à ce que la séquence de clefs non comprimées soit épuisée ce qui est indiqué dans l'éta-30 pe 12. Tant que l'étape 12 fait passer à l'étape 13 les itérations se poursuivent. Chaque fois que l'on atteint l'étape 17, ue branche est choisie parmi les trois branches 21, 22 ou 23. La branche 21 a été décrite précédemment pour le cas du décalage à gauche. La branche 22 est prise lorsque l'étape 17 déter-35 mine que S est égal à zéro, ce qui identifie un cas sans décalage. Ensuite, au cours de l'étape 26a, un test est réalisé pour déterminer si L^ emmagasiné est nul. Si L. n'est pas nul pour le cas sans décalage, on passe aux étapes H 30 et 31 et elles sont réalisées de la même manière que précédemment décrite pour le cas avec décalage à gauche. Cependant si Lft est nul pour le cas sans 40 décalage, on passe à l'étape 32 à partir de l'étape 26a. L'étape 32 provoque 69 45785 21 2027736 la mise en place d'un digit 1 dans le registre Lg et cette valeur est emmagasinée dans le champ L pour la clef comprimée qui est engendrée. Ensuite, l'éta pe 33 est exécutée qui provoque le transfert de la valeur dans le registre Eg au registre Fg et cette valeur F est emmagasinée comme partie de la clef 5 comprimée en cours. Ensuite on passe à l'étape 41 pour transférer le nombre Lg de multiplets K. qui sont pris à partir du registre dans lequel la clef UK-Z est emmagasinée. Le premier multiplet K est pris à partir de ce registre à la position de multiplet Fg+1 par rapport à la position du multiplet le plus significatif de UK-S. Ce multiplet est emmagas=né comme premier multiplet K. 10 D'autres multiplets K sont pris si c'est nécessaire à partir des positions de multiplets moins significatives adjacentes jusqu'à ce que le nombre Ln de O multiplets soit pris à partir de UK-Z. Ensuite l'étape 43 est réalisée pour emmagasiner l'adresse indicatrice associée à UK-Z, et l'itération suivante est réalisée. 15 Une itération peut trouver un cas avec- décalage à droite pendant l'étape 17 indiquée par S supérieur à zéro. Par suite la branche 23 est prise. Ensuite le registre L est testé pour trouver une valeur nulle par l'étape 26b. Si A L^ est nul, l'étape 33 est introduite à la suite de quoi un "un" est ajouté à la valeur dans le registre S et la valeur incrémentée est placée dans le 20 registre Ln. Cette valeur Ln est emmagasinée comme composante L de la clef □ D comprimée en cours de formation. L'étape 35 est introduite à la fin de l'étape 34 dans laquelle la valeur dans le registre EA est transférée au registre Fd comme valeur F pour la clef comprimée en cours et elle est emmagasinée dans D le champ F en cours. Ensuite, on passe à l'étape 41 qui sert à engendrer les 25 multiplets K de la manière précédemment décrite. D'autre part si au cours de l'étape 26b on trouve que le registre L^ a un contenu non nul, on passe à l'étape 36 qui emmagasine la valeur dans le registre S comme valeur Lg. Ensuite, on passe à l'étape 37 qui incrémente la valeur dans le registre E et charge la valeur incrémentée dans le registre A 30 Fn et 1'emmagasine dans le champ F pour la clef comprimée en cours. Ensuite Q les multiplets K sont engendrés par l'étape 41 de la manière précédemment décrite. Les étapes 43 et 44 sont introduites à la fin des étapes 31 ou 41. L'étape 44 redefinit les valeurs E0 et L0 en cours comme valeurs Eft et L^ pour l'i-35 tération suivante. L'étape 43 emmagasine l'indicateur associé à la clef UK-Y en cours comme indicateur avec la clef comprimée en cours. Puisque les étapes 43 et 44 sont indépendantes l'une de l'autre, leur ordre d'exécution n'est pas critique. Lorsque l'étape 12 détecte une indication de fin d'index, pour la chaîna 40 de clefs non comprimées, elle engendre une dernière clef comprimée d'une ma 69 45785 22 2027736 nière spéciale en emmagasinant des multiplets zéros dans les champs L et F et non des multiplets K.. l'indicateur avec la dernière clef non comprimée est emmagasiné comme indicateur avec la dernière clef comprimée dans l'étape 43b et l'opération est achevée par l'étape 47. 5 La figure 6B représente les étapes 31B, 26C et 31A qui remplacent l'étape 31 de la figure 6A, tout en conservant les autres étapes de la figure BA. L'étape 31 de la figure BA engendre une valeur F minimum pour les cas avec décalage à gauche tandis que l'étape 31A sur la figure 6B engendre les valeurs F maxima pour les clefs 'comprimées avec décalage à gauche. La valeur F minimum 10 est préférée bien que toute valeur comprise entre la valeur minimum et la valeur puisse être utilisée pour rechercher l'index comprimé. Ces valeurs F sont les valeurs minimum et maximum en vue de permettre la recherche des clefs comprimées auquel cas F peut aussi avoir une valeur quelconque entre ces limites. Les multiplets L, F et K engendrés pour la clef comprimée en cours sont 15 emmagasinés séquentiellement dans une mémoire d'un type quelconque tel qu'une mémoire à bande magnétique à noyaux à disque ou à tambour. Chaque clef comprimée successive est emmagasinée de façon à suivre la clef comprimée précédente sans qu'il y ait de positions de multiplets perdus. Cette extraction séquentielle de la chaîne de clefs comprimées peut se poursuivre sans interruption 20 jusqu'à ce que l'on atteigne une fin d'index. D'autre part elle peut être interrompu momentanément à une dimension de bloc particulière nécessaire pour réaliser l'emmagasinage sur un support d'emmagasinage magnétique telle qu'une bande un disque ou un tambour. Par suite, un bloc peut comprendre un index entier ou un bloc peut se terminer chaque fois qu'un a compté un nombre donné 25 de multiplets ou d'opérations, nombre qui peut être variable. Dans la figure 7, certaines étapes sont ajoutées aux étapes du procédé de la figure 6A. Ainsi, sur la figure 7, un compteur 0 est initialement chargé pendant l'étape 10 pour contenir approximativement la dimension des blocs de multiplets nécessaires BL, qui est testée par l'étape 51 une fois qu'une des 30 étapes 30 à 37 et 41 est réalisée. Le compteur Q est diminué dans l'étape 51 de la longueur de multiplets L, de la clef comprimée en cours et de sa Ion- b gueur d'indicateur C pour chaque clef comprimée extraite à partir des étapes 30-37, 41 et 43a. La quantité diminuée est égale à L0 Cle nombre de multiplets K. en cours) plus 1 (le nombre de multiplets pour les champs F et L ) plus CR 35 (le nombre de multiplets de l'indicateur) plus 1 (le multiplet C lui-même K pour une valeur totale diminuée de (L„ + C + 2) ) par l'opération de l'étape D K 51. Lorsque la valeur de Q atteint zéro, un bloc est écrit par l'étape 55b. L'étape 52 teste le contenu actuel du compteur Q. Tant que dans l'étape 51 on trouve que Q est supérieur à zéro, on passe à l'étape 44 à partir de 40 l'étape 52 et l'itération suivante commence. Cependant si Q est égal à ou in 69 45785 23 2027736 férieur à zéro, on passe à l'étape 55b et la partie engendrée récemment de l'index comprimé est écrite et dans l'étape 55c Q est mis aux conditions initiales pour le bloc suivant. Un nouveau bloc est annoncé quand l'étape 55b transfère une commande à l'étape 44 pour amorcer l'itération suivante qui con-5 tinue l'index comprimé dans le bloc suivant etc.. jusqu'à ce qu'une fin d'index soit détectée par l'étape 12. Leq figures BA, B et C représentent des séquences de clefs non comprimées pour illustrer les opérations des procédés des figures 6A, 6B ou 7 pour les différentes itérations utilisant les branches 21, 22 et 23 respectivement. 10 Les clefs non comprimées et les clefs comprimées correspondantes sur la figure 8 sont numérotées dans la colonne verticale gauche intitulée "numéro de clef". ' Les positions de multiplets dans chaque clef non comprimée sont numérotées : de 1 à -11-.au sommet de la figure BA. Chaque multiplet UK. est représenté par un symbole B, qui peut être un caractère choisi dans une série de caractères 15 en restant dans les contraintes de la séquence ordonnée des clefs non comprimées. C'est-à-dire un multiplet dans une colonne peut être égal ou supérieur dans la séquence de comparaison à son multiplet immédiatement précédent dans cette colonne, il ne peut être inférieur à un multiplet précédent dans la même colonne pour des conditions de classement dans l'ordre croissant. L'inverse 20 est vrai pour un classement dans l'ordre décroissant. Bien qu'on suppose qu'il y a un nombre fixe de positions de multiplets pour chaque clef noncomprimée représentées sur les figures 8, la représentation est exacte pour des nombres variables de multiplets dans les clefs non 25 comprimées. La position de différence identifiée par D0 sur la figure 5 (obtenue en comparant un couple de clefs non comprimées) est désignée par un symbole D sur les figures 8A, B et C pour indiquer la position des multiplets différents dans la seconde clef non comprimée du couple comparé. On trouve les multiplets E égaux pour une comparaison de couple de multiplets à la gauche de chaque multiplet □ et les multiplets N de bruit à la droite de chaque 30 multiplet D. Une ligne verticale en traits pleins est tracée à droite de chaque multiplet D et elle est connectée à chaque ligne verticale adjacente à une ligne horizontale. Les lignes verticales en pointillés longs sur les figures 8A, B et C sont 35 tracées de la même manière sur la limite droite des positions F des multiplets facteurs. La colonne F^ représente les valeurs F minima engendrées par le procédé de la figure 6A. La colonne F„ représente les valeurs F maxima pour les clefs A. compr=mées engendrées par le procédé de.la figure BB. Les valeurs F et 40 ne diffèrent que pour certaines clefs comprimées avec décalage à gauche et 69 45785 24 2027736 elles sont égales pour les clefs comprimées sans décalage et avec décalage à droite. Les lignes verticales en pointillés sont tracées à la droite des positions qui diffèrent des positions F^ dans la même clef non comprimée. Si F^ et F^ sont égales les lignes verticales en pointillés longs représentent 5 FNetFX' Le champ de multiplets K pour une clef comprimée est délimité à gauche par une ligne verticale en pointillés longs et à droite par une ligne verticale en traits pleins. Si la ligne en traits pleins (ligne Dg} et la ligne en pointillés longs (limite F) délimitent le même multiplet UK, ou si la ligne en 10 traits pleins est à gauche soit de la ligne en pointillés longs soit de la ligne en pointillés courts (limite Fx) il n'existe pas de champ de multiplets K pour la clef comprimée correspondante et Lg est nul. Les longueurs en multiplets des champs F (facteur), L (nombre de multiplets K), et E (nombre de multiplets égaux) sont représentées sur les figures 8A, B et C dans les colonnes 15 correspondantes. Le multiplet indicateur associé à chaque clef non comprimée est représenté par des R dans les figures. La première clef comprimée pour chaque figure BA, B ou C représente toujours une cas avec décalage à droite car Lft et Fft sont initialement mis à zéro dans l'étape 10 des figures SA, 6B ou 7. Par suite, la position des multiplets 20 différents ne peut être décalée que vers la droite pendant la comparaison des première et seconde clefs non comprimées. Ensuite sur la figure 8A les positions des multiplets différents ( représentés par la ligne en traits pleins) se déplacent vers la gauche pour représenter les cas de décalage à gauche. Il est apparent sur la figure SA que la première clef comprimée a une valeur 25 F nulle et comporte 9 multiplets K définis par la position D dans UK-2 et en conséquence" son champ L est 9. Les clefs comprimées, suivant la première clef sur la figure SA sont des clefs décalées à gauche comme on peut le voir à partir des valeurs décroissantes de E. Les clefs avec décalage à gauche n'ont pas de multiplet K et par suite ont un champ L nul. Les quantités F et L pour 30 les clefs comprimées sont représentées dans les colonnes respectives sur la figure 8A et chacune est associée £ l'indicateur au même numéro de clef. La figure 8A représente la valeur F^ minimum obtenue par le procédé de la figure 6A et la valeur F^ maximum obtenue par le procédé de la figure 6B (ligne verticale en pointillés courts). En tout cas le champ F peut avoir une 35 valeur comprise entre F^ et F^ (les lignes verticales en pointillés longs et en pointillés courts). La position de la ligne en pointillés longs F^ peut être préférée car elle permet d'obtenir une valeur numérique inférieure. En tout cas, il n'y a pas de multiplets K pour une clef comprimée avec décalage a gauche. 40 La figure BB représente la clef avec décalage à droite qui suit une va 69 45785 25 2027736 leur L^ nulle ou non nulle. Par exemple, la clef CK-3 ayant des champs F et L de 5 et de 3 est une clef avec décalage à droite ayant une valeur L. infé-rieure non nulle égale à 2. Cependant, la clef numéro 5 est une clef avec décalage à droite suivant une clef ayant une valeur nulle. Lorsque L^ est nul 5 pour un cas avec décalage à droite, la position du multiplet de différence antérieure est inclus comme multiplet K qui est nécessaire pour la continuité de la recherche. Lorsque la valeur Lft antérieure n'est pas nulle, la position de différence antérieure n'est pas inclus comme multiplet K puisqu'elle est représentée par un multiplet E dans le champ F de la clef comprimée en cours. 10 Les valeurs F^ et F^ sont égales pour des clefs avec décalage à droite. La figure 8C représente les variations de Lg entre zéro et un lorsqu'il se produit une séquence de cas sans décalage, c'est-à-dire lorsque la position Dg reste la même pendant une séquence d'opérations de comparaison de clefs non comprimées. En conséquence, lorsqu'une valeur L antérieure n'est pas nul- 15 le, L devient nul et lorsqu'une valeur L. antérieure est nulle LD devient £j AD égal à un. La variation sur la figure SC se produit lorsque L change entre 0 et 1 et revient à zéro alors que F varie en sons opposés entre 7 et 6. Les valeurs F^ et F^ sont égales pour des clefs sans décalage. La figure 9 représente une séquence générale de clefs non comprimées dans 20 laquelle les lignes en pointillés courts, en pointillés longs et en traits pleins définissant les limites de multiplets Fx> F^ et K représentent les opérations réalisées en utilisant les procédés des figures 6A et B. Les valeurs F et L correspondantes pour les clefs comprimées engendrées à partir des clefs non comprimées représentées sont représentées dans cette figure avec l'indica-25 teur associé. Ce type de tableau représente de façon dynamique ce qui va se passer pendant la formation des clefs comprimées à partir de la séquence de clefs non comprimées. Il est à noter d'après la figure 9 qu'un total de 48 multiplets K représente les 37 clefs comprimées résultant d'un total de 518 multiplets UK. En conséquence, la figure 9 représente une compression de clefs 30 dans un rapport inférieur à un dizième. Avec un multiplet ajouté à chaque clef comprimée pour représenter les valeurs F et L, le rapport de compression pour les clefs comprimées sur la figure 9 est d'environ un septième. En pratique avec des index longs la compression moyenne est inférieure à un multiplet K par clef. 35 La figure 11 représente le procédé de la figure BA modifiée pour le cas sans décalage afin d'éliminer la variation entre 0 et 1 de Lg et l'existence ou la non existence alternée d'un multiplet K c'est-à-dire, lorsque Dg reste dans la même position de multiplet pendant une séquence de clefs non comprimées. Il résulte du procédé de la figure 11 que Lg est égal à un, et que le multi-40 plet de différence Dg es$ le multiplet K pour toutes les clefs sans décalage. 69 45785 26 2027736 La figure 11 remplace la partie de la partie de la figure 6A comprise entre la sortie de l'étape 16 et l'entrée de l'étape 43, et délimitée par les points 20a et 20b sur la figure 6A. La seule différence entre les procédés des figures 11 et 6A réside dans la branche 22. Sur la figure 11 la branche 22 con-5 duit à l'étape 32 uniquement. En conséquence, on ne retrouve pas sur la figure 11 l'étape 26a de la figure 6A et on ne passe pas à l'étape 30 par la branche 22. La figure 10 représente la même séquence de clefs non comprimées que sur la figure 9. Le procédé de la figure 11 est appliqué à la séquence de clefs 10 non comprimées de la figure 10 alors que les procédés des figures 6A et B sont appliqués à la figure 9. Ainsi, la figure 10 représente l'absence de variation pour les séquences sans décalage qui auront un seul multiplet K. et une valeur Lg égale à 1. La simplification apparente dans le procédé de la figure 11 par rapport aux procédés des figures 6A ou 6B résulte qu'il y a une compression 15 de clefs moyennes inférieures, dans le cas des séquences de clefs sans décalage. Les séquences sans décalage sont courantes dans les indexs longs. Sur la figure 10, on obtient 51 multiplets K. parmi les 518 multiplets UK par rapport aux 48 multiplets K de la figure 9 pour la môme série de clefs non comprimées. Sur la figure 12A l'étape 41 entre les points 40 et 50 de la figure 6A 20 remplace l'étape 41a. L'opération de la figure 6A avec la substitution de la figure 12A permet d'obtenir des clefs comprimées du type représenté dans le tableau IV. Ces clefs comprimées éliminent les multiplets facteurs mais conservent les multiplets K et tous les multiplets de bruit. Comme on l'a dit précédemment, les multiplets de bruit sont redondants mais dans certaines condi-25 tions, la redondance peut être nécessaire afin de réaliser une correction ou une détection d'erreurs. L'organigramme de la figure 12B est introduit sur la figure 6A entre les points 20A et 20B et ainsi remplace la partie correspondante de la figure 6A. Le procédé de la substitution de la figure 12A dans la figure 6A permet d'obte-30 nir des clefs comprimées du type représenté sur le tableau III. Ces clefs comprimées conservent leurs multiplets facteurs et les multiplets K, et éliminent les multiplets de bruit. Puisque ces clefs comprimées ne représentent pas les multiplets déplacés par rapport à leur position la plus significative chaque clef comprimée a une valeur F nulle. Ainsi, il n'est pas nécessaire d'inclure 35 une valeur F dans le format de la clef comprimée pour le tableau III, et le procédé de la figure 12B puisque LD est toujours nul. Par suite le procédé b de la figure 12A n'emmagasine qu'une valeur L avec les multiplets K. Bien qu' elles ne soient pas emmagasinée dans le format CK, la figure 12B détermine les valeurs L_ et F„ qui sont maintenues dans les registres comme cela était b b 40 réalisé dans 1s procédé de la figure 6A. Uns étape supplémentaire 39 est ajou 69 45785 27 2027736 tée dans la figure 12B, dans laquelle les valeurs L„ et Fn déterminées sont □ □ ajoutées dans le registre Lç. Ensuite on passe à l'étape 41b dans laquelle le nombre Lç de multiplets à partir du début de la clef UK-Z en cours est emmagasiné. Ensuite, le procédé recommence et se poursuit jusqu'à ce que la fin 5 de l'index UK soit détectée. La figure 12C représente un procédé qui permet d'engendrer les clefs comprimées représentées dans le tableau V. Dans le procédé de la figure 120 les multiplets K sont sélectionnés à partir de la clef UK-Y par une comparaison, au lieu de l'être à partir de la clef UK-Z qui est utilisée dans le procédé 10 de la figure BA. - Il y a une autre distinction par le fait qu'une augmentation de code non uniforme dans la séquence de comparaison des caractères utilisés n'est pas importante dans le procédé de la figure 6A alors qu'une augmentation de code non uniforme doit être traitée de façon spéciale dans le procédé de la figure 15 12C dans laquelle un caractère suivant d'ordre supérieur dans la séquence de comparaison utilisée doit pouvoir être sélectionné. Si la série de comparaison est représentée par des codes séquentiels, un caractère suivant peut être sélectionné en ajoutant un au code pour le caractère donné. D'autre part, si la séquence de caractères dans une série de comparaison ne permet pas une aug-20 mentation de un du code binaire pour un caractère quelconque afin d'obtenir le caractère suivant, le caractère suivant est obtenu par d'autres moyens tels que par des tables. Dans ce dernier cas, la séquence de caractères dans la série de comparaison peut être placée dans des positions d'adresses séquentielles dans une table emmagsinées dans une mémoire à accès aléatoire. Ainsi, le 25 caractère suivant peut être obtenu en augmentant l'adresse de un pour un caractère donné afin d'obtenir l'adresse pour rechercher le caractère suivant dans la séquence de comparaison indépendamment des valeurs réelles du code pour les caractères. La partie initiale de la figure 12C à partir de l'étape 10 jusqu'à l'éta-30 pe de comparaison 17 est identique aux étapes numérotées de la même façon de la figure BA. Ces figures sont aussi identiques dans le cas du décalage à gauche pour ce qui est de la branche 1 lorsque S est inférieur à zéro et jusqu'aux étapes 30, 31, 43 et 44 et en revenant à l'étape 11. Cependant sur la figure 12C il y a des différences par rapport à la figure 35 BA à la sortie de l'étape 17 on a le choix entre la branche 22 pour le cas sans décalage ou la branche 23 pour le cas du décalage à droite. Pour le cas sans décalage, la branche 22 fait passer à l'étape 66. Au cours de l'étape 66, la position du multiplet de différence Dg est adressée dans une clef non comprimée Y, dont le caractère est appelé YQ. Ensuite, le 40 caractère suivant d'ordre supérieur après Y^ dans la séquence de comparaison 69 45785 26 2027736 utilisée e&t sélectionnée, et ce caractère est appelé Y'. Ensuite, on passe à l'étape 67 qui compare Y' au multiplet Zg dans une clef UK-Z à la position Dg pour déterminer l'égalité ou la. différence. Le test est nécessaire pour assurer que Zg est supérieur à Y', ce qui est indiqué par une inégalité. En-5 suite, les étapes 32, 33a et 68 sont exécutées, qui impliquent l'emmagasinage d'un 1 comme Lg, l'emmagasinage de Eg comme Fg, et de Y' comme multiplet K pour la clef comprimée en cours. D'autre part, si on trouve une égalité entre Y' et ZQ un ou plusieurs multiplets de bruit après Yg doivent être obtenus à partir de la clef UK-Y afin de faire une distinction entre les multiplets K 10 engendrés et les multiplets dans les positions correspondantes de UK-Z. On fait cette distinction en prenant le premier multiplet de bruit N1-Y à partir de UK-Y et en passant à l'étape 66 pour obtenir le multiplet suivant d'ordre supérieur Y* après N1-Y dans les séquences de comparaison. Dn passe à l'étape 67 et si on trouve une inégalité, Lg est égal à deux et Yg et Y' sont emmaga-15 sinés comme multiplets K. E0 est emmagasiné comme valeur F„ pour cette clef □ D comprimée. Le champ K sera augmenté tant que l'on trouve l'égalité entre Y' et Zg et N dans l'étape 32 est augmenté de un lorsque chacune de ces égalités est détectée. L'étape 41C suit l'étape 33 et emmagasine les multiplets K provenant de 20 la clef UK-Y comme cela a été fait précédemment à partir de la clef UK-Z dans l'étape 41 de la figure 6A. Ensuite, on passe à l'étape 69 à partir de l'étape 41c, dans laquelle le dernier multiplet parmi les multiplets K emmagasinés est le multiplet Y' utilisé dans l'étape 67 lorsqu'on trouve dans cette étape une inégalité. Ensui-25 te, l'organigramme de la figure 9C se poursuit comme expliqué précédemment pour la figure 6A. Dans une réalisation quelconque utilisant le procédé de cette invention, il est essentiel qu'un format particulier soit utilisé pour la chaîne d'entrée de clefs non comprimées et pour la chaîne de sortie de clefs comprimées. De 30 nombreux aspects du format sont arbitraires mais une fois qu'un format est sélectionné, on doit s'y conformer puisqu'une réalisation particulière est généralement restreinte à un format particulier. La figure 13 représente un format particulier pour la chaîne d'entrée de clefs nonjomprimées et leurs indicateurs. De même, la figure 14A fournit un format pour la chaîne de sortie 35 résultante de clefs comprimées et leurs indicateurs. Sur la figure 13 à chaque désignation de clefs non comprimées est ajouté un suffixe qui est un nombre compris entre 0 et N représentant la position de la clef non comprimée dans la séquence choisie en commençant avec la clef non comprimée UK-0 jusqu'à la clef non comprimée UK-N. 40 Le format d'entrée sur la figure 13 comprend des clefs non comprimées 69 45785 29 2027736 de longueur variable en utilisant un champ de longueur de clefs (UK CT] qui précède chaque clef non comprimée, il peut comprendre un seul multiplet de huit bits pour loger des longueurs de clefs non comprimées allant jusqu'à 255 multiplets. Le champ UK-CT est aussi muni d'un suffixe qui est aussi un nombre 5 compris entre û st N comme l'est la clef non comprimée à laquelle il s'applique. Un champ d'indicateur PTR est associé à chaque clef non comprimée et a le même suffixe que la clef non comprimée avec laquelle il est associé. L'indicateur adresse l'article représenté par la clef non comprimée. L'indicateur . peut aussi être de longueur variable et la longueur peut être déterminée par 10 un champ de valeur d'indicateur PTR CT précédent chaque champ d'indicateur PTR avec le même suffixe. La valeur de l'indicateur PTR CT ne doit pas non plus utiliser plus d'un multiplet de huit bits pour loger une adresse d'indicateur allant jusqu'à 255 multiplets. La fin d'une chaîne UK est indiquée après le dernier indicateur PTR-N 15 par un multiplet ne cntenant que des zéros. Ce multiplet sera détecté au moment ou on attendra le champ de longueur de la clef non comprimée suivante, alors qu'un champ de longueur ne peut être nul. En conséquence, l'opération de formation de clefs UK se termine lorsqu'on détecte une valeur UK nulle. Le format de clefs comprimées de la figure 14A suppose arbitrairement 20 la séquence LFK pour chaque clef CK. L est le nombre de multiplets K dans la clef CK, F est le nombre de multiplets facteurs à partir du rang le plus significatif de la clef non comprimée et K représente les multiplets UK présents dans la clef comprimée; il peut d'ailleurs n'y en avoir aucun. On peut utiliser un ordre quelconque pour L et F, mais l'ordre choisi doit être conservé par 25 toutes les clefs. Un préfère utiliser le format de la figure 14A. Le format CK fondamental est représenté sur la figure 14B. Les champs F et L peuvent occupés chacun un seul multiplet de 8 bits ou ils peuvent occuper ensemble un seul multiplet de 8 bits, par exemple 4 bits chacun. Le choix dépend de la longueur des champs L et F sauf pour l'usage de l'index envisagé. Les mul-30 tiplets K s'il y en a sont les derniers dans le format, les multiplets K se succédant dans le même ordre que dans la clef non comprimée UK à partir de laquelle ils sont obtenus, La valeur de l'indicateur PTR CT et l'indicateur PTR suivent immédiatement le champ LFK, et sont pris directement à partir des champs correspondant associés à la clef UK qui va être représenté par la clef CK. 35 La dernière clef CK dans l'index comprimé de la figure 13 est indiquée quand il n'y a que des zéros dans le champ L et le champ F qui sont suivis par les champs PTR CT-N et PTR-N, qui sont les"champs correspondants associés à la dernière clef non comprimée dans l'index non comprimé. Il est possible d'étendre les champs L ou F pour représenter des nombres 40 de caractères important pour quelques clefs comprimées même si la longueur 45785 30 2027736 moyenne de la clef comprimée pour un index comprimé doit être faible, par exemple comprise entre 1 et 2 multiplets. Généralement, seul un faible pourcentage de clefs comprimées dans un index auront plusieurs multiplets. En conséquence, il peut être avantageux d'avoir une représentation LF qui est courte telle 5 un seul multiplet ce qui est intéressant pour représenter plus de 95% des clefs comprimées dans un index. On peut ensuite utiliser des champs spéciaux étendus pour les 5% restant de clefs comprimées. La figure 14C représente un format étendu qui permet d'étendre les champs L et F d'un demi multiplet pour loger jusqu'à 255 multiplets chacun. Comme 10 mentionné précédemment, L et F ne peuvent être nuls dans le format de la figure 14A sauf pour la dernière olef comprimée dans un index comprimé. Les quatre bits pour L ou F peuvent être codés en 15 codes différents de zéro. Un de ces 15 codes tel que le code pour 15 peut être réservé pour indiquer un cas "étendu" pour chaque champ. Dans le dernier cas, les champs 15 F et L peuvent loger chacun une valeur maximum allant jusqu'à 15 multiplets c'est-à-dire une valeur maximum de 14. Cependant, si l'un ou l'autre ou les deux champs L et F dépassent 14 la condition de dépassement est indiquée par le code 15 placé dans le champ respectif qui a dépassé 14, Le code 15 pour L ou F indique que un ou deux multiplets étendus tel que sur la figure 14C, 20 D ou E suivent immédiatement le multiplet L, et F fondamental et précèdent les multiplets K. Un multiplet étendu est ajouté si le champ L ou F contient le code 15 indiquant un dépassement. Ce multiplet étendu contient alors entièrement le champ L ou F pour représenter jusqu'à 255 multiplets. Un multiplet étendu peut 25 par suite être pris comme seule représentation de la valeur L ou F. Si le champ L est étendu, le nombre de multiplets K suivants est égal à la valeur représentée par le multiplet étendu pour L. La figure 14E représente le cas où il faut étendre les champs L et F au-delà de 14. Ainsi, deux multiplets étendus sont ajoutés et ils ont le même 30 ordre que les champs L et F fondamentaux. Par conséquent, chaque valeur étendue contient les valeurs F et L exactes respectives. Par exemple, s'il existe 33 multiplets K et que la valeur F est de 21 les champs.L et F dans le format de la clef comprimée fondamental pour cette clef comprimée contiendront chacun un code 15 pour indiquer les multiplets L et F étendus suivants qui auront 35 les quantités 33 et 21 respectivement. Trente trois multiplets K suivront le multiplet étendu F dans la clef comprimée. La figure 1 représente un circuit de données contrôlé pour obtenir la formation des clefs comprimées à partir des clefs nonjomprimées. Les réalisations utilisent le format de la figure 13 pour les clefs non 40 comprimées comme chaîne d'entrée de-N champs-UlC, N: étant un entier. Cette 69 45785 31 2027736 chaîne de clefs non comprimées d'entrée est le résultat d'une opération antérieure de classement de clefs non comprimées par l'ordinateur, telle qu'un programme de classement de type classique pour traiter des clefs de longueurs variables, chaque clef étant immédiatement précédée par un champ de valeur 5 de nombre de multiplets dans la clef suivante et chaque clef non comprimée étant immédaitement suivie par un champ indicateur pour localiser les données représentées par la clef non comprimée. La réalisation utilise un champ d'indicateur de longueur variable qui comprend un champ indicateur de longueur fixe comme cas particulier. Par exemple un indicateur de longueur fixe peut 10 comprendre deux multiplets à partir desquels l'adresse de la clef respective peut être obtenue par un algortihme approprié. Le champ indicateur variable peut néanmoins être utilisé avec un indicateur de longueur fixe pour loger une partie de l'information indexée par la clef non comprimée, par suite le multiplet de valeur de l'indicateur désignera 15 la fin dB l'indicateur et du champ d'information et le commencement du champ IK suivant. Le nombre de multiplets alloué au champ de longueur UK doit naturellement être compatible avec la longueur maximum permise pour les clefs non comprimées. Le champ de longueur contenant un seul multiplet (UK CT) utilisé dans la figure 20 13 loge une longueur maximum UK de 255 multiplets qui est adéquate dans la plupart des cas. Si c'est nécessaire on peut utiliser un champ de longueur de deux multiplets qui logera une longueur UK maximum de plus de 16 000 multiplets. La séquence des multiplets d'entrée décrite en se référant à la figure 13 est transmise à partir d'une source 81 dans une mémoire d'origine 83 repré-25 sentée sur la figure 1, cette mémoire peut être unn type quelconque de mémoires à accès aléatoire, tel qu'une mémoire à noyau magnétique, une mémoire à film mince et une mémoire monolithique etc... La figure 14A représente le format des clefs comprimées CK dirigées à partir d'une mémoire de destination 84 représentée sur la figure 1 vers un 30 bloc récepteur 82. Cette chaîne de clefs comprimées se présente sous une forme qui peut ensuite être utilisée pour rechercher l'information indexée. La mémoire de destination peut être d'un type quelconque y compris une mémoire séquentielle telle qu'une mémoire à disque ou à tambour, une mémoire à bande continue ou une mémoire à accès aléatoire, telle que celle qui cons-35 titu'e la mémoire d'origine 83. ~ Sur la figure 1, une source 81 qui peut être un dispositif entrée/sortie fournit une chaîne de multiplets d'index non comprimé ayant le format représenté sur la figure 13 à une mémoire d'origine 83. Un bloc récepteur 82 qui peut être un dispositif entrée/ sortie reçoit 40 -la sortie du système Qui est la chaîne de multiplets d'index comprimé ayant 69 45785 32 2027736 le format représenté sur la figure 14A à partir de la mémoire de destination 84. La mémoire d'origine 83 et la mémoire de destination 84 peuvent être des mémoires différentes ou elles peuvent être dans des zfines, différentes ou se 5 chevaucheant, de la même mémoire telle que mémoire à noyau, mémoire monolithique ou mémoire à disque ou à tambour magnétique. Lb système de traitement de données placé entre les mémoires 83 et 84 comprend plusieurs registres, des portes d'entrée IG et des portes de sortie OG et des bus. 10 Un registre de données de la mémoire d'origine SSDR connecte la: sortie de la mémoire d'origine 83 à un bus de sortie B6 de la mémoire d'origine. Le registre SSDR fournit un multiplet de signal à un bus de sortie 87 de la mémoire de source lorsque la mémoire 83 est actionnée par un signal de mise en route SS pendant qu'elle reçoit une adresse provenant soit d'un registre d'adresses, 15 de la mémoire Y CYSAR) soit d'un registre d'adresses de la mémoire Z (ZSAR) lorsqu'elle est extraite respectivement, soit par un signal QG.CYSARJ-2, soit par un signal 0G(ZSAR)-2. Un additionneur 88 fournit son signal de sortie à une bascule 89 qui emmagasine l'amplitude des entrées A et B amenées à l'additionneur 88. La bascule 20 89 a unB position G correspondant au signe pour indiquer le signe de la valeur emmagasinée dans la bascule 89. La position G est enclenchée par un dépassement de capacité résultant des autres positions de digits dans la bascule 89. Une comparaison entre les entrées A et B de l'additionneur est réalisée en ajoutant A au complément à deux de B. Dans ce cas, A et B sont égaux si 25 il y a une valeur nulle dans la bascule 89. Une valeur non nulle indique une inégalité entre A et B, auquel cas la position G indique laquelle des deux valeurs est la plus grande. Si G est égal à 1, A est supérieur à B et si G est égal à zéro, A est inférieur à B. Le complément à deux de la valeur exacte de B appliqué à un dispositif 30 de calcul de complément 93 peut être obtenu en utilisant un signal de conditionnement IG(C) qui permet d'obtenir le complément à un de B et de lui ajouter un "un" actif. Un bus d'entrée A 91 est connecté à l'entrée A de l'additionneur 88 tandis qu'un bus d'entrée B 92 est connecté au dispositif 93 à l'entrée B de 35 l'additionneur 88. La valeur exacte des signaux du bus B passe dans le circuit de complémentation 93 lorsque son signal de commande IGCC3 n'est pas utilisé. Les autres entrées IG(B1) et IG(B20 sont connectées par l'intermédiaire du circuit 93 pour fournir un chiffre un ou un chiffre deux comme entrée de valeur exacte à la position de rang le plus bas de l'entrée B de l'additionneur 40 à moins que le signal IGtC) soit utilisé auquel cas on obtient le complément 69 45785 33 2027736 10 15 20 25 30 35 à deux. Le dispositif de test de zéro 94 est connecte au bus de sortie de l'additionneur 87 pour recevoir tous les signaux de sortie provenant de la bascule 89 sauf la sortie G. Les commande d'horloge, de branchement et de transfert 95 reçoivent les signaux à partir du dispositif de test de zéro 94 sur les lignes 94a et b et les signaux provenant de la position de signe G de la bascule 69 et fournissent le signal d'introduction de données IG et le signal d'extraction de données 0G correct, et les signaux de commande de mise en route de la mémoire nécessaires dans tous le système de la figure 1 pour lui permettre de -fonctionner conformément au procédé de la figure 6A. Plusieurs registres sont connectés entre le bus de sortie de l'additionneur 87 et le bus d'entrée A 91. Chacun de ces registres peut recevoir ses données à partir du bus 87 lorsque sa porte d'entrée est actionnée de façon correcte par un signal de commande d'introduction de données IG. De même chacun de ces registres peut fournir un signal de sortie au bus B 91 lorsque sa porte de sortie est actionnée par le signal de commande d'extraction de données appropriées DG. Ces registres sont définis dans le tableau suivant, dans lequel le symbole du registre se trouve dans la colonne gauche et la signification du symbole est donnée dans la colonne droite. ZSAR YSAR ZCNT DSAR Registre d'addresses de la mémoire Z. Il contient l'adresse pour le multiplet suivant de la clef UK-Z à rechercher à partir de la mémoire d'origine 83. Registre d'adresses de la mémoire Y. Il contient l'adresse pour le multiplet suivant de la clef UK- Y à rechercher à partir de la mémoire d'origine 83. Registre F en cours. Il reçoit la valeur F pour la clef comprimée en cours de formation. Registre des multiplets égaux en cours. Il emmagasine le nombre des multiplets égaux dans les clefs UK- Y et UK-Z comparées actuellement. Registre L en cours. Il reçoit la valeur L en cours représentant le nombre de multiplets K dans la clef comprimée en cours de formation. Registre de valeur Z. Il emmagasine le nombre de multiplets restant dans la clef IDK-Z en cours de traitement qui n'a pas été recherchée. Registre d'adresses de la mémoire de destination. Il contient l'adresse du multiplet suivant à emmagasiner dans la mémoire de destination 84. 69 45785 34 2027736 i-A Registre L. ïî emmagasine la valeur L de la dernière clef comprimée engendrée. E^ Registre des multiplets égaux. II emmagasine le nom bre des multiplets égaux déterminés dans la cornparai-5 son des clefs non comprimées immédiatement antérieures. Z Registre des multiplets Z. Il emmagasine le multiplet de la clef UK-Z en cours de traitement. Il peut être aussi utilisé pour emmagasiner le multiplet de la valeur d'indicateur Pi'R CT. 10 Y Registre du multiplet t. Il emmagasine le multiplet de UK-Y en cours de traitement. S Registre de la valeur 3. Il emmagasine la valeur S qui est la différence entre les valeurs Eg et E^. YCNT Registre de valeur Y. Il emmagasine le nombre des 15 multiplets restant dans la clef UK-Y en cours de traitement qui n'ont pas été recherchés. La mémoire d'origine 83 de la figure 1 utilise un seul cycle d'horloge CLK pour lire un multiplet et l'envoyer au registre SSDR, qui fournit le multiplet pendant le cycle suivant au bus de sortie 85 de la mémoire d'origine. 20 Un signal SS est fourni à la mémoire de source 83 pour mettre en route les commandes internes de la mémoire pour envoyer le multiplet à l'emplacement d' adresses dans le registre SSDR, à partir duquel le multiplet est amené au bus 86. La mémoire de destination 84 nécessite deux cycles d'horloge pour écrire 25 un multiplet reçu à partir du registre de données de la mémoire de destination DSDR. Pendant un cycle d'horloge la mémoire 84 reçoit un signal SD de mise en route de la mémoire de destination et elle est adressée par le signal de sortie du registre DSAR en réponse a un signal OG(D), et il vide la position de multiplets adressés. Pendant le cycle d'horloge suivant le contenu du regis-30 tre DSDR est transféré à la position de multiplets qui est adressée dans la mémoire 84. Certains des registres ont une seconde porte d'entrée ou de sortie de sorte qu'ils peuvent recevoir des signaux à partir de plusieurs bus ou envoyer des signaux à plusieurs bus. Lorsqu'un registre a plusieurs portes d'entrée 35 ou de sortie, ces différentes portes sont référencées par des numéros placés après l'identification des signaux de commande respectifs sur la figure 1. Les registres ZCNT et YCNT ont chacun une seconde porte d'entrée connectée au bus de la mémoire d'origine 86 à partir duquel ils peuvent recevoir le multiplet adressé à partir ds la mémoire d'origine 83 lorsque la porte con-40 ditionnée par un signal de commande IGCZCNT3-2, IGCYCNT3-2. Leurs autres por 45785 35 2027736 tas d'entrée font la liaison avec le bus de sortie de l'additionneur 87 lorsqu'elles sont actionnées respectivement par un signal de commande IG(ZCNT)-1, ou IGtYCNTÎ-1. Les registres ZSAR et YSAR ont chacun des secondes portes de sortie qui 5 font la liaison à l'entrée d'adressage de la mémoire d'origine 83 lorsqu'elles sont actionnées respectivement par les signaux de commande OGCZSAR3-2, ou 0GCYSAR)-2. Leurs autres portes de sortie les relient au bus A 91 lorsqu'elles sont actionnées respectivement par 0G(ZSAR]-1, ou 0G(YSAR)-1. Les registres E^, S, et YCNT ont des secondes portes de sortie qui les 10 relient au bus B 92 lorsqu'elles sont actionnées par un signal de commande respectif 0G(E^)-2, OGCSJ-2, et 0G(YCNT)-1. Leurs autres portes les relient au bus A 91 lorsqu'elles sont actionnées respectivement par les signaux de commande 0G(E^)-1, 0GCSJ-1, ou 0G(YCNT)-2. Le registre DSAR peut être connecté soit au bus A par le signal IG(DSAR), soit à la mémoire de destination 84 par 15 le signal OG(D). Les figures 2 A-N constituent un bloc diagramme d'une réalisation particulière des commandes d'horloge, de branchement et de conditionnement 91 pour engendrer les signaux de commande nécessaires pour actionner le circuit de la figure 1 conformément au procédé représenté sur la figure BA. 20 II est évident pour l'homme de l'art, après étude de cette exposé, que de nombreux autres circuits différents de celui de la figure 1 peuvent être utilisés et que en ce qui concerne le circuit de la figure 1 différentes formes de commande 95 peuvent être réalisées différemment de la forme particulière des commande représentées sur les figures 2A-2Q-3. 25 La figure 2A représente une forme détaillée des commandes d'horloge de branchement et de conditionnement 95 de la figure 1, qui sont représentées en détail dans les figures suivantes 2B-N. La figure 2B-1 représente un cycle des signaux fournis à la sortie de l'horloge 101 sur la figure 2B-2. L'horloge 101 est une horloge binaire clas-30 sique conçue pour fournir les signaux représentés. Les cinq signaux fournis sont appelés CLA, CLB, CLC, CLR et CLL. Le signal CLB devient haut en même temps que le signal CLA mais il chute avant CLA. Le signal CLC devient haut à la chute de CLA et il reste haut pendant le même temps que CLB. Le signal CLR est haut après CLC pendant approximativement le même temps que CLC, dans 35 la partie médiane du cyle d'horloge. Le signal CLL est haut à la fin du cycle d'horloge pendant approximativement le même temps que le signal CLC. Les signaux CLA, CLB et CLC conditionnent les circuits des bascules et de l'horloge de commande de séquence représentées sur les figures 2C et □. La réalisation d'une horloge telle que l'horloge 101 fournissant les si-40 gnâux représentés est connue de l'homme de l'art et par suite on ne donnera 69 45785 36 2027736 pas de détail sur cette réalisation. Un oscillateur 102, ou autre source, fournit un signal de sortie qui commande l'horloge 101 par l'intermédiaire d'une porte 103. L'oscillateur 102 peut, fournit des signaux de sortie ayant une fréquence de 10 millions ou plus 5 impulsions par seconde. Un circuit d'arrSt de l'horloge 105 commande le conditionnement de la porte 103 au moyen d'une bascule d'arrêt 104. Une ligne de signal de mise en route 100 relie l'entrée de restauration de la bascule 104, qui lorsqu'elle.est excitée conditionne la porte 103 pour 10 transmettre les impulsions de l'oscillateur afin de commander l'horloge 101 continuellement jusqu'à ce que les impulsions de l'oscillateur soient bloquées par le déclenchement de la bascule 104 avec un signal provenant d'un circuit OU 106. En conséquence l'horloge 101 fonctionne de façon cyclique continuellement une fois que la bascule 104 est restaurée par le signal de mise en route 15 et l'horloge 101 s'arrêtte lorsque la bascule 104 est enclenchée par un signal provenant de la porte OU 106. La porte OU 106 fournit un signal d'arrêt chaque fois que le procédé de la figure 6A nécessite une fin d'opération. Par exemple un signal d'arrêt se produit lorsque la fin d'index est détectée ou lorsqu'une condition d'erreur 20 est détectée qui empêche d'obtenir un résultat fiable pour les opérations réalisées par le procédé décrit. La chronologie des signaux d'arrêt particuliers est indiquée par les références sur les entrées des portes ET 107 à 110 de la figure 2A-a. La figure 14Q constitue un tableau de la séquence des signaux de commande 25 pour mettre en oeuvre le procédé des figures 3A-E avec le circuit représenté sur la figure 1. Le tableau de la figure 2Q représente la succession de plusieurs cycles CLK et représente les signaux de commande fournis pendant chaque cycle CLK. Le tableau comprend 62 cycles CLK différents identifiés sur le côté gauche du tableau par un numéro compris entre 0 et 127. Le tableau comporte 30 trois colonnes par mi lesquelles la colonne centrale est intitulée "T ou F" et c'est la colonne normale pour les opérations séquentielles. Les deux autres colonnes, T à gauche et F à droite sur la figure 2Q, sont utilisées pendant les opérations de branchemnet. L'état du signal de sortie du basculeur de branchement 110 de la figure 35 2N commande celle des colonnes T ou F de la figure 2Q qui est à utiliser. Cependant l'état de sortie T ou F du basculeur de branchement 110 est ignoré lorsque la colonne médiane de la figure 20 est à utiliser. L'utilisation du signal de sortie T ou F pour choisir une colonne particulière de la figure 2Q est déterminée par les circuits d'entrée et de sortie des figures 2 F-K 40 en combinaison avec l'entrée de conditionnement des horloges des figures 2, 69 45785 37 2027736 B-2 et 2C. Cette entrée de conditionnement de l'horloge interrompt l'arrêt normal de l'horloge. Les cycles CLK sur la figure 2Q commencent en 127, qui restaurent tous les circuits critiques. Le tableau se termine au cycle CLK 73 qui provoque 5 un branchement pour revenir au cycle CLK 0. Chaque succession de cycles CLK ■ 0 à CLK 73 permet de réaliser les étapes du procédé de la figure 6A pour engendrer une seule clef comprimée à partir d'un couple de clefs nori comprimées. Les cycles CLK initialement passent de CLK 127 a CLK 0. CLK 127 n'est exécuté qu'une fois au début de la formation d'un index CK. Ensuite, la suite 10 des cycles CLK est: 0-11, 16-27, 32-44, 48-60, et 62-73. Pendant la succession des cycles CLK certains cycles peuvent être sautés ou repris ce qui dépend de la configuration des données des couples de clefs non comprimées traités. Les circuits de commande de branchement sont sensibles à la configuration des données. 15 Les cycles CLK sur la figure 2Q exécutent les opérations détaillées re présentées dans l'organigramme des figures 3A-E qui appliquent le procédé de la figure 6A au circuit de la figure 1. Dans les figures 3A-E est indiquée une relation entre chaque étape représentée par un rectangle et les cycles CLK correspondants pendant lesquels est exécutée cette étape. 20 Tous les signaux de conditionnement qui sont groupés et séparés par une virgule dans une colonne de la figure 2Q sont amenés pendant le même cycle CLK aux portes de la figure 1 bien que certains signaux soient amenés à des instants différents pendant les mêmes cycles, tels qu'aux instants CLC, CLR, ou CLL. 25 Tous les signaux de la figure 2GJ sont représentés sur la figure 11 sauf les signaux d'entrée de restauration et les signaux de branchement TZ, TP et TN. Les signaux de branchement sont engendrés par les circuits des figures 2M et N. Les entrées de restauration aux registres, ainsi que les registres en eux-mêmes sont classiques et ne sont pas représentés en détail pour éviter 30 de compliquer les dessins. On va donner ensuite des exemples du fonctionnement des quatre premiers cycles CLK dans la figure 2Q, ce qui à l'aide des figures 3A-E montrera au lecteur comment tous les cycles CLK de la figure 2Q peuvent être compris. Pendant le premier cycle CLK 127, les registres YSAR et DSAR sont chargés 35 avec les adresses de mise en route pour une opération de formation d'index CK. Le registre YSAR est chargé par l'adresse du multiplet UK CNT-0 dans la mémoire d'origine 83 au début de l'index non comprimé du type représenté sur la figure 13. Le chargement initial pour le registre DSAR est réalisé pour adresser une première position de multiplets dans la mémoire de destination 40 84 à laquelle le multiplet L pour la première clef comprimée de la chaîne de 69 45785 38 2027736 clefs comprimées résultante doit être emmagasiné en utilisant le format repré- ' sente sur la figure 14A. Les mémoires 83 et 84 peuvent être situées dans le même emplacement physique dans lequel la chaîne de clefs comprimées engendrées chevauche la chaîne 5 des clefs non comprimées d'origine, dans ce cas,. DSAR peut initialement être chargé avec la même adresse que YSAR. Pendant le cycle CLK 0,, les signaux 0G(YSAR)-2, et SS sont au niveau haut. Il en résulte que l'adresse dans le registre YSAR est envoyée à la mémoire d8origine 83 ou elle adresse.le multiplet de valeur UK CT-0 de la première 10 clef non comprimée. Le signal SS met en route un cycle de mémoire pour lire le multiplet adressé et l'envoyer dans le registre SSDR et il sera disponible sur le bus 86 pendant le cycle suivant. Le cycle CLK 1 fournit les signaux IGCYENT5-2 et 0G(YCNT)-2 pour provoquer l'introduction du multiplet UK CT-0 sur le bus 86 dans le registre YCNT et 15 pour que ce multiplet soit extrait du registre YCNT et envoyé au bus d'entrée A 91 de l'additionneur. Lorsque l'additionneur 88 reçoit un signal d'entrée, il est introduit dans la bascule 89 par CLL à la fin du.même cycle et il sera disponible sur le bus de sortie de l'additionneur 87 et par le dispositif de test de zéro 94 pendant le cycle suivant. UK-0 sera UK-Y dans la première compa-20 raison entre UK-Y et UK-Z. Le cycle CLK 2 fournit un signal TZ qui provoque l'examen de la sortie du dispositif de test de zéro 94, le signal 0G(YSAR)-1 extrait le contenu du registre YSAR et l'envoi à l'.entrée A de l'additionneur 88, et le signal IGCB1) transfère un chiffre 1 à l'entrée B de l'additionneur 88. Pendant l'impulsion 25 d'horloge CLL à la fin du cycle CLK 2 le contenu de la bascule 89 sera l'adresse de YSAR augmenté de un. Pendant le cycle CLK 3 un branchement est réalisé qui est déterminé pendant le signal TZ dans le cycle CLK 2 par le réglage T ou F du basculeur 110 de la figure 2N. La direction du branchement T ou F dépend des conditions des 30 données d'entrée représentées sur la figure 3A, dans laquelle le multiplet UK CY-0 est testé pour voir s'il ne contient que dBs zéros. Un multiplet de valeur UK ne peut pas être nul à moins qu'il soit utilisé pour indiquer une fin d'index. Par suite, un multiplet de valeur UK ne contenant que des zéros arrête l'opération en provoquant un branchement à 3T. Si la valeur UK n'est 35 pas nulle l'opération se poursuit avec un branchement aux signaux 3F et le signal IG(YSAR) introduit dans YSAR l'adresse YSAR incrémentée, le signal OG( YCNT5-1 extrait le contenu du registre YCNT et l'envoie au bus A 91, et le signal OG[YSAR)-.1 extrait le contenu du registre YCNT et l'envoie au bus B 92. La somme de ces entrées à l'additionneur sur les bus A et B est disponible 40 dans la bascule 89 pendant le cycle suivant. Cette somme représente l'adresse 69 45785 39 «2027736 du multiplet UK CT-1 dans la mémoire 83. UK-1 deviendra UK-Z au cours de la première comparaison de UK-Y et UK-Z. De la manière précédente on peut tracer 1'organigramme des opérations de la figure 1 en utilisant le tableau représentant les signaux de commande 5 de la figure 2Q> et le tableau des figures 3 A-E pour obtenir le procédé de la figure 6A. Les signaux de commande de branchement TZ, TP et TN sont engendrés dans les circuits des figures 2M et N. Le signal de commande TZ est engendré par un circuit OU 122, le signal TP par la porte 123 et le signal TN par un circuit 1D OU 126 sur la figure 2N. Le signal TZ détermine le moment où l'état d'une bascule de test de zéro 127 sur la figure 2M doit être transféré au basculeur de branchement 110. Lorsque la bascule 127 est enclenchée, 8lle indique la valeur nulle dans la bascule 89 et lorsqu'elle est restaurée elle indique la valeur non nulle. Ainsi, 15 un signal de sortie zéro provenant de la bascule 127 est transféré comme état T pour le basculeur 110, et un signal de sortie non nul est transféré comme état S pour le basculeur 110. Les signaux de commande TP et TN déterminent lorsque l'état d'une bascule de test de signes 120 sur la figure 2M doit être transféré au basculeur de 20 branchement 110. La distinction entre les signaux TP et TN est que pour le même état de sortie de la bascule de test de signe 128, le basculeur de branchement 110 est mis à l'état opposé par TP et TN. Ainsi, pour un signal de sortie G1 Csigne positif de la bascule de l'additionneur) provenant de la bascule 128, un signal TP met la bascule 110 à un état de sortie T, tandis qu'un 25 signal TN met la bascule 110 à un état de sortie F. Les cycles CLK particuliers de la figure 2Q pendant lesquels les signaux TZ, TP et TN sont fournis sont indiqués par les numéros sur les entoées des circuits respectifs 122, 123, 124 et 126. Un circuit de demande 121 sur la figure 2M détermine lorsque le contenu 30 de la bascule 89 doit être testé pour rechercher la valeur zéro et de signe en transférant l'état de sortie du circuit de test de zéro 95 et la position G de la bascule 89 de la figure 1, aux bascules 127 et 128 respectivement. Le circuit 121 fournit le signal de demande en réponse à une introduction de signaux à la bascule 88 de l'additionneur provenant d'un des registres L^, 35 L , ZCNT, L , Z, ou YCNT. Le signal de demande est fourni aux: circuits ET 131-B A 134 de la figure 2M. Ainsi, la bascule de test de zéro 127 et la bascule de test de signe 128 sont réglées pour indiquer l'état zéro et le signe du contenu de la bascule de l'additionneur en réponse à un signal ePentrée au circuit OU 121 à la fin d'un cycle par une impulsion d'horloge CLL. 40 Lorsque la bascule de test de zéro 127 ou la bascule de test de signe 45785 40 2027736 128 est enclenchée elle conserve son réglage jusqu'à ce que le circuit OU 121 reçoive de nouveau un signal d'entrée ce qui peut se produire plusieurs cycles plus tard. Par suite, un signal TZ,.TP ou TN provoque le transfert de l'état de la bascule 127 ou 128 ou basculeur de branchement 110 pour commander l'opéra-5 tion du système conformément à la séquence représentée sur la figure 20. Le basculeur de branchement 110 est aussi enclenché à la fin d'un cycle d'horloge par une impulsion d'horloge CLL lorsqu'un signal TZ, TP, ou TN est présent, de sorte que ce signal de sortie particulier T ou F est disponible pendant les cycles CLK suivants jusqu'à ce que le basculeur 110 soit de nouveau action-10 né. Par suite la sortie du basculeur de branchement 110 est utilisée comme représenté sur la figure 2A pour sélectionner les cycles CLK désynchronisés pour l'horloge de commande de séquences de la figure 2C en utilisant les impulsions d'horloge CLA. La succession séquentielle normale de la figure 2Q est 15 provoquée par l'horloge de commande de séquences de la figure 2C recevant les impulsions CLB et la bascule de l'horloge de la figure 2C recevant les impulsions CLC. L'horloge de commande de séquence de la figure 2C fournit son signal de sortie à l'entrée de la bascule de l'horloge de commande de séquence de la 20 figure 2D. L'horloge de commande de séquence a tous ses basculeurs binaires BT mis à l'état un par une impulsion sur la ligne de départ 100 qui met aussi en route l'horloge 101 de la figure 2B-2 pour fournir ses impulsions d'horloge. Le signal de sortie ne contenant que des uns de BT 1-B4 est transféré au bascules 1-64 de la figure 2D par l'impulsion d'horloge CLC pour exciter les lignes 25 CL 1-64 allant au décodeur binaire 23 de la figure 2E qui excite sa ligne de sortie CLK -127. Le signal de sortie CLK 127 conditionne la porte ET 208 de la figure 2C, qui à l'impulsion CLA suivante, fait passer l'horloge à un état 0 partout en mettant tous les basculeurs BT à zéro. Ce réglage est transféré de la manière précédemment décrite aux circuits des figures 2D et E pour exci- 30 ter la ligne CLK 0. Ceci amorce la succession normale des cycles, dans laquelle les cycles CLK sont amorcés par les impulsions CLC qui provoquent le transfert dans les bascules L1-64. Ensuite l'horloge de commande de séquence fonctionne de façon cyclique sous commande des impulsions CLB jusqu'à ce que l'opération séquentielle soit interrompue par l'excitation d'une des portes d'entrée de 35 la figure 2C. Chaque impulsion d'horloge CLB, sauf pendant CLK 11T, 35F, 54T, 60 et 62F, passe par la porte ET 201 de la figure 2C pour mettre le basculeur BT- 1 à son état opposé-. Les portes ET 211-215 de la figure 2D ramènent leur signal de sortie C 2-64 aux portes ET 203-207 de la figure 2C. La porte ET 202 40 reçoit le signal de sortie "valeur exacte" C1 provenant de la bascule L-1 69 45785 41 2027736 de la figure 2D. Une fois que CLK □ a provoqué la mise à l'état 0 de tous les basculeurs BT par une impulsion d'horloge CLA, l'impulsion CLB suivante met le basculeur BT-1 à l'état T de sorte que l'horloge de commande de séquences est mise 5 à un» L'impulsion CLC suivante transfère cette valeur un à la bascule de l'horloge sur la figure 2D qui fournit CL1 et ramène le sighal de sortie C1 à la porte 202. CLK 1 engendre CK 1 à partir du circuit de décodage de la figure 2E. ■ L'impulsion CLB suivante pendant CLK-1 passe par la porte 202 et la porte 201 pour mettre l'horloge à la valeur 2 qui est transférée à la bascule de 10 l'horloge par l'impulsion CLC pour mettre CL2 à l'état haut et amorcer CLK 2. Il n'en résulte zucune réaction, à partir de la porte ET 211, et les cycles suivants CLB ne font basculer que BT-1 pour fournir à l'horloge dë commande une valeur 3 qui est transférée par CLC à la bascule de l'horloge et conditionne la porte 211 pour fournir CL2 et CL1 pour amorcer CLK 3. C2 est ramené à la 15 porte 203 sur la figure 2C et C1 est ramené à la porte 202, Par suite l'impulsion CLB au cycle d'horloge suivant fait basculer BT-1, BT-2, et BT-3 pour obtenir une valeur 4 pour l'horloge de commande. De cette manière l'ensemble de l'horloge de commande de séquence et de la bascule de l'horloge de commande de séquence fonctionne comme un tout de "20 sorte que les cycles séquentiels provenant de l'horloge 101 font avancer l'horloge de commande dans une séquence binaire. Cette séquence binaire est interrompue par l'excitation d'une des portes ET d'entrée au circuit 14C qui provoque l'interruption de sa séquence à la condition d'entrée indiquée conformément aux représentation de branchement du tableau de la figure'2Q sous comman-25 de des réglages T et F du basculeur de branchement 110 de la figure 2N. Les signaux CL 1-64 provenant de la bascule d'horloge de la figure 2D sont amenés comme entrées binaires à un décodeur binaire représenté sur la figure 2E, ces signaux peuvent être des signaux d'entrée binaires classiques au décodeur dans lequel chaque combinaison des signaux d'entrée binaires pro-30 vôque l'excitation d'une seule ligne de sortie différente. Les 62 lignes de sortie du décodeur correspondent aux 62 cycles CLK différents indiqués dans la colonne gauche de la figure 2Q. Chaque ligne n'est active que pendant une période de l'horloge 101 à un instant donné. Les signaux ÛG et IG d'extraction et d'introduction des données dans les 35 registres, sont engendres par les circuits de commande représentés sur les figures 2F-L qui reçoivent les signaux d'horloge CLK et les "signaux T, F à partir du basculeur de branchement 110 de la figure 2N à partir duquel tous les signaux IG et 0G sont obtenus. Les signaux de commande IG engendrés sur les figures 2F-1 et 2F-2 comman-40 dent l'introduction des données à partir du bus de sortie de l'additionneur. 69 45785 42 2027736 Ces. signaux de commande IG sont synchronisés par les impulsions CLR» Tous les autres signaux IG et DG sont actifs dans tqut le cycle CLK nécessaire qui commence à l'instant CLC et dure pendant un cycle de l'horloge 101. Les signaux de commande engendrés sur les figures 2G-1 et -2G-2 provoquent 5 l'extraction des données sur le bus A d'entrée de l'additionneur. Les signaux de commande engendrés sur la figure 2H provoquent l'extraction des données et le renvoi à l'entrée B de l'additionneur. Les signaux de commande sur la figure 2J provoquent l'extraction des données et leur envoi à la mémoire d'origine 83, Les signaux de commande sur la figure 2K provoquent, l'introduction 10 des données à partir du bus de sortie 87 de la mémoire d'origine et les signaux de commande sur .la figure 2L provoquent l'introduction des données à la mémoire de destination 84. Le tableau de.la figure 20 résume le procédé de la figure 6A mis en oeuvre avec le circuit de la figure 1 en utilisant la séquence des signaux de comman-15 de représentés dans l'organigramme des figures 3A-F. La figure 3 représente la relation entre les figures 3A-F. Sur la figure 3A, l'opération- de, restauration de tous les circuits critiques de la figure '1 est exécutée par l'étape 10. Cette opération exécute l'étape 10 de la figure 6A puisque les registres -et L^ sont mis à zéro par 20 la restauration. Les registres YSAR et DSAR sont aussi mis aux conditions initiales pour contenir les adresses de mise en route nécessaires dans les mémoires 83 et 84. Enuiste on passe à l'étape 11 pour obtenir le groupe suivant de clefs UK-Y et UK-Z (en commençant avec le premier couple). L'étape 11 est exécutée 25 lorsque deux multiplets UKCT séquentiels sont recherchés respectivement dans les registres YCNT et ZCNT. Initialement le-registre YSAR contient l'adresse du multiplet de valeur UK CT pour la première clef UK-Y. Ensuite ce multiplet est recherché dans le registre SSDR et introduit dans le registre YCNT pendant les cycles d'horloge 0 et 1. Le multiplet YCNT subit un test de zéro ainsi 30 que tous les multiplets UK CT recherchés. Ensuite l'adresse de la clef UK- Z est engendrée en recherchant le multiplet de valeur de l'indicateur Y (PTR CT) en lui ajoutant le contenu du compteur YCNT, en ajoutant cette somme au contenu de YSAR et en chargeant le résultat dans le registre ZSAR. Pour cela les contenus de YCNT et YSAR sont transférés à l'additionneur 88 et leur somme 35 est transférée de la bascula 89 au registre ZSAR pour obtenir l'adresse du premier multiplet PTR CT pendant les cycles CLK 3 et 4. Ensuite, le registre ZSAR adresse la mémoire 83 pour rechercher le multiplet de valeur de l'indicateur Y (PTR CT), qui est transféré dans le registre Y pendant les cycles CLK 4 et 5» L'adresse du multiplet UK CT suivant est engendrée en envoyant le con-40 tenu du registre Y et le contenu de ZSAR à. l'additionneur 8B, et leur somme 69 45785 43 2027736 dans la bascule 89 est transférée dans le registre ZSAR pour lui fournir l'adresse du multiplet UK. CT pour la clef UK-Z pendant les cycles CLK 5, 6 et 7. Pendant l'étape 12 est réalisé un test dé zéros de chaque multiplet de 5 valeur UK^-Z recherché tCT BT) une fois qu'il a été transmis à la bascule 89 pendant le cycle CLK 8. Si, il est nul; une fin d'index est indiquée et les cycles CLK 9T et 10T remettent les registres L0 et Fg à zéro. S'il n'est pas nul on passe à l'étape 13. L'étape 13 est réalisée lorsque les multiplets Y et Z correspondant sont 10 recherchés à partir de la mémoire 83 transférée aux registres Y et Z et comparée pendant les cycles CLK SF, 9F, 10F et 16. La comparaison est obtenue entre les multiplets Y et Z dans les registres en les transmettant à l'additionneur 88 qui ajoute le multiplet Z en valeur exacte au complément binaire à deux du multiplet Y. L'égalité entre les multiplets Y et Z est indiquée par une 15 valeur nulle dans la bascule 89 comme déterminé par le circuit de test de 0 94. L'inégalité est indiquée par une valeur non nulle dans la bascule 89. Si Z est supérieur à Y, aucun bit de dépassement n'est -fourni aux basculeurs de signe G par l'addition du complément à deux. Mais si Z est inférieur à Y un bit de dépassement est fourni aux basculeurs de signe G. Le fait que l'addi-20 tionneur 88 additionne ou soustrait est commandé par un si gnal IG (C) allant au dispositif de complémentation 92. La recherche des multiplets Y et Z se termine pour un couple de clefs non comprimées quelconques lorsque sa position Dg est détectée en trouvant Y inférieur à Z ce qui est la seule condition valable pour indiquer la posi-25 tion D_. On passe ensuite à l'étape 16. D L'étape 14 est introduite chaque fois que l'on trouve une inégalité entre les multiplets Y et Z dans l'étape 13 pendant le cycle CLK 17 et 18T. Ensuite on ajoute un "un" à la valeur des multiplets égaux dans le registre Eg pendant le cyclB CLK 18T et 19T. Ceci est réalisé en transférant le contenu de Eg dans 30 l'additionneur 88 pendant que IG CB1) est excité. Le résultat incrémenté est chargé à partir de la bascule 89 dans le registre Eg. Ensuite, les multiplets suivants Y et Z dans le couple de clefs non comprimées sont recherchés en incré-mentant chacun des contenus des registres YSAR et ZSAR de un par l'intermédiaire de l'additionneur 88 pour obtenir les adresses des multiplets Y et Z suivants 35 dans la mémoire 83. De même les valeurs des multiplets UK restant dans les registres YCNT et ZCNT doivent chacune être diminée de un pour chaque multiplet Y et Z recherché. Ceci est réalisé respectivement par les cycles CLK 19T* 21, 22, 23F, 24F et 23F, 24F, 26 ou 23T, 24T. La soustraction est réalisée en transférant le contenu du registre YCNT ou ZCNT à l'entrée A de l'addition-40 neur tout en fournissant les signaux de commande IG tC)~ et IG (BD. Chaque 45785 44 2027736 résultat diminué dans la bascule 89 subi un test de zéro pendant la période CLK 21, 22 et 27 ou 25 pour déterminer si la fin de l'Une ou l'autre clef non comprimée est atteinte. Si elle ne l'est pas, le résultat dans la bascule 89 est transféré au registre YCNT ou ZCNT, respectivement. 5 Tant que la position Dg n'est pas détectée par la comparaison dans l'éta pe 13, et que ni YCNT ni ZYNT n'est nul dans l'étape 14, les multiplets Y et Z suivants sont recherchés dans l'étape 14 en augmentant de un les valeurs des adresses de YSAR et DSAR. Chaque fois que l'on trouve la position Dg pendant l'étape de comparaison 1Q 13, l'opération de comparaison est terminée et l'étape 16 est introduite. La valeur E,-. emmagasinée actuellement est valide et cette dernière valeur E„ re- t) D présente la position des multiplet UK (Dg-1). Jusqu'à ce que la position Dg soit détectée,, les multiplets Y et Z sont recherchés et comparés, les contenus des registres YCNT et ZCNT sont diminués 15 et le contenu du registre Eg est augmenté quand les étapes 13 et 14 sont exécutées alternativement. Généralement on trouve Dg avant que YCNT ou ZCNT soit diminué jusqu'à zéro c'est-à-dire avant que la position terminale soit atteinte pour UK-Y ou UK-Z. Si YCNT devient nul avant ZNCT ce qui est indiqué pendant la période CLK 25F, la valeur Eg est emmagasinée et elle définit la position 20 Dg. Le contenu de ZCNT ne peut devenir nul avant celui de YCNT, à moins qu'il existe une erreur de classement des clefs non comprimées et une erreur 4BC-1 est indiquée. De même le contenu de ZCNT ne peut être nul à la mSme position de multiplet que celui de YCNT, et cette erreur est indiquée par 46C-2. Par suite, l'erreur 48C-1 ou 46C-2 indique que UK-Y est supérieur à ou égal à UK-25 Z, qui est une erreur de classement. Le classement de formation de clefs ne peut se poursuivre avant que l'erreur de classement dans la séquence des clefs non comprimées soit corrigée. Ensuite l'étape 16 est réalisée en transférant le contenu du registre Eg à l'entrée A de l'additionneur 88 et le contenu du registre E^ par l'inter-30 médiaire du dispositif de complémentation 93 à l'entrée B pour obtenir la valar S dans la bascule 89. Pendant que la.valeur S est transférée de la basucle 89 au registre S pendant la période CLK 32 et 33, l'étape 17 est réalisée en faisant un test ds zéro et de signe pour déterminer si S est inférieur à, égal à, ou supérieur à zéro dans le dispositif de test 94 et la position G. Si le 35 dispositif de test 94 indique une valeur non nulle, la position de signe G indique que S est supérieur ou inférieur à zéro, si S est inférieur à zéro, c'est-à-dire s'il n'y a pas de bit dans la position G et un signal de sortie non nul provenant du dispositif de test 94, on passe à l'étape 30 pendant les périodes CLK 34F et 35T, et l'étape est réalisée en mettant le contenu du re-40 gistre La à zéro en amorçant un cycle de l'additionneur sans lui fournir d'en- D 69 45785 45 2027736 trée. Il en résulte que la bascule de l'additionneur 89 n'aura que des zéros et un transfert du contenu de la bascule est provoqué à' partir de la bascule 89 au registre Lg pour terminer l'étape 30 pendant les périodes CLK 36T et 37T. 5 Ensuite, on exécute l'étape 31 pendant les périodes CLK 37T et 38T en augmentant le contenu des registres de un et en transmettant le contenu de E^ par l'intermédiaire de l'additionneur 88 tout en amenant un un par la ligne de commande IG (B1). Les résultats incrémentés dans la bascule 89 sont transférés au registre pour terminer l'étape 31. 10 Cependant si dans l'étape 17 on trouve que S=0, on passe à l'étape 26A pendant les périodes CLK 34T et 35T, pendant lesquelles le contenu du registre L^ est transféré à l'entrée A de l'additionneur 88 sans lui fournir d'entrée B. Par suite la valeur L. non modifiée se trouve alors dans la bascule 89 où A le dispositif de test de zéro 94 détermine si la valeur L. est nulle ou non n 15 pour exécuter l'étape 26a. Si la valeur L^ n'est pas nulle, les étapes 30 et 31 précédemment décrite sont réalisées. Cependant, si le dispositif de test 94 détermine que L^ est nul on passe à l'étape 32 au lieu de passer à l'étape 30 et une valeur exacte égale à un est placée dans la bascule de l'additionneur 89 en excitant la ligne de commande IG (B1) et le contenu de la bascule 20 est transféré dans le registre L^ pour terminer l'étape 32. Ensuite le contenu du registre Eg est transféré à l'entrée A de l'additionneur 88 sans exciter l'entrée B et la valeur En dans la bascule 89 est transférée dans le registre D F„ pour terminer l'étape 33. D D'autre part si l'étape 17 détermine que S est supérieur à zéro pendant 25 les périodes CLK 34F et 35F on passe à l'étape 26b pendant laquelle le contenu du registre L^ est transféré à la bascule 89 et subit un test de zéro de la même manière que décrit précédemment pour l'étape 26a. Si dans ce cas L^ est égal à zéro, comme indiqué par le dispositif de test 94, le contenu du registre S est transféré à l'additionneur 88, incrémenté de un et le résultat dans 30 la bascule 89 est transféré au registre LR pendant les périodes CLK 40T, 41T pour terminer l'étape 34. Ensuite l'étape 35 est exécutée en transférant le contenu du registre E sans modification dans l'additionneur 88 et la bascule 89 au registre FR pour terminer l'étape 35 pendant les périodes CLK 41T et 42T. 35 Si L^ n'est pas nul alors que S est supérieur à zéro, l'étape 36 est exé cutée pendant les périodes CLK 40F, 41F de même que l'étape 34 mais sans fournir le signal de commande IG CB1J à l'additionneur 88. Ensuite l'étape 37 est exécutée pendant les périodes CLK 41F et 42F de même que l'étape 35 mais en fournissant un signal de commande IG CB1) à l'additionneur avec le contenu 40 du registre E^. 69 45785 46 2027736 L'emmagasinage du contenu des registres Lg et F g engendré par les étapes 30-37 est réalisé pendant les cycles CLK 48-52. Par suite on passe à l'étape 41 à la fin d'une étape 33, 35 ou 37 pour tous les cas avec décalage à droite et les cas sans décalage avec une valeur L non nulle pendant la période CLK A 5 54F. Puisque les contenus de Lg et Eg sont transférés pendant ce temps , il est commode d'exécuter l'étape 44 pendant les cycles CLK 52-54 en les transférant aux registres Lft et E^. La valeur Lg subi un test de zéro pendant les périodes CLK 52, 53 pour déterminer si l'étape 41 doit être sautée ou non. Si Ln n'est pas nul, l'étape 41 est introduite. Cependant l'étape 41 est sautée D 10 à la fin de l'étape 31 pour le cas du décalage à gauche et le cas sans décala~_ , ge avec Lft nul par l'opération de CLK 54T. Pendant les périodes CLK 42-44, le contenu de ZSAR est réglé pour adresser le premier multiplet K qui doit être pris à partir de UK-Z. Ce réglage dépend du fait que L^ est nul ou non pour un cas de décalage à droite. Si L^ est nul, 15 la clef comprimée antérieure n'a pas de multiplet K et les multiplets K actuels commencent à la position D^ dans la clef UK-Z en cours. Ceci est réalisé par l'étape 35a. Mais si L n'est pas nul, la clef comprimée antérieure comporte des multi-A plets K et les multiplets K en cours commencent à la position £0^+1} dans la 20 clef UK-Z. Ceci est réalisé par l'étape 37a qui ajoute un chiffre 2 au lieu du chiffre 1 dans l'étape 35a. De CLK 24 à CLK 41, le compteur ZSAR contient la valeur de l'adresse de la position de multiplets Dg dans la mémoire 03. Pendant les périodes CLKS 42 et 43, D^ peut être obtenu en soustrayant S de Dd et en ajoutant un ou deux pendant les étapes 35a ou 37a. Cette valeur ZSAR 25 est disponible pour rechercher le premier multiplet K lorscjùe L^ n'est pas nul par exemple après l'étape 33 ou 35. Si L^ n'est pas nul par exemple après l'étape 36, l'adresse D^+1 est nécessaire et la valeur dans ZSAR ajustée est transférée à l'entrée A de l'additionneur pendant qu'un signal IG (B1) est amené à l'entrée B. Le résultat 30 D.+1 est alors chargé à partir de la bascule 6H dans le registre ZSAR pour A fournir la première adresse de multiplets K. Pendant l'étape 41 chaque multiplet K est transféré à partir de la mémoire d'origine 83 à la mémoire de destination 64 en recherchant le multiplet de la mémoire d'origine à l'adresse de ZSAR pendant la période CLK 55, 56 en 35 le transférant non modifié par l'additionneur 88 de la bascule 89 au registre DSDR et en l'emmagasinant à l'adresse de DSAR actuelle dans la mémoire 84 pendant les périodes CLK 56, 57. Chaque fois qu'un multiplet K est emmagasiné dans la mémoire de destination 84, les contenus des registres ZSAR et DSAR sont incrémentés de un de 40 sorte que chacun peut adresser l'emplacement du multiplet suivant respective- 69 45785 47 2027736 ment dans les mémoires 83 et 84. Pendant les périodes CLK. 57, 58 ou 59 ceci est réalisé en transférant le contenu de YSAR ou de DSAR à l'entrée A de l'additionneur 88 tout en fournissant un chiffre un exact à l'entrée B et ensuite en transférant le contenu incrémenté dans la bascule 89 pour le renvoyer à 5 YSAR ou DSAR respectivement. De cette manière l'adresse de la position de multiplet suivant est toujours disponible dans YSAR et DSAR. Le contenu de DSAR n'est Incrémenté de un que dans une direction à la différence des contenu de YSAR ou ZSAR qui changent non uniformément parfois. 10 Une fois que les contenus de ZSAR et DSAR sont incrémentés de un et que le multiplet K suivant est transféré, le contenu du registre Lg est diminué de un pendant 18s périodes CLK 59, 60 et subi un test de zéro pour déterminer si plusieurs multiplets K doivent être transférés. Si Lg n'est pas nul, pendant la période 62F le multiplet K suivant est. recherché à partir de UK-Z et l'éta-15 pe 41 de la figure 3 est reprise pour chaque multiplet K. Eventuellement, L_ D est diminué jusqu'à zéro indiquant que tous les multiplets K ont été transférés. Ensuite, CLK 62 indique que l'indicateur associé à UK-Y doit être transféré à la mémoire de destination 34 et on passe à l'étape 43. L'étape 43 transfère le multiplet PTR CT et les multiplets indicateurs associés à UK-Z. 20 Après avoir introduit l'étape 43 le registre YCNT contient une valeur représentant le nombre de multiplets de bruit dans UK-Y (qui sont les multiplets suivant la position de multiplets Dn) étant donné que le contenu du re- D gistre YCNT n'est pas modifié depuis CLK 22. De rfiime le registre YCNT contient alors l'adresse du multiplet après le multiple%Dg dans K-Y puisque le contenu 25 de YSAR n'est pas perturbé depuis CLK 21. Si le registre YCNT subi un test de zéro pendant les périodes CLK 62T et 63, le registre YSAR contient l'adres-e du multiplet PTR CT. Si YCNT n'est pas nul l'adresse pour le multiplet PTR CT doit être engendrée pendant les périodes CLK 63, 64F. Dans le dernier cas, l'adresse du multiplet PTR CT est engendrée en ajoutant le contenu du registre 30 YCNT au contenu du registre YSAR. Les cycles CLK 63 et 64F sont utilisés pour déplacer les deux contenus et les amener à l'additionneur .88 et déplacer leur somme de la bascule 89 dans le registre YSAR, qui contient maintenant l'adresse du multiplet de valeur de l'indicateur Y (PTR CT). Ensuite, le multiplet de valeur de l'indicateur Y est recherché à partir 35 de la mémoire 83 et amené dans SSDR et au registre YCNT pendant les périodes CLK 64 et 65 en utilisant l'adresse dans le registre YSAR. L'adresse est alors transférée du registre YCNT au registre DSDR pendant les périodes CLK 65 et 66 et elle est emmagasinée dans la mémoire de destination 84 à la position adressée à partir de DSAR. Ensuite YSAR est augmenté de un pendant les cycles ' 40 CLK 66 et 67 par l'intermédiaire de l'additionneur 88 de la manière p.rêcédem- 45785 48 2027736 ment décrite. Le contenu de YCNT est diminué et subi un test de zéro. Ensuite, le premier multiplet de l'indicateur Y est recherché et transféré au registre Y et le contenu de DSAR est augmenté de un pendant les périodes CLK 67, 68. Le multiplet indicateur est transféré du registre Y à DSDR et emmagasiné dans 5 la mémoire de destination 84 pendant les périodes CLK 68 et 69. Ensuite, le contenu du registre YCNT est transféré à la bascule de l'additionneur 89 et subit un test de zéro pendant CLK 69, 70. Si le contenu de YCNT est diminué et n'est pas nul, CLK.71F est exécuté pour diminuer le contenu die YSAR et rechercher le multiplet indicateur Y suivant. Ensuite, CLK 68 est introduit et DSAR 10 est incrémenté. Lorsque le contenu de YCNT est diminué à zéro le transfert de l'indicateur Y est terminé et CLK 71T est exécuté. Ensuite, les contenus de YSAR et DSAR sont incrémentés pendant. CLK 71T, 72 en préparation de l'emmagasinage du multiplet suivant dans les mémoires 83 et 84 et le registre E est mis à zéro pen- D 15 dant CLK 73. A la fin de l'étape 43 on revient à l'étape 11 en passant à CLK 0 pour rechercher le couple suivant de clefs non comprimées. Une fois que le dernier transfert de l'indicateur Y est terminé dans l'étape 43, le registre YSAR contient l'adresse pour le multiplet UK CT de la clef UK-Z dans l'opération main-20 tenant terminée. Par suite, le registre YSAR contient l'adresse de la clef UK-Y dans le couple suivant de clefs non comprimées et il est prSt à commencer l'exécution dans l'étape 11. Une seconde réalisation de la présente invention est représentée par le circuit des figures 1.5 et 15 A-F. Cette réalisation utilise le format de champ 25 F. C(Facteur) maximum pour un index comprimé qui est engendré par l'organigramme de la figure 6B. La distinction principale entre les organigrammes des figures 6A et B a lieu après la sortie de l'étape 30. Sur la figure 6B le registre E^ est utilisé pour engendrer une valeur Fg maximum tandis que sur la figure 6A, le registre E_ est utilisé pour engendrer le facteur minimum Fn. Sur la □ D 30 figure 6B on fait une étape de test 26 sur le contenu du registre L^ pour déterminer si oui ou non un digit un doit être ajouté au contenu du registre E afin d'engendrer F . Si L n'est pas nul, on passe à l'étape 31A dans la- A D A quelle un "un" est aj.outé à E^ pour engendrer F0. D'autre part si L^ est nul, comme déterminé par l'étape 26c on passe à l'étape 31B qui emmagasine le con-35 tenu du registre EA dans le registre Fn. Les deux étapes 31A et 31B conduisent D à l'étape 44 sur le figure 6B. Un circuit de commande est utilisé dans les figures 15A-F pour la seconde réalisation, et il représente les changements nécessaires dans les circuits de la première réalisation représentée sur les figures 2A-N, afin de réaliser .40 la commande, sur la seconde réalisation du circuit représenté sur la figure 69 45785 49 2027736 1. Par suite le schéma de la figure 15 applique le procédé de la figure 6B au circuit de la figure 1. Le schéma de la figure 15 est différent du schéma de la figure 3 à cause de la substitution de la figure 15A à la figure 3C. La figure 15A obtient le champ F„ maximum par les étapes 31A, 26C et 31B avec 5 une séquence quelque peu différente mais équivalente à celle trouvée dans la figure BB. Pendant les cycles 37T, 38 de la figure 15, l'étape 31A ajoute un "un" au contenu du registre E^ et emmagasine le résultat dans le registre Fg pendant les périodes CLK 37T, 38. 10 Ensuite, un branchement inconditionnel est réalisé à CLK 45 qui exécute l'étape de test de zéro 26c sur le contenu du registre L^ qui est envoyé à la bascule 89 pendant la période CLK 37T. Si L^ n'est pas nul, l'étape 26c effectue un branchement à CLK 46F qui effectue un branchement inconditionnel à CLK 48. D'autre part si L^ est nul, l'étape 26c effectue un branchement à 15 CLK 46T qui transfère le contenu du registre E. à l'additionneur 88 et CLK A 47 introduit le contenu de E^ à la bascule de l'additionneur dans le registre Fg pour exécuter l'étape 31B. Ensuite on passe à l'étape 48 et l'opération se poursuit de la même manière que pour la première réalisation. La figure 15B représente un tableau de la séquence des signaux de comman-20 de pour la seconde réalisation. La figure 15B illustre simplement en détail les cycles CLK qui sont différents des cycles CLK de la première réalisation représentés sur les figures 2Q-1 à 2Q-3. Les cycles représentés sur la figure 15B obtiennent les étapes représentées sur la figure 15A. La figure 15F représente la modification apportée à la figure 2N pour 25 obtenir la fonction de test de zéro nécessitée par les étapes et cycles des figures 15A et B. Le circuit représenté sur la figure 15F est substitué au circuit correspondant 122 de la figure 2N et tous les autres circuits de la figure 2N sans changement. La figure 15C représente une substitution dans les figures 2C-2nécessaire pour obtenir une horloge de commande de séquences pour 30 la seconde réalisation. La seconde réalisation utilise sans changement la bascule de l'horloge de commande de séquences de la figure 2D, et le décodeur de commande de séquence de la figure 2E. De même la seconde réalisation substitue le circuit représenté sur la figure 15D au circuit correspondant de la figure 2F-1 et utilise tous les autres circuits de la figure 2F sans changement. De 35 même la seconde réalisation remplace les circuits représentés sur la figure 15E aux circuits correspondants les figures 2G-2 et utilise sans changement les autres circuits des figures 2G. En conséquence, le circuit représenté sur les figures 15C-F comprenant le circuit référencé à partir des autres dessins fournit la seconde réalisa-40 tion pour exécuter le procédé utilisant une valeur F maximale pour engendrer 69 45785 50 2027736 un index comprimé. Bien que l'on ait décrit dans ce qui précède et représenté sur le dessin, les caractéristiques essentielles de l'invention appliquées à un mode de réalisation préféré de celle-ci, il est évident que l'homme de l'art peut y ap-5 porter toutes modifications de forme ou de détail qu'il juge utiles, sans pour autant sortir du cadre de ladite invention. 69 45785 51 2027736 REVENDICATIONS 1.- Procédé pour engendrer à partir d'un ensemble de groupes de signaux enregistrés représentant des clefs destinées à la recherbhe de blocs d'information (groupes qui seront ap-5 pelés "clefs non comprimées" ou éventuellement "clefs1!/, chacune des clefs non comprimées étant composée d'un ou plusieurs multiplets rangés suivant un certain ordre, la position occupée par le premier multiplet étant dite "position d'ordre 1b plus élevé" et les positions suivantes se succédant, par définition, en ordre décroissant, un ordre de classement ayant été préalablement défini 10 pour l'ensemble des multiplets susceptibles de composer des clefs, cet ordre permettant de définir un ordre de classement pour les clefs, la position relative de deux clefs dans ce classement étant déterminée par celle des multiplets d'ordre le plus élevé, ou à défaut par celle des multiplets suivants et ainsi de suite, 15 un autre ensemble de groupes de signaux (groupes qui seront appelés "clefs comprimées") chaque clef comprimée correspondant à une clef non comprimée et une seule caractérisé par les opérations suivantes: a) les clefs sont lues par paires successives, chaque paire comprenant 20 deux clefs consécutives dans l'ordre de classement défini ci-dessus, la première paire étant constitué par les deux premières clefs de ce classement et la deuxième clef de chaque paire autre que la dernière constituant la première clef de la paire suivante, b) chaque paire est examinée en vue de déterminer la première des posi-25 tiens de multiplet, comptées à partir de la position d'ordre le plus élevé, pour laquelle les multiplets des deux clefs de la paire sont différents. 2.- Dispositif pour engendrer, à partir d'un ensemble de clefs non comprimées tel que défini dans la revendication 1, et pouvant être ordonné selon le système défini dans cette revendication, un ensemble de clefs comprimées 30 tel que défini dans cette revendication, caractérisé par des moyens permettant d'effectuer les opérations suivantes : - accès à une paire constituée par une première et une deuxième clefs, la deuxième suivant immédiatement la première dans l'ordre mentionné ci-dessus 35 - détermination de la position d'ordre le plus élevé pour laquelle les multiplets des deux clefs de la paire sont différents - génération d'un signal codé représentant cette position - enregistrement de ce signal comme un des éléments de la clef comprimée 69 45785 52 2027736 correspondant à une des deux clefs de la pairs. 3.- Dispositif conforme à la revendication 2, caractérisé en outre par des moyens, éventuellement confondus en tout et en partie avec ceux mentionnés dans ladite revendication, et permettant d'effectuer les opérations suivan-5 tes: - sélection d'un certain nombre de multiplets de l'une des clefs dans le groupe constitué par les multiplets occupant ladite position et les multiplets d'ordre supérieur - enregistrement des multiplets sélectionnés comme éléments de ladite 10 clef comprimée. 4.- Dispositif conforme à la revendication 3, caractérisé en outre par des moyens, éventuellement confondus en tout "ou en partie avec ceux mentionnés dans ladite revendication et empêchant la sélection des multiplets dont l'ordre est inférieur à celui de ladite position. 15 5.- Dispositif conforme à l'une des revendications 2 à 4, caractérisé en outre par des moyens, éventuellement confondus en tout ou en partie avec ceux mentionnés dans lesdites revendications, pour enregistrer, en même temps que la clef comprimée, une adresse représentant l'emplacement dans la mémoire du bloc de données associé avec la clef non comprimée correspondant à ladite clef 20 comprimée. B.- Dispositif conforme à l'une des revendications 3 à 5;" caractérisé en outre par des moyens, éventuellement confondus en tout ou en partie avec ceux mentionnés dans lesdites revendications, pour effectuer les opérations suivantes: - accès successif à ëeux paires au moins, dans l'ordre de classement des 25 premières clefs de chaque paire tel que défini dans la revendication 1, la deuxième clef de la première paire constituant ainsi la première clef de la paire suivante, et exécution, pour chacune des deux paires, des opérations définies par l'une desdites revendications, - compataison des signaux codés représentatifs de position définis dans 30 la revendication 2, - sélection en fonction du résultat de cette comparaison des multiplets conservés comme éléments de la clef comprimée élaborée à partir de la deuxième paire. 35 7.- Dispositif conforme à la revendication B, caractérisé en outre en ce que,s*. la comparaison montre que la position représentée par le signal codé généré à 69 45785 53 2027736 partir de la deuxième paire est d'un ordre égal ou supérieur à celui de la position représentée par le signal codé généré s partir de la première pairs„ un seul multiplet au plus est conservé* 3.- Dispositif conforme à l'une dss revendications 2 à 7, caractérisé en 5 outre par dss moyens» éventuellement confondus erv tout ou an partie avec ceux définis dans lesdites revendications * peur Effectuer les opérations suivantes: - sélection d'un certain nombre ds smltiplets de la première clef riens le groupe constitué par le multiplet occupant la position définie dans ïa 10 revendication 2 et les multiplets d ■'ordre- supérieur - remplacement du multiplet silsetisnr.é d'ordre le plus bas par 1s multiplet qui lui succède immédiatement dans 1*ordre de- classement préalablement défini - enregistrement des multiplets sélectionnas;, compte tenu de ce rempla-15 cernent» 9.- Dispositif conforme à la revendication 8„ caractérisé en outre par des moyens, éventuellement confondus en tout ou en partie avec ceux mentionnés dans ladite revendication, pour effectuer les opérations suivantes: - comparaison du multiplet résultant du remplacement avec le multiplet 20 de mime rang de la deuxième clef de la paires et en cas d'égalité, exécution des opérations suivantes: a. restauration du multiplet remplacé b. sélection du multiplet occupant 1s position suivante dans la première clef et remplacement da ce multiplet par celui qui lui succède immé- 25 diatement dans l'ordre de classamsnt préalablement défini s. enregistrement de ce multiplet et du multiplet occupant la position eorresDondarvte dans la deuxième clef de "is pairs,