1

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.

2

t1 tu m'obliges à googler ton biniou inconnu?

http://fr.wikipedia.org/wiki/Distance_de_Levenshtein

ça a l'air balèze à "contourner"!

3

ouais... d'où le =~
Tout ce qui passe pas par le port 80, c'est de la triche.

4

basiquement, tu veux un truc plus rapide a calculer que cette distance?

5

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.

6

tu as penser a utiliser simplement un soundex?

7

Ben déjà dL >= |strlen(x) - strlen(y)|... donc il faut a priori que la longueur apparaisse dans ton résultat de f(x), mais pour le reste hmmm...
Peut-être qu'une comparaison avec une chaîne de référence ferait l'affaire ?
[EDIT] Sinon pencil pour le soundex ^^
avatar
Le scénario de notre univers a été rédigée par un bataillon de singes savants. Tout s'explique enfin.
T'as un problème ? Tu veux un bonbon ?
[CrystalMPQ] C# MPQ Library/Tools - [CrystalBoy] C# GB Emulator - [Monoxide] C# OSX library - M68k Opcodes

8

Non soundex ne me va pas vraiment, au pire des cas je l'utiliserai.

Mais ce truc là m'intrigue depuis un moment déjà.
Peut-être qu'une comparaison avec une chaîne de référence ferait l'affaire ?

comment ça?
Edit; ah ok, pas bête. ça revient à mettre f(x) = dL(x, reference);
g = "+", on a dL(x,reference)+dL(y,reference) >= dL(x,y)
faut trouver une réference intelligente quoi :s
Tout ce qui passe pas par le port 80, c'est de la triche.

9

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).
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

10

Wow, pas mal.

Maintenant j'ai une autre question. Ca devient de la R.O.
Sachant que l'espace contenant les chaines est finie, peut-on trouver l'élément reference, qui minimise l'erreur par rapport à Levenshtein.
Autrement dit, qui minimise par exemple :
Erreur = somme_sur_xy( | g(f(x),f(y)) - dL(x,y) | )
avec
g(a,b) = | a - b |ce)et f(x) = dL(x,referen
(on peut prendre d'autres définitions pour Erreur, un truc plus euclidienne par exemple)
mais qui risque de comporter des ennuis aussi (parce que g(f(a),f(b))=0 n'impliquera pas du tout a=b):

ouais, ça voudrait dire que le truc va proposer des "did you mean" avec des mots qui ont rien à voir, mais c'est le problème avec chaque minorant ça. C'est pour ça que j'ai parlé de majorer dans ./5
En ajoutant d'autres contraintes dans le programme massivement non linéaire précedent... peut être que... sorry
Ca commence à chauffer
Tout ce qui passe pas par le port 80, c'est de la triche.

11

Le problème du majorant de GoldenCrystal, c'est que ça ne va dans la plupart des cas rien te proposer.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

12

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.

13

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.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité