Discussion :

[JeromeMATHIAS]

Bonjour,

j'ai essayé d'implémenter via la proc fcmp une fonction d'extraction de sous séquence commune à deux chaines de caractère.

J'ai suivi le schéma de programmation suivant présent sur cette page web

http://binetacm.wikidot.com/algo:commsubseq

Le programme java en exemple étant celui-là

import java.util.Scanner;

public class LCS {

static String traceback(int[][] C,int[] x,int[] y,int i, int j){
if (i==0||j==0) return "";
else {
if (x[i-1]==y[j-1])
return traceback(C,x,y,i-1,j-1)+" "+x[i-1];
else if (C[i-1][j]>C[i][j-1])
return traceback(C,x,y,i-1,j);
else return traceback(C,x,y,i,j-1);
}

}

public static void main(String[] args){
//read
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int m=in.nextInt();
int[] x = new int[n];
int[] y=new int[m];
for (int i=0;i<n;i++)
x[i]=in.nextInt();
for (int j=0;j<m;j++)
y[j]=in.nextInt();
//init
int[][] C=new int[n+1][m+1];
for (int i=0;i<n+1;i++)
C[i][0]=0;
for (int j=0;j<m+1;j++)
C[0][j]=0;
//update
for (int i=1;i<n+1;i++)
for (int j=1;j<m+1;j++){
if (x[i-1]==y[j-1])
C[i][j]=C[i-1][j-1]+1;
else{
if (C[i-1][j]>C[i][j-1])
C[i][j]=C[i-1][j];
else
C[i][j]=C[i][j-1];
}
}
//trace back & print
String z=traceback(C,x,y,n,m).substring(1);
System.out.println(z);

}

}

mon programme est celui là

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
 
 
proc fcmp outlib=sasuser.MyFuncs.ChrFuncs;
FUNCTION f_LCS(string1$,string2$) $250;
n=length(string1);
m=length(string2);
array x[255] $1;
array y[255] $1;
array c[255,255];
do i=1 to n;x[i]=substr(string1,i,1);/*put i '*' x[i]*/;end;
do j=1 to m;y[j]=substr(string2,j,1);end;
do i=1 to n+1;c[i,1]=0;end;
do j=1 to m+1;c[1,j]=0;end;
 
do i=2 to n+1;
do j=2 to m+1;
if x[i-1]=y[j-1] then c[i,j]=c[i-1,j-1]+1;
else c[i,j]=max(c[i-1,j],c[i,j-1]);
end;
end;
return(traceback(n+1,m+1,x,y,C));
endsub;
 
 
FUNCTION traceback(i,j,x[*]$,y[*]$,C[*,*]) varargs $250;
/*put i '*' j;*/
if i=1 or j=1 then return("");
else if x[i-1]=y[j-1] then return(compress(traceback(i-1,j-1,x,y,C)!!x[i-1]));
else if C[i-1,j]>C[i,j-1] then return(traceback(i-1,j,x,y,C));
else return(traceback(i,j-1,x,y,C));
endsub;
run;
 
 
options cmplib=sasuser.MyFuncs;
 
data k;
length c $255.;
v1='ABCD';V2='BDEF';c=f_LCS(v1,v2);output;
run;

J'ai essayé a faire manuellement l'exécution du programme sur un tableau j'arrive bien au résultat voulu à savoir "ACD"

mais lorsque je lance le programme SAS il semble ne jamais finir...

J'ai beau regarder mon code je ne vois pas où est l'erreur...?

[JeromeMATHIAS]

Après un nouveau test, il semble qu'il y ai plusieurs choses qui posent problème.

J'avais dimensionné mes tableaux de façon "large" avec des

array x[255] $1;
array y[255] $1;
array c[255,255] $1;

Ce qui doit faire trop pour sas en paramètre pour une fonction et qui doit le faire bugger

en remplaçant par


array x[10] $1;
array y[10] $1;
array c[10,10] $1;

le programme s'exécute AVEC ERREUR mais il se termine, effectivement 120 paramètres c'est moins que 60 000 et quelques...
Cependant j'ai vais avoir des chaines de caractère de longueur 30 à traiter...
J'ai des erreurs du type
"ERROR : Un index ARRAY est hors limites dans l'instruction numéro 5,ligne 11, colonne 1 etc..."



Et enfin second problème , le résultat retourné avec le changement de la taille des tableaux à 10 et 10*10 n'est pas le bon car j'ai en retour une chaine vide...



EDIT


Je viens de régler un certain nombre de problèmes avec ce nouveau code

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
 
 
proc fcmp outlib=sasuser.MyFuncs.ChrFuncs;
FUNCTION f_LCS(string1$,string2$) $250;
n=length(string1);
m=length(string2);
array x[30] $1;
array y[30] $1;
array c[30,30];
do i=1 to n;x[i]=substr(string1,i,1);;end;
do j=1 to m;y[j]=substr(string2,j,1);end;
do i=1 to n+1;c[i,1]=0;end;
do j=1 to m+1;c[1,j]=0;end;
 
do i=2 to n+1;
do j=2 to m+1;
if x[i-1]=y[j-1] then c[i,j]=c[i-1,j-1]+1;
else c[i,j]=max(c[i-1,j],c[i,j-1]);
end;
end;
return(traceback(n+1,m+1,x,y,C));
endsub;
 
 
FUNCTION traceback(i,j,x[30]$,y[30]$,C[30,30]) varargs $250;
length chaine $30;
if i=1 or j=1 then return("");
else if x[i-1]=y[j-1] then do; chaine=compress(strip(traceback(i-1,j-1,x,y,C))!!strip(x[i-1]));return(chaine);end;
else if C[i-1,j]>C[i,j-1] then do;chaine=traceback(i-1,j,x,y,C);return(chaine);end;
else do;chaine=traceback(i,j-1,x,y,C);return(chaine);end;
endsub;
run;
 
 
 
options cmplib=sasuser.MyFuncs;
 
 
data k;
length c $255.;
v1='RUE_DU_GENERAL_DE_GAULLE';v2='RUE_DU_GENERAL_DE_GAULLE';output;
v1='ABCDEFGH';v2='ABCGHTJY';output;
v1='ABCDEFG';v2='ABCDEFG';output;
v1='ABCDEFGHIJKLM';v2='ABCDEFGHIJKLM';output;
run;
 
 
data k1; set k;
c=f_LCS(v1,v2);run;
 
proc print data=k1;run;

et le résultat

Code :

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

1
2
3
4
5
6
7
 
               Obs    c            v1                          v2
 
                1     RUE_DU_GE    RUE_DU_GENERAL_DE_GAULLE    RUE_DU_GENERAL_DE_GAULLE
                2     GH           ABCDEFGH                    ABCGHTJY
                3     ABCDEFG      ABCDEFG                     ABCDEFG
                4     ABCDEFGHM    ABCDEFGHIJKLM               ABCDEFGHIJKLM

Mais comme on le voit au résultat il n'y a pas encore le résultat souhaité.

La ligne 1 est coupée à 8+1 caractères
La ligne 2 on devrait avoir ABCGH comme résultat
La ligne 3 c'est OK
La ligne 4 est elle aussi coupée à 8+1 caractères...

[JeromeMATHIAS]

Personne n'a une petite idée ?

Mon problème n'est toujours pas solutionné à ce jour