XML Matters: XML y la compresión

Explorar la entropía de los documentos

Esta columna XML Matters explora varios enfoques para comprimir documentos XML. Las estructuras especiales en un XML permiten ciertas mejoras sobre las técnicas de compresión más ingenuas. El columnista David Mertz explica algunas formas de aprovecharlas e incluye un código de muestra para mostrar estas técnicas.

David Mertz, Developer, Gnosis Software, Inc.

David MertzDavid Mertz cree que los lenguajes artificiales son perfectamente naturales pero los lenguajes naturales parecen un poco artificiales. Es posible contactar a David en mertz@gnosis.cx; podrá investigar todos los aspectos de su vida en su página Web personal. Vea su libro, Text Processing in Python (Procesamiento de Texto en Python). Las sugerencias y recomendaciones sobre las columnas pasadas o futuras son bienvenidas.



21-01-2013

XML como formato posee muchas propiedades; es una forma general perfecta de representar estructuras de datos arbitrarias y es legible para el ser humano (más o menos). Pero XML tiene una notoria propiedad desagradable. Los documentos XML son VERBOSOS; no solo un poco en el área de las palabras, pero casi increíblemente gigante. La mayoría del tiempo, esta desventaja de XML realmente no hace a la diferencia. DASD es poco costoso, y el tiempo en la conexión puede ser solo una pequeña parte del tiempo total en el proceso. Pero en otros momentos, el ancho de banda y el espacio de almacenamiento pueden ser importantes.

Desarrolle habilidades de este tema

Este contenido es parte de un knowledge path progresivo para avanzar en sus habilidades. Vea Compresión de datos y XML

Para cuantificar las cosas, no es del todo inusual que los documentos XML que representan datos orientados a la tabla sean tres veces más grandes que una base de datos o representación CSV, o incluso un archivo plano. Un incremento similar es típico en la representación de datos EDI (como para proyectos ebXML). En muchos de esos contextos, uno comienza con fuentes de datos multimegabyte. Incrementar estos múltiplos puede ser inconveniente, especialmente para los propósitos de la transmisión. Por ejemplo, para los propósitos de este artículo creé una representación XML de un archivo de registro de acceso Apache de aproximadamente 1 megabyte. Esto creó un documento XML de un tamaño 3,18 veces mayor al del registro fundamental orientado a la línea. La única información agregada en el proceso fueron nombres descriptivos para campos, pero que podrían haber sido especificados en una sola línea de cabecera de menos de cien bytes. Además, mi representación específica XML no incluyó ningún espacio de nombre en las etiquetas, lo cual hubiese aumentado aún más el tamaño.

Cuando se piensa en comprimir documentos, normalmente se piensa primero en algoritmos de compresión generales como Lempel-Ziv y Huffman, y de las utilidades comunes que implementan variaciones en ellos. Específicamente, en plataformas del tipo Unix, lo que primero se viene a la mente es por lo general la utilidad gzip; en otras plataformas, zip es más común (implementando utilidades como PKZIP, Info-ZIP y WinZip). gzip resulta bastante consistente, más que zip, pero solo por un margen estrecho. Estas utilidades tienden de hecho a reducir el tamaño de archivos XML. Sin embargo, también resulta que es posible obtener tasas de compresión considerablemente mejores por dos medios, ya sea individualmente o en combinación.

La primera técnica sería utilizar el algoritmo de compresión Burrows-Wheeler en vez de los algoritmos secuenciales Lempel-Ziv. En particular, el de alguna manera menos utilizado bzip2 (o sus bibliotecas asociadas y API) es una implementación del Burrows-Wheeler para muchas plataformas de sistemas (y viene acompañado de una licencia completa al estilo BSD). Burrows-Wheeler opera agrupando cadenas relacionadas en una fuente sin comprimir, en vez de en el estilo Lempel-Ziv de desarrollar un diccionario de ocurrencias de cadenas. bzip2 obtiene una mejor compresión que gzip consistentemente y a lo largo de muchos tipos de archivos, pero el efecto es especialmente dramático para documentos XML. Por el lado negativo, bzip2 es generalmente más lento que gzip. De nuevo, la lentitud del ancho de banda por lo general satura las diferencias de velocidad en el CPU y en algoritmos limitados por la memoria.

La segunda técnica es aprovechar la estructura específica de los documentos XML para producir más declaraciones compresibles . La utilidad XMill es una implementación de esta técnica y se encuentra disponible (con fuente C++) bajo una licencia liberal de AT&T. Sin embargo XMill parece necesitar ciertas limitaciones de estilo de visitas en su licencia y no puede ser distribuido directamente por otras partes (por lo menos como yo lo entiendo). He creado mi propia implementación de la misma técnica general y presento la implementación en este artículo. El código que aparece aquí se lanza al dominio público, y la técnica tal y como se implementa fue desarrollada de manera independiente y tiene una pequeña similitud con XMill: Algunas veces XMill lo hace mejor, algunas veces lo hago yo (pero XMill es probablemente siempre más rápido que mi implementación inicial, el que le presta atención solo a los resultados de compresión).

Comparación de algoritmos básicos

Obtuve o creé cuatro documentos base con el objetivo de la comparación en este artículo. El primero es la obra de Shakespeare, Hamlet, como un documento XML (ver Recursos). La marcación incluye etiquetas como <PERSONA>, <SPEAKER> y <LINE>, lo que se correlaciona de forma bastante natural con las formas tipográficas que uno podría encontrarse en una copia impresa. Para poder comparar cómo la marcación XML contribuye al tamaño del documento y a la compresibilidad, derivé del documento hamlet.xml un documento hamlet.txt que simplemente removió todas las etiquetas XML pero dejó el contenido. Esta derivación no es reversible y es una pérdida estricta de información. Una persona que lea hamlet.txt no tendría grandes dificultades para determinar semánticamente cuál contenido es el nombre de "speaker" y cuál es "line", por ejemplo, pero no hay una forma fácil de que una computadora pueda generar el documento XML fuente.

Los siguientes dos documentos son un archivo Apache Weblog (un conjunto compacto para registros orientados a la línea), y un documento XML creado de este archivo. Debido a que el documento de origen es el archivo de registro, no se pierde información en la transformación, y es insignificante recrear exactamente el formato original del XML. Por supuesto, no puede utilizar un analizador XML, DOM, validador o un DTD con el formato de archivo de registro. Observemos los tamaños de los documentos base en el Listado 1.

Listado 1. Listado de directorio de los documentos base
 288754  hamlet.xml
 188830  hamlet.txt
 949474  weblog.txt
3021921  weblog.xml

En ambos casos, el XML es mucho más grande. En el ejemplo de Hamlet, la comparación no es completamente justa porque el contenido de la información actual de la versión del texto también ha disminuido. Pero para el archivo Weblog, el XML comienza a verse bastante mal. Sin embargo, no todo es lo que parece. Los programas de compresión hacen un buen trabajo en reducir los documentos a su contenido informativo real, y el rellenado sin sentido tiende a cero en la versión comprimida (asintomáticamente con el esfuerzo de compresión, y si todo está bien). Veamos gzip, zip y bzip2 en los listados 2 y 3.

Listado 2. Directorio de Shakespeare comprimido
  78581  hamlet.xml.gz
  72505  hamlet.txt.gz
  78696  hamlet.xml.zip
  72620  hamlet.txt.zip
  57522  hamlet.xml.bz2
  56743  hamlet.txt.bz2
Listado 3. Directorio del Weblog comprimido
  91029  weblog.txt.gz
 115524  weblog.xml.gz
  91144  weblog.txt.zip
 115639  weblog.xml.zip
  56156  weblog.txt.bz2
  66994  weblog.xml.bz2

Del estudio de los tamaños en estos dos listados surgen varias cosas interesantes. Para ambos estilos de documentos (para toda técnica de compresión), las diferencias de tamaño en los archivos comprimidos es mucho menor que entre XML y los originales del texto. También es importante destacar que los clústeres gzip y zip se agrupan muy cerca para casos correspondientes, mientras que bzip2 funciona mucho mejor todo el tiempo. Además de esto, cuando se utilizó bzip2 en el documento de Shakespeare, la diferencia de tamaño comprimido entre los formatos de texto y de XML fue prácticamente insignificante, a pesar del tamaño de que el documento base XML era un 53% más grande.

Sin embargo, el Weblog se destaca como un caso problemático. Mientras que la compresión disminuye bastante el abultamiento de la conversión XML, incluso la versión bzip2 permite a la marcación aumentar el tamaño en casi un 20% No es necesariamente un desastre, pero parece que deberíamos poder comprimirlo al contenido de la información real.


Transformaciones reversibles

Un documento XML tiene una forma un tanto ineficiente cuando se trata de compresión. Como verán, bzip2 alivia de alguna forma esta ineficiencia al reagrupar las series. Pero por naturaleza, los documentos XML son una mezcolanza de partes bastante disímiles (etiquetas, atributos, cuerpos de elemento de distintos tipos). Si pudiera tomar cada conjunto relativamente homogéneo de cosas y agruparlas cerca en un archivo transformado, los compresores estándar tendrían más elementos con los que trabajar. Por ejemplo, si cada cuerpo de etiqueta <host> en el Weblog ocurre cerca de los otros, el bloque de cosas que contiene la dirección IP de hosts serán fáciles de comprimir. El truco aquí es idear una forma de transformar un documento XML en algo que contenga la misma información completa, pero que estructure el diseño en un estilo fácil de comprimir.

Las utilidades xml2struct.py y struct2xml.py hacen exactamente lo que se pide. Las versiones a continuación tienen un par de limitaciones, pero demuestran los principios involucrados. Algunas limitaciones son que cada documento se limita a 253 etiquetas distintas, y que los atributos y las instrucciones de procesamiento no se tratan. Sin embargo, corregir esos límites no debería cambiar el punto esencial de los resultados. XMill realiza una transformación similar, pero con algunas opciones extra y con menos limitaciones.

El formato general de un documento "struct" es el siguiente:

  • Un listado de etiquetas que aparecen en el documento original XML, separadas por caracteres de línea nueva.
  • Delimitador de una sección: 0x00 (el byte nulo)
  • Una representación compacta de la estructura general del documento, donde cada etiqueta de inicio está representada por un solo byte, y la ocurrencia del contenido se encuentra marcada por un byte de 0x02.
  • Otro delimitador de sección: 0x00 (el byte nulo)
  • Los contenidos de todos los elementos indicados en el archivo del esquema de la estructura, agrupados por tipo de elemento. Cada elemento de contenido individual está delimitado por un byte de 0x02, mientras que el comienzo de elementos de un nuevo tipo está delimitado por un byte de 0x01. (Este último no es estrictamente necesario, pero permite revertir la transformación más fácilmente).

A continuación aparece un código completo Python para realizar y revertir la transformación descrita. Sería simple implementar también esta transformación en otro lenguaje de programación:

Listado 4. xml2struct.py
import sys
import xml.sax
from xml.sax.handler import *

class StructExtractor(ContentHandler):
    """Create a special structure/content form of an XML document"""
    def startDocument(self):
        self.taglist = []
        self.contentdct = {}
        self.state = []             # stack for tag state
        self.newstate = 0           # flag for continuing chars in same elem
        self.struct = []            # compact document structure

    def endDocument(self):
        sys.stdout.write('\n'.join(self.taglist))
                                    # Write out the taglist first
        sys.stdout.write(chr(0))    # section delimiter \0x00
        sys.stdout.write(''.join(self.struct))
                                    # Write out the structure list
        sys.stdout.write(chr(0))    # section delimiter \0x00
        for tag in self.taglist:    # Write all content lists
            sys.stdout.write(chr(2).join(self.contentdct[tag]))
            sys.stdout.write(chr(1)) # delimiter between content types

    def startElement(self, name, attrs):
        if not name in self.taglist:
            self.taglist.append(name)
            self.contentdct[name] = []
            if len(self.taglist) > 253:
                raise ValueError, "More than 253 tags encountered"
        self.state.append(name)     # push current tag
        self.newstate = 1           # chars go to new item
                                    # single char to indicate tag
        self.struct.append(chr(self.taglist.index(name)+3))

    def endElement(self, name):
        self.state.pop()            # pop current tag off stack
        self.newstate = 1           # chars go to new item
        self.struct.append(chr(1))  # \0x01 is endtag in struct

    def characters(self, ch):
        currstate = self.state[-1]
        if self.newstate:           # either add new chars to state item
            self.contentdct[currstate].append(ch)
            self.newstate = 0
            self.struct.append(chr(2))
                                    # \0x02 content placeholder in struct
        else:                       # or append the chars to current item
            self.contentdct[currstate][-1] += ch

if __name__ == '__main__':
    parser = xml.sax.make_parser()
    handler = StructExtractor()
    parser.setContentHandler(handler)
    parser.parse(sys.stdin)

Utilizar SAX en lugar de DOM hace que esta transformación sea bastante eficaz en términos de tiempo, incluso si el tiempo no fue de gran consideración en el desarrollo. Para revertir la transformación, se utilizaría el Listado 5.

Listado 5. struct2xml.py
def struct2xml(s):
    tags, struct, content = s.split(chr(0))
    taglist = tags.split('\n')      # all the tags
    contentlist = []                # list-of-lists of content items
    for block in content.split(chr(1)):
        contents = block.split(chr(2))
        contents.reverse()          # pop off content items from end
        contentlist.append(contents)
    state =  []                     # stack for tag state
    skeleton = []                   # templatized version of XML
    for c in struct:
        i = ord(c)
        if i >= 3:                  # start of element
            i -= 3                  # adjust for struct tag index offset
            tag = taglist[i]        # spell out the tag from taglist
            state.append(tag)       # push current tag
            skeleton.append('<%s>' % tag)
                                    # insert the element start tag
        elif i == 1:                # end of element
            tag = state.pop()       # pop current tag off stack
            skeleton.append('</%s>' % tag)
                                    # insert the element end tag
        elif i == 2:                # insert element content
            tag = state[-1]
            item = contentlist[taglist.index(tag)].pop()
            item = item.replace('&','&')
            skeleton.append(item)   # add bare tag to indicate content
        else:
            raise ValueError, "Unexpected structure tag: ord(%d)" % i

    return ''.join(skeleton)

if __name__ == '__main__':
    import sys
    print struct2xml(sys.stdin.read()),

Comprimir las transformaciones

El verdadero contenido de la transformación discutida viene cuando se trata de comprimir los resultados. Si todo sale de acuerdo con el plan, foo.struct va a ser significativamente más comprimible que foo.xml, aunque los dos contengan información idéntica (lo cual es demostrable porque son simétricamente derivables). En un sentido, xml2struct.py ya es una especie de algoritmo de compresión (produce archivos más pequeños de alguna manera), pero el punto no es utilizarlo directamente, aunque sí como base para compresión futura.

Veamos algunos tamaños, incluidos algunos repetidos de párrafos anteriores. Algunos resultados de XMill se incluyen para comparar; los podrá distinguir porque incluyen el nombre .xmi. (XMill se encuentra disponible en versiones que utilizan algoritmos gzip y bzip2).

Listado 6. Directorio de listados de "XML estructurados"
 228610  hamlet.struct
  57533  hamlet.struct.bz2
  57522  hamlet.xml.bz2
  71060  hamlet.struct.gz
  78581  hamlet.xml.gz
  61823  hamlet.xmi.bz2
  75247  hamlet.xmi.gz

Los resultados en este documento en prosa están de alguna manera entremezclados. "Reestructurar" el documento XML asiste bastante a gzip. Pero el viejo y plano bzip2 funciona 11 bytes mejor generando una estructura comprimible en el archivo XML original que mis intentos. Por supuesto, me reconforta que XMill se comporte de manera similar (pero peor) que mi transformación.

La técnica funciona un poco mejor con archivos Weblog. De hecho, aquí vale la pena.

Listado 7. Directorio de listados 2 de "XML estructurados"
1764816  weblog.struct
  59955  weblog.struct.bz2
  66994  weblog.xml.bz2
  56156  weblog.txt.bz2
  76183  weblog.struct.gz
 115524  weblog.xml.gz
  59409  weblog.xmi.bz2
  74439  weblog.xmi.gz

Como antes, reestructurar el Weblog XML asiste a la compresión gzip de forma significante. Pero como gzip ya no es mi técnica preferida, esto es solo moderadamente interesante. Algo que es de interés genuino es que también mejoré la tasa de compresión del ya fantástico bzip2 a un 11%. Aunque no sea impactante, es suficiente cuando pensamos en el problema de los megabytes. Por lo que vale, XMill funciona un poco mejor que xml2struct.py en este caso. Es también interesante que la compresión de este XML reestructurado esté dentro del 7% de la mejor compresión obtenida del Weblog textual original.


Conclusión

Aunque la utilidad presentada aquí es un intento preliminar, incluso en esta nueva forma, funciona sorprendentemente bien (por lo menos en algunos casos) al eliminar esos últimos bytes de archivos XML comprimidos. Con un poco de refinamiento y experimentación, espero que se pueda obtener un porcentaje más de reducción. Parte de lo que dificulta escribir acerca de esta utilidad es que para empezar, bzip2 hace un muy buen trabajo. Me sorprendí honestamente de lo efectivo que puede ser el algoritmo Burrows-Wheeler cuando comencé la evaluación empírica.

Algunas utilidades comerciales intentan comprimir XML en una forma que utilice el conocimiento de DTD específicos de documentos comprimidos. Es bastante probable que estas técnicas obtengan compresión adicional. Sin embargo, xml2struct.py y XMill tienen la agradable ventaja de ser simples herramientas de líneas de comando que es posible aplicar de manera transparente a los archivos XML. La programación personalizada de cada compresión no es siempre deseable o posible. Pero donde lo es, eliminar incluso más bytes puede ser un objetivo alcanzable.

Recursos

  • Mucha de la inspiración para este artículo viene del trabajo del compresor XMill XML. Es posible encontrar información y una versión descargable en la página XMill. Esta licencia requiere una visita, y la página de descarga desafortunadamente parece tener un guión con errores que no permite descargas de todos los sitios.
  • Las obras completas de Shakespeare en forma XML están disponibles para descargar desde ibiblio.org. El documento hamlet.xml que se utilizó como prueba se obtuvo aquí.
  • Lea la ponencia que introdujo el algoritmo Burrows-Wheeler (el cual se implementa ahora en la utilidad bzip2): M. Burrows y D.J. Wheeler. "A block-sorting lossless data compression algorithm". Technical Report 124, Digital System Research Center, 1994.
  • Muchos sistemas del tipo Unix incluyen bzip2 como parte de su distribución estándar. Para otras plataformas o para nuevas versiones, se puede encontrar bzip2 en Redhat.
  • Escribí lo que creo que puede considerarse una buena introducción general a la compresión de datos.
  • Encuentre otros artículos en la columna de David Mertz XML Matters .

Comentarios

developerWorks: Ingrese

Los campos obligatorios están marcados con un asterisco (*).


¿Necesita un IBM ID?
¿Olvidó su IBM ID?


¿Olvidó su Password?
Cambie su Password

Al hacer clic en Enviar, usted está de acuerdo con los términos y condiciones de developerWorks.

 


La primera vez que inicie sesión en developerWorks, se creará un perfil para usted. La información en su propio perfil (nombre, país/región y nombre de la empresa) se muestra al público y acompañará a cualquier contenido que publique, a menos que opte por la opción de ocultar el nombre de su empresa. Puede actualizar su cuenta de IBM en cualquier momento.

Toda la información enviada es segura.

Elija su nombre para mostrar



La primera vez que inicia sesión en developerWorks se crea un perfil para usted, teniendo que elegir un nombre para mostrar en el mismo. Este nombre acompañará el contenido que usted publique en developerWorks.

Por favor elija un nombre de 3 - 31 caracteres. Su nombre de usuario debe ser único en la comunidad developerWorks y debe ser distinto a su dirección de email por motivos de privacidad.

Los campos obligatorios están marcados con un asterisco (*).

(Por favor elija un nombre de 3 - 31 caracteres.)

Al hacer clic en Enviar, usted está de acuerdo con los términos y condiciones de developerWorks.

 


Toda la información enviada es segura.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=90
Zone=Information mgmt
ArticleID=855555
ArticleTitle=XML Matters: XML y la compresión
publish-date=01212013