We could extract a dictionary, likely from wiktionary, and use it to spell correct queries. For example facebok could be transformed into (facebok OR facebook). This is a very common optimization for ZRR that is applied on major search engines like bing and google.
If the results in relevance lab look promising we could port the php spell checking extension (http://php.net/manual/en/ref.pspell.php) to hhvm and run an AB test in production.