Discussion :

[Mockingbird]

Salut à tous !
Dans le cadre d'un projet, on doit réaliser un programme permettant de compresser un fichier.
Le travail demandé était d'écrire les fonctions burrows_wheeler, movetofront et huffman qu'on implantait dans un fichier main fourni
Voici l'archive contenant les fichiers nécessaires à la compilation du binaire huffman.
Pour compiler, je fais make huffman et ca génère un exécutable huffman.
Ensuite la commande :

Code :

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

huffman -e fichier

génère fichier.encoded compressé
et :

Code :

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

huffman -d fichier.encoded

génère fichier.decoded décompressé.
Mon problème vient en fait du décodage. En fait celui-ci plante parfois (sur des textes longs) et retourne un résultat faux sur des textes avec un seul mot

Par

Code :

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

1
2
3
4
5
6
 
./huffman -e fichier 
Burrows-Wheeler transformation .....     0.266933917999sec
Move to Front encoding .............     14.2474870682sec
Huffman encoding ...................     0.0310549736023sec
Compression rate achieved ..........     139%

(L'encodage du movetofront n'est pas optimisé, car le fichier ne fait que 648 octets !)

Et pour décompresser :

Code :

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

1
2
3
4
 
./huffman -d fichier.encoded 
Huffman decoding ...........................     0.00246000289917sec
Fatal error: exception Invalid_argument("Char.chr")

Le problème se situe donc dans le décodage du movetofront apparemment

Si j'essaye avec le fichier texte suivant contenant:

Code :

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

essaiessai

La décompression fonctionne :

Code :

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

1
2
3
4
5
6
 
./huffman -d essai.encoded 
Huffman decoding ...........................     2.00271606445e-05sec
Move to Front decoding .....................     0.000401973724365sec
Burrows-Wheeler inverse transformation .....     0.00131607055664sec
Resulting uncompressed file is in "essai.decoded"

Mais j'ai ça dans le fichier decoded :

Code :

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

1
2
3
 
essai
esai

Bon j'ai lu et relu plusieurs fois le fichier movetofront.ml, et tous les test internes marchent parfaitement ! Je ne vois pas d'où pourrait venir le problème car j'ai bien respecté toutes les contraintes.

Merci d'avance pour votre aide

[InOCamlWeTrust]

Etant donné que tu as le message...

Code :

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

1
2
 
Fatal error: exception Invalid_argument("Char.chr")

... tu devrais pouvoir remonter à la source du problème sans trop de difficultés : commence par regarder à quels endroits on fait appel à Char.chr, examine ses arguments avant appel, puis remonte d'un cran, et ainsi de suite. Essaye d'incorporer des traces aussi : ça aide bien !

[Mockingbird]

En fait dans le fichier movetofront.ml, on a deux fonctions encode et decode. On doit mettre en argument une fonction de codage f pour encode qui est de type 'a -> 'int. Pour decode, on doit mettre en argument la réciproque de cette fonction. On l'appelle g, elle a pour type int -> 'a.

Tout ce qui contient Char.chr (c'est la fonction g en fait) dans mon fichier ml, concerne les exemples et les test en commentaires. Ca n'apparaît nullement dans les fonctions Justement, c'est ça qui est assez bizarre

@++

[gasche]

J'ai pas encore regardé le problème lui-même mais j'ai 3 questions :
- il manque deux fichiers .ml (main et default), du coup on ne peut pas compiler nous-même. C'est assez gênant parce que ça empêche de tester des éventuelles possibilités de modification. Tu pourrais les ajouter (et au passage, virer les .cm* qui ne servent à rien si on peut compiler) ?
- il n'y a pas de licence ni rien sur le code, donc on sait pas ce qu'on est sensé pouvoir faire avec (par défaut : rien). Tu n'as pas envisagé la question ?
- on peut faire des remarques sur le code, qui n'ont rien à voir avec ton problème ?

[Mockingbird]

Salut !
Je me suis peut être embrouillé en faisant l'archive que j'ai mis en lien dans le premier message.
Voici ce qui était fourni ici
Ce que j'ai fait ici

Il n'y a pas de fichier main.ml ni default.ml. Il y avait juste les fichiers déjà compilé.

Voici un extrait du sujet :





Oui les remarques sont les bienvenues, comme ça je pourrais peut être améliorer mon movetofront

Merci à toi

@++

[gasche]

Bon, du coup, je peux pas compiler de code pour tester (j'ai sans doute pas la même version de OCaml, et du coup ça chie).

J'ai donc regardé le code "à vide", et effectivement le code de movetofront est assez terrifiant

Le principe d'une liste, c'est que tous les éléments sont rangés dans l'ordre, mais que tu ne peux accéder qu'au premier (ou rajouter des éléments devant, mais bref tu n'as le droit de toucher qu'à un bout).
Il faut impérativement que tu respectes cet état d'esprit : tu ne dois traiter les listes qu'en accédant (peut-être récursivement) qu'au premier élément à chaque fois. Tout algorithme demandant de récupérer "le k-ième élément de la liste" sans toucher aux éléments d'avant n'est pas adapté : il faut soit changer d'algo, soit changer de structure de donnée (prendre un tableau).
C'est exactement ce que fais ta fonction prendre_i : jette-la, brule-la, et ne l'utilise plus jamais (... ou presque) : ton code n'en sera que meilleur.

Par exemple, ta fonction "assemble mot" est complètement rocambolesque.

Code :

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

List.rev ((entier_k k mot f)::(List.rev (assemble_aux mot f (k-1) )))

Il ne faut pas faire ça : comme la complexité de List.rev est linéaire, tu te retrouves à parcourir tous les éléments de la liste à chaque appel récursif de ta fonction.
Au lieu de t'embêter à retourner les listes comme ça, juste pour pouvoir ajouter un élément à la fin, tu pourrais faire de la manière suivante : tu assemble tous les éléments "dans le mauvais ordre", en ajoutant le résultat de entier_k au début de la liste, et pas à la fin (donc en manipulant "normalement" ta liste), et tu retournes la liste [gras]à la fin[/gras] :

Code :

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

in List.rev (assemble_aux ...);;

Par ailleurs, une grande partie de tes fonctions existent déjà dans la bibliothèque standard OCaml (module List) :
- crepaires : List.combine
- suspnd : List.map fst
- list_paire_begin : List.find_all (à adapter)
- renvoi_paire : List.find (on pourrait presque utiliser List.assoc si tu stockais tes couples dans l'ordre inverse)

Globalement, la plupart de tes fonctions servent à reproduire le comportement d'un tableau. Pourquoi ne pas utiliser directement un tableau ? (Je pense que l'algorithme peut se faire directement avec des listes, mais alors l'approche "on met des index dans un couple et on les tripote dans tous les sens" n'est sans doute pas la meilleure)

[Mockingbird]

Oki merci pour les conseils Je sais qu'il y a des trucs assez gros comme ça (genre les liste.rev). Merci sinon pour les fonctions internes de caml

En fait dans le sujet , il est précisé qu'on doit faire les fonctions dans un style purement fonctionnel, sans procédures, sans références et sans tableaux

Je vais voir ce que je peux faire


@++

[InOCamlWeTrust]

Ca ma rapelle les petits projets que l'on nous donnait à l'ENSEEIHT... mais ils faisaient tout en Caml Light (pas cool...)...

[Mockingbird]

Voilà, j'ai refait une autre version pour encode :

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
75
76
77
78
 
(*Fonction cutbegin qui enlève d'une liste la sous-liste finissant par pairedebut*)
let rec cutbegin pairedebut listepaires=
  match pairedebut,listepaires with
    |_,[]->[]
    |(_,n),((_,k)::restepaires) when k<>n  -> cutbegin pairedebut restepaires
    |(_,n),((_,k)::restepaires)            -> restepaires;;
 
(*Fonction cutend qui enlève d'une liste la sous-liste commençant par pairefin *)
let rec cutend pairefin listepaires= List.rev (cutbegin pairefin (List.rev listepaires));;
 
(*Fonction extraction qui extrait la sous liste se situant strictement entre pairedebut et pairefin*)
let extraction pairedebut pairefin listepaires = cutend pairefin (cutbegin pairedebut listepaires);;
 
 
(*Fonction tasser : transforme une liste en ensemble (ie 
dans lequel chaque élément n'apparaît qu'une fois) *)
let rec tasser liste=
  match liste with
    |[]->[]
    |t::q -> if (List.mem t q) then tasser q 
             else t::(tasser q);;
 
(*Fonction distance : la distance entre deux lettre du mot *)
let distance pairedeb pairefin listepaires= List.length ( tasser ( List.map fst ( extraction pairedeb pairefin listepaires)));;
 
 
(*Fonction qui prend dans une listedepaires la paire la plus proche de la tête de la liste et possédant le même 
premier élément *)
 
 
let prendre_paire_next listepaires= List.hd (List.tl((List.find_all (fun x-> fst(x)=fst( List.hd listepaires)) listepaires)));;
 
 
 
(*Fonction qui créé la liste [ dim ; dim-1 ; dim-2 ; ... ; 1 ] *)
let rec nentier dim=
  match dim with
    |0->[]
    |1->[1]
    |k-> k::(nentier (k-1));;
 
 
(*mot_k représente ici les k-premières lettre du mot placé à l'envers dans une liste *)
(*Ainsi cette fonction renverra le kième entier associé au premier élément de mot_k (qui
représente en fait la kième lettre à codée) *)
 
 
let rec entier_k mot_k f=
  let k=List.length mot_k in
 
    if  (List.mem (List.hd mot_k) (List.tl mot_k))=false (*l'entier à retourner ne sera pas une distance*)
 
 
         then ( f (List.hd mot_k) +  (List.length ( List.find_all (fun x -> x >= f (List.hd mot_k)) (List.map f mot_k))) - 1)
 
    else ( distance  (List.hd (List.combine mot_k (nentier k)))
 
 
	             (prendre_paire_next (List.combine mot_k (nentier k))) 
 
 
		     (List.combine mot_k (nentier k)) );;
 
 
 
(*Fonction encode*)
 
 
(*******************************************************)
let encode f mot=
  let rec assemble_aux mot l=
    match mot with 
      |[]->[]
      |t::q -> (entier_k (t::l) f)::(assemble_aux q (t::l))
  in assemble_aux mot [];;
 
(********************************************************)

J'ai testé sur un mot de 2176 caractères, ca a duré 2 secondes seulement.
On peut sûrement faire mieux, mais faut que je m'attaque à decode maintenant
Surtout qu'en testant decode sur une liste d'entier très longue (avec plein d'entier aléatoire), je suis tombé sur la même erreur que lors de l'utilisation de huffman, à savoir "invalid argument Char.chr" !

[Mockingbird]

Et voici le décodage :

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
 
 
 
 
(*Fonction qui retire un élément d'une liste*)
let rec retirer elt liste=
  match liste with
    |[]->[]
    |t::q when t=elt -> retirer elt q
    |t::q            -> t::(retirer elt q);;
 
(*Fonction tasser qui lorsqu'elle rencontre un élément se trouvant plusieurs fois
dans la liste garde le premier trouvé et supprime tous les autres *)
(*Cette fonction est différente de la fonction tasser dans la mesure où elle conserve l'ordre
des éléments de la liste lue de gauche à droite*)
 
let rec tasser_smart liste=
  match liste with
    |[]->[]
    |t::q when (List.mem t q) -> t::(tasser_smart (retirer t q))
    |t::q                     -> t::(tasser_smart q);;
 
 
(*Fonction qui prend l'élément d'une liste distant d'une distance d+1
du premier élément*)
let prendre_a_distance d liste= List.nth (tasser_smart liste) (d+1-1);;
 
 
 
(*Fonction lcutend qui enlève la fin de la liste à partir d'une position donnée*)
(*On utilise la fonction cutend qui travaille sur une liste de paires*)
(*
let rec lcutend k liste=
  let lpa=crepaires liste (nentier (List.length liste))
  in
suppsnd (cutend (renvoi_paire k lpa) lpa);;
*)
 
(*Fonction qui calcule le nombre d'élément dans une liste
supérieur ou égal à un élément donné *)
let rec nboccursuplarge n liste=
    match liste with
      |[]->0
      |elt::reste when elt>=n -> 1+(nboccursuplarge n reste)
      |elt::reste               ->  nboccursuplarge n reste;;
 
 
 
(*La fonction renvoit la kième lettre du mot décodé si l'on rentre connait la liste l égal à la liste des k-1 premières lettres déjà décodées *)
(*Deux cas se présentent (if...then...else) : l'entier à décoder n'est pas une distance ou bien l'entier à décoder est 
une distance *)
 
let lettre_k intcode_k g l=
 if (List.length ( tasser_smart(l)) < List.hd (intcode_k)+1 )
 
             then g ( (List.hd intcode_k) - (nboccursuplarge (List.hd intcode_k) (List.tl intcode_k)) )
 
          else prendre_a_distance (List.hd intcode_k) l;;
 
 
(*Fonction decode*)
(**************************************************************************)
 
let rec decode g intcode=
  let rec assembled_aux intcode g m l=    
    match intcode with
      |[]->[]
      |t::q -> (lettre_k (t::m) g l)::(assembled_aux q g (t::m) ((lettre_k (t::m) g l)::l))
 
  in assembled_aux intcode g [] [];;
 
 
(*************************************************************************)

Mais par contre, j'ai toujours l'erreur
Huffman decoding ........................... 0.00105094909668sec
Fatal error: exception Invalid_argument("Char.chr")

Je comprends vraiment pas ce qui cause cette erreur...

[Mockingbird]

Bon c'est toujours movetofront le goulot d'étranglement de la compression.
J'ai testé la compression sur le fichier source movetofront.ml :

Code :

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

1
2
3
4
5
6
 
./huffman -e movetofront.ml
Burrows-Wheeler transformation .....     38.1416540146sec
Move to Front encoding .............     82.9550850391sec
Huffman encoding ...................     5.95185899734sec
Compression rate achieved ..........     45%

Bon il y avait une petite erreur dans huffman.ml, mais c'est toujours pareil.
J'ai testé sur un fichier texte contenant

Code :

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

essai essai

La compression ET la décompression se passe bien là. Par contre le fichier décompressé n'est pas bon, j'ai ça

Code :

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

i"i^Li"i^Li"i^L

Ca ne marche sur des fichiers plus gros par contre

Etrange non ?

[Mockingbird]

Bon alors, en fait il restait des erreurs dans movetofront.ml d'où les erreurs précédentes.
Et j'ai trouvé comment reproduire l'erreur de sortie, c'est lorsque je fais un decode du movetofront avec un entier en dehors du codage ASCII.
Mais comment corriger le code ?

[InOCamlWeTrust]

Oui, çaon s'en doutait bien que le code ASCII était invalide : c'est ce que le message d'erreur disait. Ce qui n'est pas normal, c'est que tu aies un code ASCII invalide.

[Mockingbird]

En fait, c'est le decode de burrows_wheeler qui pose problème.
Le mot ['e';'s';'s';'a';'i';' ';'e';'s';'s';'a';'i'] n'arrive pas à passer lorsque je fais
decode (encode ( mot) ).

[InOCamlWeTrust]

Cherche pourquoi tu as un code ASCII invalide.

[InOCamlWeTrust]

Ca me trottait dans la tête... et oui, les premières années ENSEEIHT ont bien eu le même sujet cette année ! Mais je ne l'ai pas eu entre les mains...

[HanLee]

Ca vient pas de l'encodage de ton fichier source ou de données?

[bounadiaf]

je dois faire un makefile qui doit faire cela j'ai fait ma fonction huffman à la main j'ai fait un

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
all: huffman
 
huffman: bib.cma graphics.cma huffman.cmo
	ocamlc -o huffmanbib.cma graphics.cma huffman.cmo
 
huffman: huffman.cmo
	ocamlc -o huffmanhuffman.cmo
 
huffman.cmo: huffman.ml
	ocamlc -c huffman.ml
 
bib.cma: huffman.cmo
	ocamlc -a -o bib.cma huffman.cmo  
 
 
 
 
 
clean:
	rm -rf *.mo

je ne vois pas comment m'y prendre pour résoudre le probleme et je vois dans la discussion le même procédé please help me!!

Code :

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

1
2
3
4
5
test : huffman
./huffman c example example1
./huffman d example1 example2
ls -la example*
diff example example2