Mineração de dados - O pesadelo dos usuários

Esses dias estava tendo problemas com uma cliente fresca (pra variar): ao mudar o nome do produto, o permalink permanecia o mesmo e ela queria que fosse atualizado. Bem, se é permalink não é pra ser atualizado. Mas como cliente fresco é cliente fresco. Não tem como argumentar. Enfim.
Como solução, elaborei um algoritmo que gerasse o novo permalink e verificasse a similaridade com o antigo. Se fosse suficientemente diferente, a troca seria realizada para o novo.

Bem, aí é que entra a questão. Como calcular similaridade entre strings?

Essa questão é muito comum quando temos que comparar valores não numéricos. Como nomes, palavras, endereços, imagens, vídeos, etc. E é a questão primordial quando estamos lidando com mineração de dados.