Search results for "Heel"
showing 10 items of 210 documents
On fixed points of the Burrows-Wheeler transform
2017
The Burrows-Wheeler Transform is a well known transformation widely used in Data Compression: important competitive compression software, such as Bzip (cf. [1]) and Szip (cf. [2]) and some indexing software, like the FM-index (cf. [3]), are deeply based on the Burrows Wheeler Transform. The main advantage of using BWT for data compression consists in its feature of "clustering" together equal characters. In this paper we show the existence of fixed points of BWT, i.e., words on which BWT has no effect. We show a characterization of the permutations associated to BWT of fixed points and we give the explicit form of fixed points on a binary ordered alphabet a, b having at most four b's and th…
A bijection between words and multisets of necklaces
2012
Two of the present authors have given in 1993 a bijection Phi between words on a totally ordered alphabet and multisets of primitive necklaces. At the same time and independently, Burrows and Wheeler gave a data compression algorithm which turns out to be a particular case of the inverse of Phi. In the present article, we show that if one replaces in Phi the standard permutation of a word by the co-standard one (reading the word from right to left), then the inverse bijection is computed using the alternate lexicographic order (which is the order of real numbers given by continued fractions) on necklaces, instead of the lexicographic order as for Phi(-1). The image of the new bijection, ins…
The Alternating BWT: an algorithmic perspective
2020
Abstract The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression. It has become a fundamental tool for designing self-indexing data structures, with important applications in several areas in science and engineering. The Alternating Burrows-Wheeler Transform (ABWT) is another transformation recently introduced in Gessel et al. (2012) [21] and studied in the field of Combinatorics on Words. It is analogous to the BWT, except that it uses an alternating lexicographical order instead of the usual one. Building on results in Giancarlo et al. (2018) [23] , where we have shown that BWT and ABWT are part of a larger class of reversible transformations, …
Balancing and clustering of words in the Burrows–Wheeler transform
2011
AbstractCompression algorithms based on Burrows–Wheeler transform (BWT) take advantage of the fact that the word output of BWT shows a local similarity and then turns out to be highly compressible. The aim of the present paper is to study such “clustering effect” by using notions and methods from Combinatorics on Words.The notion of balance of a word plays a central role in our investigation. Empirical observations suggest that balance is actually the combinatorial property of input word that ensure optimal BWT compression. Moreover, it is reasonable to assume that the more balanced the input word is, the more local similarity we have after BWT (and therefore the better the compression is).…
An extension of the Burrows-Wheeler Transform and applications to sequence comparison and data compression
2005
We introduce a generalization of the Burrows-Wheeler Transform (BWT) that can be applied to a multiset of words. The extended transformation, denoted by E, is reversible, but, differently from BWT, it is also surjective. The E transformation allows to give a definition of distance between two sequences, that we apply here to the problem of the whole mitochondrial genome phylogeny. Moreover we give some consideration about compressing a set of words by using the E transformation as preprocessing.
An extension of the Burrows-Wheeler Transform
2007
AbstractWe describe and highlight a generalization of the Burrows–Wheeler Transform (bwt) to a multiset of words. The extended transformation, denoted by ebwt, is reversible. Moreover, it allows to define a bijection between the words over a finite alphabet A and the finite multisets of conjugacy classes of primitive words in A∗. Besides its mathematical interest, the extended transform can be useful for applications in the context of string processing. In the last part of this paper we illustrate one such application, providing a similarity measure between sequences based on ebwt.
Groups whose prime graph on conjugacy class sizes has few complete vertices
2012
Abstract Let G be a finite group, and let Γ ( G ) denote the prime graph built on the set of conjugacy class sizes of G. In this paper, we consider the situation when Γ ( G ) has “few complete vertices”, and our aim is to investigate the influence of this property on the group structure of G. More precisely, assuming that there exists at most one vertex of Γ ( G ) that is adjacent to all the other vertices, we show that G is solvable with Fitting height at most 3 (the bound being the best possible). Moreover, if Γ ( G ) has no complete vertices, then G is a semidirect product of two abelian groups having coprime orders. Finally, we completely characterize the case when Γ ( G ) is a regular …
Burrows-Wheeler transform and Run-Length Enconding
2017
In this paper we study the clustering effect of the Burrows-Wheeler Transform (BWT) from a combinatorial viewpoint. In particular, given a word w we define the BWT-clustering ratio of w as the ratio between the number of clusters produced by BWT and the number of the clusters of w. The number of clusters of a word is measured by its Run-Length Encoding. We show that the BWT-clustering ratio ranges in ]0, 2]. Moreover, given a rational number \(r\,\in \,]0,2]\), it is possible to find infinitely many words having BWT-clustering ratio equal to r. Finally, we show how the words can be classified according to their BWT-clustering ratio. The behavior of such a parameter is studied for very well-…
Remote diagnosis and control of wheelchair electrical drive systems
2005
A new Diagnostic and Protective System (DPS) suitable for wheelchair electrical drive applications has been prepared. Such a system is able to perform both monitoring and long-distance transmission of key signals that are used as pre-fault and fault indicators. The system, moreover, may detect several anomalous working conditions by means of reliable diagnosis procedures and carries out actions to protect the electrical drive and to drive the disabled people in safe conditions. In particular the design, the realization and the performance analysis of the new dedicated diagnostic system, which exploits a programmable logic controller (PLC) as DRS hardware, are described and discussed. The ef…
A frequency compensation algorithm of four-wheel coherence random road
2013
Published version of an article in the journal: Mathematical Problems in Engineering. Also available from the publisher at: http://dx.doi.org/10.1155/2013/986584 Open access The road surface roughness is the main source of kinematic excitation of a moving vehicle, which has an important influence on vehicle performance. In recent decades, random road models have been widely studied, and a four-wheel random road time domain model is usually generated based on the correlation of the four-wheel input, in which a coherence function is used to describe the coherence of the road input between the left and right wheels usually. However, during our research, there are some conditions that show that…