В PostgreSQL рекомендую попробовать расширение
pgtrgm. С помощью которого можно реализовать поиск с опечатками в запросе. На небольших запросах мне удалось достичь большей скорости чем при использовании чистого ts_vector. В той же статье описывают схему при использовании триграм в содружестве с полнотекстовым поиском.
Есть ещё nltk.stem.snowball.RussianStemmer. Но он не такой быстрый. И с Python3 он ещё не совсем дружит.
Как-то подслушал что с activepython проблем меньше в винде, пакеты предкомпилированные.