Skip to content
This repository


Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

Educational implementation of BWT and FM-index

branch: master


latest commit cf645dbee9
Egon Elbre authored
Octocat-spinner-32 data restructuring
Octocat-spinner-32 doc restructuring
Octocat-spinner-32 src restructuring
Octocat-spinner-32 .gitignore init
Octocat-spinner-32 README.rst restructuring
Octocat-spinner-32 restructuring


This repository contains educational implementations of Burrows-Wheeler Tranformation and Ferragina-Manzini index.

The implementations are fully commented and the main goal is to provide clear implementations of BWT and FM-index.

Speed is considered secondary although there are different implementations with different algorithmic complexity.

Related Papers

  • Burrows M and Wheeler D (1994), "A block sorting lossless data compression algorithm"
  • Ferragina P and Manzini G (2000), "Opportunistic data structures with applications"
  • Ferragina P and Manzini G (2001), "An experimental study of an opportunistic index"
  • Ferragina P and Manzini G (2005), "Indexing compressed text"
  • Ferragina P and Manzini G (2001), "An experimental study of a compressed index"
Something went wrong with that request. Please try again.