onur Le 25/02/2008 à 17:42 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 "-"
Tout ce qui passe pas par le port 80, c'est de la triche.
basiquement, tu veux un truc plus rapide a calculer que cette distance?
onur Le 25/02/2008 à 18:58 oui, je vais précalculer les f(x), et donc il faut que g soit plus rapide que dL même si ça donne pas la même valeur. Ca serait bien qu'elle la majore par exemple.
Le but c'est de faire un "did you mean ... ?"
Tout ce qui passe pas par le port 80, c'est de la triche.
tu as penser a utiliser simplement un soundex?
C'est un majorant valide, certes, mais pour le "à peu près égal", ça ne va pas du tout.
Sinon, j'ai un minorant à te proposer, qui sera probablement plus utilisable en pratique, mais qui risque de comporter des ennuis aussi (parce que g(f(a),f(b))=0 n'impliquera pas du tout a=b):
|dL(x,reference)-dL(y,reference)|
(la fameuse inégalité triangulaire inversée).
Le problème du majorant de GoldenCrystal, c'est que ça ne va dans la plupart des cas rien te proposer.
onur Le 26/02/2008 à 09:33 Ouais... faut peut-être garder les deux? trouver un autre majorant plus serré?...
En tout cas pour le calcul de reference, tu proposes quoi? Branch & Bound?
Tout ce qui passe pas par le port 80, c'est de la triche.
AMHA, tu devrais d'abord filtrer en minorant avec plusieurs références, et ensuite calculer la vraie distance de Levenshtein sur les entrées qui te restent.