Resultados: visualización detallada
Registro 1 de 1 para la búsqueda Autor Kreft Carreño, Sebastián Andrés
Auto
Índice de Texto Basado en LZ77
Kreft Carreño, Sebastián Andrés
Navarro Badino, Gonzalo
Arroyuelo Billiardi, Diego
Barbay, Jérémy
Brisaboa, Nieves
2010
- Datos de edición CyberDocs
- Tipo de Documento Libro
- Materia Compresión de datos (ciencia de la computación); estructuras de datos (ciencia de la computación); estructuras compactas; lz77
-
Descripción
Los dominios como bioinformática, sistemas de versionamiento de código, sistemas de edición colaborativos (wikis), y otros, producen grandes colecciones de texto que son sumamente repetitivas. Esto es, existen pocas diferencias entre los elementos de la colección. Esto permite que la compresibilidad de la colección sea extremadamente alta. Por ejemplo, una colección con versiones de un mismo artículo de Wikipedia puede ser comprimida a ...Los dominios como bioinformática, sistemas de versionamiento de código, sistemas de edición colaborativos (wikis), y otros, producen grandes colecciones de texto que son sumamente repetitivas. Esto es, existen pocas diferencias entre los elementos de la colección. Esto permite que la compresibilidad de la colección sea extremadamente alta. Por ejemplo, una colección con versiones de un mismo artículo de Wikipedia puede ser comprimida a un 0.1% de su espacio original, utilizando el esquema de compresión Lempel - Ziv de 1977 (LZ77).Muchas de estas colecciones repetitivas contienen grandes volúmenes de texto. Es por eso que se requiere un método que permita almacenarlas eficientemente y a la vez operar sobre ellas. Las operaciones más comunes son extraer porciones aleatorias de la colección y encontrar todas las ocurrencias de un patrón dentro de la colección.Un auto - índice es una estructura que almacena un texto en forma comprimida y permite encontrar eficientemente las ocurrencias de un patrón. Adicionalmente los auto - índices permiten extraer cualquier porción de la colección. Uno de los objetivos de estos índices es que puedan ser almacenados en memoria principal. Esta característica es sumamente importante ya que el disco puede llegar a ser un millón de veces más lento que la memoria principal.La mayoría de los auto - índices existentes están basados en un esquema de compresión que predice los símbolos siguientes en base a una cantidad fija de símbolos anteriores. Este esquema, sin embargo, no funciona con textos repetitivos, ya que no es capaz de reconocer todos los elementos repetidos en la colección. Un esquema que sí captura las repeticiones es el LZ77, pero tiene el problema de no poder acceder aleatoriamente el texto.En este trabajo se presenta un algoritmo para extraer substrings de un texto comprimido con un esquema Lempel - Ziv. Adicionalmente se presenta LZ - End, una variante de LZ77, que permite extraer el texto eficientemente usando espacio cercano al de LZ77. LZ77 extrae del orden de 1 millón de caracteres por segundo, mientras que LZ - End extrae más del doble.Nuestro resultado más importante es el desarrollo del primer auto - índice orientado a textos repetitivos basado en LZ77/LZ - End que supera al auto - índice RLCSA, el estado del arte para textos repetitivos. La compresión de nuestros índices llega a ser dos veces mejor en ADN y colecciones de Wikipedia que la del RLCSA. Cabe destacar que nuestro índice basado en LZ77 se construye en 35% del tiempo requerido por el RLCSA, usando el 60% de espacio de construcción. La búsqueda de patrones cortos es más rápida que en el RLCSA, y para patrones largos la relación entre espacio y tiempo es favorable a nuestros índices.Finalmente, se presenta también una colección de textos repetitivos provenientes de diversos dominios. Esta colección está disponible públicamente con el objetivo que se pueda convertir en un referente en experimentación.
- Identificador 12090