Let “$” mark the end of a term such that “hello” –> “hello$”. The permuterm entry for term “hello” are:
hello$, ello$h, llo$he, lo$hel, o$hell, $hello
In a wildcard query “m*n”, rotate the query so that the “*”appears at the end of the string. So “m*n” changes to “n$m*”. The look up this string in the permuterm index. Seeking “n$m*” leads the rotations of the terms “man” and “moron”.
When query X, look up on X$, query X*, look up on $X*
*X –> X$*, *X* – > X*, X*Y –> Y$X*
That means: rotate wildcard query to the right and use B-tree to lookup.
permuterm index need a lot of space.
In a k-gram index, the dictionary contains all k-grams that occur in any term in the vocabulary. For example, the 3-gram “etr”would point to terms sucha as: retrieval, petrify, metric, beetroot.
Use “$”as a special word boundary symbol. The 2-grams in text “the month” are: $t, th, he e$, $m, mo, on, nt, th, h$”
In wildcard query “mon*”, run as: $m AND mo AND on