Levenshtein Distance

**mourbare** · 30/04/2008, 08h28

Salut chers Developpeurs,

Je suis entrain d'ecrire un Levenshtein distance en Ada, En fait le levenshtein normal fonctionne mais pour les lignes de produits je voudrais ne pas tenir compte du coût de suppression. et pour cela j'ai voulu transformer le code c++ suivant en Ada :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
#include <iostream>
#include <string>
using std::cout;
using std::cin;
using std::endl;
 
int Min(const int a, const int b)
{
    int Minimum = a;
        if( Minimum > b )
            Minimum = b;
    return Minimum;
}
unsigned int edit_distance( const std::string& s1, const std::string& s2 )
{
const unsigned int cost_del = 0;
const unsigned int cost_ins = 1;
const unsigned int cost_sub = 1;
 
  unsigned int n1 = s1.length();
  unsigned int n2 = s2.length();
 
  unsigned int* p = new unsigned int[n2+1];
  unsigned int* q = new unsigned int[n2+1];
  unsigned int* r;
 
  p[0] = 0;
  for( unsigned int j = 1; j <= n2; ++j )
    p[j] = p[j-1] + cost_ins;
 
  for( unsigned int i = 1; i <= n1; ++i )
    {
      q[0] = p[0] + cost_del;
      for( unsigned int j = 1; j <= n2; ++j )
        {
          unsigned int d_del = p[j] + cost_del;
          unsigned int d_ins = q[j-1] + cost_ins;
          unsigned int d_sub = p[j-1] + ( s1[i-1] == s2[j-1] ? 0 : cost_sub );
          q[j] = Min( Min( d_del, d_ins ), d_sub );
      }
      r = p;
      p = q;
      q = r;
    }
  unsigned int tmp = p[n2];
  delete[] p;
  delete[] q;
 return tmp;
}
 
int main()
{
    char a[50];
    char b[50];
    cout<<"donner le 1. mot comparaitre\n";
    cin>>a;
    cout<<"donner le 2. mot comparaitre\n";
    cin>>b;
    cout<<"LD : "<< edit_distance(a, b) <<endl;
 
    return 0;
}

Et voila mon essai de tranformation en Ada a la seule difference que le coût de suppression est egal a 0:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
with Ada.Text_IO;
with Ada.Integer_Text_IO;
with Ada.Strings.Unbounded;
use Ada.Strings.Unbounded;
with Ada.Strings.Unbounded.Text_IO;
use Ada.Strings.Unbounded.Text_IO;
 
procedure Test
is
            LeftS : Unbounded_String;
            RigthS : Unbounded_String;
            Result : Natural;
            function LD(Left, Rigth : in String) return Natural is
                cost_del : Natural := 0;
                cost_ins : Natural := 1;
                cost_sub : Natural := 1;
                type my_array is array(0 .. Rigth'Length+1) of Natural;
                p : my_array;
                q : my_array;
                r : my_array;
                tmp : Natural;
                d_del : Natural;
                d_ins : Natural;
                d_sub : Natural;
        begin
                p(0) := 0;
                for j in 1 .. Rigth'Length loop
                  p(j) := p(j-1) + cost_ins;
                end loop;
 
                for i in 1 .. Left'Length loop
                        q(0) := p(0) + cost_del;
                        for j in 1 .. Rigth'Length loop
                                d_del := p(j) + cost_del;
                                d_ins := q(j-1) + cost_ins;
                                if (Left(i-1) = Rigth(j-1)) then --Constraint Error faute ici
                                        d_sub := p(j-1) + 0;
                                else
                                        d_sub := p(j-1) + cost_sub;
                                end if;
                        end loop;
                r := p;
                p := q;
                q := r;
                end loop;
 
                tmp := p(Rigth'Length);
                return tmp;
end LD;
 
function "+"
        (U_S : in Ada.Strings.Unbounded.Unbounded_String)
return String
renames Ada.Strings.Unbounded.To_String;
 
function "+"
    (S : in String)
return Ada.Strings.Unbounded.Unbounded_String
renames Ada.Strings.Unbounded.To_unbounded_String;
 
begin
        Ada.Text_IO.Put("Geben Sie bitte 1 Strind ein: ");
        LeftS := Ada.Strings.Unbounded.Text_IO.Get_Line;
        Ada.Text_IO.Put("Geben Sie bitte 2 Strind ein: ");
        RigthS := Ada.Strings.Unbounded.Text_IO.Get_Line;
        declare
                test : String := +LeftS;
                test2 : String := +RigthS;
        begin
          Result := LD(test, test2);
          Ada.Text_IO.Put_Line ("Levenshtein " & Natural'Image(Result));
        end;
end Test;

Mais seuleument j'ai une faute de constraint Error au niveau de (Left(i-1) = Rigth(j-1)) et quand je commence plutot pas 2 a iterer ca fonctionne mais toujours une distance negative.

Quelqu'un pourrait m'aider et me donner un coup de main. Merci deja pour tout.

**Gaillac** · 30/04/2008, 08h48

Attention:

Code ada :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
String is array(Positive range <>)

Et 

Positive = 1..Integer'Last

Donc l'index des strings commence à 1 et pas à 0.

Voilà pourquoi tu as une erreur.

Du coup je te conseille, pour éviter toutes ambiguïté, d'indexer aussi ton type my_array à partir de 1, et ça devrait déjà aller mieux.

**mourbare** · 30/04/2008, 09h05

Envoyé par Gaillac

Attention:

Code ada :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
String is array(Positive range <>)

Et 

Positive = 1..Integer'Last

Donc l'index des strings commence à 1 et pas à 0.

Voilà pourquoi tu as une erreur.

Du coup je te conseille, pour éviter toutes ambiguïté, d'indexer aussi ton type my_array à partir de 1, et ça devrait déjà aller mieux.

Merci deja, dans ce cas devrais je itere mes for boucle de la facons suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
                for j in 2 .. Rigth'Length (+1) loop
                  p(j) := p(j-1) + cost_ins;
                end loop;

puisqu' a chaque fois j'initialise le premier index a 0 par la valeur 0 et plus 1 de plus aux longueurs de mes strings. Je m'excuse mais Ada c'est pas mon point fort.

**Gaillac** · 30/04/2008, 09h24

En reprenant ton code je ferais plus ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type my_array is array(0 .. Rigth'Length+1) of Natural;
 
p(1) := 0;
for j in 1 .. Rigth'Length loop
  p(j+1) := p(j) + cost_ins;
end loop;
 
for i in 1 .. Left'Length loop
  q(1) := p(1) + cost_del;
  for j in 1 .. Rigth'Length loop
    d_del := p(j+1) + cost_del;
    d_ins := q(j) + cost_ins;
    if (Left(i) = Rigth(j)) then
      d_sub := p(j) + 0;
    else
      d_sub := p(j) + cost_sub;
    end if;
  end loop;
...
end loop;

**mourbare** · 30/04/2008, 10h23

Merci pour les reponses, malheureusement la distance est toujours mal calculée et des distances negatives. En C++ ça fonctionne super bien. Oscar et Oscar LD = 0 mais en Ada -12092929. Je crois je suis idiot en Ada. Et je ne vois pas non plus la différence.

Je m'excuse du derangement.

Invité · 30/04/2008, 10h38

Bonjour,

Je vois qu'il y a des variable non initialisées.

?

**Gaillac** · 30/04/2008, 10h44

Faut pas être défaitiste comme ça.

D'autant plus que ton problème n'a rien à voir avec ADA je pense.

je ne vois nul part dans ton code Ada d'équivalent à:
"q[j] = Min( Min( d_del, d_ins ), d_sub );"
En fait je ne vois nul part d'affectation de q[j] pour tout autre j que 1, et pourtant tu utilise ces q[j] dans d_ins
donc tes q[j] ont des valeurs incontrôlées, que tu affecte à d_ins et que tu retrouve dans ta longueur finale...

**mourbare** · 30/04/2008, 13h36

Merci pour le super coup d'oeil, mais j'ai encore besoin de ce coup d'oeil car j ai des distances qui n ont pas de sens. Oscar = Oscar LD = 1 , maroua et marouad LD = 9, Constraint Error quand le second mot est long, je poste mon code Ada :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
with Ada.Text_IO;
with Ada.Integer_Text_IO;
with Ada.Strings.Unbounded;
use Ada.Strings.Unbounded;
with Ada.Strings.Unbounded.Text_IO;
use Ada.Strings.Unbounded.Text_IO;
 
procedure Test
is
            LeftS : Unbounded_String;
            RigthS : Unbounded_String;
            Result : Natural;
            function LD(Left, Rigth : in String) return Natural is
                cost_del : Natural := 1;
                cost_ins : Natural := 1;
                cost_sub : Natural := 1;
                type my_array is array(0 .. Rigth'Length+1) of Natural;
                p : my_array;
                q : my_array;
                r : my_array;
                tmp : Natural;
                d_del : Natural;
                d_ins : Natural;
                d_sub : Natural;
        begin
                p(1) := 0;
                for j in 1 .. Rigth'Length loop
                   p(J+1) := p(j) + cost_ins;
                end loop;
                for i in 1 .. Left'Length loop
                        q(1) := p(1) + cost_del;
                        for j in 1 .. Rigth'Length loop
                                d_del := p(J+1) + cost_del;
                                d_ins := q(j) + cost_ins;
                                if (Left(i) = Rigth(j)) then
                                        d_sub := p(j) + 0;
                                else
                                        d_sub := p(j) + cost_sub;
                                end if;
                                Q(J) := Natural'Min(Natural'Min (D_Del, D_Ins), D_Sub);
                        end loop;
                r := p;
                p := q;
                q := r;
                end loop;
                tmp := p(Rigth'Length);
                return tmp;
end LD;
 
function "+"
        (U_S : in Ada.Strings.Unbounded.Unbounded_String)
return String
renames Ada.Strings.Unbounded.To_String;
 
function "+"
     (S : in String)
return Ada.Strings.Unbounded.Unbounded_String
renames Ada.Strings.Unbounded.To_unbounded_String;
begin
        Ada.Text_IO.Put("Geben Sie bitte 1 Strind ein: ");
        LeftS := Ada.Strings.Unbounded.Text_IO.Get_Line;
        Ada.Text_IO.Put("Geben Sie bitte 2 Strind ein: ");
        RigthS := Ada.Strings.Unbounded.Text_IO.Get_Line;
        declare
                test : String := +LeftS;
                test2 : String := +RigthS;
        begin
           Result := LD(test, test2);
           Ada.Text_IO.Put_Line ("Levenshtein " & Natural'Image(Result));
        end;
end Test;

Merci

Invité · 30/04/2008, 14h16

Re bonjour,

je vois qu'il y a encore des variable non initialisées.

Invité · 30/04/2008, 14h21

Ceci dit, c'est pas gagné.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
manuel@www:~$ ./test 
Geben Sie bitte 1 Strind ein: Toto
Geben Sie bitte 2 Strind ein: Tataz
Levenshtein  1

**Gaillac** · 30/04/2008, 14h30

Envoyé par mourbare

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 for i in 1 .. Left'Length loop
                        q(1) := p(1) + cost_del;
                        for j in 1 .. Rigth'Length loop
                                d_del := p(J+1) + cost_del;
                                d_ins := q(j) + cost_ins;
                                if (Left(i) = Rigth(j)) then
                                        d_sub := p(j) + 0;
                                else
                                        d_sub := p(j) + cost_sub;
                                end if;
                                Q(J) := Natural'Min(Natural'Min (D_Del, D_Ins), D_Sub);
                        end loop;

Je pense que l'affectation tu la fais sur q(j+1) plutôt.
Ca tombe bien, ça tombe pile dans le range de q.
D'ailleurs à propos de range, maintenant qu'il n'y a plus de "'lenght+1" pour tes boucles for, tu as:
1..Tableau'Length <=> Tableau'First..Tableau'Last <=> tableau'Range
et 'Range c'est le plus Ada des trois formules.

Invité · 30/04/2008, 15h21

Faudrait tester plus en avant peut-être mais ça semble tourner.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
function LD(Left, Rigth : in String) return Natural is
      cost_del : Natural := 1;
      cost_ins : Natural := 1;
      cost_sub : Natural := 1;
      type my_array is array(0 .. Rigth'Length) of Natural;
      p : My_Array := (others => 0);
      q : My_Array := (others => 0);
      r : My_Array := (others => 0);
      tmp : Natural := 0;
      d_del : Natural := 0;
      d_ins : Natural := 0;
      d_sub : Natural := 0;
   begin
      p(0) := 0;
      for j in 1 .. Rigth'Length loop
         p(J) := p(J-1) + cost_ins;
      end loop;
 
      for i in 1 .. Left'Length loop
         q(0) := p(0) + cost_del;
         for j in 1 .. Rigth'Length loop
            d_del := p(J) + cost_del;
            d_ins := q(J-1) + cost_ins;
            if (Left(I) = Rigth(j)) then --Constraint Error faute ici
               d_sub := p(J-1) + 0;
            else
               d_sub := p(J-1) + cost_sub;
            end if;
            Q(J) := Natural'Min(Natural'Min (D_Del, D_Ins), D_Sub);
            d_del := 0;
            d_ins := 0;
            d_sub := 0;
         end loop;
         r := p;
         p := q;
         q := r;
      end loop;
      tmp := p(Rigth'Length);
      return tmp;
   end LD;

**Gaillac** · 30/04/2008, 15h28

ah ouai mais si tu lui suggère l'inverse de mes conseil!!

Tu as gardé le type my_array qui va de 0 à la longueur des string d'entrée (qui elles sont indexé de 1 à longueurs d'elles même).
Je maintiens que c'est "confusant", d'autant plus que les noms des différentes variables (p, q) ne sont pas hyper explicites.

Sans doute trivial pour toi, jovalise, mais mourbare c'est emmêlé (au moins) 2 fois dans ses indices, donc il est important que ça soit le plus clair possible (dans sa tête donc dans son code).

Invité · 30/04/2008, 15h34

Désolé

Le truc, qui m'a fait douter qui m'a fait repartir sur le code initial, c'est quand je me suis aperçu des ++j et ++i dans le code C.

**mourbare** · 30/04/2008, 15h57

Envoyé par Gaillac

ah ouai mais si tu lui suggère l'inverse de mes conseil!!

Tu as gardé le type my_array qui va de 0 à la longueur des string d'entrée (qui elles sont indexé de 1 à longueurs d'elles même).
Je maintiens que c'est "confusant", d'autant plus que les noms des différentes variables (p, q) ne sont pas hyper explicites.

Sans doute trivial pour toi, jovalise, mais mourbare c'est emmêlé (au moins) 2 fois dans ses indices, donc il est important que ça soit le plus clair possible (dans sa tête donc dans son code).

Je vois combien vous vous donnez de la peine pour moi et ne m'empecher de vous remercier mais j'avoue que je ressemble a chien devient un poste de televiseur

et ne comprends plus rien.

**Gaillac** · 30/04/2008, 16h12

Envoyé par mourbare

J je ressemble a chien devient un poste de televiseur

et ne comprends plus rien.

Si un jour ton chien est dans cet état (d'incompréhension devant la télé), mets lui TF1, ça ira mieux.
Sinon, s'il y a vraiment quelque chose que tu ne comprends pas dans nos explications (en omettant le fait que je parle tantôt à toi tantôt à jovalise dans la même phrase), demande (précisément), c'est quand même le but du forum : l'aide à la compréhension.

mais bon, je ne pense pas que tu ai eu des problèmes majeur si ce n'est que tu t'es embrouillé dans tes indices, entre les +1, les -1, les 0..length, les 1..length+1, etc...

**mourbare** · 30/04/2008, 16h29

Envoyé par mourbare

Je vois combien vous vous donnez de la peine pour moi et ne m'empecher de vous remercier mais j'avoue que je ressemble a chien devient un poste de televiseur

et ne comprends plus rien.

J'ai completement change de strategie et je crois cette fois ci c'est la bonne avec ce code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
with Ada.Text_IO;
with Ada.Integer_Text_IO;
with Ada.Strings.Unbounded;
use Ada.Strings.Unbounded;
with Ada.Strings.Unbounded.Text_IO;
use Ada.Strings.Unbounded.Text_IO;
 
procedure newtest
is
            LeftS : Unbounded_String;
            RigthS : Unbounded_String;
            Result : Natural;
            function LD(Left, Rigth : in String) return Natural is
                cost_del : Natural := 0;
                cost_ins : Natural := 1;
                cost_sub : Natural := 1;
                D : array (0 .. Left'Last, 0 .. Rigth'Last) of Natural;
                tmp : Natural;
                d_del : Natural;
                d_ins : Natural;
                d_sub : Natural;
        begin
                for I in D'range(1) loop
                	D(I, 0) := I;
                end loop;
                for J in D'range(2) loop
                	D(0, J) := J;
                end loop;
                for i in Left'Range loop
                     for j in Rigth'Range loop
                     		D_Del := D(I, J-1) + cost_del;
                     		D_Ins := D(I-1, J) + cost_ins;
                                if (Left(i) = Rigth(j)) then
                                        d_sub := D(I-1, J-1) + 0;
                                else
                                        d_sub := D(I-1, J-1) + cost_sub;
                                end if;
                               	D(I,J) := Natural'Min(Natural'Min (D_Del, D_Ins), D_Sub);
                        end loop;
                end loop;
                tmp := D(D'Last(1), D'Last(2));
                return tmp;
end LD;
function "+"
        (U_S : in Ada.Strings.Unbounded.Unbounded_String)
return String
renames Ada.Strings.Unbounded.To_String;
 
function "+"
     (S : in String)
return Ada.Strings.Unbounded.Unbounded_String
renames Ada.Strings.Unbounded.To_unbounded_String;
 
begin
        Ada.Text_IO.Put("Geben Sie bitte erste String ein: ");
        LeftS := Ada.Strings.Unbounded.Text_IO.Get_Line;
        Ada.Text_IO.Put("Geben Sie bitte zweite String ein: ");
        RigthS := Ada.Strings.Unbounded.Text_IO.Get_Line;
        declare
                test : String := +LeftS;
                test2 : String := +RigthS;
        begin
           Result := LD(test, test2);
           Ada.Text_IO.Put_Line ("Levenshtein " & Natural'Image(Result));
        end;
end newtest;

Et une fois de plus un grand merci jovalise et Gaillac

**Gaillac** · 30/04/2008, 16h40

Effectivement, utiliser une matrice correspond plus à la version littérale du calcul de la distance de Levenshtein.

Si je peut me permettre un dernier conseil:

évite les nom de variable du style "D".
C'est un peu cours.
Sans t'imposer de norme, quand tu as un nom de variable (hors indice) inférieur à 3 lettres, demande toi s'il est vraiment explicite.

Ca facilite la lecture du code, sur le moment et surtout plus tard, si tu dois y revenir un jour ou l'autre : des noms clairs, on voit tout de suite de quoi il s'agit.

**mourbare** · 30/04/2008, 16h50

Là je donne 150% raison, je m'en souviendrai de ton conseil pour les prochaines fois et je me lasserai pas de dire encore merci.

**Gaillac** · 30/04/2008, 16h55

Mais merci à toi, ton topic m'a permis de passer la barre des 50 posts et de devenir membre du club !

Levenshtein Distance

Ada

Discussions similaires

Partager

Partager