Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Codage de Huﬀman Marc Lorenzi 29 décembre 2018 In [1]: Voici trois chaînes de c

Codage de Huﬀman Marc Lorenzi 29 décembre 2018 In [1]: Voici trois chaînes de caractères que nous utiliserons dans tout le notebook. La chaîne abra est très courte et a des propriétés intéressantes. La chaîne ovide est un peu plus longue. In [2]: 1 Notion de code 1.1 Alphabets, lettres, mots Un alphabet est un ensemble ﬁni d'objets. Les éléments d'un alphabet sont appelés des lettres. Jusque là tout le monde me suit ? L'alphabet auquel nous pensons tous est évidemment , auquel nous pourrions rajouter les lettres majuscules, les chiﬀres, les symboles de ponctuation, etc. Mais n'importe quel ensemble ﬁni fera l'aﬀaire. Un mot sur l'alphabet est une suite ﬁnie, éventuellement vide, de lettres. Notation : On note l'ensemble des mots sur l'alphabet . Un mot de longueur (ou taille) , est noté plus simplement par la juxtaposition de ses lettres. Le mot vide, l'unique mot de longueur 0, qui n'a pas de lettre, est noté si besoin. Nous noterons la longueur du mot . Nous disposons donc de la fonction déﬁnie par . Convention : Nous identiﬁerons un mot de longueur 1 avec son unique lettre. Avec cette convention, . Dans toute la suite, désigne un alphabet. Lorsque nous écrivons et que est un mot, les sont les lettres de et est sa longueur. Le mot vide ne sera pas systématiquement traité comme il conviendrait à son rang, le lecteur est censé s'assurer que ce que nous raconterons s'applique aussi dans ce cas. A A = {a, b, … , z} A A∗ A n ≥1 u = ( , … , ) a0 an−1 u = … a0a1 an−1 ε |u| u | ∙| : →ℕ A∗ u ↦|u| A ⊂A∗ A u = … a0 an−1 u ai u n 1.2 Produit de mots import math import heapq abra = 'abracadabra' ovide = 'Ante mare et terras et quod tegit omnis caelum unus erat toto nat L'ensemble est muni de l'opération de concaténation (ou produit) des mots, que nous noterons multiplicativement : Déﬁnition : Soient et deux mots non vides. Le produit de et est le mot Si est le mot vide, on pose . Si est le mot vide, on pose . Propriété : , muni du produit des mots, est un monoïde en général non commutatif. Précisément : Pour tous , . Pour tout , . L'opération de concaténation est non commutative dès que possède au moins 2 lettres. Démonstration : Sans diﬃculté particulière. Noter que si et sont deux lettres diﬀérentes de l'alphabet , alors . Le produit n'est donc pas commutatif si possède au moins deux lettres. Propriété : Tout mot est le produit de ses lettres. Propriété : Pour tous mots , . La fonction est donc un morphisme de monoïdes. Démonstrations : faciles. A∗ u = … a0a1 am−1 v = … b0b1 bm−1 u v uv = … … a0a1 am−1b0b1 bn−1 u = ϵ uv = v v = ϵ uv = u A∗ u, v, w ∈A∗(uv)w = u(vw) u ∈A∗uε = εu = u A a b A a. b ≠b. a A u, v ∈A∗|uv| = |u| + |v| | ∙| Remarque : Dans tout ce notebook, sauf tout à la ﬁn dans la partie théorique, nous prendrons pour un ensemble contenant uniquement des lettres "usuelles" , , etc, des chiﬀres, des espaces, des caractères de ponctuation. Cela nous permet de représenter en Python un mot sur l'alphabet par une chaîne de caractères ( string ). A a b A 1.3 Coder Une étape essentielle dans le stockage ou la transmission de l'information est le codage des mots. Pour être stocké ou transmis, un mot doit être codé. Et ce que nous obtenons après codage doit pouvoir être décodé (c'est préférable). Pour ceux d'entre-vous qui se disent qu'ils ne stockent jamais de mots, dites vous qu'un ﬁchier n'est qu'un long mot dont les lettres sont, par exemple, les octets du ﬁchier. Nous allons travailler dans ce notebook sur des chaînes de caractères mais tout ce que je vais raconter peut s'adapter assez facilement à des ﬁchiers concrets. Déﬁnition incomplète : Un code est une fonction où . Proposition : Soit un code. Il existe un unique morphisme de monoïdes tel que pour tout , . Preuve : Soit . Si un tel morphisme existe, on a puisque l'image d'un produit est le produit des images. Inversement, cette fonction convient. Bref, si on sait coder les lettres alors on sait coder les mots. Exercice : Pensez-vous au mot vide ? Que vaut ? Indication : Un morphisme conserve le neutre. c : A →픹∗ 픹= {0, 1} c : → c∗ A∗ 픹∗ u ∈A (u) = c(u) c∗ u = … ∈ a0 an−1 A∗ (u) = c( ) … c( ) c∗ a0 an−1 (ε) c∗ 1.4 Le code ASCII ASCII signiﬁe "American Standard Code for Information Interchange". Le code ASCII a été développé au paléolithique, plus précisément dans les années 1960. C'est une norme de codage des caractères. Le code ASCII "pur" code 128 caractères par des mots de 7 bits sur l'alphabet . Par exemple, la lettre est codée 01100001 , la lettre est codée 01100010 , etc. En interprétant ces mots de comme des entiers en base 2, on retient plutôt que le code ASCII de est 97, celui de est 98, etc. Il existe de nombreuses extensions du code ASCII permettant de coder caractères. La plus utilisée par les français est le code ISO 8859-1, appelé aussi ISO Latin-1. Il permet de coder, en particulier, les lettres accentuées, par des codes supérieurs ou égaux à 128. Remarque : Le code ASCII s'est avéré au ﬁl du temps insuﬃsant pour coder les nombreux caractères des langues de la Galaxie. Son évolution est le code Unicode qui peut coder caractères, dont je ne parlerai pas plus avant. Les idées sous-tendant Unicode et ses implémentations concrètes sont intéressantes et je ne saurais trop vous conseiller de vous documenter sur le sujet. 픹 a b 픹∗ a b = 256 28 65536 = 216 La fonction Python ord permet d'obtenir le code ASCII d'un caractère. In [3]: Sa "réciproque" est la fonction chr . J 74 e 101 32 v 118 a 97 i 105 s 115 32 à 224 32 l 108 a 97 32 p 112 ê 234 c 99 h 104 e 101 32 l 108 e 101 32 d 100 i 105 m 109 a 97 n 110 c 99 h 104 e 101 . 46 for c in 'Je vais à la pêche le dimanche.': print(c, ord(c)) In [4]: Histoire de nous échauﬀer, écrivons une fonction Python qui code un mot au moyen du code ASCII. Voici tout d'abord une fonction qui prend en entier un entier et renvoie sa représentation binaire sous forme d'une chaîne de 8 caractères. n [(0, '\x00'), (1, '\x01'), (2, '\x02'), (3, '\x03'), (4, '\x04'), (5 , '\x05'), (6, '\x06'), (7, '\x07'), (8, '\x08'), (9, '\t'), (10, '\ n'), (11, '\x0b'), (12, '\x0c'), (13, '\r'), (14, '\x0e'), (15, '\x0 f'), (16, '\x10'), (17, '\x11'), (18, '\x12'), (19, '\x13'), (20, '\ x14'), (21, '\x15'), (22, '\x16'), (23, '\x17'), (24, '\x18'), (25, '\x19'), (26, '\x1a'), (27, '\x1b'), (28, '\x1c'), (29, '\x1d'), (30 , '\x1e'), (31, '\x1f'), (32, ' '), (33, '!'), (34, '"'), (35, '#'), (36, '$'), (37, '%'), (38, '&'), (39, "'"), (40, '('), (41, ')'), (4 2, '*'), (43, '+'), (44, ','), (45, '-'), (46, '.'), (47, '/'), (48, '0'), (49, '1'), (50, '2'), (51, '3'), (52, '4'), (53, '5'), (54, '6 '), (55, '7'), (56, '8'), (57, '9'), (58, ':'), (59, ';'), (60, '<') , (61, '='), (62, '>'), (63, '?'), (64, '@'), (65, 'A'), (66, 'B'), (67, 'C'), (68, 'D'), (69, 'E'), (70, 'F'), (71, 'G'), (72, 'H'), (7 3, 'I'), (74, 'J'), (75, 'K'), (76, 'L'), (77, 'M'), (78, 'N'), (79, 'O'), (80, 'P'), (81, 'Q'), (82, 'R'), (83, 'S'), (84, 'T'), (85, 'U '), (86, 'V'), (87, 'W'), (88, 'X'), (89, 'Y'), (90, 'Z'), (91, '[') , (92, '\\'), (93, ']'), (94, '^'), (95, '_'), (96, '`'), (97, 'a'), (98, 'b'), (99, 'c'), (100, 'd'), (101, 'e'), (102, 'f'), (103, 'g') , (104, 'h'), (105, 'i'), (106, 'j'), (107, 'k'), (108, 'l'), (109, 'm'), (110, 'n'), (111, 'o'), (112, 'p'), (113, 'q'), (114, 'r'), (1 15, 's'), (116, 't'), (117, 'u'), (118, 'v'), (119, 'w'), (120, 'x') , (121, 'y'), (122, 'z'), (123, '{'), (124, '|'), (125, '}'), (126, '~'), (127, '\x7f'), (128, '\x80'), (129, '\x81'), (130, '\x82'), (1 31, '\x83'), (132, '\x84'), (133, '\x85'), (134, '\x86'), (135, '\x8 7'), (136, '\x88'), (137, '\x89'), (138, '\x8a'), (139, '\x8b'), (14 0, '\x8c'), (141, '\x8d'), (142, '\x8e'), (143, '\x8f'), (144, '\x90 '), (145, '\x91'), (146, '\x92'), (147, '\x93'), (148, '\x94'), (149 , '\x95'), (150, '\x96'), (151, '\x97'), (152, '\x98'), (153, '\x99' ), (154, '\x9a'), (155, '\x9b'), (156, '\x9c'), (157, '\x9d'), (158, '\x9e'), (159, '\x9f'), (160, '\xa0'), (161, '¡'), (162, '¢'), (163, '£'), (164, '¤'), (165, '¥'), (166, '¦'), (167, '§'), (168, '¨'), uploads/S4/ huffman.pdf