Compression Sensitivity of the Burrows–Wheeler Transform and Its Bijective Variant

Hyodam Jeon and Dominik Köppl ()
Additional contact information
Hyodam Jeon: Department of Computer Science and Engineering, University of Yamanashi, Kōfu 400-8511, Japan
Dominik Köppl: Department of Computer Science and Engineering, University of Yamanashi, Kōfu 400-8511, Japan

Mathematics, 2025, vol. 13, issue 7, 1-47

Abstract: The Burrows–Wheeler Transform (BWT) is a widely used reversible data compression method, forming the foundation of various compression algorithms and indexing structures. Prior research has analyzed the sensitivity of compression methods and repetitiveness measures to single-character edits, particularly in binary alphabets. However, the impact of such modifications on the compression efficiency of the bijective variant of BWT (BBWT) remains largely unexplored. This study extends previous work by examining the compression sensitivity of both BWT and BBWT when applied to larger alphabets, including alphabet reordering. We establish theoretical bounds on the increase in compression size due to character modifications in structured sequences such as Fibonacci words. Our devised lower bounds put the sensitivity of BBWT on the same scale as of BWT, with compression size changes exhibiting logarithmic multiplicative growth and square-root additive growth patterns depending on the edit type and the input data. These findings contribute to a deeper understanding of repetitiveness measures.

Keywords: lossless data compression; Burrows–Wheeler Transform (BWT); bijective BWT (BBWT); compression sensitivity; string transformations; Fibonacci words; Lyndon factorization; compression efficiency analysis (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/7/1070/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/7/1070/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:7:p:1070-:d:1620288

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().