Lempel-Ziv-Welch

Algorithme de compression de données

Lempel-Ziv-Welch (LZW)


LZW (pour Lempel-Ziv-Welch) est un algorithme de compression de données sans perte. Il s'agit d'une amélioration de l'algorithme LZ78 inventé par Abraham Lempel et Jacob Ziv en 1978. LZW fut créé en 1984 par Terry Welch, d'où son nom.

Dans le cadre des cours de programmation fonctionnelle, en Master 1 Informatique à l'université, il nous a été demandé de réaliser, en binôme, avec le langage fonctionnel Haskell, les programmes d'encodage et de décodage de Zempel-Ziv-Welch.

Bien que notre projet ne soit pas achevé par manque de temps (mais fonctionnel), l'objectif a été atteint. Nous avons deux programmes qui encodent et décodent les chaînes de caractères.

Pour mener à bien le projet, il nous a été donné quelques directives. En effet, l'algorithme LZW, fonctionne avec une structure de données dans laquelle sont effectuées plusieurs opérations d'insertion, de modification et de tests lors de l'exécution de l'encodage et du décodage. On nous a donc donné pour consigne de dissocier ces opérations pour simplifier l'écriture du code. Et pour cela, une classe nommée "Table" a été créée Elle contient ainsi toutes les fonctions qui se chargent de ces opérations.

Soit, la classe suivante :

class Table a where
	empty :: a
	insert  :: a -> String  -> a
	codeOf  :: a -> String  -> Maybe  Code
	stringOf  :: a -> Code  -> Maybe  String
	isIn :: a -> String  -> Bool
	split :: a -> String -> (String, Maybe Code, String)

Nous avons programmé nos programmes à l'aide de cette classe. Il a donc fallu implémenter les fonctions d'encodage et de décodage mais aussi toutes les fonctions de la classe.

L'objectif était de les programmer avec, dans un premier temps, des listes associatives et dans un deuxième temps, des arbres. Dans notre projet, uniquement les listes associaives ont été réalisées (Je vous conseille d'aller prendre connaissance de l'algortihme de base pour bien comprendre le code disponible ci-dessous via Github).

Caractéristiques du projet


Titre Lempel-Ziv-Welch
Description Implémentation des programmes d'encodage et de décodage de Lempel-Ziv-Welch.
Langage utilisé Haskell
Année de réalisation 2016
Accès au code Lien