ES2276144T3 - Procedimiento para codificar posiciones de elementos de datos en una estructura de datos. - Google Patents
Procedimiento para codificar posiciones de elementos de datos en una estructura de datos. Download PDFInfo
- Publication number
- ES2276144T3 ES2276144T3 ES03787617T ES03787617T ES2276144T3 ES 2276144 T3 ES2276144 T3 ES 2276144T3 ES 03787617 T ES03787617 T ES 03787617T ES 03787617 T ES03787617 T ES 03787617T ES 2276144 T3 ES2276144 T3 ES 2276144T3
- Authority
- ES
- Spain
- Prior art keywords
- data
- codes
- data elements
- procedure
- elements
- 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
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
- H03M7/14—Conversion to or from non-weighted codes
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
Procedimiento para codificar posiciones de elementos de datos en una estructura de datos, en el que a los elementos de datos se les asignan códigos de posición en una secuencia predeterminada, caracterizado porque - los códigos de posición se eligen tal que para posiciones de otros elementos de datos entre las posiciones de dos elementos de datos contiguos pueden otorgarse otros códigos de posición para la codificación de posición de otros elementos de datos, siendo la longitud de código al menos otro código de posición mayor que la longitud más larga de las longitudes de código de los códigos de posición de dos elementos de datos contiguos, - los códigos de posición representan números racionales.
Description
Procedimiento para codificar posiciones de
elementos de datos en una estructura de datos.
La invención se refiere a un procedimiento para
codificar posiciones de elementos de datos en una estructura de
datos.
En una estructura de datos se presentan a menudo
elementos de datos que han de diferenciarse entre sí mediante sus
posiciones. En los procedimientos de codificación de posición esto
es posible otorgando códigos de posición a todos los elementos de
datos en una secuencia predeterminada.
En [1] se describe un procedimiento de
codificación de posición que se utiliza en un procedimiento para la
codificación binaria de datos XML. Este procedimiento utiliza
definiciones de esquema XML (por ejemplo en el marco de un
procedimiento estandarizado MPEG-7) para generar los
códigos para los distintos elementos de datos de la descripción
XML. Aquí pueden presentarse varias veces en el documento elementos
individuales o grupos de elementos del mismo tipo según la
definición de esquema XML. En este caso se transmite un código de
posición (PC). El código de posición es la representación binaria de
un número entero que especifica la posición respecto a los
elementos contiguos. El código de posición se asigna al elemento en
base a la posición respecto a los elementos contiguos en el
documento a codificar. Esto tiene la ventaja de que el código de
posición de un elemento se mantiene con independencia de la
secuencia en la que se transmiten los elementos contiguos. Así
pueden perderse en la transmisión elementos sin que esto influya
sobre el código de posición o bien la posición de los elementos
decodificados a continuación mediante un decodificador.
Un inconveniente de este procedimiento conocido
es que en el momento de la codificación ha de ser conocido el
documento XML, ya que con el código de posicionado existente hasta
ahora no puede intercalarse ninguna nueva posición, sino que
solamente pueden anexarse nuevas posiciones. Esto es en particular
un inconveniente cuando durante la confección de un documento XML
éste debe ya codificarse o transmitirse, por ejemplo en
transmisiones en vivo (Live) tras una transmisión estándar, p. e.
MPGE-4 ó MPEG-7.
Para solucionar este problema pueden dejarse
huecos entre los códigos de posición utilizados, que pueden llenarse
cuando sea necesario. No obstante, en especial en la codificación
en vivo (Live) es difícilmente previsible qué huecos hay que fijar
de antemano para mantenerlos dispuestos para atender las
necesidades. Además, la cantidad total de huecos posibles está
limitada en muchos casos por la definición de esquema XML. Si en la
posición a insertar no existe ya ningún código de posición que haya
quedado libre debido a tales huecos, entonces deben enviarse de
nuevo todos los elementos contiguos ya enviados con nuevos códigos
de posición generados. En particular sucede esto con frecuencia
para varios elementos de datos del mismo tipo, por ejemplo en
elementos idénticos o grupos de elementos que se presentan varias
veces en un documento. La consecuencia es un claro empeoramiento de
la eficiencia de la codificación, así como un claro aumento del
coste de procesamiento tanto en el codificador como también en el
decodificador.
Es tarea de la invención por lo tanto lograr un
procedimiento y un dispositivo para codificar posiciones de
elementos de datos en una estructura de datos en los cuales puedan
codificarse de manera sencilla y eficiente las posiciones de los
nuevos elementos de datos a añadir.
Esta tarea se resuelve mediante el procedimiento
según la reivindicación 1 y el dispositivo según la reivindicación
11 y 12. Ventajosos perfeccionamientos de la invención se describen
en las reivindicaciones dependientes.
El procedimiento correspondiente a la invención
tiene la ventaja de que la codificación de posición es resistente a
la pérdida de datos, ya que los códigos de posición se mantienen. A
la vez pueden codificarse eficientemente al utilizar el
procedimiento para codificar documentos XML documentos dinámicos que
se generan durante la codificación. Esto es posible debido a que
pueden codificarse nuevas posiciones entre posiciones existentes
sin que los elementos y sus códigos de posición tengan que
transmitirse de nuevo.
Una forma constructiva de la invención se
describe a continuación en base a los adjuntos dibujos.
Se muestra en:
Fig. 1 una representación de un código de
posición de un elemento de datos, habiéndose generado el código de
posición con la ayuda del procedimiento correspondiente a la
invención;
fig. 2 una estructura de datos, estando
asignados códigos de posición a los elementos de datos, que se han
generado con la ayuda del procedimiento correspondiente a la
invención;
fig. 3 la estructura de datos según la figura 2,
habiéndose añadido nuevos elementos de datos.
En la forma constructiva de la invención
considerada a continuación, se asignan a los elementos de datos de
la estructura de datos códigos de posición, en secuencia creciente
de las posiciones de los elementos de datos, que llevan asociados
igualmente en secuencia creciente números racionales en una gama de
valores predeterminada. Si ha de direccionarse ahora una posición
entre dos posiciones existentes, esto es posible siempre, ya que
entre dos números racionales dados R_{1} y R_{2} con R_{1}
\neq R_{2}, siempre existe un número infinitesimal de números
racionales. En implantaciones reales ciertamente este número no es
infinitesimal, pero puede elegirse siempre suficientemente grande,
por ejemplo > 1024. Cuando el código de posición del primer
elemento de datos es diferente a cero, pueden insertarse también
elementos de datos cuyo código de posición sea menor que el código
de posición del primer elemento de datos.
La utilización de números racionales tiene la
ventaja adicional de que permite una representación binaria lo más
corta posible.
En la figura 1 se muestra un código de posición
de un elemento de datos. Este código de posición es la
representación binaria de un número racional en base 2 en la gama
de valores [0,1]. La representación binaria del número racional
incluye N = 15 bits, existiendo N* = 12 bits de datos (bit MSB, bit
1 a bit 11; N* <= N) que están dispuestos en tres cuádruplos.
Los valores de los bits de datos se citan en cada caso debajo de los
bits. Los bits de datos van precedidos de tres bits de extensión,
indicando la cantidad de bits de extensión la cantidad de
cuádruplos de bits de datos existentes. Los dos bits anteriores de
extensión están colocados en uno y el último bit de extensión a
cero. Mediante la colocación del último bit de extensión a cero, se
señaliza que los siguientes bits son bits de datos. Con la
representación elegida en la figura 1 se representa así un número
racional mediante N bits, de los cuales N* bits son bits de datos,
siendo N*< = N y N* = 4 k (k es aquí un número entero en la gama
de valores [1, \infty].
En la figura 2 se muestra una estructura de
datos en forma de un árbol de datos, habiéndose generado los códigos
de posición de los elementos de datos mediante el procedimiento
antes descrito. La estructura de datos incluye un elemento de datos
A combinado con cinco elementos B. Los elementos de datos B llevan
asociados dos códigos de posición P en secuencia ascendente, en
forma de números racionales 1/8, 1/4, 3/8, 1/2 ó bien 5/8. Además
se indican las representaciones binarias de los códigos de posición
según la representación de la figura 1.
En la figura 3 se muestra una estructura de
datos según la figura 2, estando intercalados entre el elemento de
datos con el código de posición 3/8 y el elemento de datos con el
código de posición 1/2 adicionalmente dos nuevos elementos de
datos. Estos elementos de datos recién añadidos se representan en la
figura 3 en gris. Mediante la utilización de números racionales
para los códigos de posición, pueden encontrarse ahora dos valores
para los códigos de posición de los nuevos elementos de datos que se
encuentren entre los valores 3/8 y 1/2. En la figura 3 se han
elegido para estos valores los números 7/16 y 15/32. En
consecuencia, es posible generar nuevos códigos de posición para
nuevos elementos de datos en la estructura de datos sin tener que
modificar los códigos de posición existentes. De esta manera pueden
conservarse los códigos de posición asignados e intercalarse en
cualquier posición cualquier cantidad de nuevos elementos de
datos.
[1] ISO/IEC 15938-1 Interfaz de
descripción de contenido multimedia - Parte 1: Sistemas, Ginebra
2002.
Claims (13)
1. Procedimiento para codificar posiciones de
elementos de datos en una estructura de datos, en el que
a los elementos de datos se les asignan códigos
de posición en una secuencia predeterminada,
caracterizado porque
- -
- los códigos de posición se eligen tal que para posiciones de otros elementos de datos entre las posiciones de dos elementos de datos contiguos pueden otorgarse otros códigos de posición para la codificación de posición de otros elementos de datos, siendo la longitud de código al menos otro código de posición mayor que la longitud más larga de las longitudes de código de los códigos de posición de dos elementos de datos contiguos,
- -
- los códigos de posición representan números racionales.
2. Procedimiento según la reivindicación 1,
caracterizado porque
el primer y/o el último código de posición de
los elementos de datos se eligen tal que antes del primer y/o
después del último código de posición pueden intercalarse otros
códigos de posición.
3. Procedimiento según la reivindicación 2,
caracterizado porque
el primer código de posición es distinto de cero
y/o el último código de posición es distinto de uno.
4. Procedimiento según una de las
reivindicaciones precedentes,
caracterizado porque los códigos de
posición son datos binarios.
5. Procedimiento según la reivindicación 4,
caracterizado porque
los códigos de posición incluyen en uno o varias
n-tuplas de bits de datos y uno o varios bits de
extensión, correspondiendo la cantidad de bits de extensión, a la
cantidad de n-tuplas de bits de datos.
6. Procedimiento según una de las
reivindicaciones precedentes,
caracterizado porque
la estructura de datos es parte de un árbol de
datos.
7. Procedimiento según una de las
reivindicaciones precedentes,
caracterizado porque los elementos de
datos son códigos de datos para los elementos de datos de un
documento.
8. Procedimiento según la reivindicación 7,
caracterizado porque
el documento es un documento XML.
9. Procedimiento según la reivindicación 7 u
8,
caracterizado porque
los códigos de datos para el documento se
generan con un procedimiento de codificación MPEG.
10. Procedimiento según la reivindicación 9,
caracterizado porque el procedimiento de
codificación es un procedimiento de codificación
MPEG-7 estandarizado.
11. Dispositivo para codificar códigos de
posición de elementos de datos en una estructura de datos,
caracterizado porque
con el dispositivo puede realizarse un
procedimiento según una de las reivindicaciones precedentes.
12. Dispositivo para decodificar códigos de
posición de elementos de datos en una estructura de datos,
caracterizado porque
con el dispositivo pueden decodificarse los
códigos de posición codificados según uno de los procedimientos de
las reivindicaciones 1 a 10.
13. Sistema de transmisión de datos, que incluye
un dispositivo según la reivindicación 11 y un dispositivo según la
reivindicación 12.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| DE10231970 | 2002-07-15 | ||
| DE10231970A DE10231970B3 (de) | 2002-07-15 | 2002-07-15 | Verfahren zur Codierung von Positionen von Datenelementen in einer Datenstruktur sowie Vorrichtungen zur entsprechenden Codierung und/oder Decodierung |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| ES2276144T3 true ES2276144T3 (es) | 2007-06-16 |
Family
ID=30774924
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| ES03787617T Expired - Lifetime ES2276144T3 (es) | 2002-07-15 | 2003-06-30 | Procedimiento para codificar posiciones de elementos de datos en una estructura de datos. |
Country Status (8)
| Country | Link |
|---|---|
| US (2) | US7546303B2 (es) |
| EP (2) | EP1717958A3 (es) |
| JP (1) | JP4221366B2 (es) |
| CN (3) | CN101834607B (es) |
| AU (1) | AU2003250279A1 (es) |
| DE (2) | DE10231970B3 (es) |
| ES (1) | ES2276144T3 (es) |
| WO (1) | WO2004017523A1 (es) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE10231970B3 (de) | 2002-07-15 | 2004-02-26 | Siemens Ag | Verfahren zur Codierung von Positionen von Datenelementen in einer Datenstruktur sowie Vorrichtungen zur entsprechenden Codierung und/oder Decodierung |
| US8321465B2 (en) * | 2004-11-14 | 2012-11-27 | Bloomberg Finance L.P. | Systems and methods for data coding, transmission, storage and decoding |
| US20090094263A1 (en) * | 2007-10-04 | 2009-04-09 | Microsoft Corporation | Enhanced utilization of network bandwidth for transmission of structured data |
| CN107092656B (zh) * | 2017-03-23 | 2019-12-03 | 中国科学院计算技术研究所 | 一种树状结构数据处理方法及系统 |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB8515482D0 (en) * | 1985-06-19 | 1985-07-24 | Int Computers Ltd | Search apparatus |
| DE3921646A1 (de) * | 1989-06-30 | 1991-01-03 | Siemens Ag | Verfahren zu einer codierung einer elementfolge und einrichtung zur durchfuehrung des verfahrens |
| DE4014931A1 (de) * | 1990-05-10 | 1991-11-14 | Telefunken Electronic Gmbh | Datenuebertragungssystem |
| US6415398B1 (en) * | 1995-09-29 | 2002-07-02 | Kabushiki Kaisha Toshiba | Coding system and decoding system |
| US7233953B2 (en) * | 2000-12-22 | 2007-06-19 | Siemens Aktiengesellschaft | Method for improving functionality of the binary representation of MPEG-7 and of other XML-based contents descriptions |
| AUPR440901A0 (en) * | 2001-04-12 | 2001-05-17 | Silverbrook Research Pty. Ltd. | Error detection and correction |
| DE10231970B3 (de) | 2002-07-15 | 2004-02-26 | Siemens Ag | Verfahren zur Codierung von Positionen von Datenelementen in einer Datenstruktur sowie Vorrichtungen zur entsprechenden Codierung und/oder Decodierung |
-
2002
- 2002-07-15 DE DE10231970A patent/DE10231970B3/de not_active Expired - Fee Related
-
2003
- 2003-06-30 ES ES03787617T patent/ES2276144T3/es not_active Expired - Lifetime
- 2003-06-30 JP JP2004528333A patent/JP4221366B2/ja not_active Expired - Fee Related
- 2003-06-30 WO PCT/DE2003/002168 patent/WO2004017523A1/de not_active Ceased
- 2003-06-30 CN CN201010181835.3A patent/CN101834607B/zh not_active Expired - Fee Related
- 2003-06-30 AU AU2003250279A patent/AU2003250279A1/en not_active Abandoned
- 2003-06-30 EP EP06016611A patent/EP1717958A3/de not_active Withdrawn
- 2003-06-30 DE DE50306202T patent/DE50306202D1/de not_active Expired - Lifetime
- 2003-06-30 EP EP03787617A patent/EP1522148B1/de not_active Expired - Lifetime
- 2003-06-30 CN CNA038169428A patent/CN1669225A/zh active Granted
- 2003-06-30 US US10/521,620 patent/US7546303B2/en not_active Expired - Fee Related
- 2003-06-30 CN CN03816942.8A patent/CN1669225B/zh not_active Expired - Fee Related
-
2009
- 2009-06-08 US US12/480,397 patent/US8117236B2/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| US8117236B2 (en) | 2012-02-14 |
| CN101834607A (zh) | 2010-09-15 |
| WO2004017523A1 (de) | 2004-02-26 |
| EP1522148A1 (de) | 2005-04-13 |
| CN101834607B (zh) | 2015-04-29 |
| CN1669225A (zh) | 2005-09-14 |
| DE10231970B3 (de) | 2004-02-26 |
| US20060089937A1 (en) | 2006-04-27 |
| JP4221366B2 (ja) | 2009-02-12 |
| EP1522148B1 (de) | 2007-01-03 |
| JP2006501704A (ja) | 2006-01-12 |
| DE50306202D1 (de) | 2007-02-15 |
| EP1717958A2 (de) | 2006-11-02 |
| US7546303B2 (en) | 2009-06-09 |
| CN1669225B (zh) | 2015-11-25 |
| EP1717958A3 (de) | 2010-04-28 |
| AU2003250279A1 (en) | 2004-03-03 |
| US20090307243A1 (en) | 2009-12-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Collet et al. | Zstandard compression and the application/zstd media type | |
| EP0732855A3 (en) | Moving picture coding and/or decoding system, and variable-length coding system | |
| ES2277174T3 (es) | Codificacion aritmetica de coeficientes de transformacion. | |
| ATE269605T1 (de) | Entropiekodierung von variabler zu variabler länge | |
| BR0107329A (pt) | Processo de codificação para codificar um elemento de descrição de uma instância de um esquema tipo xml, processo de decodificação para decodificar um fragmento compreendendo um conteúdo e uma sequência de informação de identificação, codificador para codificar um elemento de descrição de uma instância de um esquema tipo xml, decodificador para decodificar um fragmento compreendendo um conteúdo e uma sequência de informação de identificação, sistema de transmissão, sinal para transmissão através de uma rede de transmissão, e, tabela destinada a ser usada em um codificador | |
| ES2442215T3 (es) | Procedimiento y dispositivo de codificación y descodificación aritméticas de estados binarios y programa informático correspondiente y soporte de almacenamiento correspondiente legible por ordenador | |
| DE60141329D1 (de) | Videokodierung | |
| MX2021011102A (es) | Inicializacion de probabilidad para codificacion de video. | |
| TW200511736A (en) | Method and apparatus for varying lengths of low density parity check codewords | |
| RU2020119054A (ru) | Аудиокодеры, аудиодекодеры, способы и компьютерные программы, применяющие кодирование и декодирование младших значащих битов | |
| ES2276144T3 (es) | Procedimiento para codificar posiciones de elementos de datos en una estructura de datos. | |
| ATE241873T1 (de) | Verfahren zur dekodierung von mit einem entropie- code kodierten daten, entsprechende dekodierungsvorrichtung und übertragungssystem | |
| ES3050734T3 (en) | Apparatuses for encoding and decoding a sequence of integer values, methods for encoding and decoding a sequence of integer values and computer program for implementing these methods | |
| US20170318314A1 (en) | Variable Length Coding and Decoding Methods and Devices for Grouped Pixels | |
| US20180205952A1 (en) | Method and apparatus for performing arithmetic coding by limited carry operation | |
| CN1168218C (zh) | 产生数据流的设备和方法和读取数据流的设备和方法 | |
| US20070109160A1 (en) | Method for efficient variable length decoding | |
| ES2106131T3 (es) | Escamoteador/desescamoteador y dispositivo de sincronizacion para un sistema de transmision de datos. | |
| US5936559A (en) | Method for optimizing data compression and throughput | |
| US6867715B2 (en) | System, method, and apparatus for variable length decoder | |
| US6298165B1 (en) | Method for improving data encoding and decoding efficiency | |
| US8327027B2 (en) | Data compression system and method | |
| Figueiredo | Elias Coding | |
| JPH06216781A (ja) | 可変長符号復号器 | |
| EP1170872A3 (en) | Code and iteratively decodable code structure, encoder, encoding method, and associated decoder and decoding method |