Also wenn es um Rechtschreibfehler o.ä. geht, kommst Du sicher um eine Vergleichsauswertung nicht rum.
Ob das mit similar_text() oder levenshtein() noch in einer brauchbaren Performance liegt, kann ich nicht beurteilen. Das müsstest Du mal ausprobieren.
Alternativ kann der Prozess selbst bspw. in C/C++ ausgelagert werden, aber das erfordert etwas mehr Kenntnisse, als für die reine PHP-Variante.