Brevet FR2683346A1 — publié le 19930507

La présente invention concerne un procédé d'indexa- tion et de recherche de données conservées dans une base de données de grande dimension. La dimension physique de nombreuses bases de données contenant une documentation technique, par exemple sous forme de graphiques et de textes, devient de plus en plus gênante lorsque le contenu comprend des pages imprimées. Les descriptions techniques de nombreux systèmes électro- niques par exemple peuvent comprendre une multitude de cahiers d'informations imprimées Mise à part la dimension physique des pages imprimées et reliées, il est difficile de chercher des termes ou phrases contenus dans les pages imprimées d'un cahier Récemment, on a constaté qu'il était plus commode en pratique de conserver les bases de données sur un support électronique plutôt que sur du papier. Habituellement, des lecteurs couplés à des terminaux d'affichage vidéo donnent accès aux informations contenues dans les dispositifs électroniques de mémorisation. Un type courant de dispositif de mémorisation actuellement utilisé pour le stockage d'informations non différenciées telles que le texte, est le disque à haute densité seulement lu (de type compact) appelé "CD-ROM". D'autres types de support électronique de mémorisation sont les disques durs, les bandes magnétiques et les disquettes. Les disques à haute densité sont souvent choisis comme support de mémorisation de données car ils sont commodes, ils contiennent des centaines de mégaoctets d'informations sur un disque peu coûteux et ils sont pratiquement indes- tructibles Malheureusement, la vitesse avec laquelle les informations peuvent être obtenues sur un disque à haute densité, par utilisation de dispositifs d'entraînement non connectés, constitue une restriction importante; par exemple, ils sont beaucoup plus lents que les dispositifs de lecture de disques durs En moyenne, une unité d'infor- mation peut être obtenue à partir d'un disque à haute densité en 1,5 seconde environ et des opérations de lecture séquentielles destinées à l'obtention d'informations contiguës nécessite environ 0,1 seconde Si des informa- tions doivent être obtenues et si l'emplacement des infor- mations sur le disque est inconnu, l'ensemble du disque peut nécessiter une recherche La recherche dans 650 mégaoctets de disque à haute densité prend habituellement plus de soixante minutes. On connaît des schémas destinés à réduire le temps nécessaire à la recherche d'informations sur un disque à haute densité et d'autres dispositifs de mémorisation de grande dimension Ces réalisations mettent souvent en oeuvre des index alphabétiques de mots-clés contenus dans un document sous forme d'un dictionnaire, et des pointeurs dirigés sur les emplacements d'un document auxquels les mots-clés peuvent être trouvés Ces réalisations de recherche de données dans une base de données sont propres au type de données qui sont recherchées Par exemple, les bases de données relatives aux brevets ont souvent des dispositions d'indexation qui lient les champs particuliers d'une base de données Ces champs peuvent comprendre le cessionnaire, le breveté, l'inventeur, etc L'organisation des données de cette manière peut donner des résultats favorables et rapides à la recherche mais l'index de recherche est spécifique à l'application et les informa- tions relatives au type de données recherchées doivent être connues au préalable Il serait préférable d'utiliser un procédé plus générique d'organisation de données dans lequel les champs d'indexation pourraient être utilisés dans l'une quelconque des bases de données textuelles mémorisées Une possibilité de stockage et de lecture d'informations est décrite dans le brevet des Etats-Unis d'Amérique N O 4 276 597 de Dissly et al Ce document décrit un procédé et un appareil d'identification d'enregistre- ments particuliers contenant des informations voulues, ayant les caractéristiques prédéterminées identifiables voulues, dans un ensemble de tels enregistrements dans un fichier de données de la base Un fichier spécial de recherche comprenant des ensembles d'éléments codés sous forme binaire est produit et entretenu à partir du contenu d'informations du fichier de données de la base Bien que ces réalisations soient meilleures que les autres, cer- taines conviennent mieux à des supports particuliers, et la plupart des indexations nécessitent une gestion coûteuse. Le dictionnaire des motsclés et les tables d'indexation occupent souvent autant d'espace de mémorisation sur le disque haute densité que le document lui-même et même plus. L'utilisation d'un dictionnaire important et d'un index de base de données important a aussi tendance à ralentir le processus de recherche car le dictionnaire et la base de données doivent aussi être analysés En conséquence, l'index doit rester aussi petit que possible et les infor- mations associées doivent rester aussi proches que possible. L'invention a pour objet une amélioration du temps nécessaire à l'accès aux données d'un support de mémorisa- tion de données. Elle a aussi pour objet la réalisation d'un ensemble perfectionné d'indexation de données conservées sur un support de mémorisation de données. L'invention concerne un mécanisme de recherche de mots-clés dans une base de données' conservées sur un support d'enregistrement Les mots-clés sont classés en fonction de leur fréquence d'apparition dans la base de données, le classement correspondant à une forme particu- lière d'indexation, l'indexation donnant des tables de consultation qui sont conservées sur le support d' enregistrement. L'invention concerne un procédé d'indexation de mots-clés permettant la recherche dans une base de données enregistrées sur un support d'enregistrement d'informa- tions, le procédé comprenant les étapes suivantes l'ana- lyse de la base de données, l'affectation d'un numéro unique d'identification à chaque mot-clé, plusieurs mots- clés au moins parmi les plus fréquemment utilisés ayant des numéros d'identification qui sont numériquement les plus faibles, la conservation de chaque mot-clé dans l'ordre alphabétique sur le support d'enregistrement, avec le numéro d'identification affecté correspondant qui donne au moins un niveau d'indexation entre les mots-clés et la base de données, la mémorisation d'une table sur le support d'enregistrement, la table liant chaque numéro d'identifi- cation à un mot-clé correspondant de la base de données, et la mémorisation de la base de données sur une partie du support d' enregistrement. L'invention concerne aussi un procédé d'indexation de mots-clés, comprenant l'affectation de l'une de plu- sieurs étiquettes de classe à chaque mot-clé, chaque classe dépendant de la fréquence d'apparition du mot-clé dans la base de données, chaque classe étant associée à un niveau différent d'indexation pour la recherche d'un mot-clé, la classe des mots-clés apparaissant le moins fréquemment dans une base de données ayant les plus petits niveaux d' indexation. Dans un autre aspect, l'invention concerne une base de données et un index de recherche, comprenant au moins un fichier de données, un dictionnaire de mots-clés, le dictionnaire ayant une liste de mots-clés contenus dans le fichier, chaque mot-clé ayant un numéro associé d'identifi- cation, plusieurs mots-clés apparaissant le plus f réquem- ment ayant des numéros d'identification qui varient en sens opposé à la fréquence d'apparition du mot-clé, et plusieurs cartes de page, chaque carte de page comprenant des numéros d'identification, les positions des numéros d'identifica- tion dans une carte de page correspondant à la position des mots-clés dans le fichier de données. On décrit un mode de réalisation de l'invention en référence aux dessins sur lesquels la figure 1 est un schéma d'un disque à haute densité, qui a subi une partition en structures de données selon l'invention; la figure 2 est un tableau représentant l'une des structures de données de la figure i; la figure 3 est un schéma de tables d'indexation représentant la relation entre les structures de données représentées sur les figures 1 et 2; et la figure 4 est un schéma de cartes de page et de tableaux de page selon l'invention. La figure 1 représente un disque à haute densité 10 qui a subi une partition en structures de données Une structure de données peut être sous forme d'une ou plu- sieurs tables ou de la base de données qui est destinée à être mémorisée et vue Les structures de données sont conservées sur le disque 10 et sont codées sous forme binaire Un moteur de recherche (non représenté) sous forme d'un microprocesseur convenablement programmé, exécutant un programme logiciel d'observation, est couplé à un dispo- sitif d'entraînement de disque amovible à haute densité (non représenté) et permet l'accès aux informations conser- vées sur le disque 10 et leur décodage De manière géné- rale, il est souhaitable d'obtenir des informations liées qui sont lues ou analysées sous forme d'un bloc de données continues ou de données ayant des positions proches. Un dictionnaire 12 représenté dans la partition externe adjacente à la périphérie du disque 10 peut conte- nir des millions d'octets d'informations Le dictionnaire 12 n'est pas obligatoirement placé à la périphérie Cepen- dant, pour que la tête du dispositif d'entraînement de disque à haute densité, qui se déplace lentement, puisse se déplacer d'une distance aussi courte que possible à la surface du disque 10 lors de la lecture d'informations, il est avantageux que les informations liées soient aussi proches que possible les unes des autres. Le dictionnaire Selon l'invention, lorsqu'un disque à haute densité est utilisé pour la formation d'un disque-mère, un grand pourcentage du disque est affecté à la mémorisation d'une base de données de documents formés de nombreuses pages dans des fichiers sous une forme qui peut être imprimée ou vue Cependant, une partie du disque est affectée à d'autres structures de données sous forme d'index et de tables utilisés pour la gestion et la recherche des docu- ments conservés sur le disque Ces structures de données liées à la gestion et à la recherche sont transparentes pour l'utilisateur de la base de données Lorsqu'un utili- sateur veut retrouver un mot ou une phrase sur un disque, un énoncé de la recherche est saisi et le mot apparaît sur le terminal s'il se trouve dans le document Il n'est pas nécessaire que l'utilisateur ait une connaissance ou compréhension quelconque du dictionnaire 12, de la table 14 d'apparitions ou des cartes 16 de page Ces structures de données, qui sont décrites plus en détail, forment un mécanisme permettant l'accès rapide aux données Les tables représentées sur les figures 2, 3 et 4 sont des représenta- tions de tables en format binaire qui sont conservées sur le disque 10 Les tables binaires ne sont pas sous une forme que l'utilisateur puisse lire Ces représentations des tables binaires des figures 2 et 3 sont destinées à permettre à l'homme du métier de comprendre les structures de données et les mécanismes qui sont en place. Avant la formation d'un disque-père ou original du disque à haute densité 10, les documents de la base de données destinés à être placés sur le disque 10 sont analysés et un dictionnaire 12 de tous les mots originaux est compilé Chaque mot original se voit affecter un numéro unique d'identification et chaque numéro d'identification est précédé d'un octet de commande La fonction de l'octet de commande est double, un champ de cinq bits identifiant la nature du mot qui suit et ce type est désigné par un mot terminal tel que "the, and, if, but, and then", un champ à trois bits de l'octet de commande à huit bits spécifie le nombre de mots terminaux qui suivent successivement l'octet de commande Après la formation du disque-père, les cartes de page 16 sont construites afin qu'elles correspondent à la disposition directe des pages dans les documents de la base de données Les mots terminaux sont remplacés par l'octet de commande indiqué sur la figure 4, un X indiquant leur apparition La carte 16 de page est un relevé des positions des mots-clés sur une page, sous forme comprimée. Le dictionnaire 12, qui est une structure à deux niveaux, peut comporter des centaines de milliers de mots originaux; ainsi, pour qu'une recherche générale soit réalisée avant la recherche spécifique d'un mot, une recherche de premier niveau est réalisée Comme l'indique les figures 2 et 3, le premier niveau correspond à un index primaire 12 a de mots-clés, et un second niveau correspond à plusieurs blocs 12 b d'index de mots-clés La segmentation du dictionnaire 12 en une structure à deux niveaux réduit au minimum le nombre de mots qui doivent être lus dans le dictionnaire 12 La localisation d'une chaîne initiale d'un mot dans l'index principal 12 a indique de façon générale l'endroit auquel un mot peut être trouvé La comparaison d'un terme de recherche à toutes les clés de l'index primaire 12 a donne le bloc 12 b d'index de mots-clés auquel se trouve le mot recherché, si le mot existe L'index principal 12 a est une table qui comprend des clés ou des blocs initiaux de mots alphabétiques, chaque bloc de début étant un pointeur sur le bloc 12 b d'index de mot-clé Par exemple, les mots-clés "append, apple, asymmetry, and axe" sont tous représentés par la chaîne "appe" et ont un numéro correspondant à leur ligne dans l'index de mots- clés primaire, tel que " 1 " indiquant la ligne 1 Le bloc suivant de mots séquentiels au point de vue alphabétique est "axiom, axis, batmobile, and bust", la seconde ligne de l'index principal 12 a a la forme la moins ambiguë du mot défini par la chaîne "axio" avec le numéro 2 dans le champ de ligne Une recherche de l'un quelconque des mots axiom, axis, batmobile et bust est limitée au bloc 2 du bloc d'index de mots-clés comme représenté sur la figure 2 Le nombre d'entrées de blocs dans le bloc 12 b peut varier et l'exemple donné est purement illustratif L'index principal de mots-clés doit rester aussi petit que possible et doit se trouver dans une mémoire rapide (non représentée) qui est couplée au moteur de recherche, la plupart du temps sinon tout le temps, afin que la localisation rapide d'un bloc d'index de mots-clés soit facilitée. Les blocs 12 b d'index de mots-clés indiqués par l'index primaire 12 a sont transférés sur les parties du disque 10 dans le dictionnaire 12 Ces blocs contiennent des informations particulières relatives à la chaîne de texte cherchée Par exemple, s'il a été déterminé, par une recherche générale binaire de l'index 12 a, que le mot recherché est dans le bloc 2, l'élimination des autres blocs alphabétiquement différents permet la lecture du bloc 2 parmi les blocs d'index de mots- clés et le mot-clé recherché, par exemple "batmobile" est localisé D'autres champs d'informations conservées dans le bloc 2 sont utilisés de façon générale pour la localisation du mot "batmobile" dans le document L'information conservée dans un bloc de blocs 12 b d'index de mots-clés est sous forme du mot complet, du numéro d'identification, du type de mot et de l'information d'apparition ou de l'information de la table 14 d'apparitions Le type de mot et l'information d'apparition sont décrits plus en détail dans la suite. Les blocs 12 b d'index de mots-clés sont placés dans l'ordre alphabétique et des numéros d'identification de mots-clés sont affectés aux mots ou chaînes de texte de manière convenable Cependant, une exception est le fait que les deux cent cinquante six mots statistiquement les plus fréquemment utilisés ont des numéros d'identification qui varient de O à 255, selon leur fréquence d'apparition. Le mot le plus fréquemment utilisé a le numéro d'identifi- cation le plus bas 0, le mot le plus fréquemment utilisé suivant a le numéro d'identification 1, et ainsi de suite jusqu'au numéro d'identification 255 Ainsi, ces deux cent cinquante six numéros d'identification de O à 255 sont pondérés en sens inverse et inversement d'après leur fréquence d'apparition dans une base de données Le but de l'étiquetage des mots les plus fréquemment utilisés avec les numéros O à 255 permet l'identification de chaque apparition dans une mémoire de données d'octets sur une carte de page 16 Lorsque tous les numéros d'identification de O à 255 ont été affectés, le bloc 12 b est mis sous forme alphabétique et tous les mots-clés restant du document qui n'ont pas de numéro d'identification affecté sont désignés par un numéro unique d'identification ayant des valeurs supérieures ou égales à 256 Le terme "document" peut se référer à un seul fichier important ou à de nombreuses centaines de fichiers plus petits, un fichier ayant par exemple de nombreuses pages. La table d'apparitions La table 14 d'apparitions est un index conservé sur une partie du disque 10 contenant des champs ayant les numéros de page et les emplacements des mots-clés sur les cartes de page 16 Une carte de page 16 est une représenta- tion, sous forme lisible par l'homme, d'une page d'un document Des chaînes de texte sous forme de mots-clés n'apparaissent pas sur la carte 16, et les mots-clés sont remplacés par leur numéro respectif d'identification La forme lisible par l'homme se réfère à l'ordre dans lequel les mots sont lus et ne se réfère pas à la carte 16 de page comme étant lisible ou discernable par l'homme. Le dictionnaire 12 a des mots-clés ou chaînes uniques désignés par des numéros uniques d'identification. Cependant, les numéros d'identification doivent être indiqués d'après leurs positions uniques ou multiples dans un document afin que le mot-clé soit positionné dans le document Ce relevé est réalisé dans la plupart des cas à l'aide de la table 14 d'apparitions et des cartes 16 de page Lorsqu'une chaîne ou un mot parmi des mots recherchés se trouve sur une carte particulière 16 de page, le moteur de recherche mettant en oeuvre le logiciel d'observation, utilise la page actuelle et l'emplacement absolu du mot dans le document pour afficher la page sur un terminal d'affichage. Les types de mot Les mots-clés, qui sont des mots simples, apparais- sant une seule fois dans document ou une base de données ayant des fichiers 18 de données, sont appelés mots-clés de type 1 Comme les motsclés de type 1 n'apparaissent qu'une seule fois, il faut peu d'informations pour décrire complè- tement l'emplacement de ces mots-clés dans le document Par exemple, un mot de type 1 n'est localisé qu'une seule fois dans une page particulière d'emplacement particulier Un mot de type 4 d'autre part apparaît sur plusieurs pages à plusieurs emplacements En conséquence, les mots de type 1 ont des informations d'apparition spécifiées dans le bloc 12 b d'index de mots-clés et la table d'apparitions 14 n'est pas utilisée pour la recherche de ces mots-clés; en conséquence, ces mots de type 1 sont localisés plus rapide- ment car le niveau d'indexation nécessaire est plus petit. Un mot de type 2 est celui qui apparaît sur moins de 10 % des pages d'une base de données, un mot de type 3 apparaît sur moins de 25 % des pages et un mot de type 4 apparaît sur plus de 25 % des pages Comme les mots des types 2 et 3 ont des apparitions multiples et ont de multiples emplace- ments, il faut plus d'espace pour décrire ces classes de mots Comme le nombre d'apparitions d'un mot de type 3 est supérieur au nombre d'apparitions d'un mot de type 2, la table 14 d'apparitions ne spécifie que le bloc de pages de cartes 16 dans lesquelles le mot de type 3 se trouve Un bloc de pages peut représenter jusqu'à seize pages Les numéros de page et positions de mots sont spécifiés dans la table d'apparitions 14 pour les mots de type 2 Les mots de type 4 apparaissent si souvent dans un document que le moteur de recherche doit lire directement les cartes 16 de page; la probabilité de trouver un mot de type 4 sur une page donnée est supérieure à 25 % Les pourcentages affec- tés aux-mots de types 2, 3 et 4 sont de simples exemples et peuvent varier D'autres avantages apparaissent clairement à la lecture de l'utilisation des types ou classes de mots. Par exemple, si une personne veut rechercher la phrase "My apple is in the batmobile", la phrase apparaissant sur une carte de page est sous la forme "X, 213, X, 69021 ", ("X" étant un octet de commande et désignant un mot terminal). z Si le mot apple qui est un mot de type 4 doit être recher- ché en premier, chaque page de la table des cartes de page doit être lue avant la découverte du mot apple En consé- quence, lors de la recherche d'une phrase, un mot de type x est recherché avant un mot de type y, avec x chaîne de recherche 213, X, 69021 se trouve sur la page. Dans le cas o la chaîne de recherche n'est pas trouvée, d'autres cartes de page contenant le mot "batmobile" sont lues jusqu'à ce que la chaîne de recherche soit trouvée. En résumé, l'affectation d'une classe ou d'un type à des mots-clés en fonction du nombre d'apparitions du mot dans une base de données, ayant un ou plusieurs niveaux d'indexation reliés à chaque classe, constitue un mécanisme de recherche qui est relativement rapide et qui nécessite moins d'espace de mémorisation que la plupart des index classiques. REVENDICATIONS 1 Procédé d'indexation de mots-clés permettant des recherches dans une base de données enregistrées sur un support d'enregistrement d'informations, le procédé étant caractérisé en ce qu'il comprend les étapes suivantes l'analyse de la base de données, l'affectation d'un numéro unique d'identification à chaque mot-clé unique, plusieurs des mots-clés les plus fréquemment utilisés étant affectés aux numéros d'identifi- cation numériquement les plus faibles, la mémorisation de chaque mot-clé par ordre alphabé- tique sur le support d'enregistrement ( 10), avec le numéro d'identification affecté correspondant donnant au moins un niveau d'indexation entre les mots-clés et la base de données, la mémorisation d'une table sur le support d'enre- gistrement ( 10), la table faisant un lien entre chaque numéro d'identification et le mot-clé correspondant dans la base de données, et la mémorisation de la base de données sur une partie du support d'enregistrement ( 10). 2 Procédé d'indexation selon la revendication 1, caractérisé en ce qu'il comprend en outre l'affectation d'une étiquette parmi plusieurs étiquettes de classe à chaque mot-clé, chacune des étiquettes de classe dépendant de la fréquence d'apparition du mot-clé dans la base de données, chaque étiquette de classe étant associée à une forme différente d'indexation pour la recherche d'un mot- clé, l'étiquette de classe liant les mots-clés apparaissant le moins fréquemment dans la base de données et ayant le plus petit nombre de niveaux d'indexation et la plus grande quantité d'informations relatives à l'emplacement exact du mot-clé dans un document, les étiquettes de classe corres- pondant aux mots-clés apparaissant plus fréquemment dans la base de données ayant un plus grand nombre de niveaux d'indexation et moins d'informations relatives à l'emplace- ment d'un mot-clé dans un document. 3 Procédé de localisation d'une chaîne de mots-clés dans un fichier de données, chaque chaîne de mots-clés étant formée de mots-clés de plusieurs classes comprend au moins un mot-clé de classe x et au moins un mot-clé de classe y, x et y représentant des nombres entiers dis- tincts, le procédé comprenant les étapes suivantes: la détermination des classes des mots-clés de la chaîne, et la recherche des mots-clés de classe x avant la recherche des mots-clés de classe y dans une chaîne de recherche, x et y étant des classes distinctes et x 4 Base de données et index de recherche destinés à être utilisés sur un support ( 10) de mémorisation de données, caractérisé en ce qu'ils comprennent au moins un fichier de données ( 18), un dictionnaire ( 12) de mots-clés, le dictionnaire comprenant une liste de mots-clés dans le fichier de données ( 18), chaque mot-clé ayant un numéro d'identifica- tion associé, plusieurs mots-clés apparaissant le plus fréquemment ayant des numéros d'identification variant en sens inverse de la fréquence d'apparition du mot-clé, et plusieurs cartes de page ( 16) contenant chacune des numéros d'identification, la position de chacun des numéros d'identification dans une carte de page correspondant à la position du mot-clé associé dans le fichier de données, tel qu'il serait normalement lu par un être humain. Base de données et index de recherche selon la revendication 4, caractérisés en ce que le fichier de données ( 18) est un fichier qui peut être imprimé et qui contient des données et des commandes d'impression spéci- fiant l'emplacement sur une page de l'endroit o des caractères doivent être affichés.