Recursive Prefix-Free Parsing for Building Big BWTs.

Area of Science:

• Computer Science
• Data Compression
• String Algorithms

Background:

• Prefix-free parsing is crucial for data structures like the Burrows-Wheeler Transform (BWT), suffix arrays, and compressed suffix trees.
• Existing methods face challenges with parse size, which becomes burdensome for large, repetitive inputs.

Purpose of the Study:

• To introduce and implement a novel algorithm, recursive prefix-free parsing, to address the scalability of parse size.
• To improve memory efficiency in constructing the run-length encoded BWT.

Main Methods:

• Developed a recursive approach to prefix-free parsing, applying it to the parse generated by an initial parsing step.
• Addressed the complexities of building the BWT from the parse-of-the-parse and associated dictionaries.

Main Results:

• Recursive prefix-free parsing effectively reduces memory requirements for building the run-length encoded BWT.
• Experimental results validate the significant memory savings achieved by the new algorithm.

Conclusions:

• Recursive prefix-free parsing offers a scalable solution for handling large, repetitive datasets in string algorithm applications.
• The implemented open-source solution provides a practical tool for memory-efficient BWT construction.