Permuterm Indexes

Problem:

If we look up words that start with “Cat” (e.g. search: cat*) then we flip to the index and return everything that starts with that. But this trick only works if we’re searching for a “starts with” type. What about “ends with…” (e.g. *ing.

Then we’d have to search every single word. Too Long…

Solution:

What if, we write the index so the thing we’re searching for is at the start of the index. E.g:

• We take “playing” and turn it to:
  • playing$
  • laying$p
  • aying$pl
  • ying$pla
  • ing$play
  • … etc.
• We then put each one as actual entries in our sorted index, each pointing to the original word “playing”
• Note: we have the $ so we can tell where the word wraps around.
• The problem is our index has no DRASTICALLY increased.