Hace poco escribí un artículo sobre distancia Levenstein en php donde se explicaba lo que era y para que se usaba así que solo voy a explicarlo como se usa en mysql. Bastaría con usar la sentencia SELECT levenshtein('abcde', 'abced') donde retornaría 2. Es bastante sencillo.