Figure 6.
Illustration of the difference between the FM-index and r-index. There are 15 runs in the BWT, in which a run is the consecutive occurrence of a single character. The complete BWT matrix consisting of all rotations of the input in lexicographical order. The FM-index consists of SA, BWT array, and the first column of the BWT matrix (F). We note that F can be stored as an integer array consisting of the number of times each character occurs in the input. This compression is illustrated. The r-index stores only a single entry of the BWT and SA for each run in the BWT.
