Search results for "Burrows"

Balancing and clustering of words: a combinatorial analysis of the Burrows & Wheeler Transform

2010

The Burrows-Wheeler Transform (denoted by BWT) is a well founded mathematical transformation on sequences introduced in 1994, widely used in the context of Data Compression and recently studied also from a combinatorial point of view. The transformation does not itself compress the data, but it produces a permutation bwt(w) of an input string w that is easier to compress than the original one, with some fast locally-adaptive algorithms, such as Move-to-Front in combination with Huffman or arithmetic coding. It is well-known that in most real texts, characters with the same or similar contexts tend to be the same. So, the BWT tends to group together characters which occur adjacent to similar…

A New Class of Searchable and Provably Highly Compressible String Transformations

2019

The Burrows-Wheeler Transform is a string transformation that plays a fundamental role for the design of self-indexing compressed data structures. Over the years, researchers have successfully extended this transformation outside the domains of strings. However, efforts to find non-trivial alternatives of the original, now 25 years old, Burrows-Wheeler string transformation have met limited success. In this paper we bring new lymph to this area by introducing a whole new family of transformations that have all the "myriad virtues" of the BWT: they can be computed and inverted in linear time, they produce provably highly compressible strings, and they support linear time pattern search direc…

Relationships between earthworm communities and burrow numbers under different land use systems

2010

International audience; This study addresses the influence of three different land use systems (continuous maize, pasture/maize rotation, permanent pasture) on the relationships between earthworm populations and the number of earthworm burrows quantified in a soil profile. Quantified burrows were limited to those observable by the naked eye (i.e. >2 mm in diameter) and enumerated earthworms were limited to those which could have created the observable burrows (i.e. >0.3 g). The results were combined with data from the literature coming from different geographical regions. This study showed that earthworm abundance decreased with the increasing land management intensity (maize crop vs. pastu…

Repetitiveness Measures based on String Attractors and Burrows-Wheeler Transform: Properties and Applications

2023

Evaluation of GPU-based Seed Generation for Computational Genomics Using Burrows-Wheeler Transform

2012

Unprecedented production of short reads from the new high-throughput sequencers has posed challenges to align short reads to reference genomes with high sensitivity and high speed. Many CPU-based short read aligners have been developed to address this challenge. Among them, one popular approach is the seed-and-extend heuristic. For this heuristic, the first and foremost step is to generate seeds between the input reads and the reference genome, where hash tables are the most frequently used data structure. However, hash tables are memory-consuming, making it not well-suited to memory-stringent many-core architectures, like GPUs, even though they usually have a nearly constant query time com…

Boosting Textual Compression in Optimal Linear Time

2005

We provide a general boosting technique for Textual Data Compression. Qualitatively, it takes a good compression algorithm and turns it into an algorithm with a better compression performance guarantee. It displays the following remarkable properties: (a) it can turn any memoryless compressor into a compression algorithm that uses the “best possible” contexts; (b) it is very simple and optimal in terms of time; and (c) it admits a decompression algorithm again optimal in time. To the best of our knowledge, this is the first boosting technique displaying these properties.Technically, our boosting technique builds upon three main ingredients: the Burrows--Wheeler Transform, the Suffix Tree d…

The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words

2013

The Burrows-Wheeler Transform (BWT) is a tool of fundamental importance in Data Compression and, recently, has found many applications well beyond its original purpose. The main goal of this paper is to highlight the mathematical and combinatorial properties on which the outstanding versatility of the $BWT$ is based, i.e. its reversibility and the clustering effect on the output. Such properties have aroused curiosity and fervent interest in the scientific world both for theoretical aspects and for practical effects. In particular, in this paper we are interested both to survey the theoretical research issues which, by taking their cue from Data Compression, have been developed in the conte…

Lossless and nearly-lossless image compression based on combinatorial transforms

2011

Common image compression standards are usually based on frequency transform such as Discrete Cosine Transform or Wavelets. We present a different approach for loss-less image compression, it is based on combinatorial transform. The main transform is Burrows Wheeler Transform (BWT) which tends to reorder symbols according to their following context. It becomes a promising compression approach based on contextmodelling. BWT was initially applied for text compression software such as BZIP2 ; nevertheless it has been recently applied to the image compression field. Compression scheme based on Burrows Wheeler Transform is usually lossless ; therefore we imple-ment this algorithm in medical imagi…

Probable root structures and associated trace fossils from the Lower Pleistocene calcarenites of favignana island, southern italy: dilemmas of interp…

2012

Two types of large, branched structures from the Lower Pleistocene (Calabrian) high-energy calcarenites of Favignana Island are described: Faviradixus robustus gen. et sp. nov. and Egadiradixus rectibrachiatus gen. et sp. nov. They may be interpreted as root structures of large plants, trees and trees or shrubs, respectively. The former taxon co-occurs with the marine animal trace fossils Ophiomorpha nodosa , Ophiomorpha isp., Thalassinoides isp. and Beaconites isp. The interpretation as root structures although tentative is probable and can be related to short emergence episodes for the formation of E . rectibrachiatus or to longer emergence, responsible for the discontinuity at the base o…