Aqui está um bom ponto de partida para o MySQL:http://www.artfulsoftware.com/infotree /queries.php#552
Uma distância Levenshtein é o número de edições necessárias para transformar uma string em outra. Você provavelmente poderia mexer com a divisão dessa distância pelo comprimento da string para obter uma porcentagem de tipos.
Para PHP, existe uma função Levenshtein embutida:http://www.php .net/manual/en/function.levenshtein.php
