Estoy usando el algoritmo de Levenshtein para encontrar la similitud entre dos cadenas. Esta es una parte muy importante del programa que estoy haciendo, por lo que debe ser eficaz. El problema es que el algoritmo no encuentra los siguientes ejemplos como similares:

AIRE ACONDICIONADO
AIRE

El algoritmo le dará una distancia de 6. Entonces, para esta palabra de 6 letras (mira la palabra con la mayor cantidad de letras), la diferencia es de 100% => la similitud es 0%.

Necesito encontrar una manera de encontrar las similitudes entre dos cuerdas, pero también teniendo en cuenta casos como el que presenté anteriormente.

¿Hay algún algoritmo mejor que pueda usar? ¿O qué me recomiendan?

EDITAR: También he investigado el algoritmo "Damerau-Levenshtein", que agrega transposiciones. El problema es que estas transposiciones son solo para caracteres adyacentes (y no para un número de caracteres).