Eu mantenho um banco de dados de música no mySQL, como retorno os resultados armazenados em, por exemplo 'Tiësto' quando as pessoas pesquisam 'Tiesto'?

Todos os dados são armazenados sob indexação de texto completo, se isso fizer alguma diferença.

Já estou empregando uma combinação de Levenshtein no PHP e REGEXP no SQL - não na tentativa de resolver esse problema, mas apenas para aumentar a capacidade de pesquisa em geral.

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 adicionar, eu frequentemente realizo conversões de conjuntos de caracteres e limpeza de string em PHP, mas essas sempre foram a OUTRA maneira - padronizando caracteres não latinos. Não consigo entender o processo do oppsite, mas apenas em certas circunstâncias, com base nos dados armazenados.