ES2234878T3 - Procedimiento para la compresion/decompresion de documentos estructur dos. - Google Patents
Procedimiento para la compresion/decompresion de documentos estructur dos.Info
- Publication number
- ES2234878T3 ES2234878T3 ES01967412T ES01967412T ES2234878T3 ES 2234878 T3 ES2234878 T3 ES 2234878T3 ES 01967412 T ES01967412 T ES 01967412T ES 01967412 T ES01967412 T ES 01967412T ES 2234878 T3 ES2234878 T3 ES 2234878T3
- Authority
- ES
- Spain
- Prior art keywords
- document
- information
- elements
- type
- compression
- 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
- 238000000034 method Methods 0.000 title claims abstract description 45
- 230000006835 compression Effects 0.000 title claims abstract description 38
- 238000007906 compression Methods 0.000 title claims abstract description 38
- 230000006837 decompression Effects 0.000 title claims description 12
- 230000007704 transition Effects 0.000 claims abstract description 27
- 230000005540 biological transmission Effects 0.000 claims description 11
- 238000010586 diagram Methods 0.000 abstract 4
- 238000011282 treatment Methods 0.000 description 23
- 238000010606 normalization Methods 0.000 description 7
- 230000008569 process Effects 0.000 description 6
- 230000009467 reduction Effects 0.000 description 6
- 238000009472 formulation Methods 0.000 description 4
- 239000000203 mixture Substances 0.000 description 4
- 230000000694 effects Effects 0.000 description 3
- 238000005457 optimization Methods 0.000 description 3
- 230000009466 transformation Effects 0.000 description 3
- 101150069304 ASN1 gene Proteins 0.000 description 2
- 230000008901 benefit Effects 0.000 description 2
- 238000000926 separation method Methods 0.000 description 2
- 150000001875 compounds Chemical class 0.000 description 1
- 230000003247 decreasing effect Effects 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 230000004927 fusion Effects 0.000 description 1
- 230000014509 gene expression Effects 0.000 description 1
- 230000001131 transforming effect Effects 0.000 description 1
- 238000011144 upstream manufacturing Methods 0.000 description 1
- 239000003643 water by type Substances 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
- H04N21/20—Servers specifically adapted for the distribution of content, e.g. VOD servers; Operations thereof
- H04N21/23—Processing of content or additional data; Elementary server operations; Server middleware
- H04N21/235—Processing of additional data, e.g. scrambling of additional data or processing content descriptors
- H04N21/2353—Processing of additional data, e.g. scrambling of additional data or processing content descriptors specifically adapted to content descriptors, e.g. coding, compressing or processing of metadata
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/20—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using video object coding
- H04N19/25—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using video object coding with scene description coding, e.g. binary format for scenes [BIFS] compression
Landscapes
- Engineering & Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
- Library & Information Science (AREA)
- Document Processing Apparatus (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Computer And Data Communications (AREA)
- Compression Of Band Width Or Redundancy In Fax (AREA)
Abstract
Procedimiento para la compresión y la descompresión de un documento estructurado, asociado con al menos un esquema de estructura arborescente (1; 31, 39, 43) que define una estructura del documento y que comprende elementos de estructura (32, 33, 34, 40, 44, 45, 46, a3, a4, X, Y, a1, a5, a1, a2, A, B) imbricados, que representan conjuntos de informaciones del documento, estando distribuidos los elementos de estructura en tres categorías, a saber elementos raíz estructurados (31, 39, 43), grupos de elementos (32, 33, 34, 40, 44, 45, 46) y elementos de base estructurados (X, Y, A, B) o no estructurados (a3, a4, a1, a5, a1, a2) que corresponden a los elementos de nivel más bajo en la estructura, estando asociado cada elemento de base con un tipo de información, caracterizado porque al menos un tipo de información de los elementos de base está asociado previamente con un algoritmo de compresión (16) adaptado, comprendiendo el procedimiento las etapas siguientes: - el análisis sintáctico (11) del esquema de estructura del documento, - la compilación (13) del esquema de estructura con vistas a obtener un autómata de estados finitos (5) por elemento raíz, comprendiendo cada autómata estados (¿0¿, ¿1¿, ... ¿n¿) conectados entre sí mediante transiciones (¿m1¿, ¿m2¿, ... ¿mn¿) que representan, respectivamente, los elementos de la estructura, y - la compresión (15) del documento estructurado (2) a ser comprimido, que comprende la ejecución de los autómatas con estados finitos (5) sobre el documento, y la ejecución del algoritmo de compresión (16) cuando se encuentre en el documento estructurado (2) un conjunto de informaciones que tenga un tipo de información asociado con dicho algoritmo.
Description
Procedimiento para la compresión/descompresión de
documentos estructurados.
La presente invención se refiere a un
procedimiento para la compresión/descompresión de documentos
estructurados.
La invención se aplica, principalmente, pero no
de manera exclusiva, a la transmisión de documentos tales como
imágenes o secuencias de imágenes, datos vídeo o audio, a través de
redes de transmisión de datos numéricos, así como al almacenamiento
de tales documentos.
En el momento actual, existen varios algoritmos
para la compresión numérica de documentos. Algunos algoritmos de
compresión están concebidos para tratar directamente los datos
binarios del documento, sin tener en cuenta el tipo de estos datos.
Estos algoritmos presentan la ventaja de poder tratar cualquier
documento, pero tienen pocas prestaciones (grado de compresión poco
elevado) para tratar documentos voluminosos que son generalmente del
tipo sonido o imagen.
Se conocían, por otra parte, otros algoritmos
para la compresión más eficaces, pero especialmente adaptados a un
tipo de datos, por ejemplo de tipo imagen o sonido, de manera que no
son utilizables, o no dan prestaciones si son aplicados a documentos
que no contengan exclusivamente datos para los cuales han sido
concebidos.
Ahora bien, cada vez más los documentos
utilizados y que circulan a través de las redes de transmisión de
datos contienen varios tipos de informaciones integradas en una
estructura.
Un documento estructurado es una colección de
conjuntos de informaciones asociados cada uno a un tipo, y
compuestos entre sí según relaciones principalmente jerárquicas.
Estos documentos emplean un lenguaje de estructuración tal como
SGML, HTML, XML, que permiten principalmente distinguir los
diferentes conjuntos de informaciones que compone el documento. En
oposición, en un documento denominado lineal, las informaciones de
contenido del documento están mezcladas con las informaciones de
presentación y de tipaje.
De este modo, un documento estructurado incluye
marcas de separación de los diferentes conjuntos de informaciones
del documento. En el caso de los formatos SGML, XML o HTML, estas
marcas denominadas "balizas" tienen la forma
"<XXXX>" y "</XXXX>", indicando la primera
marca el inicio del conjunto de informaciones "XXXX" y la
segunda el final de este conjunto. Un conjunto de informaciones
puede estar compuesto por varios conjuntos de informaciones de nivel
más bajo. De este modo, un documento estructura presenta un esquema
de estructura jerárquica o arborescente, representando cada nudo un
conjunto de informaciones y que está conectado a un nudo de nivel
jerárquico superior, que representa un conjunto de informaciones que
contiene los conjuntos de informaciones de nivel inferior. Los nudos
situados en el extremo de la rama de esta estructura arborescente
representan conjuntos de informaciones que contienen datos de un
tipo predefinido, que no pueden ser descompuestos en subconjuntos de
informaciones.
Un documento estructurado está asociado,
generalmente, a lo que se denomina un esquema de estructura que
define bajo la forma de reglas la estructura y el tipo de
información de cada conjunto de informaciones del documento. Un
esquema está constituido por grupos imbricados de estructuras de
conjuntos de informaciones, pudiendo ser estos grupos secuencias
ordenadas, grupos de elementos alternativos o grupos de elementos
necesarios, ordenados o no ordenados.
De este modo, un documento estructurado está
asociado con un esquema de estructura y contienen marcas de
separación representadas en la forma de datos textuales o binarios,
delimitando estas marcas conjuntos de informaciones que pueden
constituir en sí mismas otros conjuntos de informaciones delimitados
por las marcas. De aquí resulta que un documento, estructura de este
tipo, puede comprender, no solamente datos textuales, sino también
cualquier tipo de información (por ejemplo datos sonoros, imágenes,
etc). Como consecuencia, los algoritmos de compresión, específicos
de un tipo particular de datos, son poco eficaces y están mal
adaptados para tratar este tipo de documentos.
La presente invención tiene por objeto suprimir
estos inconvenientes. A este efecto, la invención propone un
procedimiento para la compresión y la descompresión de un documento
estructurado, asociado con al menos un esquema de estructura
arborescente que define una estructura del documento y que comprende
elementos de estructura imbricados que representan conjuntos de
informaciones, estando distribuidos los elementos de estructura en
tres categorías, a saber elementos raíz, estructurados descompuestos
en grupos de elementos y en elementos de base estructurados, o no
estructurados que corresponden a los elementos del nivel más bajo en
la estructura, estando asociado cada elemento de base y elemento
raíz con un tipo de información.
Según la invención, este procedimiento se
caracteriza porque al menos un tipo de información de los elementos
de base está asociado previamente con un algoritmo de compresión
adaptado, comprendiendo el procedimiento las etapas siguientes:
- -
- el análisis sintáctico del esquema de estructura del documento,
- -
- la compilación del esquema de estructura con vistas a obtener un autómata con estados definidos por elementos raíz, comprendiendo cada autómata estados relacionados entre sí por transmisiones que representan, respectivamente, los elementos de la estructura, y
- -
- la compresión del documento estructura, que comprende la ejecución de los autómatas con estados finitos sobre el documento, y la ejecución del algoritmo de compresión cuando se encuentre en el documento a ser comprimido un conjunto de informaciones que tenga un tipo de información asociado con dicho algoritmo.
Merced a la compilación del sistema de
estructura, la estructura del documento está representada de una
manera muy compacta, y debido a que cada conjunto de informaciones,
que corresponde a un elemento de estructura de base, está asociado
con un tipo de información, puede ser tratado por el algoritmo de
compresión mejor adaptado a su tipo. De esta manera, si el documento
contiene, por ejemplo, datos textuales, imágenes y datos sonoros,
estos datos son marcados perfectamente en el documento estructurado,
y asociados con un elemento de estructura de bajo nivel y un tipo.
En el transcurso de la ejecución de los autómatas, estos detectan la
presencia de conjunto de informaciones que tengan un tipo de base
asociado con un algoritmo de compresión y aplican sucesivamente los
algoritmos correspondientes sobre estos datos para obtener
secuencias de informaciones binarias correspondientes que son
insertadas a medida que se producen en el documento que resulta de
la compresión.
Además, en el caso de una transmisión de datos,
si los documentos transmitidos presentan siempre el mismo esquema de
estructura, no es necesario transmitirlo con cada transmisión de
documento, de donde se deduce una ganancia suplementaria al nivel
del grado de compresión obtenido merced al procedimiento según la
invención. Esta transmisión es incluso inútil cuando el esquema sea
previamente conocido por el destinatario del documento. Por ejemplo,
si se trata de un documento HTML, no hay nunca necesidad, ni
siquiera la primera vez, de codificar el esquema del documento.
Por autómata con estados finitos, es preciso
entender un conjunto de estados, estando asociado cada estado a un
conjunto de acontecimientos de entrada y una función de transición
que determina, para cada acontecimiento de entrada, el conjunto de
estados activos del autómata. Teniendo en cuenta esta definición, se
pueden imaginar numerosas representaciones, por ejemplo haciendo
intervenir tablas de transcodificación, a razón de una tabla por
estado que indique, para cada acontecimiento de entrada, la tabla
que corresponde al estado siguiente, o incluso tablas de
correspondencia, a razón de una tabla por autómata, que tenga tantas
líneas y columnas como estados tenga el autómata, conteniendo cada
casilla de la tabla la descripción de la transición entre los dos
estados correspondientes.
Durante la descompresión, el esquema de
estructura es tratado de la misma manera para determinar los
autómatas que hayan servido para la compresión y analizan el
contenido del documento comprimido con vistas a reconstituir un
documento con formato original que tenga una estructura al menos
equivalente, sino idéntica, ejecutándose algoritmos de
descompresión, que corresponden a los algoritmos de compresión
utilizados durante la compresión, para restituir los conjuntos de
informaciones de origen a partir de las secuencias de informaciones
binarias marcadas en el documento comprimido.
En el caso en que el esquema de estructura deba
ser transmitido con el documento, el procedimiento según la
invención comprende, ventajosamente, una etapa de transmisión del
esquema de estructura que puede ser el de origen, el obtenido tras
la transformación y normalización, o incluso el obtenido tras la
compilación.
Según una particularidad de la invención, cada
conjunto de información está marcado en el documento comprimido con
el fin de permitir un acceso directo a un elemento de información
particular, sin que sea necesario descomprimir todo el documento, ni
los conjuntos de informaciones que preceden al conjunto a ser
descomprimido.
Según otra particularidad de la invención, cada
elemento de esquema de estructura está asociado, además, con un
conjunto de numerosos acontecimientos posibles, que indican el
número de veces que un conjunto de informaciones que tenga este
elemento de estructura puede aparecer en el conjunto de
informaciones de nivel inmediatamente superior a aquél en el que
aparece.
El procedimiento según la invención puede
comprender una etapa de optimización del esquema de estructura del
documento que consiste en reducir el número de niveles jerárquicos
de grupos de elementos de estructura. Esta optimación permite
simplificar el esquema de estructura, pero hace que el tratamiento
de compresión sea menos eficaz.
Un modo de realización del procedimiento según la
invención se describe a continuación a título de ejemplo no
limitativo, con referencia a los dibujos adjuntos, en los que:
la figura 1 representa, en forma de un esquema de
bloques, el encadenamiento de las diferentes etapas del
procedimiento según la invención;
las figuras 2a, 2b y 2c representan gráficamente
un esquema de estructura en forma de un árbol;
la figura 3 muestra un esquema de estructura
obtenido aplicando un método de reducción según la invención al
esquema de estructura representado en la figura 2;
las figuras 4a, 4b y 4c muestran un esquema de
estructura obtenido aplicando otro método de reducción según la
invención al esquema de estructura representado en la figura 2;
las figuras 5a hasta 5c representan,
respectivamente, tres autómatas con estados finitos obtenidos y
utilizados por el procedimiento según la invención;
la figura 6 representa otro autómata que ilustra
un método de optimación utilizado por el procedimiento según la
invención;
las figuras 7a y 7b representan dos autómatas
obtenidos por medio del procedimiento según la invención a partir de
un esquema de estructura particular; y
la figura 8 ilustra la aplicación de un método de
reducción a los autómatas representados en las figuras 7a y 7b.
La figura 1 representa el encadenamiento de las
diferentes etapas del procedimiento según la invención.
Este procedimiento está concebido para tratar un
documento estructurado constituido por un esquema de estructura 1,
que define la estructura del documento e informaciones estructuradas
2 del documento.
En el lenguaje esquema XML, un esquema de
estructura presenta, por ejemplo, la forma siguiente:
\vskip1.000000\baselineskip
<nombre del elemento =
"C">
<complejo Tipo>
- <nombre del atributo = "a2" requerido = falso tipo = "booleano"/>
- <nombre del atributo = "a1" requerido = verdadero tipo = "integrar"/>
- <orden del Grupo = elección>
- <nombre del
elemento = "A" tipo = "TA" Acontecimiento mínimo =
1
\hskip6cm
Acontecimiento máximo = 1/>
- <nombre del
elemento = "B" tipo = "TB" Acontecimiento mínimo =
1
\hskip6cm
Acontecimiento máximo = 1/>
- </Grupo>
</complejo Tipo>
</elemento>
\vskip1.000000\baselineskip
Este esquema indica que el elemento denominado
"C" presenta una estructura compleja constituida por un primer
elemento denominado "a2" de tipo booleano, que es opcional, por
un segundo elemento denominado "a1" de tipo entero, que está
siempre presente en la estructura, y por un grupo de elementos
alternativos denominados "A" y "B" de tipos respectivos
"TA" y "TB", estando presentes uno de estos dos elementos
una sola vez en la estruc-
tura.
tura.
Los tipos "TA" y "TB" están definidos
en el esquema de estructura del documento por una formulación
aná-
loga.
loga.
De una manera general, se utilizan los grupos de
elementos siguientes para definir una estructura del documento:
- -SEQ:
- que define una lista de elementos ordenados, que deben aparecer siempre en el documento y en el orden indicado,
- -CHO:
- que define un conjunto de elementos alternativos, debiendo aparecer un solo elemento del grupo,
- -ET:
- que define un conjunto de elementos, todos los cuales deben aparecer en el documento y en un orden cualquiera que no debe ser modificado,
- -ET_{NO}:
- que define un conjunto de elementos, todos los cuales deben estar presentes en el documento en un orden cualquiera, que no tiene importancia, y
- -ANY:
- que comprende un elemento cualquiera entre todos los elementos posibles que se pueden encontrar en el documento.
Según la invención esta formulación es analizada
y transformada en la etapa 11 del procedimiento para obtener árboles
sintácticos 4, a razón de un árbol por elemento de estructura. El
árbol sintáctico que corresponde a un elemento de estructura TC está
simbolizado por la fórmula siguiente:
\vskip1.000000\baselineskip
(1)TC
\rightarrow ((a1^{1.\text{.}1}_{\{int\}} \binampersand_{no}
a2^{0.\text{.}1}_{\{bool\}})^{1.\text{.}1},
(A^{1.\text{.}1}_{\{TA\}} |
B^{1.\text{.}1}_{\{TB\}})^{1.\text{.}1})^{1.\text{.}1}
\vskip1.000000\baselineskip
en la
que:
- "\rightarrow"
- indica que TC es el nombre dado a la estructura definida después de este símbolo,
- "( )"
- indica las periodicidades con las cuales los grupos de elementos deben ser leídos,
- ","
- corresponde a un grupo de elementos de tipo secuencia (SEQ),
- "|"
- representa un grupo de elementos alternativos (CHO),
- "&"
- representa un grupo de elementos de tipo ET,
- "&_{no}"
- representa un grupo de elementos de tipo ET no ordenado,
- "{}"
- asocia con un elemento un nombre de elemento de estructura o bien un tipo de base (por ejemplo entero o booleano), y
- "A^{x..y}"
- indica que el elemento A está repetido desde x hasta y veces en el documento, pudiendo ser y igual a "*" que representa un valor indeterminado.
- \quad
- Esta formulación utiliza igualmente el símbolo \textdollar'', que representa cualquier elemento (ANY).
La fórmula (1) puede estar representada por el
árbol representado en la figura 2c, comprendiendo este árbol un
elemento raíz "TC" 43 constituido por un acontecimiento único
de un grupo de tipo secuencia 44. Este grupo comprende un
acontecimiento único de un grupo de tipo "ET" no ordenado 45 y
un acontecimiento único de un grupo alternativo 46.
El grupo 45 está constituido por un
acontecimiento único de un entero denominado "a1" y por un
booleano denominado "a2", y el grupo 46 comprende un
acontecimiento único de un elemento denominado "A" de tipo
"TA" y de un elemento "B" denominado tipo "TB".
Los tipos "TA" y "TB" obtenidos en la
etapa 11 están dados, por ejemplo, por las fórmulas siguientes:
\vskip1.000000\baselineskip
(2)TA
\rightarrow ((a3^{1.\text{.}1}_{\{int\}} \binampersand
a4^{0.\text{.}1}_{\{int\}})^{1.\text{.}1},
(X^{1.\text{.}1}_{\{TC\}} |
Y^{1.\text{.}1}_{\{TC\}})^{1.\text{.}1})^{1.\text{.}1}
(3)TB
\rightarrow (a1^{1.\text{.}1}_{\{bool\}},
a5^{0.\text{.}1}_{\{bool\}})^{1.\text{.}1}
\vskip1.000000\baselineskip
y están representados por los
árboles mostrados, respectivamente, en las figuras 2a y
2b.
El tipo "TA" 31 comprende un grupo único 32
de tipo secuencia constituido por dos grupos únicos 33, 34,
respectivamente de tipo ET y SEQ. El grupo 33 comprende dos
acontecimientos únicos de tipo entero, denominados, respectivamente,
"a3" y "a4". El grupo 34 comprende dos acontecimientos
únicos de tipo "TC" denominados respectivamente "X" y
"Y".
El tipo "TB" 39 está constituido por un
grupo único 40 de tipo secuencia que comprende dos booleanos
respectivamente denominados "a1" y "a5".
Aún cuando en la descripción que precede, se ha
distinguido el nombre de cada elemento y su tipo, el procedimiento
según la invención se aplica, igualmente, a los lenguajes de
estructuración que no hacen esta distinción.
Por otra parte, los elementos de estructura deben
ser deterministas, es decir que un elemento no puede ser
interpretado de varias maneras diferentes. Por ejemplo, en el
esquema "(a | (a , b))", en el caso en que "a" aparezca,
no se sabe si "b" debe aparecer a continuación. A este efecto
existen algoritmos que pueden ser aplicados por el procedimiento
según la invención para transformar un esquema no determinista en un
esquema determinista. De manera ejemplificativa se puede hacer
referencia a los documentos ["Regular expressions into finite
automata" Brüggemann-Klein, Anne, Extended
Abstract in I. Simon, Hrsg. LATIN 1992, páginas
97-98. Springer-Verlag, Berlín 1992.
Full Version in Theoretical Computer Science 120:
197-213, 1993]. De este modo, el esquema anterior
puede ser reemplazado por ejemplo por "(a ,
b^{0.\text{.}1})".
En la etapa 12 siguiente del procedimiento según
la invención, los elementos del esquema de estructura transformados
en árboles sintácticos pueden sufrir, en primer lugar, un
tratamiento de reducción o de simplificación.
Este tratamiento de reducción consiste en
efectuar un aplastamiento global generando un solo árbol sintáctico
51 a partir de todos los árboles 31, 39 y 43, como se ha
representado en la figura 3.
Este árbol presenta, de hecho, un diccionario de
todos los tipos de elementos susceptibles de ser encontrados en el
documento, estando agrupados estos elementos en un grupo 52 de tipo
alternativo que aparece al menos una vez (1..*) en el documento. En
este árbol, los elementos de tipo complejo "A", "B",
"X" e "Y" están asociados a un tipo "ANY", y el
elemento "a1" que aparece dos veces (en los elementos "TB"
y "TC") con tipos diferentes, está asociado con un tipo por
defecto "pcdata" según el lenguaje XML o al tipo del elemento
en el documento inicial, por ejemplo texto. Un mismo conjunto de
informaciones puede ser representado, en efecto, de varias maneras:
por ejemplo una secuencia binaria puede ser considerada igualmente
como una cadena de caracteres o un número
entero.
entero.
Alternativamente, este tratamiento de reducción
consiste en aplastar localmente los árboles sintácticos para obtener
los árboles representados 31', 39' y 43' en las figuras 4a hasta
4c.
En cada una de las figuras, los grupos 32 hasta
34 (figura 2a), 40 (figura 2b) y 44 hasta 46 (figura 2c) han sido
reemplazados, respectivamente, por un grupo 53, 55, 54 de tipo
alternativo que aparece, al menos, una vez
(1..*).
(1..*).
Los árboles "TA", "TB" y "TC"
pueden sufrir, además, un tratamiento suplementario para suprimir
las ambigüedades que aparecen en el esquema de estructura.
En la etapa 12, los árboles "TA", "TB"
y "TC" sufren, igualmente, un tratamiento de normalización, que
consiste en reordenar el esquema con el fin de obtener un orden
único de los elementos del esquema. Este tratamiento asigna un
número binario a los diferentes nudos de los árboles sintácticos
obtenidos como consecuencia de los tratamientos precedentes. Este
número es utilizado durante la compresión del elemento
correspondiente.
Este tratamiento de normalización consiste en
atribuir a cada grupo una signatura constituida por la concatenación
del nombre del grupo con la signatura de todos los elementos y de
los subgrupos del grupo, previamente ordenados. De este modo, el
grupo 53 en la figura 4 está asociado a la signatura
"CHO.a3.a4.X.Y" (o "| a3.a4.X.Y.").
Para este tratamiento de normalización, se
considera que los grupos ordenados (SEQ) están ya normalizados. Los
grupos a normalizar son, por lo tanto, los grupos de tipo
alternativo ("CHO"), y los grupos "ET" y "ET_{NO}".
Este tratamiento comprende las etapas siguientes para cada grupo G
compuesto por subgrupos g_{i} y de elementos
e_{i}:
e_{i}:
- -
- la normalización de los subgrupos gi eventuales del grupo G antes de normalizar el grupo G, siendo recursivo el algoritmo de normalización,
- -
- el reagrupamiento de los elementos e_{i} eventuales del grupo G antes que los subgrupos g_{i},
- -
- el reagrupamiento de los elementos e_{i} en un orden predefinido,
- -
- el reagrupamiento de los subgrupos g_{i} en el orden predefinido y
- -
- la determinación de la signatura del grupo G dada por la concatenación de todas las signaturas de sus componentes (elementos y subgrupos) según el orden establecido como consecuencia de las etapas precedentes.
El orden predefinido de reagrupamiento de los
compuestos del grupo puede ser el orden alfanumérico de sus
signaturas respectivas, o el orden decreciente de su número mínimo
de acontecimientos, siendo dispuestos a continuación por orden
alfanumérico los componentes que tengan el mismo número mínimo de
acontecimientos.
Debe señalarse que este tratamiento de
normalización no es necesario en el procedimiento según la
invención. En efecto, puede conservarse el orden de aparición de los
componentes en el esquema.
La etapa 13 siguiente del procedimiento consiste
en genera autómatas con estados finitos 5. Este tratamiento consiste
en generar, para cada árbol sintáctico, un conjunto de autómatas de
base, a razón de un autómata por grupo del árbol sintáctico, y a
continuación en combinar estos autómatas de base.
En la figura 5a, el autómata de un grupo
secuencial (SEQ) de n elementos de signaturas m1, m2, ... mn, de
nivel jerárquico inmediatamente inferior comprende n +2 estados
numerados desde 0 hasta n+1 simbolizados en la figura por círculos,
estando conectado cada nudo con su sucesor por una transición
simbolizada con un arco que corresponde a un elemento del grupo y
denominado por la signatura del elemento, marcando la última
transición F (hacia el estado n+1) el final del grupo.
En la figura 5b, el autómata de un grupo de tipo
alternativo (CHO) de n elementos de signaturas m1, m2, ... mn, de
nivel jerárquico inmediatamente inferior comprende un estado inicial
numerado "0" y n estados finitos numerados desde 1 hasta n,
estando conectado el estado 0 con los estados finitos 1 hasta n
respectivamente por n transiciones que corresponden,
respectivamente, a los n elementos del grupo.
En la figura 5c, el autómata de un grupo ET de n
elementos de signaturas m1, m2, ... mn, de nivel jerárquico
inmediatamente inferior, comprende
1+n+n*(n-1)+n*(n-1)*(n-2)+...+n!
estados que representan todas las combinaciones posibles de n
elementos.
Un autómata de este tipo puede ser generado por
un algoritmo simple tal como el siguiente:
E es el conjunto de los componentes posibles del
grupo
Ejecute la función_1 (E, estado inicial)
Función_1 (E, estado e):
- Repita mientras que E no esté vacío
- Seleccione un elemento mi de E y retírelo de E
- Cree un estado e' y un arco que una e y e' notado mi
- Duplique E en E'
- Ejecute la función_1 (E', estado e')
- Final repita
El autómata de un grupo ET_{NO} de n elementos
de signaturas m1, m2, ... mn, de nivel jerárquico inmediatamente
inferior puede ser el de un SEQ desde que se acepte perder
información relativa al orden de aparición de los elementos en el
grupo en el que está fijado.
Estos autómatas (caso de los grupos de tipo CHO,
ET y ET_{NO}) pueden ser optimizados aplicándoles un tratamiento
de evitación de los elementos opcionales, es decir cuyo conjunto de
acontecimientos posibles tenga la forma (0...k). Esta regla refleja
el hecho de que cada elemento asociado con un número de
acontecimientos mínimo nulo no está obligatoriamente codificado.
Como se ha representado en la figura 6, este
tratamiento consiste en añadir una transición entre el estado
"1" situado inmediatamente aguas arriba de un elemento opcional
"2" y todos los estados "3" inmediatamente situados aguas
abajo de este elemento, estando asociada esta nueva transición a la
signatura "m3" del elemento correspondiente al estado al que
conduce.
Si uno de los estados situados inmediatamente
aguas abajo está asociado igualmente con un elemento opcional, es
preciso haber previsto también una transición hacia todos los
estados situados inmediatamente aguas abajo de este estado.
Este tratamiento puede efectuarse por el
algoritmo siguiente:
Sea Z el subconjunto de nudos del autómata, cuyo
elemento asociado tiene un acontecimiento mínimo nulo.
Repita (en tanto en cuanto el autómata es
modificado por el procedimiento siguiente):
- Para cada elemento X de Z:
- Para cada transmisión entre TEx de X:
- Para cada transmisión que sale de TEx de X:
- 1.
- Cree una nueva transición N, uniendo el nudo fuente de la transición TEx y el nudo destino de la transición TSx. La transición está marcada por el valor del arco TSx.
- 2.
- Si no existe ya una transición idéntica en el gráfico, añadirla al gráfico.
- Fin para
- Fin para
- Fin para
Fin repita
Debe señalarse que los autómatas generados de
este modo para un esquema de estructura están imbricados en los
otros. En efecto, en los autómatas que corresponden al ejemplo del
esquema representado en la figura 2, cuando el tipo TC (elementos X
e Y) sea encontrado en el autómata correspondiente al tipo TA 31, el
autómata que corresponde al tipo TC 43 es ejecutado por completo
antes de proseguir la ejecución del autómata correspondiente al tipo
TA.
La etapa 14 siguiente del procedimiento según la
invención consiste en reducir y transformar los autómatas obtenidos
precedentemente.
De este modo se pueden fusionar autómatas de un
mismo árbol sintáctico (y no autómatas de árboles diferentes que se
llaman los unos a los otros), de la manera explicada con referencia
a las figuras 7a y 7b.
Estas figuras representan los autómatas que han
sido generados de acuerdo con el procedimiento según la invención a
partir de los elementos de estructura
(a_{1}^{0..\text{*}},(b_{1} |
b_{2})^{0..\text{*}}). El primer autómata (figura
7a) corresponde al grupo SEQ (","), mientras que el segundo
autómata (figura 7b) corresponde al grupo alternativo
("|").
En el transcurso de la ejecución de estos
autómatas, la llegada al estado 2 en el primer autómata entraña la
ejecución del segundo autómata y la llegada al estado finito 1 o 2
en el segundo autómata va seguida por la prosecución de la ejecución
del primer autómata, es decir de la ejecución de la transición F
entre el estado 2 y el estado finito 3 del primer autómata.
El tratamiento de fusión de los dos autómatas
permite obtener el autómata representado en la figura 8, en el que
cada alternativa al grupo CHO está representada por una transición
asociada con la signatura "cho.b1.b2" del grupo, concatenada
con la signatura "b1", "b2" del elemento del grupo que
figura en la alternativa elegida.
En el transcurso de esta etapa 14, los autómatas
pueden sufrir igualmente un tratamiento de minimización del número
de estados, por ejemplo aplicando el algoritmo de Hopcroft, y a
continuación un tratamiento de normalización para obtener autómatas
normalizados 6.
Después de este tratamiento, las transiciones al
inicio de cada nudo están numeradas desde 0 hasta n.
La etapa siguiente 15 consiste en volver a leer
el documento 2, comprimir los datos que contiene, ejecutando los
autómatas sobre la estructura del documento, con el fin de obtener
una sucesión de secuencias binarias en las cuales se encuentra el
valor comprimido de cada elemento o conjunto de informaciones de
base del documento. Según un primer tipo de codificación, estas
secuencias binarias tienen la forma
(K.N.V_{1}...V_{N})_{e} para cada elemento o grupo de
elementos e, siendo N el número de acontecimientos del elemento e o
el número de conjuntos de informaciones sucesivos que corresponden
al elemento e, siendo K el número de la transición que ha permitido
alcanzar el elemento e, y (V_{1}...V_{N}) son los valores
respectivos, eventualmente comprimidos, de los N acontecimientos del
elemento e. Si e es un grupo de elementos, su valor V está
descompuesto en tantas secuencias binarias (K.N.V.) como elementos
contenga. Sin embargo, en ciertos casos, N puede ser omitido,
principalmente cuando este número sea fijo. Lo mismo ocurre con K en
el caso en que no haya más que un solo arco procedente de un estado,
por ejemplo en un grupo de tipo secuencia.
Previamente se puede realizar un encabezado
general del documento comprimido que reagrupe varios parámetros
codificados, útiles para la descripción del documento. De este modo,
un encabezado de este tipo puede comprender una signatura del o de
los esquemas de estructura utilizados, y un conjunto de parámetros
que describa la codificación utilizada, como por ejemplo:
- -
- un parámetro, que indique si la codificación de la longitud de cada elemento es obligatoria u opcional o no está presente en el documento,
- -
- un parámetro, que indique si los elementos pueden o no ser subtipos, es decir asociados a un tipo más preciso que su tipo de base, y
- -
- un parámetro, que indique el tipo de codificación utilizado para el número de acontecimientos.
Cada elemento de información del documento puede
estar asociado, igualmente, con un descabezado, estando precisadas
su presencia y su naturaleza en el encabezado del documento.
De este modo, el encabezado de un elemento puede
comprender la longitud codificada de este, con el fin de permitir,
durante la descompresión del documento, el acceso a un elemento
particular sin descomprimir todos los elementos precedentes en el
documento. Los encabezados de elementos están insertados en el
documento por ejemplo justo antes de la codificación del valor de
los elementos.
De una manera general, la compresión del
documento consiste en leer secuencialmente el documento, ejecutando
los autómatas del esquema, lo que permite, además, verificar que la
estructura del documento corresponda al esquema compilado.
En el transcurso de este tratamiento, se codifica
el número de acontecimientos de cada elemento que aparezca en el
documento. A este efecto, se aplican las reglas siguientes.
En el caso en que el número de acontecimientos de
un elemento e esté definido por (i...j), se distinguen los casos
siguientes:
Si j es diferente de "*" e i es diferente de
0, la codificación se descompone en dos partes, a saber (i...i) y
(0...j-i), no estando codificada la primera parte
por esta formulación específica más que si son necesarios i
acontecimientos. La segunda parte está codificada sobre |
log_{2}(j-i+1) | bitios.
Si j es diferente de "*" e i es igual a 0,
la codificación del número de acontecimientos es efectuada entre 1 y
j, es decir sobre | log_{2}(j) | bitios, puesto que si esta
codificación es necesaria, esto significa que al menos hay un
elemento e en el documento.
Si j es igual a "*", se utiliza una técnica
de codificación tal como ASN1 según la cual el primer octeto indica
el número de octetos sobre los que se ha efectuado la codificación,
y los octetos siguientes contienen el valor del número de
acontecimientos. También se puede utilizar el bitio más
significativo de cada octeto para indicar si es o no es el último
octeto de codificación del número de acontecimientos, sirviendo los
siete bitios siguientes de cada octeto para codificar el número de
acontecimientos.
Alternativamente, se puede elegir otro tipo de
codificación en el que no sea necesario introducir el número de
acontecimientos de los elementos de un esquema de estructura. Según
este tipo de codificación, se introduce un tipo denominado
"escape" o "esc" que indica el estado finito de los
autómatas. Por lo tanto es necesario aplicar previamente una
transformación a los autómatas obtenidos precedentemente.
Esta transformación consiste en añadir a cada
estado de los autómatas una transición de retorno hacia el estado
precedente y añadir una transición "esc" hacia un estado
finito, que marca el final de la ejecución del autómata. La
codificación de los elementos es entonces sólo de la forma (KV),
terminándose la codificación de un autómata por el número K_{esc}
de la transición "esc".
De hecho, este tipo de codificación no es
interesante más que para la codificación de formas complejas y para
elementos que no tengan un número máximo de acontecimientos. En
particular está completamente adaptado a la codificación de grupos
de tipo alternativo que comprendan un número de elementos diferente
de 2^{p}, siendo p un número entero.
Este tipo de codificación puede combinarse con el
precedente. Para ello es suficiente entonces indicarlo en el
encabezado del documento comprimido y atribuir un bitio a los puntos
de la codificación en los que debe encontrarse un número de
acontecimientos.
Según la invención, al menos un tipo de base de
los conjuntos de informaciones del documento está asociado con un
módulo externo de compresión 16. De esta manera, durante la lectura
del documento, los tipos respectivos de los conjuntos de
informaciones encontrados son analizados, y cuando un tipo de
conjunto de informaciones esté asociado con un módulo externo de
compresión 16, éste es aplicado al contenido del conjunto de
información y el resultado de la compresión se inserta en el
documento comprimido como valor del conjunto de información
correspondiente.
Los módulos externos de compresión pueden
aplicar, por ejemplo, la norma "mp3" para las informaciones
sonoras, "jpeg" para las imágenes y "MPEG 1" o "MPEG
2" para los datos de tipo vídeo.
Si no está asociado ningún módulo de compresión
con un tipo de conjunto de informaciones, se puede utilizar un
módulo de compresión por defecto o recuperar los conjuntos de
informaciones que tengan este tipo tales como los que aparecen en el
documento inicial.
Si se ha indicado en el encabezado del documento,
que la codificación de la longitud es opcional u obligatoria, los
elementos están asociados a un encabezamiento en el documento
comprimido, que contiene la longitud en número de bitios del valor
del elemento. Esta particularidad permite un acceso directo a un
elemento del documento comprimido sin tener que descomprimir los
elementos situados por delante en el documento, leyendo por medio de
los autómatas únicamente las longitudes respectivas de estos
elementos hasta el elemento buscado.
La longitud de los elementos puede estar
codificada de la manera siguiente.
En el caso en que el encabezado del documento, se
haya indicado que la codificación de la longitud de los elementos es
obligatoria, la longitud L de los elementos en número de bitios es
calculada por medio de la fórmula siguiente:
(4)L =
8*p+h
en la que p representa el número de
octetos (en codificación ASN1 se utilizan los bitios más
significativos de cada octeto utilizado para codificar este número)
utilizados para codificar la longitud del elemento, y h representa
el número de bitios restantes de esta longitud (h <
8).
Debe señalarse que el módulo externo de
compresión 16, que está llamado a efectuar la codificación del valor
de un elemento, puede proporcionar, como contestación, esta
longitud.
En el caso en que la codificación de la longitud
de los elementos no sea obligatoria, el valor del primer bitio, que
corresponde al valor del elemento, indica si los bitios siguientes
representan o no la longitud del elemento.
Si los elementos pueden ser subtipos (indicado en
el encabezado del documento), los nuevos tipos eventuales son
insertados en un encabezado de elemento colocado en el documento
comprimido justo delante del valor del elemento. El primer bitio
indica si el tipo del elemento es diferente o no del tipo esperado.
En el primer caso, los bitios siguientes en el encabezado del
elemento contienen el código del nuevo tipo, determinándose este
código por numeración de todos los subtipos posibles del tipo de
base del elemento, estando dada esta numeración por la codificación
de la estructura del documento.
De una manera más precisa, la codificación de un
documento se efectúa en tres etapas principales.
En la primera etapa, se numeran los arcos que
salen de cada nudo. Esta etapa es facultativa si únicamente hay un
solo arco de partida del nudo. Si hay n arcos salientes, se asocia
con cada uno de estos arcos un número dado por el orden de los arcos
atribuidos durante la normalización (etapa 14). Este número está
codificado sobre n' bitios, siendo n' tal que
2^{n'-1} < n \leq 2^{n'}.
De este modo, si n transiciones son originarias
del estado E, cada transición será codificada sobre |
log_{2}(n-1) | +1 bitios.
En la segunda etapa, se codifica el número de
acontecimientos de cada subautómata como se ha descrito
anteriormente.
En la tercera etapa, se codifica el subautómata.
Este tratamiento puede ser formulado por el algoritmo siguiente:
Colocarse al comienzo del autómata,
Mientras que el estado activo no sea final
- Se codifica el arco que se atraviesa, si es necesario
- Se codifica el número n de acontecimientos, si es necesario
- Se desplaza en el subautómata correspondiente hasta el nudo esperado,
- Se codifica n veces este subautómata.
- Se reemplaza en el autómata inicial.
Fin por el momento.
Por ejemplo, para la codificación del
acontecimiento "a_{2} a_{3} a_{1} a_{1} a_{3}" del
autómata (a_{1} | a_{2} | a_{3})^{(0...\text{*})},
hay tres arcos salientes. La numeración de los arcos se efectúa por
lo tanto sobre dos bitios. Como consecuencia, el resultado de la
codificación es el siguiente, en el caso en que se codifique el
número de acontecimientos:
0000 \ 0101 \
01 \ V_{a2} \ 10 \ V_{a3} \ 00 \ V_{a1} \ 00 \ V_{a1} \ 10 \
V_{a3}
en el cual "0000 0101"
representa el valor binario del número de acontecimientos, es decir
5, y V_{a1}, V_{a2} y V_{a3} son, respectivamente, los valores
de los acontecimientos de a1, a2 y
a3.
En el caso en que no se codifique el número de
acontecimientos:
01 \ V_{a2} \
10 \ V_{a3} \ 00 \ V_{a1} \ 00 \ V_{a1} \ 10 \ V_{a3} \
11
11 corresponde al número de
transiciones de salida
"esc".
En el ejemplo de las figuras 7a, 7b, la
codificación del acontecimiento "b_{2} b_{1} a_{1}" del
autómata (a_{1}^{0..\text{*}}, (b_{1} |
b_{2})^{0..\text{*}}) conduce al resultado
siguiente (caso en el que los estados no estén fusionados):
| 0000 0010 | número de acontecimientos de la secuencia (en este caso 2 veces) |
| 1 | codificación del arco "cho.b_{1}.b_{2}" |
| 0000 0010 | número de acontecimientos del grupo "cho.b1.b2" (en este caso 2 veces) |
| 1 | codificación del arco b_{2} en el grupo "cho.b1.b2" |
| V_{b2} | codificación del valor de b_{2} |
| 0 | codificación del arco b_{1} en el grupo "cho.b1.b2" |
| V_{b1} | codificación del valor de b_{1} |
| 0 | codificación del arco a_{1} |
| 0000 0001 | número de acontecimientos de a_{1} |
| V_{a1} | codificación del valor de a_{1} |
| 1 | codificación del arco de salida F. |
En el caso en que los estados estén fusionados
(figura 8):
| 0000 0010 | número de acontecimientos de la secuencia |
| 10 | codificación del arco "cho.b_{1}.b_{2}-b_{2}" |
| 0000 0010 | número de acontecimientos del grupo "cho.b1.b2" |
| V_{b2} | codificación del valor de b_{2} |
| 0 | codificación del arco b_{1} en el grupo "cho.b1.b2" |
| V_{b1} | codificación del valor de b_{1} |
| 00 | codificación del arco a_{1} |
| 0000 0001 | número de acontecimientos de a_{1} |
| V_{a1} | codificación del valor de a_{1} |
| 10 | codificación del arco de salida F. |
Puede ser necesario efectuar una reordenación del
autómata, principalmente si el esquema ha sido interpretado y
reordenado con el fin de optimizar la codificación en el caso del
grupo ET_{NO}.
Si el orden de los atributos no es útil (como en
el lenguaje XML), se puede efectuar una codificación que reordene
los atributos de los elementos en un orden predeterminado, por
ejemplo según un orden alfanumérico, y a continuación según que sean
requeridos o no. Esta disposición permite reducir
correspondientemente el tamaño de la descripción comprimida.
El tratamiento de descompresión de un documento,
obtenido de este modo, se efectúa ejecutando las etapas 11 a 15
sobre el esquema de estructura del documento para obtener los
autómatas, a continuación se ejecuta la etapa 15' de descodificación
o de descompresión del documento, esta etapa consiste en recorrer el
documento comprimido ejecutando los autómatas obtenidos como
consecuencia de las etapas 11 a 14, con el fin de poder determinar
el tipo y el número de los elementos de información comprimidos
encontrados en el documento. Los valores de los elementos que han
sido obtenidos por medio de los módulos 16 de compresión externos
son descomprimidos por medio de módulos de descompresión 16'
correspondientes.
Debe señalarse que si deben tratarse (comprimirse
o descomprimirse) varios documentos que tengan el mismo esquema de
estructura, las etapas 11 a 15 no son ejecutadas más que una sola
vez, únicamente las etapas 15 y 16 (o 15' y 16') deben ser aplicadas
a cada documento a ser tratado.
Claims (10)
1. Procedimiento para la compresión y la
descompresión de un documento estructurado, asociado con al menos un
esquema de estructura arborescente (1; 31, 39, 43) que define una
estructura del documento y que comprende elementos de estructura
(32, 33, 34, 40, 44, 45, 46, a3, a4, X, Y, a1, a5, a1, a2, A, B)
imbricados, que representan conjuntos de informaciones del
documento, estando distribuidos los elementos de estructura en tres
categorías, a saber elementos raíz estructurados (31, 39, 43),
grupos de elementos (32, 33, 34, 40, 44, 45, 46) y elementos de base
estructurados (X, Y, A, B) o no estructurados (a3, a4, a1, a5, a1,
a2) que corresponden a los elementos de nivel más bajo en la
estructura, estando asociado cada elemento de base con un tipo de
información, caracterizado porque al menos un tipo de
información de los elementos de base está asociado previamente con
un algoritmo de compresión (16) adaptado, comprendiendo el
procedimiento las etapas siguientes:
- -
- el análisis sintáctico (11) del esquema de estructura del documento,
- -
- la compilación (13) del esquema de estructura con vistas a obtener un autómata de estados finitos (5) por elemento raíz, comprendiendo cada autómata estados ("0", "1",... "n") conectados entre sí mediante transiciones ("m1", "m2", ... "mn") que representan, respectivamente, los elementos de la estructura, y
- -
- la compresión (15) del documento estructurado (2) a ser comprimido, que comprende la ejecución de los autómatas con estados finitos (5) sobre el documento, y la ejecución del algoritmo de compresión (16) cuando se encuentre en el documento estructurado (2) un conjunto de informaciones que tenga un tipo de información asociado con dicho algoritmo.
2. Procedimiento según la reivindicación 1,
caracterizado porque, con vistas a la descompresión del
documento comprimido (10), éste comprende la ejecución de las etapas
(11, 12, 13) para determinar los autómatas (5) que han servido para
la compresión a partir del esquema de estructura (1), la ejecución
(15') de los autómatas (5) sobre el documento comprimido (10) para
analizar el contenido de este, con vistas a reconstituir un
documento con el formato de origen que tenga una estructura al menos
equivalente, siendo ejecutados algoritmos de descompresión (16'),
que corresponden a los algoritmos de la compresión (16), utilizados
durante la compresión (15), para restituir los conjuntos de
informaciones del documento estructurado (2) de origen a partir de
secuencias de informaciones binarias marcadas en el documento
comprimido durante la ejecución de los autómatas.
3. Procedimiento según la reivindicación 1 ó 2,
caracterizado porque en el caso en que el esquema de
estructura (1) deba ser transmitido con el documento, el
procedimiento según la invención comprende una etapa de transmisión
del esquema de estructura (5).
4. Procedimiento según una de las
reivindicaciones 1 a 3, caracterizado porque comprende una
etapa de normalización (12) del esquema de estructura (5) del
documento con el fin de obtener un orden único predefinido de los
elementos del esquema.
5. Procedimiento según una de las
reivindicaciones 1 a 4, caracterizado porque cada conjunto de
información está marcado en el documento comprimido, con el fin de
permitir el acceso directo a un conjunto de informaciones
particular, sin que sea necesario descomprimir los conjuntos de
informaciones que preceden al conjunto a ser descomprimido.
6. Procedimiento según una de las
reivindicaciones 1 a 5, caracterizado porque cada elemento
del esquema de estructura está asociado, además, con un conjunto de
números de acontecimientos posibles, que indica el número de veces
que un conjunto de informaciones que tiene este elemento de
estructura puede aparecer en el conjunto de informaciones del nivel
inmediatamente superior a aquél al que pertenece.
7. Procedimiento según una de las
reivindicaciones 1 a 6, caracterizado porque comprende una
etapa de optimización del esquema de estructura del documento que
consiste en reducir el número de niveles jerárquicos de grupos de
elementos de estructura.
8. Procedimiento según una de las
reivindicaciones 1 a 7, caracterizado porque el documento
comprimido (10) comprende para cada conjunto de informaciones del
documento de origen, un número de transición que corresponde al
elemento de estructura asociado con el elemento de informaciones y
con el valor binario del conjunto de informaciones comprimido.
9. Procedimiento según la reivindicación 8,
caracterizado porque en el documento comprimido (10), cada
elemento de estructura de al menos una parte de los elementos de
estructura del esquema de estructura, está asociado con un número de
acontecimientos de conjuntos de informaciones en el documento.
10. Procedimiento según las reivindicaciones 8 ó
9, caracterizado porque en el documento comprimido (10), está
marcado el fin de un grupo de varios acontecimientos de conjuntos de
informaciones del mismo tipo, por una secuencia binaria que
representa un número de transición hacia el estado finito.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR0011356A FR2813743B1 (fr) | 2000-09-06 | 2000-09-06 | Procede de compression/decompression de documents structures |
| FR0011356 | 2000-09-06 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2234878T3 true ES2234878T3 (es) | 2005-07-01 |
Family
ID=8854020
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES01967412T Expired - Lifetime ES2234878T3 (es) | 2000-09-06 | 2001-08-31 | Procedimiento para la compresion/decompresion de documentos estructur dos. |
Country Status (11)
| Country | Link |
|---|---|
| US (2) | US8015218B2 (es) |
| EP (1) | EP1316220B1 (es) |
| JP (1) | JP4653381B2 (es) |
| AT (1) | ATE285656T1 (es) |
| AU (1) | AU2001287796A1 (es) |
| DE (1) | DE60107964T2 (es) |
| DK (1) | DK1316220T3 (es) |
| ES (1) | ES2234878T3 (es) |
| FR (1) | FR2813743B1 (es) |
| PT (1) | PT1316220E (es) |
| WO (1) | WO2002021848A1 (es) |
Families Citing this family (25)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3368883B2 (ja) * | 2000-02-04 | 2003-01-20 | インターナショナル・ビジネス・マシーンズ・コーポレーション | データ圧縮装置、データベースシステム、データ通信システム、データ圧縮方法、記憶媒体及びプログラム伝送装置 |
| ATE341901T1 (de) * | 2001-07-13 | 2006-10-15 | France Telecom | Verfahren zur komprimierung einer baumhierarchie, zugehöriges signal und verfahren zur dekodierung eines signals |
| US20030188265A1 (en) * | 2002-04-02 | 2003-10-02 | Murata Kikai Kabushiki Kaisha | Structured document processing device and recording medium recording structured document processing program |
| KR100968083B1 (ko) * | 2002-07-15 | 2010-07-05 | 지멘스 악티엔게젤샤프트 | 구조화된 문서들, 특히 ｘｍｌ 문서들을인코딩/디코딩하기 위한 방법 및 장치 |
| AU2003250302A1 (en) * | 2002-07-15 | 2004-03-03 | Siemens Aktiengesellschaft | Method and devices for encoding/decoding structured documents, especially xml documents |
| US7603654B2 (en) * | 2004-03-01 | 2009-10-13 | Microsoft Corporation | Determining XML schema type equivalence |
| US8977859B2 (en) * | 2004-05-04 | 2015-03-10 | Elsevier, Inc. | Systems and methods for data compression and decompression |
| US7509631B2 (en) * | 2004-05-21 | 2009-03-24 | Bea Systems, Inc. | Systems and methods for implementing a computer language type system |
| US8111694B2 (en) | 2005-03-23 | 2012-02-07 | Nokia Corporation | Implicit signaling for split-toi for service guide |
| US20070143664A1 (en) * | 2005-12-21 | 2007-06-21 | Motorola, Inc. | A compressed schema representation object and method for metadata processing |
| WO2007134407A1 (en) * | 2006-05-24 | 2007-11-29 | National Ict Australia Limited | Selectivity estimation |
| DE112007001386A5 (de) * | 2006-07-07 | 2009-03-19 | Universität Paderborn | Verfahren zur Kompression einer Datensequenz eines elektronischen Dokuments |
| US7747558B2 (en) | 2007-06-07 | 2010-06-29 | Motorola, Inc. | Method and apparatus to bind media with metadata using standard metadata headers |
| US7925643B2 (en) * | 2008-06-08 | 2011-04-12 | International Business Machines Corporation | Encoding and decoding of XML document using statistical tree representing XSD defining XML document |
| EP2161667A1 (en) * | 2008-09-08 | 2010-03-10 | Thomson Licensing, Inc. | Method and device for encoding elements |
| EP2219117A1 (en) * | 2009-02-13 | 2010-08-18 | Siemens Aktiengesellschaft | A processing module, a device, and a method for processing of XML data |
| RU2413985C2 (ru) * | 2009-03-05 | 2011-03-10 | Борис Васильевич Черников | Способ преобразования слабоформализуемых документов для минимизации их объема при хранении |
| JP5570202B2 (ja) * | 2009-12-16 | 2014-08-13 | キヤノン株式会社 | 構造化文書解析装置、構造化文書解析方法、及びコンピュータプログラム |
| EP2388701A1 (en) * | 2010-05-17 | 2011-11-23 | Siemens Aktiengesellschaft | Method and apparatus for providing a service implementation |
| WO2012128830A2 (en) * | 2011-03-24 | 2012-09-27 | Okeefe Kevin J | System and mehtod for information exchange and processing |
| US9543980B2 (en) | 2014-10-10 | 2017-01-10 | Massachusettes Institute Of Technology | Systems and methods for model-free compression and model-based decompression |
| US10733237B2 (en) | 2015-09-22 | 2020-08-04 | International Business Machines Corporation | Creating data objects to separately store common data included in documents |
| JP6903892B2 (ja) * | 2016-10-12 | 2021-07-14 | 富士通株式会社 | 検証プログラム、検証装置、検証方法、符号化プログラム、符号化装置および符号化方法 |
| US10467275B2 (en) * | 2016-12-09 | 2019-11-05 | International Business Machines Corporation | Storage efficiency |
| CN108763379B (zh) * | 2018-05-18 | 2022-06-03 | 北京奇艺世纪科技有限公司 | 一种数据压缩方法、数据解压缩方法、装置及电子设备 |
Family Cites Families (22)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5438512A (en) * | 1993-10-22 | 1995-08-01 | Xerox Corporation | Method and apparatus for specifying layout processing of structured documents |
| WO1997034240A1 (en) * | 1996-03-15 | 1997-09-18 | University Of Massachusetts | Compact tree for storage and retrieval of structured hypermedia documents |
| JPH10187680A (ja) * | 1996-12-20 | 1998-07-21 | Nec Corp | 単語、文、部分の粒度で管理するドキュメントリポジトリ装置 |
| US6266419B1 (en) * | 1997-07-03 | 2001-07-24 | At&T Corp. | Custom character-coding compression for encoding and watermarking media content |
| US6121903A (en) * | 1998-01-27 | 2000-09-19 | Infit Communications Ltd. | On-the-fly data re-compression |
| US6363381B1 (en) * | 1998-11-03 | 2002-03-26 | Ricoh Co., Ltd. | Compressed document matching |
| US6553141B1 (en) * | 2000-01-21 | 2003-04-22 | Stentor, Inc. | Methods and apparatus for compression of transform data |
| JP3368883B2 (ja) * | 2000-02-04 | 2003-01-20 | インターナショナル・ビジネス・マシーンズ・コーポレーション | データ圧縮装置、データベースシステム、データ通信システム、データ圧縮方法、記憶媒体及びプログラム伝送装置 |
| US6883137B1 (en) * | 2000-04-17 | 2005-04-19 | International Business Machines Corporation | System and method for schema-driven compression of extensible mark-up language (XML) documents |
| IT1314626B1 (it) * | 2000-04-21 | 2002-12-20 | Ik Multimedia Production Srl | Procedimento per la codifica e la decodifica di flussi di dati,rappresentanti suoni in forma digitale, all'interno di un |
| US20020029229A1 (en) * | 2000-06-30 | 2002-03-07 | Jakopac David E. | Systems and methods for data compression |
| CN1401188B (zh) * | 2000-10-17 | 2011-06-08 | 皇家菲利浦电子有限公司 | Mpeg-7样品的二进制格式 |
| US6850948B1 (en) * | 2000-10-30 | 2005-02-01 | Koninklijke Philips Electronics N.V. | Method and apparatus for compressing textual documents |
| JP4774145B2 (ja) * | 2000-11-24 | 2011-09-14 | 富士通株式会社 | 構造化文書圧縮装置および構造化文書復元装置並びに構造化文書処理システム |
| JP2004518327A (ja) * | 2001-01-11 | 2004-06-17 | コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ | 逆進的にストリングを参照する為の識別子を用いたデータ圧縮方法 |
| FR2820563B1 (fr) * | 2001-02-02 | 2003-05-16 | Expway | Procede de compression/decompression d'un document structure |
| US7246177B2 (en) * | 2001-05-17 | 2007-07-17 | Cyber Ops, Llc | System and method for encoding and decoding data files |
| JP3832807B2 (ja) * | 2001-06-28 | 2006-10-11 | インターナショナル・ビジネス・マシーンズ・コーポレーション | データ処理方法及びその手法を用いたエンコーダ、デコーダ並びにｘｍｌパーサ |
| US20030028673A1 (en) * | 2001-08-01 | 2003-02-06 | Intel Corporation | System and method for compressing and decompressing browser cache in portable, handheld and wireless communication devices |
| AU2003250302A1 (en) * | 2002-07-15 | 2004-03-03 | Siemens Aktiengesellschaft | Method and devices for encoding/decoding structured documents, especially xml documents |
| US6667700B1 (en) * | 2002-10-30 | 2003-12-23 | Nbt Technology, Inc. | Content-based segmentation scheme for data compression in storage and transmission including hierarchical segment representation |
| US7509574B2 (en) * | 2005-02-11 | 2009-03-24 | Fujitsu Limited | Method and system for reducing delimiters |
-
2000
- 2000-09-06 FR FR0011356A patent/FR2813743B1/fr not_active Expired - Fee Related
-
2001
- 2001-08-31 WO PCT/FR2001/002719 patent/WO2002021848A1/fr not_active Ceased
- 2001-08-31 ES ES01967412T patent/ES2234878T3/es not_active Expired - Lifetime
- 2001-08-31 EP EP01967412A patent/EP1316220B1/fr not_active Expired - Lifetime
- 2001-08-31 US US10/363,330 patent/US8015218B2/en not_active Expired - Fee Related
- 2001-08-31 AT AT01967412T patent/ATE285656T1/de not_active IP Right Cessation
- 2001-08-31 DE DE60107964T patent/DE60107964T2/de not_active Expired - Lifetime
- 2001-08-31 JP JP2002526128A patent/JP4653381B2/ja not_active Expired - Fee Related
- 2001-08-31 DK DK01967412T patent/DK1316220T3/da active
- 2001-08-31 AU AU2001287796A patent/AU2001287796A1/en not_active Abandoned
- 2001-08-31 PT PT01967412T patent/PT1316220E/pt unknown
-
2011
- 2011-07-26 US US13/190,692 patent/US20110283183A1/en not_active Abandoned
Also Published As
| Publication number | Publication date |
|---|---|
| WO2002021848A1 (fr) | 2002-03-14 |
| EP1316220B1 (fr) | 2004-12-22 |
| PT1316220E (pt) | 2005-02-28 |
| DE60107964D1 (de) | 2005-01-27 |
| FR2813743B1 (fr) | 2003-01-03 |
| AU2001287796A1 (en) | 2002-03-22 |
| FR2813743A1 (fr) | 2002-03-08 |
| ATE285656T1 (de) | 2005-01-15 |
| JP2004508647A (ja) | 2004-03-18 |
| US20040013307A1 (en) | 2004-01-22 |
| US20110283183A1 (en) | 2011-11-17 |
| EP1316220A1 (fr) | 2003-06-04 |
| DK1316220T3 (da) | 2005-01-24 |
| DE60107964T2 (de) | 2005-05-25 |
| JP4653381B2 (ja) | 2011-03-16 |
| US8015218B2 (en) | 2011-09-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| ES2234878T3 (es) | Procedimiento para la compresion/decompresion de documentos estructur dos. | |
| ES2272666T3 (es) | Procedimiento de compresion/descompresion de un documento estructurado. | |
| JP3368883B2 (ja) | データ圧縮装置、データベースシステム、データ通信システム、データ圧縮方法、記憶媒体及びプログラム伝送装置 | |
| JP3009727B2 (ja) | 改良形データ圧縮装置 | |
| JP4373721B2 (ja) | マークアップ言語文書を符号化するための方法およびシステム | |
| US20050120031A1 (en) | Structured document encoder, method for encoding structured document and program therefor | |
| US20070112810A1 (en) | Method for compressing markup languages files, by replacing a long word with a shorter word | |
| JPH07160473A (ja) | バイト整列式データ圧縮方法及び装置 | |
| CN101040444B (zh) | 压缩结构化文档的方法和装置 | |
| US20090254882A1 (en) | Methods and devices for iterative binary coding and decoding of xml type documents | |
| US20070143664A1 (en) | A compressed schema representation object and method for metadata processing | |
| KR100667293B1 (ko) | 허프만 코드 길이 정보를 생성하는 방법 | |
| US9128912B2 (en) | Efficient XML interchange schema document encoding | |
| US7676742B2 (en) | System and method for processing of markup language information | |
| CN118523780A (zh) | 一种对sas数据集进行解压以及压缩的方法及应用 | |
| Wang et al. | XCpaqs: compression of XML document with XPath query support | |
| JP4821287B2 (ja) | 構造化文書の符号化方法、符号化装置、符号化プログラム、復号装置及び符号化された構造化文書のデータ構造 | |
| KR20060123197A (ko) | 구조적 문서의 압축 및 압축 해제 방법 | |
| US7043502B1 (en) | Methodology for JEDEC file repair through compression field techniques | |
| Liefke et al. | XMill: an E cient Compressor for XML Data | |
| JP2004342029A (ja) | 構造化文書圧縮方法及び装置 | |
| JP4675748B2 (ja) | Ｘｍｌデータ変換装置及びｘｍｌデータ復元装置 | |
| JP2633121B2 (ja) | データ解析処理方式 | |
| Conner | Compact Binary XML | |
| Muqtida et al. | Improvement in Compression Efficiency of Huffman Coding |