Вы можете использовать SOUNDEX для поиска похожих по звучанию имен, например:
SELECT * FROM users WHERE SOUNDEX(name) = SOUNDEX(:input)
или подобного
SELECT * FROM users WHERE name SOUNDS_LIKE :input
(что полностью эквивалентно)
Редактировать: если вам нужно использовать алгоритм, отличный от Soundex, как предложил Мартин Хоенберг, вам нужно добавить дополнительный столбец в вашу таблицу, который называется, например, sound_equivalent.(На самом деле это более эффективное решение, поскольку этот столбец может быть проиндексирован).Тогда запрос будет:
SELECT * FROM users WHERE sound_equivalent = :input_sound_equivalent
Содержимое столбца sound_equivalent может быть сгенерировано с помощью алгоритма PHP и вставлено в таблицу с остальными пользовательскими параметрами.