Lempel-Ziv-Welch
Data compression algorithm
Lempel-Ziv-Welch (LZW)
Lempel–Ziv–Welch (LZW) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch. It was published by Welch in 1984 as an improved implementation of the LZ78 algorithm published by Lempel and Ziv in 1978.
As part of the functional programming courses, in Master 1 Computer Science at the university, we were asked to carry out, in pairs, with the functional language Haskell, the encoding and decoding programs of Zempel-Ziv-Welch.
Although our project is not completed due to lack of time (but functional), the objective has been achieved. We have two programs that encode and decode strings.
To carry out the project, we were given some guidelines. Indeed, the LZW algorithm works with a data structure in which several operations of insertion, modification and tests are carried out during the execution of the encoding and decoding. We were therefore instructed to separate these operations to simplify the writing of the code. And for that, a class named "Table" was created. It thus contains all the functions that take care of these operations.
Either the following class :
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)
We programmed our programs using this class. It was therefore necessary to implement the encoding and decoding functions but also all the functions of the class.
The objective was to program them with, firstly, associative lists and secondly, trees. In our project, only associaive lists have been created (I advise you to read the basic algorithm to fully understand the code available below via Github).
Informations about the project
| Title | Lempel-Ziv-Welch |
| Description | Implementation of Lempel-Ziv-Welch encoding and decoding programs. |
| Used language | Haskell |
| Year of work | 2016 |
| Access to code | Lien |