Si vous n'êtes lié qu'à MySQL, il n'y a pas de solution simple.
Habituellement, cela est résolu en utilisant une indexation ngram spécialisée pour un filtrage rapide de la recherche de candidats, puis en calculant le levensthein uniquement sur 10 à 50 candidats, ce qui est plus rapide que le calcul de levensthein pour toutes les paires.
Les moteurs de recherche en texte intégral spécialisés comme Solr/Lucene l'ont intégré.
PostgreSQL a le module contrib pg_trgm (http://www.postgresql.org/docs/9.0/static/pgtrgm.html) qui fonctionne comme un charme.
Vous pouvez même simuler cela dans MySQL en utilisant l'indexation de texte intégral, mais vous devez collecter des mots de tous vos documents, les convertir en ngrams, créer des index de texte intégral sur eux et les pirater tous ensemble pour une recherche rapide. Ce qui apporte toutes sortes de problèmes avec la redondance, la synchronisation... ça ne vaut pas votre temps.
