FM-Index Backward Search

Worked Example

Let's perform a backward search for the pattern "ana" in the text "Banana$". First, we construct the BWT, Suffix Array (SA), and the C-array (which stores the number of characters strictly smaller than a given character). For "Banana$", the BWT is annb$aa, and the C-array values are: $: 0, a: 1, b: 4, n: 5.

We search backward, starting with the last character of the pattern, "a", and initial interval [0, 7).

Pattern: "ana"
Initial interval: [0, 7)

Step 1: Match 'a'
  C('a') = 1
  rank('a', 0) = 0
  rank('a', 7) = 3
  Left = 1 + 0 = 1
  Right = 1 + 3 = 4
  Interval: [1, 4)

Step 2: Match 'n'
  C('n') = 5
  rank('n', 1) = 0
  rank('n', 4) = 2
  Left = 5 + 0 = 5
  Right = 5 + 2 = 7
  Interval: [5, 7)

Step 3: Match 'a'
  C('a') = 1
  rank('a', 5) = 1
  rank('a', 7) = 3
  Left = 1 + 1 = 2
  Right = 1 + 3 = 4
  Final Interval: [2, 4)

The final interval is [2, 4). Looking up the Suffix Array values at indices 2 and 3, we get the original text positions 3 and 1. This means "ana" occurs 2 times, at indices 1 and 3 of "Banana".

Experiment

You can interact with the FM-Index using the provided controls. Try the following steps to observe the backward search process:

1. Open the FM-Index Backward Search module.
2. Set Text to "Mississippi".
3. Set Pattern to "issi".
4. Set Rank character to "s" and Rank prefix to "6".
5. Observe the search trace and the highlighted interval on the BWT. The actual search interval updates backward character by character.
6. Notice how setting Pattern to "Empty" selects the entire text interval, while setting it to "zzz" results in an empty interval [0, 0) since the characters do not exist.

Assumptions and Limitations

The provided visualization assumes a small, finite domain of strings to fit comfortably within the UI. In a real-world scenario (like genomics), the text length can be in the billions of characters. To handle such large texts, the FM-Index employs compression techniques, such as only sampling the suffix array at regular intervals and using wavelet trees or other compressed data structures for the rank queries. This module shows the uncompressed logic to clarify the core algorithmic behavior. Additionally, the pattern length must be finite, and if a character in the pattern does not appear in the text, the search interval immediately collapses to the empty interval [0, 0).

References

The following reference provides the foundational theory and formal description of the FM-Index data structure:

• Paolo Ferragina and Giovanni Manzini. "Opportunistic Data Structures with Applications". Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000). See their FM-index implementation and documentation at https://pages.di.unipi.it/ferragina/Libraries/fmindexV2/index.html.