TypeScript implementation of Burrows–Wheeler transform. It is more effective than naive implementation and requires O(n) additional memory for direct and inverse transformation.

bwt.ts

const enum Order {
  LT = -1,
  EQ = 0,
  GT = 1
}

interface BWTransformed {
  data: string,
  start: number,
  eof: number
}

function bwt(input: string): BWTransformed {
  const len = input.length + 2
  const rotations = new Int32Array(len)
  for (let i = 0; i < len; i++) {
    rotations[i] = i
  }
  const EOF = len - 2
  const START = -1
  rotations.sort((a, b) => {
    for (let i = 0; i < len; i++) {
      const x = a + i > len - 1 ? i - (len - a) - 1 : i + a - 1
      const y = b + i > len - 1 ? i - (len - b) - 1 : i + b - 1
      if (x === EOF) {
        return Order.GT
      }
      else if (x === START) {
        return y === EOF ? Order.LT : Order.GT
      }
      else if (y === EOF || y === START) {
        return Order.LT
      }
      else if (input[x] < input[y]) {
        return Order.LT
      }
      else if (input[x] > input[y]) {
        return Order.GT
      }
    }
    return Order.EQ
  })
  let start = 0
  let eof = 0
  const data = new Array(input.length)
  let added = 0
  const lastIdx = len - 1
  for (let i = 0; i < len; i++) {
    const shift = rotations[i]
    const real = shift + lastIdx > len - 1 ? lastIdx - (len - shift) - 1 : lastIdx + shift - 1
    if (real === EOF) {
      eof = i
    }
    else if (real === START) {
      start = i
    }
    else {
      data[added++] = input[real]
    }
  }
  return { start, data: data.join(''), eof }
}

function ibwt({start, data, eof}: BWTransformed): string {
  const len = data.length + 2
  const sorted = new Int32Array(len)
  const permutations = new Int32Array(len)
  for (let i = 0; i < len; i++) {
    sorted[i] = i
  }
  sorted.sort((a, b) => {
    if (a === eof) {
      return Order.GT
    }
    else if (a === start) {
      return b === eof ? Order.LT : Order.GT
    }
    else if (b === start || b === eof) {
      return Order.LT
    }
    const x = a + (a >= start ? -1 + (a >= eof ? -1 : 0) : 0)
    const y = b + (b >= start ? -1 + (b >= eof ? -1 : 0) : 0)
    return data[x] < data[y]
      ? Order.LT
      : (
        data[x] > data[y]
        ? Order.GT
        : (a < b ? Order.LT : Order.GT)
      )
  })
  for (let i = 0; i < len; i++) {
    permutations[sorted[i]] = i
  }
  let current = len - 1
  const result = new Array(len - 2)
  let i = len - 2
  while (i--) {
    const idx = current + (current < start ? 0 : (-1 + (current < eof ? 0 : -1)))
    result[i] = data[idx]
    current = permutations[current]
  }
  return result.join('')
}

const WORD = `banana`

console.log(ibwt(bwt(WORD)) === WORD)