Open AccessMedium-Space Algorithms for Inverse BWT
Author(s) -
Juha Kärkkäinen,
Simon J. Puglisi
Publication year - 2010
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
DOI - 10.1007/978-3-642-15775-2_39
Subject(s) - bottleneck , algorithm , inverse , inversion (geology) , computer science , space (punctuation) , range (aeronautics) , focus (optics) , artificial intelligence , mathematics , physics , engineering , geometry , geology , optics , aerospace engineering , operating system , paleontology , structural basin , embedded system
The Burrows-Wheeler transform is a powerful tool for data compression and has been the focus of intense research in the last decade. Little attention, however, has been paid to the inverse transform, even though it is a bottleneck in decompression. We introduce three new inversion algorithms with improved performance in a wide range of the space-time spectrum, as confirmed by both theoretical analysis and experimental comparison.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom