Computing the inverse sort transform in linear time
Ge Nong, Sen Zhang, Wai Hong Chan · ACM Transactions on Algorithms · 2011
The Sort Transform (ST) can significantly speed up the block sorting phase of the Burrows-Wheeler Transform (BWT) by sorting the limited order contexts. However, the best result obtained so far for the inverse ST has a time complexity O ( N log k ) and a space complexity O ( N ), where N and k are the text size and the context order of the transform, respectively. In this article, we present a novel algorithm that can compute the inverse ST for any k -order contexts in an O ( N ) time and space complexity, a linear result independent of k . The main idea behind the design of this linear algorithm is a set of cycle properties of k -order contexts that we explore for this work. These newly discovered cycle properties allow us to quickly compute the Longest Common Prefix (LCP) between any pair of adjacent k -order contexts that may belong to two different cycles, which eventually leads to the proposed linear-time solution.