Pas toutes les techniques de compression des données adoptent le principe de dictionnaire pour représenter ses mots de code. Le dictionnaire est un ensemble de mots de code associés aux symboles sources lors de l’opération d’encodage. La correspondance entre le mot de code et le symbole source dépend de l’algorithme de compression adopté. Généralement, chaque algorithme construit son dictionnaire selon un ensemble de propriétés. Parmi ces propriétés nous avons celle de préfixe. Elle est primordiale pour les codes de type fixe à variable (FV) tels que l’algorithme de Huffman et celui de Shannon-Fano. Par contre, la propriété préfixe est optionnelle pour les codes de longueur variable à fixe (VF). Donc cela peut causer le but de pouvoir construire un dictionnaire plus performant, comme le cas des codes quasi-instantanés. Dans cette optique, Yamamoto et Yokoo ont éliminé cette condition pour créer un dictionnaire meilleur que celui de Tunstall. Les dictionnaires proposés par Yamamoto et Yokoo sont appelés les codes VF quasi-instantanés ou en anglais almost instantaneous VF codes. En s’appuyant sur leurs contributions, nous avons déduit que leur technique peut fournir dans certains cas des codes variables à fixes sous-optimaux, d’où notre suggestion de correctifs à leurs algorithmes pour en améliorer l’efficacité. Aussi nous proposons un autre mécanisme pour construire des codes VF en utilisant le principe de la programmation dynamique. / Various techniques of data compression use a dictionary to represent their codewords. A dictionary is a set of codewords associated with the source symbols during the encoding operation. The correspondence between the codeword and the symbol source depends on the compression algorithm. Usually, the prefix property is key for the fixed-to-variable type codes FV as demonstrated in the Huffman and the Shannon-Fano algorithms. However, such a property may be eliminated for fixed-length codes in order to build a more efficient dictionary. In this context, Yamamoto and Yokoo excluded this condition to create a dictionary better than Tunstall. This new dictionary is called instantaneous variable-to-fixed code. Based on their contributions, we have deduced that their technique can provide, in some cases, suboptimal variable-to-fixed codes. Hence, we suggested to improve their algorithms. Also, we proposed another mechanism for building optimal AIVF codes by adopting the principle of dynamic programming.
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/27733 |
| Date | 24 April 2018 |
| Creators | Haddad, Fatma |
| Contributors | Dubé, Danny |
| Source Sets | Université Laval |
| Language | French |
| Detected Language | French |
| Type | mémoire de maîtrise, COAR1_1::Texte::Thèse::Mémoire de maîtrise |
| Format | 1 ressource en ligne (xi, 59 pages), application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
Page generated in 0.0029 seconds