How does a permuterm index works?

Question

I have read Permuterm indexes page on stanford website, however I can't still figure out how we can reach from: *X* to X*.

So where is the $?

---

I can get these ones:

For X, look up X$
For X*, look up $X*
For *X, look up X$*
For X*Y, look up Y$X*

Answer 1

The idea behind Permuterm Index is to rotate wildcard query such that * goes to the end.

Thus, you convert vague query to comparable query. As you wrote, lookup $X* for query X* because * is uncertain but the start part X is deterministic.

When it comes to X, we have two stars. The problem is which star should we rotate .

1. Rotate 1st star

   You regard X* as one part Y, then we get *Y. So we should lookup Y$*, which is X*$*, equivalent to X*.

2. Rotate 2nd star

   You regard *X as one part Y, then we get Y*. So we should lookup *$Y, which is *$*X.This is not easy to handle with.

Based on that, we can know why we lookup X* when we have queries like *X*. The reason is not $ is that $ means the end of the word whereas our query doesn't contain information about the end.