No Cover Image

Journal article 315 views 39 downloads

Heuristics for the run-length encoded Burrows–Wheeler transform alphabet ordering problem

Lily Major Orcid Logo, Amanda Clare Orcid Logo, Jacqueline W. Daykin Orcid Logo, Benjamin Mora Orcid Logo, Christine Zarges Orcid Logo

Journal of Heuristics, Volume: 31, Issue: 1, Start page: 11

Swansea University Author: Benjamin Mora Orcid Logo

  • 67539.VOR.pdf

    PDF | Version of Record

    © The Author(s) 2025. This article is licensed under a Creative Commons Attribution 4.0 International License (CC-BY 4.0).

    Download (1.84MB)

Check full text

DOI (Published version): 10.1007/s10732-025-09548-3

Abstract

The Burrows-Wheeler Transform (BWT) is a string transformation technique widely used in areas such as bioinformatics and file compression. Many applications combine a run-length encoding (RLE) with the BWT in a way which preserves the ability to query the compressed data efficiently. However, these...

Full description

Published in: Journal of Heuristics
ISSN: 1381-1231 1572-9397
Published: Springer Nature 2025
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa67539
first_indexed 2024-09-03T09:14:08Z
last_indexed 2025-02-15T05:34:12Z
id cronfa67539
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2025-02-14T14:05:07.2879143</datestamp><bib-version>v2</bib-version><id>67539</id><entry>2024-09-03</entry><title>Heuristics for the run-length encoded Burrows&#x2013;Wheeler transform alphabet ordering problem</title><swanseaauthors><author><sid>557f93dfae240600e5bd4398bf203821</sid><ORCID>0000-0002-2945-3519</ORCID><firstname>Benjamin</firstname><surname>Mora</surname><name>Benjamin Mora</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2024-09-03</date><deptcode>MACS</deptcode><abstract>The Burrows-Wheeler Transform (BWT) is a string transformation technique widely used in areas such as bioinformatics and file compression. Many applications combine a run-length encoding (RLE) with the BWT in a way which preserves the ability to query the compressed data efficiently. However, these methods may not take full advantage of the compressibility of the BWT as they do not modify the alphabet ordering for the sorting step embedded in computing the BWT. Indeed, any such alteration of the alphabet ordering can have a considerable impact on the output of the BWT, in particular on the number of runs. For an alphabet &#x3A3; containing &#x3C3; characters, the space of all alphabet orderings is of size &#x3C3;!. While for small alphabets an exhaustive investigation is possible, finding the optimal ordering for larger alphabets is not feasible. Therefore, there is a need for a more informed search strategy than brute-force sampling the entire space, which motivates a new heuristic approach. In this paper, we explore the non-trivial cases for the problem of minimizing the size of a run-length encoded BWT (RLBWT) via selecting a new ordering for the alphabet. We show that random sampling of the space of alphabet orderings usually gives sub-optimal orderings for compression and that a local search strategy can provide a large improvement in relatively few steps. We also inspect a selection of initial alphabet orderings, including ASCII, letter appearance, and letter frequency. While this alphabet ordering problem is computationally hard we demonstrate gain in compressibility</abstract><type>Journal Article</type><journal>Journal of Heuristics</journal><volume>31</volume><journalNumber>1</journalNumber><paginationStart>11</paginationStart><paginationEnd/><publisher>Springer Nature</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>1381-1231</issnPrint><issnElectronic>1572-9397</issnElectronic><keywords>Alphabet ordering; Burrows-Wheeler Transform; Compression; Local search; Random sampling; Run-Length Encoding</keywords><publishedDay>1</publishedDay><publishedMonth>3</publishedMonth><publishedYear>2025</publishedYear><publishedDate>2025-03-01</publishedDate><doi>10.1007/s10732-025-09548-3</doi><url/><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm>Another institution paid the OA fee</apcterm><funders>This work is supported by the UKRI AIMLAC CDT, http://cdt-aimlac.org, grant no. EP/S023992/1, and was part-funded by the European Regional Development Fund through the Welsh Government, grant 80761-AU-137 (West).</funders><projectreference/><lastEdited>2025-02-14T14:05:07.2879143</lastEdited><Created>2024-09-03T09:07:44.9209564</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Lily</firstname><surname>Major</surname><orcid>0000-0002-5783-8432</orcid><order>1</order></author><author><firstname>Amanda</firstname><surname>Clare</surname><orcid>0000-0001-8315-3659</orcid><order>2</order></author><author><firstname>Jacqueline W.</firstname><surname>Daykin</surname><orcid>0000-0003-1123-8703</orcid><order>3</order></author><author><firstname>Benjamin</firstname><surname>Mora</surname><orcid>0000-0002-2945-3519</orcid><order>4</order></author><author><firstname>Christine</firstname><surname>Zarges</surname><orcid>0000-0002-2829-4296</orcid><order>5</order></author></authors><documents><document><filename>67539__33593__bbea8e9ff386419e824dc46d59635082.pdf</filename><originalFilename>67539.VOR.pdf</originalFilename><uploaded>2025-02-14T14:00:23.0931624</uploaded><type>Output</type><contentLength>1933560</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>&#xA9; The Author(s) 2025. This article is licensed under a Creative Commons Attribution 4.0 International License (CC-BY 4.0).</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>http://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807>
spelling 2025-02-14T14:05:07.2879143 v2 67539 2024-09-03 Heuristics for the run-length encoded Burrows–Wheeler transform alphabet ordering problem 557f93dfae240600e5bd4398bf203821 0000-0002-2945-3519 Benjamin Mora Benjamin Mora true false 2024-09-03 MACS The Burrows-Wheeler Transform (BWT) is a string transformation technique widely used in areas such as bioinformatics and file compression. Many applications combine a run-length encoding (RLE) with the BWT in a way which preserves the ability to query the compressed data efficiently. However, these methods may not take full advantage of the compressibility of the BWT as they do not modify the alphabet ordering for the sorting step embedded in computing the BWT. Indeed, any such alteration of the alphabet ordering can have a considerable impact on the output of the BWT, in particular on the number of runs. For an alphabet Σ containing σ characters, the space of all alphabet orderings is of size σ!. While for small alphabets an exhaustive investigation is possible, finding the optimal ordering for larger alphabets is not feasible. Therefore, there is a need for a more informed search strategy than brute-force sampling the entire space, which motivates a new heuristic approach. In this paper, we explore the non-trivial cases for the problem of minimizing the size of a run-length encoded BWT (RLBWT) via selecting a new ordering for the alphabet. We show that random sampling of the space of alphabet orderings usually gives sub-optimal orderings for compression and that a local search strategy can provide a large improvement in relatively few steps. We also inspect a selection of initial alphabet orderings, including ASCII, letter appearance, and letter frequency. While this alphabet ordering problem is computationally hard we demonstrate gain in compressibility Journal Article Journal of Heuristics 31 1 11 Springer Nature 1381-1231 1572-9397 Alphabet ordering; Burrows-Wheeler Transform; Compression; Local search; Random sampling; Run-Length Encoding 1 3 2025 2025-03-01 10.1007/s10732-025-09548-3 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University Another institution paid the OA fee This work is supported by the UKRI AIMLAC CDT, http://cdt-aimlac.org, grant no. EP/S023992/1, and was part-funded by the European Regional Development Fund through the Welsh Government, grant 80761-AU-137 (West). 2025-02-14T14:05:07.2879143 2024-09-03T09:07:44.9209564 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Lily Major 0000-0002-5783-8432 1 Amanda Clare 0000-0001-8315-3659 2 Jacqueline W. Daykin 0000-0003-1123-8703 3 Benjamin Mora 0000-0002-2945-3519 4 Christine Zarges 0000-0002-2829-4296 5 67539__33593__bbea8e9ff386419e824dc46d59635082.pdf 67539.VOR.pdf 2025-02-14T14:00:23.0931624 Output 1933560 application/pdf Version of Record true © The Author(s) 2025. This article is licensed under a Creative Commons Attribution 4.0 International License (CC-BY 4.0). true eng http://creativecommons.org/licenses/by/4.0/
title Heuristics for the run-length encoded Burrows–Wheeler transform alphabet ordering problem
spellingShingle Heuristics for the run-length encoded Burrows–Wheeler transform alphabet ordering problem
Benjamin Mora
title_short Heuristics for the run-length encoded Burrows–Wheeler transform alphabet ordering problem
title_full Heuristics for the run-length encoded Burrows–Wheeler transform alphabet ordering problem
title_fullStr Heuristics for the run-length encoded Burrows–Wheeler transform alphabet ordering problem
title_full_unstemmed Heuristics for the run-length encoded Burrows–Wheeler transform alphabet ordering problem
title_sort Heuristics for the run-length encoded Burrows–Wheeler transform alphabet ordering problem
author_id_str_mv 557f93dfae240600e5bd4398bf203821
author_id_fullname_str_mv 557f93dfae240600e5bd4398bf203821_***_Benjamin Mora
author Benjamin Mora
author2 Lily Major
Amanda Clare
Jacqueline W. Daykin
Benjamin Mora
Christine Zarges
format Journal article
container_title Journal of Heuristics
container_volume 31
container_issue 1
container_start_page 11
publishDate 2025
institution Swansea University
issn 1381-1231
1572-9397
doi_str_mv 10.1007/s10732-025-09548-3
publisher Springer Nature
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 1
active_str 0
description The Burrows-Wheeler Transform (BWT) is a string transformation technique widely used in areas such as bioinformatics and file compression. Many applications combine a run-length encoding (RLE) with the BWT in a way which preserves the ability to query the compressed data efficiently. However, these methods may not take full advantage of the compressibility of the BWT as they do not modify the alphabet ordering for the sorting step embedded in computing the BWT. Indeed, any such alteration of the alphabet ordering can have a considerable impact on the output of the BWT, in particular on the number of runs. For an alphabet Σ containing σ characters, the space of all alphabet orderings is of size σ!. While for small alphabets an exhaustive investigation is possible, finding the optimal ordering for larger alphabets is not feasible. Therefore, there is a need for a more informed search strategy than brute-force sampling the entire space, which motivates a new heuristic approach. In this paper, we explore the non-trivial cases for the problem of minimizing the size of a run-length encoded BWT (RLBWT) via selecting a new ordering for the alphabet. We show that random sampling of the space of alphabet orderings usually gives sub-optimal orderings for compression and that a local search strategy can provide a large improvement in relatively few steps. We also inspect a selection of initial alphabet orderings, including ASCII, letter appearance, and letter frequency. While this alphabet ordering problem is computationally hard we demonstrate gain in compressibility
published_date 2025-03-01T05:34:12Z
_version_ 1836508358094356480
score 11.380001

Similar Items