jinh68
Messages postés215Date d'inscriptionmardi 29 juillet 2003StatutMembreDernière intervention 1 septembre 2006
-
18 août 2006 à 11:03
cs_Forman
Messages postés600Date d'inscriptionsamedi 8 juin 2002StatutMembreDernière intervention 6 avril 2010
-
29 août 2008 à 02:12
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
cs_Forman
Messages postés600Date d'inscriptionsamedi 8 juin 2002StatutMembreDernière intervention 6 avril 20101 29 août 2008 à 02:12
Merci.
Ca a l'air bien efficace cette méthode de Jaro-Winkler!
kam_2006
Messages postés49Date d'inscriptionvendredi 13 janvier 2006StatutMembreDernière intervention29 novembre 2010 21 août 2006 à 19:09
Bonsoir
Intéréssant, je veux tester cette source
jinh68
Messages postés215Date d'inscriptionmardi 29 juillet 2003StatutMembreDernière intervention 1 septembre 2006 21 août 2006 à 14:39
Nickel merci ;).
cs_Forman
Messages postés600Date d'inscriptionsamedi 8 juin 2002StatutMembreDernière intervention 6 avril 20101 21 août 2006 à 14:24
Ca y est j'ai mis le source à jour avec ta fonction Florenth. J'ai corrigé un petit bug dans la fonction de comparaison (c'est même curieux que ça ait fonctionné ainsi...).
Jinh: Il y a un PDF dans le zip avec des explications
ahhhh je viens de comprendre le secret du code ! (oui je sais, j'en ai mis du temps ^^)
Je suis tout épaté.
En fait, le recherche se fait par ressemblance "orthographique" par rapport au mot de départ. J'avais pas compris ça comme ça au début.
Ca m'inspire ton idée, je crois que je vais pondre un truc dans pas longtemps .. à suivre donc.
cs_Forman
Messages postés600Date d'inscriptionsamedi 8 juin 2002StatutMembreDernière intervention 6 avril 20101 18 août 2006 à 14:54
@Jinh: Effectivement, ce code est inspiré de la distance de Levenshtein, aussi appelée "string distance" qui est utilisée dans les algo de Diff. Certes celle-ci est très bien adaptée aux comparaisons de sources par exemple, pour déterminer avec le moins d'opérations possible une séquence de suppressions/insertions de caractères (ou lignes) permettant de passer d'une version à une autre d'un texte. Mais je trouvais que ce n'était pas assez pertinent dans le cas d'une comparaison "élastique". En effet, par exemple:
exact -> exactement (distance 5 car 5 insertions)
exact -> le (distance 5 aussi car une suppression et 4 insertions)
J'ai donc défini ma distance à partir d'un relation de récurrence un peu semblable, mais qui fait intervenir le nombre de tronçons ajouttés/supprimés plutôt que le nombre de caractères. Le problème, c'est que ça fait un moment, et je ne me souviens plus exactement comment je la justifiais... Et vu que l'algo est optimisé, ça n'aide pas beaucoup pour retrouver la justification. Je vais regarder chez moi, j'avais noté ça quelque part et peut-être que je l'ai encore.
@Florenth: Ok, je l'ai bien cherché avec mon défi de l'autre jour :-)
Je vais remplacer mon code par le tien
Tiens forman, c'est pas toi qui disait que les allocationas cachées de mémoire ralentissent le code ? lol
Allez, je suis bonne poire, voila ta fonction optimisée (8 ms contre 22~28 pour la tienne avec ton texte) et il y a sûrement moyen de faire encore bien moins :
------------------------------------------------------------------
function FlorenthExtractTextWords(const Text: string): TStringList;
var
PText, WDeb: PChar;
Word: string;
begin
Result := TStringList.Create;
Result.Sorted := True;
Result.Duplicates := dupIgnore;
PText := PChar(Text);
repeat
while (PText^ <> #0) and not IsCharAlpha(PText^) do
Inc(PText);
WDeb := PText;
repeat
Inc(PText);
until not IsCharAlpha(PText^);
if WDeb <> PText then
begin
SetLength(Word, PText - WDeb);
StrLCopy(PChar(Word), WDeb, PText - WDeb);
Result.Add(AnsiLowerCase(Word));
end;
until PText^ = #0;
end;
------------------------------------------------------------------
Tu l'appelles soit avec Memo1.Text où bien Memo1.Lines.Text mais je crois quele premier est un chouilla plus rapide.
jinh68
Messages postés215Date d'inscriptionmardi 29 juillet 2003StatutMembreDernière intervention 1 septembre 2006 18 août 2006 à 12:53
Le plus simple pour commenter à mon avis serait un shéma d'ailleurs.
Intéréssant mais l'unité Smartcompare manque de commentaires si tu vois ce que je veux dire ...
Et as tu déjà essayé avec SoundEx ou son homologue français Phonex (bien que le but recherché n'est pas le même)?
jinh68
Messages postés215Date d'inscriptionmardi 29 juillet 2003StatutMembreDernière intervention 1 septembre 2006 18 août 2006 à 11:03
Tiens tiens, pas mal du tout.
Cela ressemble vaguement à la manière dont opére l'outil diff pour les différences de fichier(algorithme de Myers). Une matrice avec une chaîne sur la longueur, l'autre sur la largeur, et on trace son chemin en fonction des similitudes(un graphe en gros).
29 août 2008 à 02:12
Ca a l'air bien efficace cette méthode de Jaro-Winkler!
21 août 2006 à 19:09
Intéréssant, je veux tester cette source
21 août 2006 à 14:39
21 août 2006 à 14:24
Jinh: Il y a un PDF dans le zip avec des explications
18 août 2006 à 16:50
Je suis tout épaté.
En fait, le recherche se fait par ressemblance "orthographique" par rapport au mot de départ. J'avais pas compris ça comme ça au début.
Ca m'inspire ton idée, je crois que je vais pondre un truc dans pas longtemps .. à suivre donc.
18 août 2006 à 14:54
exact -> exactement (distance 5 car 5 insertions)
exact -> le (distance 5 aussi car une suppression et 4 insertions)
J'ai donc défini ma distance à partir d'un relation de récurrence un peu semblable, mais qui fait intervenir le nombre de tronçons ajouttés/supprimés plutôt que le nombre de caractères. Le problème, c'est que ça fait un moment, et je ne me souviens plus exactement comment je la justifiais... Et vu que l'algo est optimisé, ça n'aide pas beaucoup pour retrouver la justification. Je vais regarder chez moi, j'avais noté ça quelque part et peut-être que je l'ai encore.
@Florenth: Ok, je l'ai bien cherché avec mon défi de l'autre jour :-)
Je vais remplacer mon code par le tien
18 août 2006 à 13:39
Tiens forman, c'est pas toi qui disait que les allocationas cachées de mémoire ralentissent le code ? lol
Allez, je suis bonne poire, voila ta fonction optimisée (8 ms contre 22~28 pour la tienne avec ton texte) et il y a sûrement moyen de faire encore bien moins :
------------------------------------------------------------------
function FlorenthExtractTextWords(const Text: string): TStringList;
var
PText, WDeb: PChar;
Word: string;
begin
Result := TStringList.Create;
Result.Sorted := True;
Result.Duplicates := dupIgnore;
PText := PChar(Text);
repeat
while (PText^ <> #0) and not IsCharAlpha(PText^) do
Inc(PText);
WDeb := PText;
repeat
Inc(PText);
until not IsCharAlpha(PText^);
if WDeb <> PText then
begin
SetLength(Word, PText - WDeb);
StrLCopy(PChar(Word), WDeb, PText - WDeb);
Result.Add(AnsiLowerCase(Word));
end;
until PText^ = #0;
end;
------------------------------------------------------------------
Tu l'appelles soit avec Memo1.Text où bien Memo1.Lines.Text mais je crois quele premier est un chouilla plus rapide.
18 août 2006 à 12:53
18 août 2006 à 12:50
Et as tu déjà essayé avec SoundEx ou son homologue français Phonex (bien que le but recherché n'est pas le même)?
18 août 2006 à 11:03
Cela ressemble vaguement à la manière dont opére l'outil diff pour les différences de fichier(algorithme de Myers). Une matrice avec une chaîne sur la longueur, l'autre sur la largeur, et on trace son chemin en fonction des similitudes(un graphe en gros).