ES2311699T3 - Representacion informatica de una estructura de datos arborescente y metodos de codificacion/decodificacion asociados. - Google Patents
Representacion informatica de una estructura de datos arborescente y metodos de codificacion/decodificacion asociados. Download PDFInfo
- Publication number
- ES2311699T3 ES2311699T3 ES03718905T ES03718905T ES2311699T3 ES 2311699 T3 ES2311699 T3 ES 2311699T3 ES 03718905 T ES03718905 T ES 03718905T ES 03718905 T ES03718905 T ES 03718905T ES 2311699 T3 ES2311699 T3 ES 2311699T3
- Authority
- ES
- Spain
- Prior art keywords
- node
- tree
- child
- order
- relation
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
- G06F16/31—Indexing; Data structures therefor; Storage structures
- G06F16/316—Indexing structures
- G06F16/322—Trees
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Databases & Information Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
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.
Description
Representación informática de una estructura de
datos arborescente y métodos de codificación/decodificación
asociados.
\global\parskip0.900000\baselineskip
La presente invención se refiere a una
representación informática de un árbol orientado que representa la
organización de un conjunto de datos, especialmente de un
diccionario. La presente invención se refiere igualmente a un
método de codificación de dicho árbol orientado en dicha
representación informática. La presente invención se refiere
también a un método de codificación de un dato perteneciente a
dicho conjunto en un Indice de dicha representación informática. La
presente invención se refiere finalmente a un método de
decodificación que permite encontrar a partir de un Indice de dicha
representación informática dicho dato correspondiente.
Previamente a la exposición del estado de la
técnica, conviene definir un cierto número de términos que serán
utilizados a continuación.
Se le llama gráfico orientado (denominado
después simplemente gráfico) a una pareja G=(S,A) donde S es un
conjunto de vértices (denominados después igualmente nodos) y A es
un subconjunto de SxS, llamado conjunto de los arcos.
Un camino del gráfico es una serie ordenada
(s_{0},s_{1},...,s_{n}) de vértices tales
que (s_{i-1},s_{i}), es un arco,
para i=1,...n, cuando s_{n}=s_{0} con n\geq1, el
camino es llamado circuito o ciclo. Se dice que un gráfico está
conectado si dos nodos cualquiera del mismo están unidos por un
camino.
Un árbol está definido como un gráfico conectado
sin circuito. Se puede mostrar que dos vértices cualquiera de un
árbol están unidos por un camino único. Un árbol posee un vértice
particular R, tal que todo vértice s distinto de
R está unido a éste último por un camino. Este vértice
particular se llama raíz del árbol.
Para un vértice S dado, se le llama
descendiente de S a todo vértice s_{d} del árbol
tal que exista un camino entre s y s_{d}.
Recíprocamente, para un vértice s dado, se le llama ancestro
de s a todo vértice S_{a} del árbol tal que exista
un camino entre S_{a} y s. Se le llama vértice hijo
de un vértice S a un descendiente s_{f} de s
tal que (S, s_{f}) \epsilon A. Para todo vértice
s, del árbol se le llama subárbol resultante de s, al
árbol de raíz s que incluye a todos los descendientes de
s.
Finalmente se le llama hoja a todo vértice del
árbol que no tenga descendiente.
Numerosos métodos de tratamiento de la
información hacen referencia a una representación de los datos
según una estructura arborescente (o árbol), especialmente los
métodos de clasificación, de comprensión o de almacenamiento de la
información.
El documento Chang H: "Bubble structure and
operation to facilitate free traversal", IBM Technical
disclosure Bulletin, vol-26, no.9, divulga un
material burbuja y un algoritmo que exigen al menos dos tablas para
representar un árbol en una memoria.
Según el tipo de aplicación considerado, los
datos pueden ser cadenas de caracteres, series de fonemas, formas
de ondas, patrones de luminancia/crominancia etc.
Sin pérdida de generalidad, se considera a
continuación que los datos están constituidos por cadenas de
entidades elementales o caracteres (por ejemplo letras, símbolos,
cifras, signos alfanuméricos). El conjunto de estos posibles
caracteres constituye un alfabeto. Se supone que este alfabeto está
provisto de una relación de orden total, llamado orden
alfabético.
En numerosas aplicaciones de tipo "motores de
búsqueda", "búsqueda en un directorio", "búsqueda en un
diccionario" etc., un volumen muy importante de datos debe poder
ser almacenado y accedido, lo cual impone severas restricciones en
condiciones de explotación en tiempo real, especialmente para los
accesos en línea.
Cada dato debe poder ser accesible rápidamente
sin necesidad de grandes recursos de cálculo. También, para
reducir los tiempos de acceso, los volúmenes importantes de datos
deben residir en la memoria central. A fin de no aumentar
desmesuradamente el tamaño de esta memoria, frecuentemente es
necesario efectuar una compresión previa de los datos.
Ventajosamente, los datos deben poder ser accedidas sin ser
descomprimidas, lo que todavía penalizaría los tiempos de
acceso.
En los tipos de aplicación considerados mas
arriba, se avizora un tratamiento asimétrico de los datos: la fase
de compresión de los datos puede incluir un tratamiento
relativamente largo y complejo aunque lo que permite su acceso y
recuperación debe ser simple y rápida. Los datos pueden ser de esta
forma almacenados en la memoria bajo una forma comprimida y fijada,
siendo realizada su actualización "off-line"
antes de que sean puestos en línea.
Existe una estructura de organización de los
datos que se presta particularmente bien para la compresión:
aquella del árbol definido más arriba. Se encuentra especialmente
en los diccionarios o los directorios. Un diccionario en el sentido
común de la palabra es un fichero de datos (llamados igualmente
entradas), cada dato estando constituido por una cadena de
caracteres alfabéticos, estando organizados estos últimos según una
estructura arborescente.
\global\parskip1.000000\baselineskip
En la práctica, en una representación
informática, cada dato del diccionario está asociado a un Indice.
La búsqueda de una cadena de caracteres (o palabra) en el
diccionario conlleva a identificar el Indice de la palabra
correspondiente. De esta forma un texto puede ser representado por
una serie de Indices, más adaptado al tratamiento informático que
la representación inicial.
Diferentes tipos de representación fueron
propuestos en el estado de la técnica y especialmente:
- en forma de tabla de dicotomía, utilizando una
compresión de Ziv-Lempel
- en forma de tabla de fragmentos
- en forma de árbol lexical
Estos diferentes tipos de representación
conducen a desempeños equivalentes en caso de acceso perfecto. Se
le llama acceso perfecto a un modo de acceso donde se busca la
cadena de caracteres exacta en el diccionario correspondiente a la
palabra a analizar, sin tener en cuenta los errores o las
alteraciones.
La representación por árbol lexical supone un
análisis (o "parsing") de las cadenas de caracteres. Un
ejemplo de árbol lexical es dado en la Fig. 1 por el diccionario
\Delta siguiente:
Se observa que en el árbol lexical, los arcos
están asociados a los caracteres de las palabras del diccionario.
Más precisamente, a cada arco del árbol está asociada una etiqueta,
cada etiqueta teniendo como marca un carácter. El árbol lexical es
la reunión de todos los caminos donde el esqueleto corresponde a
una palabra del diccionario. Se le llama esqueleto de un camino a
la cadena de los caracteres de las etiquetas de los arcos que
constituyen ese camino. Una palabra del diccionario es también
llamada "entrada" del diccionario.
Se notará que las hojas del árbol lexical han
sido representadas por círculos aunque los otros vértices han sido
representados por discos. La raíz del árbol ha sido indicada como
R.
Se supone que el árbol está indizado, lo que
quiere decir que a cada vértice está asociado un Indice. Una
operación elemental en un árbol lexical es buscar a partir de una
palabra dada, el Indice de la entrada del diccionario
correspondiente. Esta operación necesita recorrer el árbol según
los arcos etiquetados por los caracteres sucesivos que componen la
palabra.
Particularmente, el algoritmo de búsqueda pone
en marcha una función Analizar Palabra que arroja como valor
el Indice (Indice-asociado(s)) de la entrada
del diccionario si ésta última está presente, o, por defecto, un
código de no identificación
(Indice-Palabra-Desconocida). Ésta
se muestra a continuación en seudo-código C:
La navegación por las instrucciones
s=descendiente-correspondiente(s) supone que
se dispone de una representación informática del árbol lexical.
\global\parskip0.900000\baselineskip
De manera general, es necesario disponer de una
representación informática de un árbol para poder recorrerlo,
utilizarlo y modificarlo fácilmente.
Según, una primera representación informática
conocida, un árbol está representado por un tabla de adyacencia
M=(m_{ij}) i=0, ..., n; j=0, ..., n almacenado en la memoria con
m_{ij}=1 si (s_{i}, s_{j}) \epsilon A.
Según una representación informática mas
corriente, un árbol está representado como una serie de punteros
informáticos. Según una primera variante conocida ilustrada en la
Fig. 2A, cada nodo está representado por un valor (o Indice) y un
tabla de punteros apuntando hacia sus nodos hijos. El tamaño del
tabla corresponde al número máximo de hijos (k) que puede tener un
nodo del árbol (se dice en este caso el árbol
"k-aire"). La Fig. 2A muestra un ejemplo de
representación de un árbol 3-aire según esta
variante.
La codificación de los hijos de un nodo a través
de un tabla de punteros presenta el inconveniente de consumir
demasiado espacio de memoria cuando el árbol contiene un pequeño
número de nodos que tienen muchos hijos y otros numerosos nodos que
tienen pocos hijos. Según una segunda variante conocida de
representación, se remedia esta dificultad utilizando para un nodo
dado un puntero hacia uno de sus nodos hijos, llamado hijo mayor, y
un puntero del hijo mayor hacia una lista encadenada de sus
hermanos. La Fig. 2B muestra un ejemplo de representación según
esta segunda variante, para un árbol 5-aire.
Los punteros permiten modificar rápidamente la
estructura del árbol pero son relativamente costosos en espacio en
memoria. Además, la detección de una relación de descendencia entre
nodos no es inmediata. Se supone que determine el camino que une a
los dos nodos, los que, en el marco de una representación por
punteros, implican importantes recursos de cálculo. Se puede reducir
considerablemente la cantidad de cálculos a efectuarse memorizando
el cierre transitivo del árbol, en el caso de que un nodo apunte
hacia cada uno de sus descendientes. Sin embargo, ésta última
opción es particularmente voraz en espacio de memoria.
El problema base de la invención es proponer una
representación informática de un árbol que ocupe poco espacio de
memoria, que permita recorrerlo fácilmente y modificarlo
simplemente.
Ese problema es resuelto por la representación
informática de un árbol 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,
incluyendo esta representación una tabla de valores almacenados en
una memoria, dichos valores siendo representativos de los rangos de
los nodos de dicho árbol ordenados según una primera relación de
orden total, las direcciones a las cuales dichos valores son
almacenados siendo representativos de los rangos de los nodos de
dicho árbol ordenados según una segunda relación de orden
total.
Ventajosamente, 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 una relación
de orden de primogenitura ordenando los nodos hijos de un mismo
nodo.
Según un primer modo de realización, 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.
Según un segundo modo de realización, 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 de 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.
Ventajosamente, 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 de dicha relación de orden de
primogenitura.
Según una primera variante, un primer nodo del
árbol es inferior a un segundo nodo del árbol según dicha segunda
relación de orden total si el primer nodo es un descendiente del
segundo 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.
Según una segunda variante, un primer nodo del
árbol es superior a un segundo nodo del árbol según dicha segunda
relación de orden total si el primer nodo es un descendiente del
segundo 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.
\global\parskip1.000000\baselineskip
Si 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 puede estar
dada por la relación de orden alfabético entre los caracteres
asociados a los arcos respectivos entre dicho nodo y sus dos
hijos.
La invención se refiere igualmente a un 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, en el cual se 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 ordenando 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 ordenando un
nodo con respecto a sus descendientes y una relación de orden de
primogenitura ordenando 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 de dicha relación de orden de primogeni-
tura.
tura.
Ventajosamente el método de codificación incluye
una referencia 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.
Para un primer y segundo hijo de un mismo nodo,
llamado nodo padre, adyacentes en una lista de hijos ordenada 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 resultante 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 resultante
del segundo
hijo.
hijo.
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.
Dicha etapa de cálculo determina igualmente el
tamaño del subárbol resultante de dicho nodo padre a partir de la
suma de los tamaños de los subárboles resultantes de sus hijos.
Ventajosamente, dicho método de codificación
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.
La invención es igualmente definida por un
método de codificación de un dato de entrada perteneciente a un
conjunto de datos organizados según una estructura de árbol
orientado, especialmente de un diccionario de datos, estando
formados 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, en el cual dicho árbol está representado por
medio de la representación informática ya mencionada, se recorre el
árbol de nodo en nodo según un camino partiendo de 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 escogiéndose 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 el carácter en curso de dicho dato de
entrada y el carácter asociado al arco que une al nodo corriente
con uno de sus hijos, siendo interrumpido el recorrido sólo cuando
dicho dato de entrada fue enteramente analizada, brindando el
método 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.
La invención también es definida por un 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, los datos siendo formados 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, en el cual dicho árbol está
representado por medio de la representación informática ya
mencionada, se recorre el árbol según un camino que parte desde la
raíz, el nodo siguiente de un nodo corriente de dicho camino
escogiéndose 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, brindando el método como dato decodificado la cadena
de caracteres asociados a los arcos que forman dicho camino.
Las características de la invención mencionadas
más arriba, de igual forma que otras, aparecerán mas claramente
tras la lectura de la descripción siguiente de ciertos modelos de
realización, dicha descripción hecha en relación con los dibujos
adjuntos, entre los cuales:
La Fig. 1 representa un árbol lexical;
La Fig. 2A muestra una primera representación
informática de un árbol con ayuda de punteros;
La Fig. 2B muestra una segunda representación
informática de un árbol con ayuda de punteros;
La Fig. 3A ilustra con un ejemplo un método de
codificación de árbol según un primer modo de realización de la
invención;
La Fig. 3B muestra una primera variante de
representación informática del árbol de la Fig. 3A;
La Fig. 3C muestra una segunda variante de
representación informática del árbol de la Fig. 3A;
La Fig. 4 ilustra una porción de árbol antes de
la indización por rango prefijo y rango posfijo.
La idea en la base de la invención es crear una
nueva representación informática de un árbol a partir de una nueva
relación de orden total traduciendo las relaciones de dependencia
entre nodos.
La relación de dependencia entre nodos induce
una relación de orden parcial sobre el conjunto de nodos del
árbol. Por ejemplo, si se convenía para dos nodos s_{1} y
s_{2} del árbol que: s_{1} > s_{2} si
y sólo si s_{2} es un descendiente de s_{1}, se
dispone de una relación de orden. Sin embargo este orden no es más
que un orden parcial ya que todos los nodos del árbol no pueden ser
comparados de esta forma (por ejemplo los hijos de un mismo
nodo).
Se puede construir una relación de orden total
sobre los nodos de un árbol si se sabe ordenar todos los hijos de
un mismo nodo. El orden según el cual se ordenan los hijos de un
mismo nodo será convencionalmente llamado orden de primogenitura.
Para un árbol lexical, donde las etiquetas de los arcos contienen
los caracteres alfabéticos, se puede conveniar que dos hijos
s_{1} y s_{2} de un mismo nodo S satisfacen a la
relación s_{1} > s_{2} si el carácter de la
etiqueta asociada al arco (S, s_{1}) es precedido
por aquel de la etiqueta asociada al arco (S,
s_{2}). De otro modo el orden alfabético de las marcas de
las etiquetas induce un orden de primogenitura sobre los nodos
hijos de un mismo nodo.
La combinación de la relación de orden parcial
de descendencia (señalada a continuación 1000 ) y de
la relación de orden de primogenitura (señalada a continuación
1001 ) permite obtener una relación de orden total
sobre el conjunto de los nodos. Esta combinación puede ser
realizada de varias maneras diferentes:
- relación de orden prefijo (señalada
convencionalmente 1002 ):
donde a' y b' son los
hijos del ancestro común de a y b, tales que a
desciende o es confundida con a' y b desciende o es
confundida con
b'.
Dicho de otra forma, el nodo a es
inferior al nodo b en el sentido del orden prefijo si
b es un descendiente de a o a' es un hermano
mayor de b'.
- relación de orden prefijo inverso (señalada
convencionalmente 1003 ):
- relación de orden posfijo inverso (señalada
convencionalmente 1004 ):
dicho de otra forma el nodo
a es inferior al nodo b en el sentido del orden
posfijo si a es un descendiente de b o a' es
un hermano mayor de
b'.
- relación de orden posfijo inverso (señalada
convencionalmente 1005 ):
Siendo dado que dos nodos cualquiera de un árbol
son, ya sean descendientes el uno del otro, ya sea descendientes
de un ancestro común, las relaciones de orden definidas más arriba
son relaciones de orden total.
Las relaciones de orden 1002 (o
1003 ) y 1004 (o
1005 ) permiten pues ordenar enteramente el conjunto
S de los nodos del árbol. Dicho de otra forma, a cada una de las
relaciones de orden se le puede asociar una función "rango" de
S en [0,n], por ejemplo:
tal que s_{1}
1002 s_{2} si y sólo si
RangoPrefijo(s_{1})<RangoPrefijo(s_{2})
tal que s_{1}
1004 s_{2} si y sólo si
RangoPosfijo(s_{1})<RangoPosfijo(s_{2}).
\vskip1.000000\baselineskip
RangoPrefijo y RangoPosfijo son
morfismos de conjuntos ordenados. De la misma manera se puede
definir las funciones rango RangoPrefijoInverso y
RangoPosfijoInverso a partir de relaciones de orden
1003 y 1005 :
tal que s_{1}
1003 s_{2} si
RangoPrefijoInverso(s_{1})<RangoPrefijoInverso(s_{2})
tal que s_{1}
1005 s_{2} si y sólo si
RangoPosfijoInverso(s_{1})<RangoPosfijoInverso(s_{2}).
\vskip1.000000\baselineskip
Según un primer modo de realización, se utiliza,
para construir la representación informática, una biyección
T de [0,n] en [0,n] definida por:
T=RangoPosfijo o
RangoPrefijo^{-1}.
Según una variante de este primer modo de
realización, se utiliza la biyección T^{1}.
De la misma manera, se podrá utilizar las
biyecciones formadas por composición: RangoPosfijoInverso
o
RangoPrefijo^{-1}, RangoPosfijo o RangoPrefijoInverso^{-1} ó RangoPosfijoInverso o RangoPrefijoInverso^{-1} en otros modos de realización de la invención o bien, en las variantes de éstos, las inversas de sus biyecciones.
RangoPrefijo^{-1}, RangoPosfijo o RangoPrefijoInverso^{-1} ó RangoPosfijoInverso o RangoPrefijoInverso^{-1} en otros modos de realización de la invención o bien, en las variantes de éstos, las inversas de sus biyecciones.
Con objetivo de simplificar, limitaremos la
exposición de la invención a la utilización de las biyecciones
T y T^{1}, a fin de que las otras biyecciones puedan
ser igualmente utilizadas.
Dicha biyección T puede ser representada de
manera informática bajo la forma de un primer tabla de valores
almacenados en memoria, el rango posfijo de un nodo siendo
almacenado en una dirección representativa del rango prefijo de ese
nodo.
Del mismo modo, la biyección T^{1}
puede ser representada de manera informática bajo la forma de un
segundo tabla de valores almacenados en la memoria, el rango
posfijo de un nodo siendo almacenado en una dirección
representativa del rango prefijo de ese nodo.
Un ejemplo hará comprender mejor el interés y la
utilización de esas biyecciones.
La Fig. 3A ilustra un árbol donde los nodos han
sido indizados por los rangos prefijo (en negrita y subrayado) y los
rangos posfijo (en cursiva). La relación de orden de primogenitura,
por ejemplo inducida por un orden alfabético sobre las marcas de
las etiquetas en el caso de un árbol lexical, ha sido representada
convencionalmente en el sentido creciente de izquierda hacia
derecha. A cada nodo s está de esta forma asociado una
pareja:
Estas parejas son ventajosamente almacenadas en
una tabla por medio de la biyección T (Fig. 3B) o
T^{1}(Fig. 3C). En Fig. 3B los valores de rango
posfijo han sido almacenados en las direcciones dadas por los
valores de rango prefijo correspondientes. A la inversa, en la Fig.
3C los valores de rango prefijo han sido almacenados en las
direcciones dadas por los valores de rango posfijo
correspondientes.
Una primera ventaja de la representación
informática del árbol según la invención es que no ocupa un espacio
de memoria del tamaño del árbol (n+1) al contrario de una
representación clásica por punteros (Figs. 2A y 2B) que necesita al
menos el doble de espacio de memoria.
Una segunda ventaja esencial de esta
representación informática es que permite detectar muy simplemente
una relación de dependencia entre dos nodos del árbol. En efecto,
para determinar si un nodo s_{2} es dependiente de un nodo
s_{1}, basta con comparar
RangoPrefijo(s_{1}) a
RangoPrefijo(s_{2}) de una parte, y
RangoPosfijo(s_{1}) a
RangoPosfijo(s_{2}) de otra parte:
s_{2} es dependiente de s_{1}
si y sólo si se tiene:
De esta forma, en el ejemplo de la Fig. 3A, se
verifica que el nodo representado por la pareja (RangoPrefijo,
RangoPosfijo) = (5, 1) es bien dependiente de aquel
representado por la pareja (RangoPrefijo, RangoPosfijo) =
(1, 5) pero no de aquel representado por la pareja
(RangoPrefijo, RangoPosfijo) = (22, 21).
De la misma manera, gracias a la tabla de la
Fig. 3B, es muy fácil determinar los descendientes o los ancestros
de un nodo dado. Por ejemplo, para determinar la lista de los
descendientes del nodo (8, 12), basta con barrer la tabla en
el sentido de las direcciones crecientes a partir de la dirección
8 y de buscar entre los datos almacenados aquellos que son
inferiores al posfijo 12 (aquí 6, 10, 11, 7, 8, 9). Estos valores
indican el rango posfijo de los descendientes del nodo en cuestión.
Para determinar la lista de los ancestros del nodo (8, 12),
basta con barrer la tabla en el sentido de las direcciones
decrecientes a partir de la dirección 8 y de buscar entre
los datos almacenados aquellos que son inferiores al posfijo 12
(aquí 19, 22). Estos valores indican los rangos posfijo de los
ancestros del nodo en cuestión.
Se procede de manera dual a partir de la tabla
de la Fig. 3C. Tomando el ejemplo anterior, basta, para determinar
la lista de los descendientes, con borrar la tabla en el sentido de
las direcciones decrecientes a partir de la dirección 12 y de
buscar entre los datos almacenados aquellos que son superiores al
prefijo 8 (aquí 14, 10, 13, 12,
11, 9). Esos valores indican los rangos prefijo de los
descendientes del nodo en cuestión. Del mismo modo, para determinar
la lista de los ancestros de (8, 12), basta con barrer la
tabla en el sentido de las direcciones crecientes a partir de la
dirección 12 y de buscar entre los datos almacenados aquellos que
son inferiores al prefijo 8 (aquí 7, 0).
Una tercera ventaja de la representación
informática según la invención es que permite un fácil recorrido
del árbol, si es de la raíz hacia las hojas, recorrido que se
efectúa por ejemplo cuando se analiza una cadena de caracteres
(palabra) con la ayuda de un árbol lexical, si es de las hojas
hacia la raíz, recorrido que se efectúa por ejemplo cuando se
genera una cadena de caracteres a partir del Indice de un nodo.
El recorrido del árbol de la raíz hacia las
hojas supone que se sepa determinar los hijos de un nodo dado. Como
se verá, la tabla de la Fig. 3B (o aquella de la Fig. 3C) permite
encontrarlos rápidamente.
Supongamos que el algoritmo de navegación busca
los hijos del nodo (12,8) y consideremos la tabla de la Fig.
3B. La tabla es barrida en el sentido de las direcciones crecientes
a partir de la dirección 8. Como anteriormente, se busca los
datos del tabla inferiores a 12. Cuando se retiene un dato x
inferior a 12, no se consideran los datos siguientes que son
inferiores a x. Dicho de otra forma, se continua barriendo la tabla
hasta que se encuentre de nuevo un dato x' superior a x (pero
siempre inferior al valor inicial 12). Se itera el proceso hasta el
fin de la tabla. De esta forma en el presente ejemplo, se encuentra
ante todo el valor 6 que está retenido (<12) después el valor 10
que está igualmente retenido (6<10<12). Los valores
siguientes 7, 8, 9, no son retenidos ya que, si son bien inferiores
a 12, no son superiores al último valor retenido 10. El valor 11 es
retenido a continuación (10<11<12) pero no los valores
siguientes ya que son superiores a 12.
Se procede de manera dual a partir de la tabla
de la Fig. 3C. Tomando el ejemplo anterior, se barre la tabla en
el sentido de las direcciones decrecientes a partir de la dirección
12. Como anteriormente, se buscan los datos almacenados superiores
al prefijo 8. Cuando se encuentra un dato x superior
a 8, no se consideran más los datos siguientes que son
superiores a x. Dicho de otra forma, se barre la tabla hasta
que se encuentra de nuevo un dato y inferior a x
(pero siempre superior al valor inicial 8). Se itera el
proceso hasta que se alcanza el principio del tabla. De esta forma
en el presente ejemplo, se encuentra ante todo el valor 14
que está retenido (>8) y después el valor 10 que
está retenido igualmente (8<10<14). Los
valores siguientes 11, 12, 13 no están
retenidos ya que, si son bien superiores a 8, no son
inferiores al último valor retenido 10. El valor 9 es
retenido a continuación (8<9<10) pero no
los valores siguientes ya que son superiores a 8.
Esta manera de determinar los hijos de un nodo
dado puede convenir para los árboles de débil tamaño. Sin embargo,
como se verá más adelante, para los árboles de gran tamaño, es más
rápido calcular directamente los rangos prefijo/posfijo de dichos
hijos.
Se notará que, si se había empleado, en lugar de
tablas construidos a partir de biyecciones T y
T^{1}, tablas construidos respectivamente a partir de
biyecciones RangoPosfijoInverso o RangoPrefijo^{-1},
RangoPosfijo o RangoPoefijoInverso^{-1} o
RangoPosfijoInverso o RangoPoefijoInverso^{-1} o
bien a partir de las inversas de sus biyecciones, se hubiera podido
determinar de manera similar los hijos de un nodo dado, al precio
eventual de un cambio de sentido de barrido y/o de cambio de sentido
de las desigualdades.
De la misma forma, el recorrido de un árbol
desde sus hojas hacia la raíz supone que se sepa determinar el
padre de un nodo dado. Suponiendo que el algoritmo de navegación
busca el padre de un nodo (12, 8) y considerando ante todo
el tabla de la Fig. 3B. Se barre el tabla en el sentido de las
direcciones decrecientes a partir de la dirección 8. El
primer dato encontrado superior a 12 da el indicio posfijo del
padre del nodo en cuestión (aquí 19).
Entendido esto, se procede de manera dual a
partir de la tabla de la Fig. 3C. En ese caso se barre la tabla en
el sentido de las direcciones crecientes a partir de la dirección
12. El primer dato encontrado inferior a 8 da el indicio
prefijo del padre del nodo en cuestión (aquí 7).
Para transformar un árbol cualquiera en su
representación informática, operación llamada codificación del
árbol, se debe ante todo proceder a una indización de los nodos.
Para codificar el árbol bajo la forma de una representación
informática según la invención, se debe indizar los nodos por medio
de las funciones RangoPrefijo y RangoPosfijo (u otras
funciones equivalentes vistas más arriba). Sin pérdida de
generalidad, limitaremos la exposición del método de indización
según la invención a dos funciones precitadas.
El método de indización opera sobre una
representación informática clásica del árbol por medio de punteros
como, por ejemplo, aquella ilustrada en la Fig. 2B. Esta
representación informática clásica será obtenida de manera conocida
a partir de un fichero de las entradas del diccionario. La cadena
vertical de los punteros corresponde a una relación prefija de las
entradas. La cadena horizontal de los hermanos de un mismo nodo se
hace según el orden de primogenitura, tal que aquel hereda una
clasificación de las marcas de las etiquetas.
Se inicializa el rango prefijo de la raíz en 0 y
se recorre el árbol a partir de la raíz siguiendo los punteros del
hijo mayor hasta que se alcanza una hoja (la más a la izquierda
según la convención de representación aquí escogida). El rango
posfijo de esta hoja se inicializa en 0.
Sea ahora un nodo S del árbol teniendo como
hijos s_{0}, s_{1}, ..., s_{p} ordenados según el orden
creciente de primogenitura (quiere decir ordenadas según la cadena
horizontal), como se ilustra en la Fig. 4. Se tienen las relaciones
siguientes:
donde \Gamma (s) es el
tamaño del subárbol resultante de
s.
\vskip1.000000\baselineskip
La indización por rango prefijo y rango posfijo
puede ser efectuada en un solo paso, a partir de la raíz del árbol,
utilizando la referencia recurrente de una función que arroja como
valor, para un vértice s dado, el tamaño \Gamma (s) del
subárbol que resulta. Esta función se muestra a continuación en
seudo-código C:
Se notará en el programa de más arriba que la
variable TamañoSubArbol es el tamaño del subárbol resultante
del nodo hijo(s) corriente y que la variable
TamañoSubArbolesDeHijos es el valor acumulado de los tamaños
de los subárboles resultantes de los nodos hijos ya explorados.
La función CodificaciónArbol crea
directamente una representación informática bajo la forma de una
tabla de Indice del tipo de la Fig. 3B, almacenado en la memoria.
Una vez creada esta representación informática, la representación
inicial por punteros, al hacerse inútil, es suprimida de la
memoria.
A continuación, nos ubicaremos, por razones de
simplificación, en el contexto de un diccionario organizado según
un árbol lexical, donde cada entrada del diccionario corresponde a
una hoja del árbol. Como se acaba de ver, una representación
informática bajo forma de tabla del mismo tamaño que la del árbol
puede ser obtenida por medio del método de codificación según la
invención.
Esta representación informática es
ventajosamente utilizada para buscar, a partir de una cadena de
caracteres dada, el Indice de la entrada del diccionario
correspondiente. Se tomará convencionalmente como Indice el rango
prefijo de la hoja (alternativamente se puede escoger su rango
prefijo inverso). La búsqueda del Indice hace referencia a un
primer método de recorrido del árbol desde la raíz hacia las hojas
según la invención.
Recíprocamente, esta representación informática
es ventajosamente utilizada para generar, a partir del Indice de
una entrada del diccionario, la cadena de caracteres
correspondiente. La generación de la cadena de caracteres hace
referencia a un segundo método de recorrido de árbol desde la raíz
hacia las hojas según la invención.
Se considera en primer lugar el caso de una
búsqueda del Indice de una cadena de caracteres C. El árbol es
recorrido a partir de la raíz siguiendo los arcos donde las
etiquetas tienen los caracteres sucesivos de C.
\newpage
Ventajosamente, el primer método de recorrido de
árbol desde la raíz hasta las hojas según la invención opera de la
siguiente manera.
Durante la llegada al primer hijo s_{0}
de un nodo S, se inicializa:
y se calcula el tamaño \Gamma
(s_{0}) resultante de s_{0} a partir
de:
donde UltimoPosfijo es el
rango posfijo del último nodo donde se abandonó el recorrido del
subárbol (en otros términos, el rango posfijo de la raíz del último
subárbol expuesto en el recorrido). A modo de ilustración, si en la
Fig. 3A el nodo de rango posfijo 5 no ha sido retenido porque el
arco que une la raíz y ese nodo no tiene el carácter buscado, el
subárbol resultante de ese nodo no es recorrido y se tiene como
UltimoPosfijo = 5. Se continua el recorrido por el nodo del
rango posfijo 19 y, de ser exitoso, por aquel de rango posfijo 12.
El tamaño del subárbol resultante de ese nodo (primer hijo
s_{0} del nodo S de rango posfijo 19) es
efectivamente
7.
\vskip1.000000\baselineskip
Se determinan a continuación los rangos prefijos
de los hijos sucesivos s_{i} de S por medio de las
relaciones de recurrencia siguientes:
A cada hijo explorado s_{i}, se le
prueba si el carácter en curso c de C es igual al
carácter que tiene la etiqueta del arco que une S a
s_{i}. Si ese no es el caso se prosigue con la exploración
del hijo siguiente s_{i+1} y así I sucesivamente hasta que
se encuentre el carácter en curso o se exploren todos los hijos de
S.
Cuando se llega a un nodo S dado, no se
conoce a priori el nombre de sus hijos. Para hacer esto,
ventajosamente se memoriza durante la exploración del nodo S
el tamaño \Gamma(S) del subárbol que resulta. A
continuación, durante la exploración sucesiva de los hijos
s_{i}, se pone al día la variable
TamañoSubArbolesDeHijos.
Y se sabe que todos los hijos s_{i} de
S fueron explorados cuando:
Si todos los hijos han sido explorados sin que
se haya encontrado el carácter en curso, la cadena de carácter
completa C no corresponde a una entrada del diccionario (al
menos una porción de C puede formar parte). Si el carácter en
curso fue encontrado por uno de los hijos s_{t} entonces
S=s_{t} y el ciclo de búsqueda reinicia con el
carácter siguiente. El proceso es iterado hasta que se alcanza una
hoja del árbol. El Indice buscado es el rango prefijo de esta hoja.
Ventajosamente, a fin de poder buscar las palabras que son
prefijos una de otra, como por ejemplo "bar" y "barrister"
en la Fig. 1, se puede agregar, al final de cada palabra un
marcador de fin de palabra, por ejemplo un carácter espacio. En
este caso, todas las hojas del árbol tienen marcadores de fin de
palabra.
Se puede definir de esta forma una función
RecorridoArbol que arroja a partir de una cadena de
caracteres PalabraAnálisis, el rango prefijo de la hoja
alcanzada al término del recorrido. Esta función utiliza la
representación informática del árbol según la invención. Su
seudo-código se muestra a continuación:
Recíprocamente, si se desea generar a partir de
un Indice/(supuesto igual al rango prefijo de una hoja del árbol)
la cadena de caracteres de la entrada correspondiente del
diccionario, se utiliza un segundo método de recorrido según la
invención. Este segundo método difiere del primero en que la
selección del nodo hijo es a partir de ahora guiada por la
comparación del rango prefijo de ese nodo con el Indice/buscado.
Más precisamente, el hijo s_{t} es seleccionado desde que
la relación siguiente es verificada:
El Indice/es de esta forma aproximado por
valores crecientes de rango prefijo de los nodos explorados.
El segundo método hace referencia al mismo
cálculo iterativo de los rangos prefijos de los hijos de un nodo S
dado a partir de los tamaños respectivos de los subárboles
\Gamma(s_{i}). El criterio de parada de la exploración de
los hijos s_{i} de un nodo S dado está igualmente
basado en una comparación de \Gamma(S) y de la suma de las
\Gamma(s_{i}) para los hijos ya explorados.
Se puede definir una función
GeneraciónPalabra que arroja a partir de un Indice
GuíaPrefijo la cadena de caracteres correspondientes. Esta
función utiliza igualmente 1 la representación informática del árbol
según la invención. Su seudo-código C se muestra a
continuación:
Claims (25)
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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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.
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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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.
\newpage
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.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR0202664A FR2836573A1 (fr) | 2002-02-27 | 2002-02-27 | Representation informatique d'une structure de donnees arborescente et methodes de codage/decodage associees |
| FR0202664 | 2002-02-27 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2311699T3 true ES2311699T3 (es) | 2009-02-16 |
Family
ID=27676213
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES03718905T Expired - Lifetime ES2311699T3 (es) | 2002-02-27 | 2003-02-21 | Representacion informatica de una estructura de datos arborescente y metodos de codificacion/decodificacion asociados. |
Country Status (9)
| Country | Link |
|---|---|
| US (1) | US7882109B2 (es) |
| EP (1) | EP1483693B1 (es) |
| JP (2) | JP2005525625A (es) |
| AT (1) | ATE403907T1 (es) |
| AU (1) | AU2003222939A1 (es) |
| DE (1) | DE60322678D1 (es) |
| ES (1) | ES2311699T3 (es) |
| FR (1) | FR2836573A1 (es) |
| WO (1) | WO2003073320A2 (es) |
Families Citing this family (36)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8037102B2 (en) | 2004-02-09 | 2011-10-11 | Robert T. and Virginia T. Jenkins | Manipulating sets of hierarchical data |
| US9646107B2 (en) | 2004-05-28 | 2017-05-09 | Robert T. and Virginia T. Jenkins as Trustee of the Jenkins Family Trust | Method and/or system for simplifying tree expressions such as for query reduction |
| US7620632B2 (en) | 2004-06-30 | 2009-11-17 | Skyler Technology, Inc. | Method and/or system for performing tree matching |
| EP1635273A1 (fr) * | 2004-09-10 | 2006-03-15 | France Telecom | Construction informatique d'un arbre lexical |
| US7627591B2 (en) | 2004-10-29 | 2009-12-01 | Skyler Technology, Inc. | Method and/or system for manipulating tree expressions |
| US7801923B2 (en) | 2004-10-29 | 2010-09-21 | Robert T. and Virginia T. Jenkins as Trustees of the Jenkins Family Trust | Method and/or system for tagging trees |
| US7630995B2 (en) | 2004-11-30 | 2009-12-08 | Skyler Technology, Inc. | Method and/or system for transmitting and/or receiving data |
| US7636727B2 (en) | 2004-12-06 | 2009-12-22 | Skyler Technology, Inc. | Enumeration of trees from finite number of nodes |
| US8316059B1 (en) | 2004-12-30 | 2012-11-20 | Robert T. and Virginia T. Jenkins | Enumeration of rooted partial subtrees |
| US8615530B1 (en) | 2005-01-31 | 2013-12-24 | Robert T. and Virginia T. Jenkins as Trustees for the Jenkins Family Trust | Method and/or system for tree transformation |
| US7681177B2 (en) | 2005-02-28 | 2010-03-16 | Skyler Technology, Inc. | Method and/or system for transforming between trees and strings |
| US8356040B2 (en) * | 2005-03-31 | 2013-01-15 | Robert T. and Virginia T. Jenkins | Method and/or system for transforming between trees and arrays |
| US7899821B1 (en) | 2005-04-29 | 2011-03-01 | Karl Schiffmann | Manipulation and/or analysis of hierarchical data |
| US8015061B2 (en) * | 2005-10-21 | 2011-09-06 | Sap Ag | File export channel |
| US7801136B2 (en) * | 2006-02-15 | 2010-09-21 | Ericsson Ab | Source routed multicast LSP |
| CN100445987C (zh) * | 2006-09-15 | 2008-12-24 | 北京北大方正电子有限公司 | 一种表格的可变数据排版的方法 |
| WO2009155574A1 (en) | 2008-06-19 | 2009-12-23 | Servicemesh, Inc. | Cloud computing gateway, cloud computing hypervisor, and methods for implementing same |
| US20140201017A1 (en) | 2008-06-19 | 2014-07-17 | Servicemesh, Inc. | Systems and methods for providing repeated use of computing resources |
| US9489647B2 (en) | 2008-06-19 | 2016-11-08 | Csc Agility Platform, Inc. | System and method for a cloud computing abstraction with self-service portal for publishing resources |
| US10411975B2 (en) | 2013-03-15 | 2019-09-10 | Csc Agility Platform, Inc. | System and method for a cloud computing abstraction with multi-tier deployment policy |
| US20140201218A1 (en) * | 2008-06-19 | 2014-07-17 | Servicemesh, Inc. | Systems and methods for providing ranked deployment options |
| US8645350B2 (en) * | 2008-07-11 | 2014-02-04 | Adobe Systems Incorporated | Dictionary compilations |
| DE102008038509A1 (de) | 2008-08-20 | 2010-02-25 | Daimler Ag | Verfahren zum Betrieb einer Verbrennungskraftmaschine eines Fahrzeuges und Fahrzeug mit einer Verbrennungskraftmaschine |
| TW201013433A (en) * | 2008-09-19 | 2010-04-01 | Esobi Inc | Filtering method for the same or similar documents |
| US20110314028A1 (en) * | 2010-06-18 | 2011-12-22 | Microsoft Corporation | Presenting display characteristics of hierarchical data structures |
| US8392433B2 (en) * | 2011-04-14 | 2013-03-05 | Amund Tveit | Self-indexer and self indexing system |
| US9904721B1 (en) * | 2013-01-25 | 2018-02-27 | Gravic, Inc. | Source-side merging of distributed transactions prior to replication |
| CN105339931B (zh) | 2013-02-08 | 2020-09-08 | 黄馥萍 | 用于处理数据容器的方法和设备 |
| US9063916B2 (en) * | 2013-02-27 | 2015-06-23 | Oracle International Corporation | Compact encoding of node locations |
| RU2640322C2 (ru) * | 2014-01-30 | 2017-12-27 | Общество с ограниченной ответственностью "Аби Девелопмент" | Способы и системы эффективного автоматического распознавания символов |
| JP2020004132A (ja) * | 2018-06-28 | 2020-01-09 | エヌ・ティ・ティ・コミュニケーションズ株式会社 | 検索装置、検索方法、プログラム、及び記録媒体 |
| US11263195B2 (en) * | 2020-05-11 | 2022-03-01 | Servicenow, Inc. | Text-based search of tree-structured tables |
| FR3120718B1 (fr) * | 2021-03-09 | 2023-02-10 | Commissariat Energie Atomique | Procédé d’exécution d’un programme d’ordinateur par un appareil électronique |
| US12106231B2 (en) * | 2021-05-28 | 2024-10-01 | Enviro Networks, Inc. | Method and apparatus for predictive calculation of plant water need |
| CN114025024B (zh) * | 2021-10-18 | 2023-07-07 | 中国银联股份有限公司 | 一种数据传输方法及装置 |
| WO2023177321A1 (ru) * | 2022-03-16 | 2023-09-21 | Ануар Райханович КУЛМАГАМБЕТОВ | Способ организации поиска документов в прикладных базах |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CA2117846C (en) * | 1993-10-20 | 2001-02-20 | Allen Reiter | Computer method and storage structure for storing and accessing multidimensional data |
| JP2683870B2 (ja) * | 1994-05-23 | 1997-12-03 | 日本アイ・ビー・エム株式会社 | 文字列検索システム及び方法 |
| US5893100A (en) * | 1996-11-27 | 1999-04-06 | Teralogic, Incorporated | System and method for tree ordered coding of sparse data sets |
| EP1039646A1 (en) * | 1999-03-05 | 2000-09-27 | Mitsubishi Electric France | Interleaver device and method for interleaving a data set |
| US6813611B1 (en) * | 1999-06-08 | 2004-11-02 | International Business Machines Corporation | Controlling, configuring, storing, monitoring and maintaining accounting of bookkeeping information employing trees with nodes having embedded information |
| US7235358B2 (en) * | 2001-06-08 | 2007-06-26 | Expression Diagnostics, Inc. | Methods and compositions for diagnosing and monitoring transplant rejection |
| US6839005B1 (en) * | 2003-11-07 | 2005-01-04 | Broadcom Corporation | Low memory and MIPS efficient technique for decoding Huffman codes using multi-stage, multi-bits lookup at different levels |
-
2002
- 2002-02-27 FR FR0202664A patent/FR2836573A1/fr not_active Withdrawn
-
2003
- 2003-02-21 EP EP03718905A patent/EP1483693B1/fr not_active Expired - Lifetime
- 2003-02-21 AU AU2003222939A patent/AU2003222939A1/en not_active Abandoned
- 2003-02-21 ES ES03718905T patent/ES2311699T3/es not_active Expired - Lifetime
- 2003-02-21 US US10/505,483 patent/US7882109B2/en not_active Expired - Fee Related
- 2003-02-21 AT AT03718905T patent/ATE403907T1/de not_active IP Right Cessation
- 2003-02-21 WO PCT/FR2003/000576 patent/WO2003073320A2/fr not_active Ceased
- 2003-02-21 DE DE60322678T patent/DE60322678D1/de not_active Expired - Lifetime
- 2003-02-21 JP JP2003571942A patent/JP2005525625A/ja active Pending
-
2008
- 2008-07-28 JP JP2008193807A patent/JP4805315B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| US7882109B2 (en) | 2011-02-01 |
| JP2008299867A (ja) | 2008-12-11 |
| AU2003222939A1 (en) | 2003-09-09 |
| JP4805315B2 (ja) | 2011-11-02 |
| US20050149471A1 (en) | 2005-07-07 |
| ATE403907T1 (de) | 2008-08-15 |
| WO2003073320A2 (fr) | 2003-09-04 |
| DE60322678D1 (de) | 2008-09-18 |
| EP1483693B1 (fr) | 2008-08-06 |
| JP2005525625A (ja) | 2005-08-25 |
| FR2836573A1 (fr) | 2003-08-29 |
| WO2003073320A3 (fr) | 2004-04-01 |
| EP1483693A2 (fr) | 2004-12-08 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| ES2311699T3 (es) | Representacion informatica de una estructura de datos arborescente y metodos de codificacion/decodificacion asociados. | |
| Munro et al. | Succinct representation of balanced parentheses and static trees | |
| Bille et al. | Random access to grammar-compressed strings and trees | |
| US6600841B1 (en) | Method and system for compressing data and a geographic database formed therewith and methods for use thereof in a navigation application program | |
| US20080016066A1 (en) | Adaptive index with variable compression | |
| Bille et al. | Random access to grammar-compressed strings | |
| KR20110025799A (ko) | 위치를 표시하는 부호화된 데이터로부터 위치를 분석하는 방법 | |
| US20140082021A1 (en) | Hierarchical ordering of strings | |
| Röver | Abstract commensurators of groups acting on rooted trees | |
| JPH07210569A (ja) | 情報検索方法および情報検索装置 | |
| Brisaboa et al. | A new approach for document indexing usingwavelet trees | |
| ES2895999T3 (es) | Sistema y método informático para selección rápida de nombres en una base de datos de datos de personas | |
| Köppl | Exploring regular structures in strings | |
| Bays | The compleat PATRICIA | |
| Kolpakov et al. | New algorithms for text fingerprinting | |
| Daciuk et al. | Natural Language Dictionaries Implemented as Finite Automata. | |
| Ehrenfeucht et al. | String searching | |
| Lecroq et al. | Sequence indexing | |
| JP2005050226A (ja) | 住所データマッチング処理システム及びマッチング処理方法 | |
| Vladu et al. | Suffix arrays–a programming contest approach | |
| Claude | Space-efficient data structures for information retrieval | |
| Rosenstiehl | Scaffold permutations | |
| Weese et al. | Full-Text Indexes for High-Throughput Sequencing | |
| Arimura | Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing | |
| CN118193543A (zh) | 一种基于eda的节点树的查找方法、电子设备及存储介质 |