Burrows–Wheeler Transform

Explanation

- The **Burrows-Wheeler Transform (BWT)** is a string transformation algorithm used in data compression. It reorders the characters of a string into runs of similar characters, making it easier to compress.

-

• Steps

  • Generate all cyclic rotations of the string.
  • Sort these rotations lexicographically.
  • The last column of the sorted rotations is the BWT of the string.

• Time Complexity

  • Time complexity: O(n log n) for sorting the rotations.