FM-index and pattern search with wildcards

Question

in one of my algorithm courses i'm studying the FM-Index.

In one of the exercise I'm trying to do I was asked to give a procedure to search patterns of the form w* (where * indicates any character) using backwards search (see here).

How could this be possible? It seems to me that the algorithm already returns all the possible patterns of the form w* (because the starting range in which the search start is $0 - |T|$).And what kind of modification requires the procedure to search pattern in which for example one char is *, for example www*ww?

Answer 1

You are correct that w* is already addressed by fixed-substring search. I'll give some pointers on general regex search; most text indexes can be searched for variable patterns with a bit of extra work.

First, backwards search is a consequence of the fact that the FM index and most full text indexes use suffix sorting with the most significant digit on the left, because virtually no one thinks in terms of prefix sorting with the MSD on the right. If the latter were used the FM index would use forward search; it's simply a product of the choices made when setting up the data structure. Another fact to note is that regex's can be reversed, so any pattern in the forward direction can be reversed and applied using backward search.

Search with wildcards is not hard to do, but it requires multiple branches through the wildcard matches, which must be searched through some sort of tree-traversal strategy, with backtracking and so on. This paper describes pattern-matching on Patricia trees for instance.

It's not that different from searching sequential text; in the FM index case you can always find the characters immediately preceding the matches found so far and determine if they match the pattern correctly.