Journal article 88 views
Heuristics for the Run-length Encoded Burrows-Wheeler Transform Alphabet Ordering Problem
Journal of Heuristics
Swansea University Author: Benjamin Mora
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...
Published in: | Journal of Heuristics |
---|---|
Published: |
|
URI: | https://cronfa.swan.ac.uk/Record/cronfa67539 |
first_indexed |
2024-09-03T09:14:08Z |
---|---|
last_indexed |
2025-01-09T20:31:07Z |
id |
cronfa67539 |
recordtype |
SURis |
fullrecord |
<?xml version="1.0"?><rfc1807><datestamp>2025-01-09T17:08:21.3775837</datestamp><bib-version>v2</bib-version><id>67539</id><entry>2024-09-03</entry><title>Heuristics for the Run-length Encoded Burrows-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 Σ containing σ characters, the space of all alphabetorderings 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 informedsearch 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/><journalNumber/><paginationStart/><paginationEnd/><publisher/><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic/><keywords>Alphabet ordering; Burrows-Wheeler Transform; Compression; Local search; Random sampling; Run-Length Encoding</keywords><publishedDay>0</publishedDay><publishedMonth>0</publishedMonth><publishedYear>0</publishedYear><publishedDate>0001-01-01</publishedDate><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>Engineering and Physical Sciences Research Council (EP/S023992/1); European Regional Development Fund (80761-AU-137)</funders><projectreference/><lastEdited>2025-01-09T17:08:21.3775837</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>https://orcid.org/0000-0001-8315-3659</orcid><order>2</order></author><author><firstname>Jacqueline</firstname><surname>Daykin</surname><orcid>https://orcid.org/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>https://orcid.org/0000-0002-2829-4296</orcid><order>5</order></author></authors><documents/><OutputDurs/></rfc1807> |
spelling |
2025-01-09T17:08:21.3775837 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 alphabetorderings 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 informedsearch 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 Alphabet ordering; Burrows-Wheeler Transform; Compression; Local search; Random sampling; Run-Length Encoding 0 0 0 0001-01-01 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University Another institution paid the OA fee Engineering and Physical Sciences Research Council (EP/S023992/1); European Regional Development Fund (80761-AU-137) 2025-01-09T17:08:21.3775837 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 https://orcid.org/0000-0001-8315-3659 2 Jacqueline Daykin https://orcid.org/0000-0003-1123-8703 3 Benjamin Mora 0000-0002-2945-3519 4 Christine Zarges https://orcid.org/0000-0002-2829-4296 5 |
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 Daykin Benjamin Mora Christine Zarges |
format |
Journal article |
container_title |
Journal of Heuristics |
institution |
Swansea University |
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 |
0 |
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 alphabetorderings 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 informedsearch 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 |
0001-01-01T14:43:20Z |
_version_ |
1821416987419475968 |
score |
11.247077 |