Mantengo una base de datos de música en mySQL, ¿cómo devuelvo los resultados almacenados en p. Ej. 'Tiësto' cuando la gente busca 'Tiesto'?

Todos los datos se almacenan en indexación de texto completo, si eso hace alguna diferencia.

Ya estoy empleando una combinación de Levenshtein en PHP y REGEXP en SQL, no para tratar de resolver este problema, sino solo para una mayor capacidad de búsqueda en general.

PHP:

function Levenshtein($word) {

$words = array();
for ($i = 0; $i < strlen($word); $i++) {
    $words[] = substr($word, 0, $i) . '_' . substr($word, $i);
    $words[] = substr($word, 0, $i) . substr($word, $i + 1);
    $words[] = substr($word, 0, $i) . '_' . substr($word, $i + 1);
    }
$words[] = $word . '_';
return $words;
}

$fuzzyartist = Levenshtein($_POST['searchartist']);
$searchimplode = "'".implode("', '", $fuzzyartist)."'";

MySQL:

SELECT *
FROM new_track_database
WHERE artist REGEXP concat_ws('|', $searchimplode);

Para agregar, con frecuencia realizo conversiones de juegos de caracteres y saneamiento de cadenas en PHP, pero siempre han sido de la OTRA forma: estandarizando caracteres no latinos. No puedo entender cómo realizar el proceso oppsite, pero solo en ciertas circunstancias en función de los datos que tengo almacenados.