Você precisa configurar um índice usando conjuntos ou conjuntos classificados nos quais você grava quando salva qualquer coisa.

Há um bom artigo em http://web.archive.org/web/20121013063245/http://playnice.ly/blog/2010/05/05/a-fast-fuzzy-full-text-index-using-redis isso é bem próximo do que eu uso.