Soit dL la distance de Levenshtein.
Je voudrais trouver deux transformations f et g, telles que pour tout chaine x et yy), g(f(x), f(y) ) =~ dL(x,
avec "=~" dans le sens: "à peu près égale". f peut être de complexité quelconque, mais g, de complexité le plus faible possible.

Par exemple, un truc pourri serait: f(x) = somme des ascii de chaque lettre de x et g = la fonction "-"