The Prague Stringology Conference 2008
Mikaël Salson, Thierry Lecroq, Martine Léonard and Laurent Mouchard
Dynamic Burrows-Wheeler Transform
| Abstract: |
| The Burrows-Wheeler Transform is a building block for many text compression applications and self-index data structures. It reorders the letters of a text T to obtain a new text bwt(T) which can be better compressed. This forward transform has been intensively studied over the years, but a major problem still remains: bwt(T) has to be entirely recomputed whenever T is modified. In this article, we are considering standard edit operations (insertion, deletion, substitution of a letter or a factor) that are transforming a text T into T'. We are studying the impact of these edit operations on bwt(T) and are presenting an algorithm that converts bwt(T) into bwt(T'). Moreover, we show that we can use this algorithm for converting the suffix array of T into the suffix array of T'. Even if the theoretical worst-case time complexity is O(|T|), the experiments we conducted indicate that it performs really well in practice. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |