Algorithme de LZ77 en Ada

Version imprimable

04/10/2007, 22h31
miomikio

Algorithme de LZ77 en Ada

Bonjour, je suis de retour avec ma 2eme année ;)

J'ai un projet à faire et j'ai besoin d'explications pour commencer à programmer.
Le projet est : faire un compresseur base sur l'algorithme de LZ77 avec le langage Ada.

Je pense que je sais comment l'algorithme fonctionne, je veux une idée sur la manière de procéder.
05/10/2007, 09h21
PRomu@ld

La première chose est d'essayer d'éviter d'utiliser le langage sms (perso j'ai hésité à deux fois avant de te répondre).

La première chose à faire, c'est papier crayon et essayer d'écrire l'algo sur papier. Ensuite, tu identifies les structures de données dont tu auras besoin.

Si tu es un peu dans le flou concernant l'algorithme, je peux te conseiller ceci http://tuxtina.de/files/seminar/LempelZiv.pdf

Enfin, pour ce qui est de l'implémentation en ADA, elle ne devrait pas poser énormément de problèmes.

Si tu as des soucis, n'hésite pas à indiquer ce qui te pose problème.
11/10/2007, 10h08
miomikio

Par défaut Algorithme de LZ77 en Ada

ciao , apres avoir bien compris comment fonctionne l'algorithme j'ai pense de creer 2 liste , une pour dictionaire et l'autre pour coder :

ouvrire le fichier
liste 1 creer le premier element dans la liste , verifier si elle existe dans la liste dictionaire , dictionaire est vide le code par (0,0)character'succ - mette le premier character dans la liste dictionaire , creer le second element dans la premier liste voir si existe dans la liste dictionaire , si il existe va creer le 3 element dans la premier liste verifie si il existe dans le dictionaire ansi de suite quand le caractere suivant n'exste pas je code mon (l,p)d ansi de suite ..........

je veux savoir si l idee de creer de liste est bien ???
11/10/2007, 11h06
PRomu@ld

Pour débuter, ça n'est pas trop mal, c'est assez simple à mettre en oeuvre mais peut-être pas hyper efficace (notament pour la recherche).

Je pense que dans un premier temps tu peux faire comme ça et si ensuite tu as le temps tu pourras changer de structure (hash par ex).

Premiere version beta ;) de compresseur en ada LZ77

bonjour
j'ai reussi de faire le compresseur mais j'ai toujours besoin de vous , j'ai essaye avec un file text 62bytes il ne compresse pas il alourdi => 378 bytes le nouveaux fichier ;)
aider moi ;)

Code:

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
la prima versione debola di condifica    
----- 
 
 
 
with text_io,short_short_integer_text_io,sequential_io;
use text_io,short_short_integer_text_io;
 
procedure test is 
 
type nodo ;
type lista is access nodo ;
type nodo is record 
ch:character;
next:lista;
end record;
 
type out_data is record
        first,second:short_short_integer;
	caracter:Character;
end record;
 
   package out_Data_io is new Sequential_Io(Element_Type=>out_data);
 
type window is array (integer range <>) of character;
 
buffer:window(1..1273):=(others=>' ');
 
----------------------------------------------------------------------------------------------------------
 
procedure insert(ch:character;p1:in out lista) is 
begin  
if p1=null then 
p1:=new nodo'(ch,null);
else 
insert(ch,p1.next);
end if;
end insert;
---------------------------------------------------------------------------------------------------------
procedure put(p:in out lista) is -- stampa lista 
begin 
while p/=null loop 
put(p.ch);
p:=p.next;
end loop;
end put;
 
 
--------------------------------------------------------------------------------------------------------
function cambia(punt:lista) return out_data is
 
ind:integer; 						
position:short_short_integer:=0;
cercabo:boolean:=false;
tmpunt:lista;
count:short_short_integer:=0;
bestposition:short_short_integer:=0;
dato:out_data;  
dic:window:=buffer;
--  record di (posizione , numeri caracteri )caractere succesivo 
begin 
tmpunt:=punt;
for i in reverse 1..1273 loop 
position:=position+1; 			 -- posizione di caracteri 
if tmpunt.ch=dic(i)then 
ind:=i;        				 -- indeci per la positione di primo caracteri trovato 
count:=count+1;  			 --  countatore di caractere 
cercabo:=true;   			 -- primo caractere ce va verificare il prossimo 
	while cercabo loop 
		if tmpunt.next.ch=dic(ind-1) then 
		count:=count+1;   			 -- counta il seconde caractere trovato 
		ind:=ind+1;
		cercabo:=true;
		tmpunt:=tmpunt.next;
		else 
		dato.first:=position;
		dato.second:=count;
		dato.caracter:=tmpunt.ch;
		position:=0;
		count:=0;
		return dato;    ---  return la (length,Num)C
		end if;
	end loop;
else 
dato.first:=0;
dato.second:=0;
dato.caracter:=tmpunt.ch;
for k in  1..buffer'last-1 loop 
dic(k):=dic(k+1);
end loop;
tmpunt.ch:=buffer(1273);
return dato;   -- return (0,0)C
end if;
end loop;
end cambia;
 
--------------------------------------------------------------------------------------------------------
position:short_integer:=0;
ccount:short_integer:=0;
procedure fichier is 
 
punt:lista;
F_in:file_type;
f_out:out_data_io.file_type;
l1,l2:integer;
max:short_integer:=60;
b,a:string(1..15):=(others=>' ');
ch:character;
position,num_c:integer:=0;
 
begin  
 
put("file name ");
get_line(a,l1);new_line(1);
put("Out file name : " );
get_line(b,l2);
open(File=>F_in,Mode=>in_file,Name=>a(1..l1));
out_data_io.create(f_out,out_data_io.out_file,b(1..l2));
loop 
get(F_in,ch);
insert(ch,punt);
out_data_io.write(f_out,cambia(punt));
exit when end_of_file(F_in);
end loop;
close(File=>f_in);new_line(1);
exception 
when NAME_ERROR=>put("Scrivere il nome a nuovo");new_line(2);
test;
end fichier;
---------------------------------------------------------------------------------------------------
 
 
--------------------------------------------------------------------------------------------------
 
begin 
fichier;
end test;

19/10/2007, 07h43
PRomu@ld

Essaie avec un texte beaucoup plus gros. J'ai des vagues souvenirs de Huffman, quand tu stockes la look-up table dans ton fichier (le dico ici) tu peux avoir une look-up qui est plus grosse que ton fichier à encoder, c'est peut-être le cas ici.

essay echoue

j'ai essaye avec un document word de ¨25 kb il le rend 5 kb mais je pense pas qu'il compresse parceque j ouvre le fichier et je trouve 3 caratere :s ,
avec un fichier .txt il rend plus grand et aussi il prend beaucoup de temps , je pense que j'ai une erreur dans le programme au de hors de ca j'ai 1 warning dans la compilation je sais pas quoi la solution .
aller les pro une d'aide per il bene di tutti ;)

Code:

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
----- la prima versione di condifica  
with text_io,short_short_integer_text_io,sequential_io;
use text_io,short_short_integer_text_io;
 
procedure test is 
 
type nodo ;
type lista is access nodo ;
type nodo is record 
ch:character;
next:lista;
end record;
 
type out_data is record
        first,second:short_short_integer;
	caracter:Character;
end record;
 
   package out_Data_io is new Sequential_Io(Element_Type=>out_data);
 
type window is array (integer range <>) of character;
 
buffer:window(1..6666):=(others=>' ');
----------------------------------------------------------------------------------------------------------
procedure insert(ch:character;p1:in out lista) is 
begin  
if p1=null then 
p1:=new nodo'(ch,null);
else 
insert(ch,p1.next);
end if;
end insert;
--------------------------------------------------------------------------------------------------------
procedure put(p:in out lista) is -- stampa lista 
begin 
while p/=null loop 
put(p.ch);
p:=p.next;
end loop;
end put;
 
 
--------------------------------------------------------------------------------------------------------
function cambia(punt:lista) return out_data is
 
ind:integer; 						
position:short_short_integer:=0;
cercabo:boolean:=false;
tmpunt:lista;
count:short_short_integer:=0;
bestposition:short_short_integer:=0;
dato:out_data;  
dic:window:=buffer;
--  record di (posizione , numeri caracteri )caractere succesivo 
begin 
tmpunt:=punt;
for i in reverse 1..6666 loop 
position:=position+1; 			 -- posizione di caracteri 
if tmpunt.ch=dic(i)then 
ind:=i;        				 -- indeci per la positione di primo caracteri trovato 
count:=count+1;  			 --  countatore di caractere 
cercabo:=true;   			 -- primo caractere ce va verificare il prossimo 
	while cercabo loop 
		if tmpunt.next.ch=dic(ind-1) then 
		count:=count+1;   			 -- counta il seconde caractere trovato 
		ind:=ind+1;
		cercabo:=true;
		tmpunt:=tmpunt.next;
		else 
		dato.first:=position;
		dato.second:=count;
		dato.caracter:=tmpunt.ch;
		position:=0;
		count:=0;
		return dato;    ---  return la (length,Num)C
		end if;
	end loop;
else 
dato.first:=0;
dato.second:=0;
dato.caracter:=tmpunt.ch;
for k in  1..buffer'last-1 loop 
dic(k):=dic(k+1);
end loop;
tmpunt.ch:=buffer(6666);
--tmpunt:=tmpunt.next;
return dato;   -- return (0,0)C
end if;
end loop;
end cambia;
 
--------------------------------------------------------------------------------------------------------
position:short_integer:=0;
ccount:short_integer:=0;
procedure fichier is 
 
punt:lista;
F_in:file_type;
f_out:out_data_io.file_type;
l1,l2:integer;
max:short_integer:=60;
b,a:string(1..15):=(others=>' ');
ch:character;
position,num_c:integer:=0;
 
begin  
 
put("file name ");
get_line(a,l1);new_line(1);
put("Out file name : " );
get_line(b,l2);
open(File=>F_in,Mode=>in_file,Name=>a(1..l1));
out_data_io.create(f_out,out_data_io.out_file,b(1..l2));
loop 
get(F_in,ch);
insert(ch,punt);
out_data_io.write(f_out,cambia(punt));
exit when end_of_file(F_in);
end loop;
close(File=>f_in);new_line(1);
exception 
when NAME_ERROR=>put("Scrivere il nome a nuovo");new_line(2);
test;
end fichier;
---------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------
 
begin 
fichier;
end test;

merci pour vous aides que j'ai pas eu :)
enfin j ai reussi un faire le compresseur sans aide , mais encore la version essay ,
le temps de compression d'un fichier de 500 KO a peu pres 30 min haha :lol:
je voulais mettre mon code et recevoire vos suggestion pour ameliore le programme , parceque il ya bcp de bug

Code:

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
 
 
 
 
with Ada.text_io,Ada.Short_Integer_Text_Io,sequential_io;
use Ada.text_io,Ada.Short_Integer_Text_Io;
 
procedure projet2 is
 
type nodo ;
type lista is access nodo ;
type nodo is record
ch:character;
next:lista;
end record;
 
type out_data is record
        first,second:Short_Integer;
        caracter:Character;
end record;
 
   package out_Data_io is new Sequential_Io(Element_Type=>out_data);
 
 
 
----------------------------------------------------------------------------------------------------------
 
   --procedure insert(p1:in out Lista;Ch:character) is
   procedure Insert (P1: in out Lista;Ch:Character) is
     -- Tmp:Lista:=P1;
   -- Tmpc:Character;
begin
if p1=null then
   p1:=new nodo'(ch,null);
  -- return Tmp;
else
 insert(p1.Next,ch );
end if;
end insert;
---------------------------------------------------------------------------------------------------------
procedure put(p:in out lista) is -- stampa lista
begin
while p/=null loop
put(p.ch);
p:=p.next;
end loop;
end put;
 
 
--------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
--function PProssimo(PP:in Lista) return Lista is
 
--begin
 --  return PP.Next;
 --end PProssimo;
procedure Put(X:Out_Data)is
 
begin
   Put(X.First);Put("  ");
   Put(X.Second);Put("  ");
   Put(X.Caracter);
   New_Line;
   end Put;
---------------------------------------------------------------------------------------------------------
procedure Comprimi is
 
 
  After,Dic:Lista:=null;
   F_In:File_Type;
   F_Out:Out_Data_Io.File_Type;
   Count,Position:Short_Integer:=0;
   Nomein:String(1..16);
   Nomeout:String(1..16);
   L:Integer;
   Car:Character;
   Ok:Boolean:=False;
   Dato:Out_Data;
   esci:boolean:=false;
 
begin
   Put("inserire il nome dell file :");
   Get_Line(Nomein,L);
   Open(File=>F_In,Mode=>In_File,Name=>nomein(1..L));
   New_Line;
   Put("inserire il nome dell file out :");
   Get_Line(Nomeout,L);
   Out_Data_Io.Create(F_Out,Out_Data_Io.Out_File,Nomeout(1..L));
 
   loop
        Get(F_In,Car);
        after:=Dic;
        esci:=false;
      while Dic/=null loop
           if car=after.ch then
           Position:=Position+1;
           Count:=Count+1;
           insert(dic,car);
           insert(after,car);
           After:=after.next;
           Ok:=True;
                 while Ok and after/=null  loop
 
                  Get(F_In,Car);
                 -- After:=after.next;
                        if car=after.ch then
                         -- After:=Prossimo(Punt);
                        Insert(Dic,car);
                        --insert(after,car);
                        insert(after,car);
                        Count:=Count+1;
                        Ok:=True;
                        --Get(F_In,Car);
                        After:=after.next;
 
                       -- if End_Of_File(F_In) and Car/=After.ch then
                         --  Car:=' ';
                         --  end if;
                       elsif Car/=After.Ch and not End_Of_File(F_In) Then
                       --f end_of_file(F_In) then
                      --car:=' ';
                      --end if;
                        --elsif car/=after.ch then
                        Dato.First:=Position;
                        Dato.Second:=Count;
                        Dato.Caracter:=car;
                        Out_Data_Io.Write(F_Out,Dato);
                        Insert(Dic,car);
                        --insert(after,car);
                        Put(Dato);
                        position:=0;
                        --after:=dic;
                        Count:=0;
                        after:=null;
                        -- Get(F_In,Car);
                     --   Insert(Punt,Car);
                        -- Punt:=Prossimo(Punt.Next);
                        Ok:=False;
                        esci:=true;
                       -- elsif Car/=After.Ch and End_Of_File(F_In) then
                          -- Dato.First:=Position;
                          -- Dato.Second:=Count;
                          -- Dato.Caracter:=' ';
                          -- Out_Data_Io.Write(F_Out,Dato);
 
                       exit;
                        end if;
                        -- exit when Punt=null or Dic=null;
                       --exit when  After=null;
                        exit when End_Of_File(F_In);
 
                 end loop;
 
 
        elsif car/=after.ch and after.Next/=null then
            after:=after.next;-- VVVVVVV
            Position:=Position+1;
        elsif car/=after.ch and after.next=null then
           Dato.First:=0;
           Dato.Second:=0;
           Dato.Caracter:=car;
           Insert(dic,car);
          -- insert(after,car);
           Out_Data_Io.Write(F_Out,Dato);
           position:=0;Count:=0;
           esci:=true;
           -- Get(F_In,car);
           ---- Insert(Punt,car);
           --   Punt:=Punt.Next;
          put(Dato);
          --after:=null;
          -- exit ;
        end if ;
        --   exit when Punt=null;
        --  end loop;
        --get(F_in,car);
        exit when esci=true;
        end loop;
if Dic=null then
   Dato.First:=0;
   Dato.Second:=0;
   Dato.Caracter:=car;
   Out_Data_Io.Write(F_Out,Dato);
   Put(Dato);
   Insert(Dic,car);
   --insert(after,car);
 --  Count:=0;
--position:=0;
 
--  Punt:=Punt.Next;
  --  exit when Dic/=null;
--end if;
-- Get(F_In,Car);
-- Insert(Punt,Car);
-- Punt:=Punt.Next;
 
      end if;
 
exit when End_Of_File(F_in);
end loop;
     Close(F_In);
     Out_Data_Io.Close(F_Out);
exception
   when Name_Error=>Put("Scrive il nome a nuovo");New_Line(2);
 
   Projet2;
 
   end Comprimi;
 
   begin
      Comprimi;
      end Projet2;

26/10/2007, 20h28
PRomu@ld

Citation:

merci pour vous aides que j'ai pas eu

On fait ce qu'on peut mais il arrive parfois (souvent) que l'on ait pas le temps nécessaire pour s'occuper des autres.

La première chose que je vois lorsque je regarde ton programme et sa fonction insérer, c'est d'une part qu'elle est récursive (avec une boucle tu fais le même travail sans surcharger la pile d'appel), et ensuite qu'elle s'effectue avec une liste simplement chaînée, ce qui veut dire que l'insertion (en fin) va s'effectuer en O(n), avec une liste doublement chaînée ça va s'effectuer en O(1), le gain n'est pas négligeable ;).

merci pour la suggestion , j'ai change la fonction ricursive et j'ai diviser le temp /3 presque ou plus je me souviens plus , mais c encore lent si je voulais
coucurrencer winrar :) , est ce que tu ma suggerer de faire une liste bidirectionnelle ??
oups j ai commence a oublier comment s'ecrit le francais ...:)

Code:

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
with Ada.text_io,Ada.Short_Integer_Text_Io,float_text_IO,sequential_io,calendar;
--with Ada.Unchecked_Deallocation;
use Ada.text_io,Ada.Short_Integer_Text_Io,float_text_io,calendar;
 
procedure projetit is
 
type nodo ;
type lista is access nodo ;
type nodo is record
ch:character;
next:lista;
end record;
 
type out_data is record
        first,second:Short_Integer;
        caracter:Character;
end record;
 
  package out_Data_io is new Sequential_Io(Element_Type=>out_data);
 
inizio,fine:time;
 
----------------------------------------------------------------------------------------------------------
 
 
 
procedure Insert (P1: in out Lista;Ch:Character) is
tmp:lista;
begin
if p1=null then
   p1:=new nodo'(ch,null);
 
else
tmp:=p1;
while tmp.next/=null loop
tmp:=tmp.next;
end loop;
tmp.next:=new nodo'(ch,null);
end if;
end insert;
---------------------------------------------------------------------------------------------------------
procedure put(p:in out lista) is
begin
while p/=null loop
put(p.ch);
p:=p.next;
end loop;
end put;
 
 
--------------------------------------------------------------------------------------------------------
procedure Stampa_Tempo (Inizio, Fine : in Time ) is
-- Stampa tempo di calcolo –
begin
New_Line(2);
Put("Tempo di calcolo: ");
Put(Float(Seconds(Fine))-Float(Seconds(Inizio)),1,3,0);
Put(" sec");
New_Line;
end Stampa_Tempo;
---------------------------------------------------------------------------------------------------------
 
procedure Put(X:Out_Data)is
 
begin
   Put(X.First);Put("  ");
   Put(X.Second);Put("  ");
   Put(X.Caracter);
   New_Line;
   end Put;
  -- procedure Free is new ada.Unchecked_Deallocation(Nodo,lista);
---------------------------------------------------------------------------------------------------------
procedure Comprimi is
 
 
  After,Dic:Lista:=null;
   F_In:File_Type;
   F_Out:Out_Data_Io.File_Type;
   Count,Position:Short_Integer:=0;
   Nomein:String(1..16);
   Nomeout:String(1..16);
   L:Integer;
   Car:Character;
   Ok:Boolean:=False;
   Dato:Out_Data;
   esci:boolean:=false;
 
begin
   Put("inserire il nome dell file :");
   Get_Line(Nomein,L);
   Open(File=>F_In,Mode=>In_File,Name=>nomein(1..L));
   New_Line;
   Put("inserire il nome dell file out :");
   Get_Line(Nomeout,L);
   Out_Data_Io.Create(F_Out,Out_Data_Io.Out_File,Nomeout(1..L));
   inizio:=clock;-- memorizzazione dell orologio;
   loop
        Get(F_In,Car);
        after:=Dic;
        esci:=false;
      while Dic/=null loop
           if car=after.ch then
           Position:=Position+1;
           Count:=Count+1;
           insert(dic,car);
           insert(after,car);
           After:=after.next;
           Ok:=True;
 
                 while Ok and after/=null  loop
 
                    Get(F_In,Car);
                    Insert(Dic,Car);
                    Insert(After.next,Car);
 
                        if car=after.Ch  then
                           Insert(Dic,car);
                           insert(after,car);
                         Count:=Count+1;
                         After:=after.next;
                         Ok:=True;
                         if End_Of_File(F_In) then
                                Car:=' ';
                                end if;
                       -- elsif Car=After.Next.Ch and End_Of_File(F_In) then
                      --     Insert(Dic,Car);
                      --    Insert(After,Car);
                      --     Count:=Count+1;
                      --     Ok:= False ;
                       --   Dato.First:=Position;
                        -- Dato.Second:=Count;
                          -- Dato.Caracter:='1';
                          -- Out_Data_Io.Write(F_Out,Dato);
                         -- Put(Dato);
                        -- Esci:=True;
 
                        elsif Car/=After.Next.Ch Then
 
                        Dato.First:=Position;
                        Dato.Second:=Count;
                        Dato.Caracter:=car;
                        Out_Data_Io.Write(F_Out,Dato);
                        Insert(Dic,car);
 
                        Put(Dato);
                        position:=0;
 
                        Count:=0;
                        after:=null;
			--free(after);
                        Ok:=False;
                        esci:=true;
 
                        end if;
 
                      exit when End_Of_File(F_In);
 
                 end loop;
 
 
        elsif car/=after.ch and after.Next/=null then
            after:=after.next;
            Position:=Position+1;
        elsif car/=after.ch and after.next=null then
           Dato.First:=0;
           Dato.Second:=0;
           Dato.Caracter:=car;
           Insert(dic,car);
 
           Out_Data_Io.Write(F_Out,Dato);
           position:=0;Count:=0;
           esci:=true;
 
          put(Dato);
 
        end if ;
 
        exit when esci=true;
        end loop;
if Dic=null then
   Dato.First:=0;
   Dato.Second:=0;
   Dato.Caracter:=car;
   Out_Data_Io.Write(F_Out,Dato);
   Put(Dato);
   Insert(Dic,car);
        end if;
 
exit when End_Of_File(F_in);
end loop;
     Close(F_In);
     Out_Data_Io.Close(F_Out);
     fine:=clock;   -- memorizzazione dell orologio;
     stampa_tempo(Inizio,Fine);
exception
   when Name_Error=>Put("Scrive il nome a nuovo");New_Line(2);
 
   projetit;
 
   end Comprimi;
 
   begin
      Comprimi;
      end projetit;

30/10/2007, 08h35
PRomu@ld

Citation:

est ce que tu ma suggerer de faire une liste bidirectionnelle ??

J'appelle ça une liste doublement chaînée. En fait ça pourrait être une bonne idée, comme je te l'ai dit, ça permettrait de faire des insertions en O(1) au lieu de O(n) ce qui sera sûrement plus rapide. ;)
30/10/2007, 22h19
miomikio

salut , il me manque seulement ceux changement de la liste => liste doublement chaine , mais vraiment j'arrive pas a le faire j'ai fait tout le defficile le facile j'arrive pas , tu peux me dire comment je doit faire changer seulement la procedure insert en introduissant un element precedent de la liste ou quoi ??

En fait, il faut que tu changes ton type de liste.

Comme ça, de tête je dirais ça :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
type T_node;
type T_access is access T_node;
 
type T_list is
     record 
          first : T_access := null;
          last : T_access := null;
     end record;
 
type T_node is
     record
          Next : T_access := null ;
          Prev : T_access := null ;
          data : character ;
     end record ;

Ensuite, pour ce qui est de l'insertion, on va faire de l'insertion en fin de liste.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
procedure Insert( L : in out T_List ; c : in Character )
begin
     if L.first = null then
          L.first := new T_node'(null,null,c);
          L.last := L.first ;
     elsif L.first = L.last then
          L.last := new T_node'(L.first,null,c);
          L.first.all.next := L.last ;
     else 
          L.last.all.next := new T_node'(T.last,null,c);
          L.last := L.last.all.next ;
     end if;
end;

Je n'ai absolument pas testé ce code, je viens de l'écrire. Mais grosso modo, le principe est là.

14/11/2007, 12h28
miomikio

salut toujours en cadres de mon projet,je suis dans la phase d'amelioration , j'ai de manque d'information pour une utilisation "professionelle" des strings , je veux savoir les avantage de package Unbounded_String et comment l'utiliser ? ma premiere question . ??
ma seconde : je lit un caracterer d'un file get(F_in,ch); et attache ceux caractere avec le caratere lit presedament pour construire une string , exactement comment la fonction strcat en C ????
25/11/2007, 19h27
miomikio

dans le cadre de mon projet je cherche cette article en francais ???
http://www.cosc.canterbury.ac.nz/res...89/tr_8906.pdf
j 'ai pas encore trouve, un peux d'aide ??
25/11/2007, 19h47
PRomu@ld

Tu n'auras jamais cet article en français, sauf si tu le fais traduire. Il n'est pas fait par des personnes francophones ...

projet deja fini

j'ai fini mon projet

Code:

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
with text_io,ada.Sequential_Io,ada.command_line,ada.integer_text_io;
use text_io,ada.command_line,ada.integer_text_io;
 
 
procedure compressore is
 
 
 
   type Nodo;
   type Punta is access Nodo;
   type Nodo is record
      Carattere: Character;
      succ: Punta;
   end record;
 
   type Dato is record
      Carattere:Character;
      Primo:integer;
         Secondo:integer;
   end record;
 
 
 TYPE Data IS RECORD
      Byte:Character;
   END RECORD;
 
 
   package Dato_io is new ada.Sequential_Io(Element_Type=> Dato);
 
 
 
 
   PACKAGE Data_Io IS NEW Ada.Sequential_IO(Element_Type=>Data);
   USE Data_Io;
 
 
 
 
   PROCEDURE Get(Filein:Data_Io.File_Type;What:IN OUT Character) IS
      Temp:Data;
   BEGIN
      Data_Io.Read(Filein,Temp);
      What:=Temp.Byte;
   END Get;
 
 
 
   PROCEDURE Put(Fileout:Data_Io.File_Type;What:IN OUT Character) IS
      Temp:Data;
   BEGIN
      Temp.Byte:=What;
      Data_Io.Write(Fileout,Temp);
   END Put;
 
 
procedure put(ini:punta) is
pun:punta;
begin
	pun:=ini;
	while (pun/=null) loop
		put(pun.carattere);
		pun:=pun.succ;
	end loop;
end put;
 
 
-- Procedura Inserisci
--	 IN: inizio, fine (puntatori alla coda)
--	     lung: lunghezza attuale della coda
--           max:  grandezza massima della coda
--           chr:  carattere da inserire
 
   procedure Inserisci (Ini,Fine:in out Punta;lung,Max:in out integer;Chr:Character) is
   temp,temp2:punta;
   begin
      if Lung=0 then               -- Se la coda non esiste
         Temp:=new Nodo'(Chr,null);
         Ini:=Temp;
         Fine:=Temp;
         Lung:=1;
 
 
      elsif Lung<Max then          -- Se non ho raggiunto la lunghezza massima
         Temp:=new Nodo'(Chr,null);
         Ini.Succ:=Temp;
         Ini:=Temp;
         lung:=lung+1;
 
 
      else                         -- Se ho raggiunto la lunghezza massima
         Temp:=new Nodo'(Chr,null);
         Ini.Succ:=Temp;
         Ini:=Temp;
         temp2:=Fine.Succ;          -- Si spera che il Garbage Collector lo elimini
	 fine.succ:=null;
	 fine:=temp2;
      end if;
 
   end Inserisci;
 
 
-- Funzione cerca
--  IN: buffer,stringa da cercare;
-- OUT: posizione sul buffer della stringa nella posizione migliore
-- TESTATA OK!
 
function cerca(buf,str:punta) return integer is
buffer,stringa:punta;
i,temp:integer:=0;
ok,complete:boolean:=true;
begin
	if buf = null or str = null then
		return 0;
	else
		complete:=false;
		buffer:=buf;
		i:=1;
		while buffer /= null loop
			stringa:=str;
			if buffer.carattere = stringa.carattere then
				temp:=i;
				complete:=false;
				ok:=true;
				while ok loop
					buffer:=buffer.succ;
					stringa:=stringa.succ;
					i:=i+1;
					if stringa = null or buffer = null then
						ok:=false;
						complete:=true;
					elsif stringa.carattere /= buffer.carattere then
						ok:=false;
					end if;
				end loop;
			else
				buffer:=buffer.succ;
				i:=i+1;
			end if;
			if complete=true then
				if buffer = null then
					return 0;
				else
					return temp;
				end if;
			end if;
		end loop;
		return 0;
	end if;
end cerca;
 
-- procedure Inserisci (Ini,Fine:in out Punta;lung,Max:in out integer;Chr:Character)
 
 
procedure ributta(inicarne,fincarne,inivitt,finvitt:in out punta;lcarn,maxcarn,lvitt:in out integer) is
temp:punta;
begin
	temp:=finvitt;
	while temp/= null loop
		inserisci(inicarne,fincarne,lcarn,maxcarn,temp.carattere);
		temp:=temp.succ;
	end loop;
	finvitt:=null;
	inivitt:=null;
	lvitt:=0;
end ributta;
 
-- function cerca(buf,str:punta) return integer is
-- procedure Inserisci (Ini,Fine:in out Punta;lung,Max:in out integer;Chr:Character)
 
procedure comprimi(fin,fout:string;maxbuf,maxwin:in out integer) is
	filein:data_io.file_type;
	fileout:dato_io.file_type;
	bufferi,bufferf,windowi,windowf:punta;
	lbuf,lwin,best:integer:=0;
	tmp:character;
	data:dato;
 
begin
	data_io.open(File=>filein,mode=>in_file,name=>fin);
	dato_io.create(fileout,dato_io.out_file,fout);
	best:=0;
	while not end_of_file(filein) loop
		get(filein,tmp);
		--new_line;put("Byte numero: ");put(bytes,0);new_line;
		--put("Letto:    ");put(tmp);new_line;
		--put("Finestra: ");put(windowf);new_line;
		if not end_of_file(filein) then inserisci(windowi,windowf,lwin,maxwin,tmp); end if;
		if cerca(bufferf,windowf) = 0 or lwin=256 or end_of_file(filein) then
			data.carattere:=tmp;
			data.primo:=best;
			best:=0;
			if not end_of_file(filein) then
				lwin:=lwin-1;
			end if;
			data.secondo:=lwin;
			dato_io.write(fileout,data);
		--	put("Scrivo ");put(data.carattere);
		--	put(",");put(data.primo,0);put(",");put(data.secondo,0);new_line;
			ributta(bufferi,bufferf,windowi,windowf,lbuf,maxbuf,lwin);
		--	put("Buffer:   ");put(bufferf);new_line;
			windowi:=null;			-- Cancella la finestra
			windowf:=null;
			lwin:=0;
		else
			best:=cerca(bufferf,windowf);
			--put("Buffer:   ");put(bufferf);new_line;
			--put("Migliore posizione: ");put(best);new_line;
		end if;
	end loop;
close(filein);
dato_io.close(fileout);
new_line;
put("Done");
new_line;
end comprimi;
 
 
 
procedure decomprimi(fin,fout:string;maxbuf: in out integer) is
	filein:dato_io.file_type;
	fileout:data_io.file_type;
	bufferi,bufferf,temp,fitempi,fitempf:punta;
	lbuf,best,i,a,ltemp:integer:=0;
	data:dato;
      maxtemp:integer:=256;
begin
	dato_io.open(filein,dato_io.in_file,fin);
	data_io.create(fileout,out_file,fout);
 
 
	while not dato_io.end_of_file(filein) loop
      Dato_Io.Read(Filein,Data);
      --New_Line;
      --Put("Dato letto: primo: ");Put(Data.Primo,0);Put("   secondo:");Put(Data.Secondo,0);Put("   carattere:");Put(Data.Carattere);
      --New_Line;
      --Put("Buffer: ");
      --put(bufferf);
		if data.primo = 0 then			-- Se non richiede di riprecorrere il buffer
                  Put(Fileout,Data.Carattere);
                  Inserisci(Bufferi,Bufferf,Lbuf,Maxbuf,Data.Carattere);
		else
                  Temp:=Bufferf;
         FOR I IN 1..Data.Primo-1 LOOP			-- si posiziona sull'elemento
            temp:=temp.succ;
         END LOOP;
 
         FOR I IN 1..Data.Secondo LOOP			-- scrive il numero di caratteri indicato nel buffer
            Inserisci(Fitempi,Fitempf,Ltemp,maxtemp,Temp.Carattere);
            Temp:=Temp.Succ;
         END LOOP;
 
         Ributta(Bufferi,Bufferf,Fitempi,Fitempf,Lbuf,Maxbuf,Ltemp);
         Inserisci(Bufferi,Bufferf,Lbuf,Maxbuf,Data.Carattere);
 
                  temp:=bufferf;
			for i in 1..data.primo-1 loop   -- posizionamento sull'elemento
				temp:=temp.succ;
			end loop;
 
			for i in 1..data.secondo loop   -- scrittura del pezzo di stringa su file
                  Put(Fileout,Temp.Carattere);
				temp:=temp.succ;
			end loop;
         Put(Fileout,Data.Carattere);    -- scrittura del carattere
 
		end if;
	end loop;
	dato_io.close(filein);
	close(fileout);
	new_line;
	put("Done");
	new_line;
end decomprimi;
 
 
 
 
-- NOTA PER IL PASSAGGIO DI ATTRIBUTI TRAMITE LINEA DI COMANDO
-- Ottenere il numero di argomenti: 	Argument_count (restituisce un natural);
-- Ottenere l'argomento numero x:	argument(x);
-- Ottenere l'intera stringa:		command_name (restituisce una stringa);
 
buffer,stringa:punta:=null;
i,maxbuf,maxstringa:integer:=0;
finput,foutput:string(1..32):=(others=>' ');
lin,lout:integer:=0;
decomp:boolean:=false;
begin
	if Argument_count = 0 then
		new_line;
		put("Error: Parameters are missing!");
		new_line(2);
	else
		i:=1;
		while i <= argument_count loop
			if argument(i)="-in" then
				i:=i+1;
				finput(argument(i)'range):=argument(i)(argument(i)'range);
				lin:=i;
			elsif argument(i)="-out" then
				i:=i+1;
				foutput(argument(i)'range):=argument(i)(argument(i)'range);
				lout:=i;
			elsif argument(i)="-undo" then
            			decomp:=true;
			end if;
			i:=i+1;
		end loop;
 
		if lin=0 or lout=0 then
			new_line;
			if lin=0 then
				put("Error: No input file specified!"); new_line;
			end if;
			if lout=0 then
				put("Error: No output file specified!"); new_line;
			end if;
			new_line(2);
		else
			if maxbuf=0 then
				new_line;
				put("No buffer max length specified! Using Default (65535)");
				maxbuf:=65535;
			end if;
 
			if maxstringa=0 then
				new_line;
				put("No window max length specified! Using Default (256)");
				maxstringa:=256;
			end if;
 
			if decomp=true then
			 decomprimi(finput(argument(lin)'range),foutput(argument(lout)'range),maxbuf);
			else
 
			comprimi(finput(argument(lin)'range),foutput(argument(lout)'range),maxbuf,maxstringa);
 
			end if;
		end if;
	end if;
end compressore;