Fast Computation of the Generalized BWT on Limited-Order Contexts: Algorithms and Applications

    Project: Other project

    Project Details


    As an important variant of the Burrows-Wheeler transform (BWT), the Schindler transform (ST)—which generalizes the BWT on limited-order contexts—can run much faster by sorting shorter contexts; thus it can be employed to build fast and efficient data compression solutions. However, the current inverse ST algorithms require a complete k-order contexts restoration and the use of hash tables with a time/space complexity O(kN) for a text of N characters, which are far less efficient than the inverse BWT. Consequently, time and space efficiently inverting ST remains a difficult problem and constitutes an application bottleneck for the ST.
    Recently, we have obtained some preliminary results for reducing the space complexity for the inverse ST from O(kN) to O(N), by mathematically formalizing the ST and its inversion with matrices operations that have not been tried by others. In this project, we will study the problem of inverting ST time and space efficiently. The outcome of this project includes a set of novel efficient algorithms for the inverse ST, a routines library in C++ for third-party’s applications, and a compression software for application demonstration of the project’s achievements. The results of this project will break the bottleneck and solve the problem of efficiently inverting ST.
    Effective start/end date01/11/0730/10/09