Nova Patents
ES2311699T3

Computer representation of a data tree structure and the associated encoding/decoding methods

Abstract

Computer representation of an oriented tree representative of the organization of a data set, in particular of a data dictionary, each data being associated with a particular node of said tree, characterized in that a first range is associated with each node of said tree according to a first total order relationship and a second rank is associated with each node of said tree according to a second total order relationship, the same comprising a table of values ​​stored in a memory, such that the first rank of a node is represented by a value that is stored in the address of the representative table of second rank of that node.

ES2311699T3, drawing sheet 1
Sheet 1 of 15

Term

Term ended

Projected expiry passed 21 February 2023, 3.6 years ago.

  1. Priority
  2. Filed
  3. Published
  4. Projected expiry
  5. Today

25 claims: 2 independent, 23 dependent

  1. 1
    ES 2 311 699 T3 REIVINDICACIONES 1. Representación informática de un árbol orientado representativo de la organización de un conjunto de datos, en particular de un diccionario de datos, cada dato estando asociado a un nodo particular de dicho árbol, caracterizada porque un primer rango está asociado a cada nodo de dicho árbol según una primera relación de orden total y un segundo rango está asociado a cada nodo de dicho árbol según una segunda relación de orden total, la misma comprendiendo una tabla de valores almacenados en una memoria, tal que el primer rango de un nodo está representado por un valor que está almacenado en la dirección de la tabla representativa de segundo rango de ese nodo.
  2. 2
    Representación informática según la reivindicación 1, caracterizada porque la primera relación de orden total es una combinación de una relación de orden de descendencia ordenando un nodo con respecto a sus descendientes, y de una relación de orden de primogenitura ordenando los nodos hijos de un mismo nodo.
  3. 3
    Representación informática según la reivindicación 2, caracterizada porque un primer nodo del árbol es inferior a un segundo nodo del árbol según dicha primera relación de orden total si el segundo nodo es un descendiente del primer nodo o si, el ancestro común del primer y segundo nodo tiene un primer hijo del cual desciende el primer nodo o confundido con éste último y un segundo hijo del cual desciende el segundo nodo o confundido con éste último, dicho primer hijo es inferior a dicho segundo hijo según la relación de orden de primogenitura.
  4. 4
    Representación informática según la reivindicación 2, caracterizada porque un primer nodo del árbol es superior a un segundo nodo del árbol según dicha primera relación de orden total si el segundo nodo es un descendiente del primer nodo o si, el ancestro común del primer y segundo nodo tiene un primer hijo del cual desciende el primer nodo o confundido con éste último y un segundo hijo del cual desciende el segundo nodo o confundido con éste último, dicho primer hijo es inferior a dicho segundo hijo según la relación de orden de primogenitura.
  5. 5
    Representación informática según una de las reivindicaciones de 2 a 4, caracterizada porque la segunda relación de orden total es una combinación de la relación de orden inversa de dicha relación de orden de descendencia y dicha relación de orden de primogenitura.
  6. 6
    Representación informática según la reivindicación 5, caracterizada porque un primer nodo del árbol es inferior a un segundo nodo del árbol según dicha segunda relación de orden total si el segundo nodo es un descendiente del primer nodo o si, el ancestro común del primer y segundo nodo tiene un primer hijo del cual desciende el primer nodo o confundido con éste último y un segundo hijo del cual desciende el segundo nodo o confundido con éste último, dicho primer hijo es inferior a dicho segundo hijo según la relación de orden de primogenitura.
  7. 7
    Representación informática según la reivindicación 5, caracterizada porque un primer nodo del árbol es superior a un segundo nodo del árbol según dicha segunda relación de orden total si el segundo nodo es un descendiente del primer nodo o si, el ancestro común del primer y segundo nodo tenga un primer hijo del cual desciende el primer nodo o confundido con éste último y un segundo hijo del cual desciende el segundo nodo o confundido con éste último, dicho primer hijo es inferior a dicho segundo hijo según la relación de orden de primogenitura.
  8. 8
    Representación informática según una de las reivindicaciones de 2 a 7, caracterizada porque, los datos son series de caracteres de un alfabeto provisto de un orden alfabético, cada arco de dicho árbol estando asociado a un carácter de al menos un dato, la relación de orden de primogenitura entre dos hijos de un mismo nodo está dada por la relación de orden alfabético de los caracteres asociados a los arcos respectivos entre dicho nodo y sus dos hijos.
  9. 9
    Método de codificación de un árbol orientado representativo de la organización de un conjunto de datos, especialmente de un diccionario, cada dato de dicho conjunto estando asociado a un nodo particular de dicho árbol, caracterizado porque se le atribuye a cada nodo de dicho árbol un primer y segundo Indice, el primer Indice siendo representativo del rango del nodo según una primera relación de orden total que ordena los nodos de dicho árbol, el segundo Indice siendo representativo del rango del nodo según una segunda relación de orden total, la primera relación de orden total siendo una combinación de una relación de orden de descendencia que ordena un nodo con respecto a sus descendientes y de una relación de orden de primogenitura que ordena los nodos hijos de un mismo nodo, la segunda relación de orden total siendo una combinación de la relación de orden inversa de dicha relación de orden de descendencia y dicha relación de orden de primogenitura, dicho método brindando un tabla en el cual son ordenados los valores representativos de los dichos primeros Indices de los nodos de dicho árbol en direcciones representativas de dichos segundos Indices de los nodos de dicho árbol.
  10. 10
    Método de codificación según la reivindicación 9, caracterizado porque comprende una llamada recurrente de una etapa de cálculo que brinda para un nodo cualquiera del árbol, el tamaño del subárbol resultante de dicho nodo.
  11. 11
    Método de codificación según la reivindicación 10, caracterizado porque, para un primer y segundo hijo de un mismo nodo, llamado nodo padre, adyacentes en una lista de hijos ordenados según dicha relación de orden de primogenitura, la etapa de cálculo determina el primer Indice del segundo hijo a partir del primer Indice del primer hijo y del tamaño del subárbol descendiente del primer hijo, y el segundo Indice del segundo hijo a partir del segundo Indice del primer hijo y del tamaño del subárbol del segundo hijo. ES 2 311 699 T3
  12. 12
    Método de codificación según la reivindicación 11, caracterizado porque dicha etapa de cálculo determina el primer Indice del hijo clasificado primero en dicha lista a partir del primer Indice de dicho nodo padre y el segundo Indice de dicho nodo padre a partir del segundo Indice del hijo clasificado último en dicha lista.
  13. 13
    Método de codificación según una de las reivindicaciones de 10 a 12, caracterizado porque dicha etapa de cálculo determina el tamaño del subárbol descendiente de dicho nodo padre a partir de la suma de los tamaños de los subárboles resultantes de sus hijos.
  14. 14
    Método de codificación según una de las reivindicaciones de 9 a 13, caracterizado porque opera sobre una primera representación de dicho árbol por medio de punteros en la cual, para un nodo dado, un primer tipo de puntero brinda un nodo hijo según la relación de orden de descendencia y un segundo tipo de puntero brinda la lista de sus otros hijos.
  15. 15
    Método de codificación según una de las reivindicaciones de 9 a 13, caracterizado porque brinda un tabla en la cual son ordenados los valores representativos de los dichos segundos Indices de los nodos de dicho árbol en direcciones representativas de dichos primeros Indices de los nodos de dicho árbol.
  16. 16
    Método de codificación de un dato de entrada perteneciente a un conjunto de datos organizadas según una estructura de árbol orientado, especialmente de un diccionario de datos, estando formadas los datos por series de caracteres de un alfabeto provisto de un orden alfabético, cada dato estando asociado a un nodo particular de dicho árbol y a cada arco de dicho árbol estando asociado un carácter, caracterizado porque, dicho árbol es representado por medio de la representación informática según una de las reivindicaciones de 1 a 8, se recorre el árbol de nodo en nodo según un camino que parte desde la raíz y se analiza dicho dato de entrada carácter por carácter, el nodo siguiente de un nodo corriente de dicho camino siendo escogido a través de los hijos de éste último, la elección siendo efectuada por medio de una sucesión de etapas de comparación, cada etapa de comparación comparando el carácter en curso de dicho dato de entrada y el carácter asociado al arco que une el nodo corriente con uno de sus hijos, siendo interrumpido el recorrido sólo cuando dicho dato de entrada fue enteramente analizado, el método proporcionando como valor codificado de dicho dato de entrada un Indice función de la dirección de la tabla de dicha representación informática representativa del último nodo de dicho camino.
  17. 17
    Método de codificación según la reivindicación 16, caracterizado porque dicho Indice es igual a la dirección representativa del último nodo de dicho camino.
  18. 18
    Método de codificación según la reivindicación 16, caracterizado porque dicho Indice es igual al valor almacenado en dicha tabla en la dirección representativa del último nodo de dicho camino.
  19. 19
    Método de codificación según una de las reivindicaciones de 16 a 18, caracterizado porque los hijos sucesivos del nodo corriente son determinados a partir de sus respectivas direcciones representativas en la tabla de dicha representación informática, obteniéndose la dirección representativa del hijo siguiente a un hijo corriente a partir de la dirección representativa del hijo corriente y del tamaño del subárbol resultante del hijo corriente.
  20. 20
    Método de codificación según la reivindicación 19, caracterizado porque el tamaño del subárbol resultante del hijo corriente es obtenido a partir del valor almacenado en dicha tabla en la dirección representativa del hijo corriente y del valor almacenado en dicha tabla en la dirección representativa del hijo precedente.
  21. 21
    Método de decodificación de un Indice representativo de un dato perteneciente a un conjunto de datos organizados según una estructura de árbol orientado, en particular de un diccionario de datos, formándose los datos por series de caracteres de un alfabeto provisto de un orden alfabético, cada dato estando asociada a un nodo particular de dicho árbol y a cada arco de dicho árbol estando asociado un carácter, caracterizado porque, dicho árbol es representado por medio de la representación informática según una de las reivindicaciones de 1 a 8, el árbol siendo recorrido según un camino que parte desde la raíz, el nodo siguiente de un nodo corriente de dicho camino siendo escogido a través de los hijos de éste último, efectuándose la elección por medio de una sucesión de etapas de comparación, cada etapa de comparación comparando dicho Indice a un Indice representativo de uno de dichos hijos en dicha representación informática, el método proporcionando como dato decodificado la cadena de caracteres asociada a los arcos que forman dicho camino.
  22. 22
    Método de codificación según la reivindicación 21, caracterizado porque dicho Indice representativo es una dirección en dicha tabla de la representación informática.
  23. 23
    Método de codificación según la reivindicación 21, caracterizado porque dicho Indice representativo es un valor almacenado en dicha tabla de la representación informática.
  24. 24
    Método de codificación según una de las reivindicaciones 21 a 23, caracterizado porque los hijos sucesivos del nodo corriente son determinados a partir de sus respectivas direcciones representativas en la tabla de dicha representación informática, obteniéndose la dirección representativa del hijo siguiente a un hijo corriente a partir de la dirección representativa del hijo corriente y del tamaño del subárbol resultante del hijo corriente. ES 2 311 699 T3
  25. 25
    Método de codificación según la reivindicación 24, caracterizado porque el tamaño del subárbol resultante del hijo corriente es obtenido a partir del valor almacenado en dicha tabla en la dirección representativa del hijo corriente y del valor almacenado en dicha tabla en la dirección representativa del hijo precedente.
Independent claims25