Hachage par XOR et LZ78
Méthode de Compression en Hachage⚓︎
La méthode de compression consiste à utiliser tous les bits de la représentation de données, que l'on découpe en sous-mots d'un nombre égal de bits, et à les combiner à l'aide de l'opérateur XOR. Cet opérateur a l'avantage de maintenir l'équilibre des valeurs (en évitant de rendre les résultats systématiquement plus petits ou plus grands).
Dans cet exemple, nous allons utiliser des sous-mots de 5 bits pour effectuer les opérations de compression.
Chaque lettre de l'alphabet est encodée par sa position dans l'alphabet
| lettre | position | code 5 bits |
|---|---|---|
| A | 1 | 00001 |
| N | 14 | 01110 |
L'espace est encodé 27 : 11011
La table suivante illustre le calcul des hachages pour différents mots en utilisant l'opérateur XOR.
Table de Compression⚓︎
| Mot | 1er Sous-mot (5 bits) | 2e Sous-mot (5 bits) | 3e Sous-mot (5 bits) | 4e Sous-mot (5 bits) | RĂ©sultat (5 bits) |
|---|---|---|---|---|---|
| NAT | 01110 | 00001 | 10100 | 11011 | 11111 (27 en décimal) |
| CARO | 00011 | 00001 | 10010 | 01111 | 11111 (31 en décimal) |
| REDA | 10010 | 00101 | 00100 | 00001 | 10010 (18 en décimal) |
| KRIS | 01011 | 10010 | 01001 | 10011 | 00011 (3 en décimal) |
Explication des Calculs⚓︎
- Mot "NAT" :
- 1er sous-mot: 01110
- 2e sous-mot: 00001
- 3e sous-mot: 10100
- 4e sous-mot: 11011
-
Calcul :
01110 XOR 00001 XOR 10100 XOR 11011 = 11111(En décimal, cela donne 27) -
Mot "CARO" :
- 1er sous-mot: 00011
- 2e sous-mot: 00001
- 3e sous-mot: 10010
- 4e sous-mot: 01111
-
Calcul :
00011 XOR 00001 XOR 10010 XOR 01111 = 11111(En décimal, cela donne 31) -
Mot "REDA" :
- 1er sous-mot: 10010
- 2e sous-mot: 00101
- 3e sous-mot: 00100
- 4e sous-mot: 00001
-
Calcul :
10010 XOR 00101 XOR 00100 XOR 00001 = 10010(En décimal, cela donne 18) -
Mot "KRIS" :
- 1er sous-mot: 01011
- 2e sous-mot: 10010
- 3e sous-mot: 01001
- 4e sous-mot: 10011
- Calcul :
01011 XOR 10010 XOR 01001 XOR 10011 = 00011(En décimal, cela donne 3)
Résumé⚓︎
La méthode de compression par XOR permet de "réduire" une séquence de bits en un seul nombre en combinant les sous-mots. Cette technique est utile dans les algorithmes de hachage, où chaque entrée de taille variable est condensée en une valeur de taille fixe (ici 5 bits).
Table avec les valeurs en 8 bits et 32 bits⚓︎
En 8 bits⚓︎
Si l'on adapte cette méthode pour des sous-mots de 8 bits, les mêmes principes de fonctionnement s'appliquent, mais avec une plus grande capacité pour chaque sous-mot, ce qui peut influencer le résultat global du hachage.
En 32 bits⚓︎
Si l'on utilise des sous-mots de 32 bits, la même technique serait mise en œuvre mais avec une plus grande précision pour chaque élément de la séquence. Cela permettrait de gérer des ensembles de données beaucoup plus volumineux tout en conservant une structure cohérente pour l'opération de compression.
Ecrire une fonction pyhton qui retourne le hachage sur 32 bits d'un texte avec la méthode précédente.⚓︎
La répartition de cette méthode de hachage paraît-elle uniforme ?⚓︎
Algorithme LZ78⚓︎
Je vous conseille de lire cette page.
Principe :⚓︎
– On a un dictionnaire qu’on met à jour progressivement – À chaque étape, on cherche le plus cours mot non présent dans le dictionnaire. – On écrit la position du mot trouvé, ainsi que la lettre à ajouter (10,r) – On écrit le nouveau mot dans le dictionnaire. – Et on continue à partir de la suite
Exemple⚓︎
texte = 'theoreme de parseval'
Construction du dictionnaire :
theoreme de parseval
| Index | Préfixe |
|---|---|
| 0 | '' |
| 1 | t |
| 2 | h |
| 3 | e |
| 4 | o |
| 5 | r |
| 6 | em |
| 7 | e |
| 8 | d |
| 9 | e p |
| 10 | a |
| 11 | rs |
| 12 | ev |
| 13 | al |
sortie :[(0, 't'),(0, 'h'),(0, 'e'),(0, 'o'),(0, 'r'),(3, 'm'),(3, ' '),(0, 'd'),(7, 'p'),(0, 'a'),(5, 's'),(3, 'v'),(10, 'l')]
Reconstruire le texte à partir de sortie⚓︎
Le dictionnaire est construit dans l'aure sens Préfixe, Index.
Important On obtient le même dictionnaire en inversant clé et valeur. Cela permet de se passer de l'indication du dictionnaire dans le fichier compressé.
entrée : [(0, 't'),(0, 'h'),(0, 'e'),(0, 'o'),(0, 'r'),(3, 'm'),(3, ' '),(0, 'd'),(7, 'p'),(0, 'a'),(5, 's'),(3, 'v'),(10, 'l')]
| Index | Préfixe |
|---|---|
| '' | 0 |
| t | 1 |
| h | 2 |
| ... | .. |
sortie : 'theoreme de parseval'
Complète le code suivant pour implémenter en Python les fonctions compress et decompress avec l'algorithme LZ78⚓︎
Remarque : Le code présenté ne tient pas compte d'une situation particulière où la toute fin du texte contient un préfixe entièrement dans le dictionnaire.
Dans ce cas, on ajoute simplement le couple (prefixe, '') Ă datac.
- adapter le code pour prendre en compte cette situation.
Remarque 2 : Il est aussi possible d'adapter le code pour imposer une taille de dictionnaire maximale.
Version avec taille de dictionnaire limitée
```python def compress(texte): current = '' tailledict = 0 datac = [] dictionnaire = {'': 0} taille_max = 10 for c in texte: if (current+c) in dictionnaire: current+=c flag = True else: datac.append((dictionnaire[current], c)) # ajout du couple (tuple) valeur dans dictionnaire, caractère supplémentaire tailledict += 1 if tailledict < taille_max: dictionnaire[current +c] = tailledict # ajout d'une nouvelle entrée dans le dictionnaire flag = False current = '' # Retour à la chaîne vide if flag: datac.append((dictionnaire[current], '')) return datac
def decompress(datac): dictionnaire = {0: ''} # on inverse le sens clé-valeur pour simplifier les recherches texte = "" tailledict = 0 taille_max = 10 for index, caractere in datac: texte += dictionnaire[index] + caractere tailledict += 1 if tailledict < taille_max: dictionnaire[tailledict] = dictionnaire[index] + caractere print(dictionnaire) return texte ````
Questions⚓︎
-
Complète le script pour trouver à partir de quelle taille de texte la compression occupe moins d'espace que le texte initial. A la louche, on néglige la taille du dictionnaire (c'est le cas pour un texte très long) et on considère que chaque élément de la compression occupe le double d'espace d'un caractère.
Pour cela on peut utiliser le texte suivant issu du H2G2, The Hitchhiker's Guide to the Galaxy:
Text Only 1 2
```python texte = '''Far out in the uncharted backwaters of the unfashionable end of the Western Spiral arm of the Galaxy lies a small unregarded yellow sun.Orbiting this at a distance of roughly ninety-eight million miles is an utterly insignificant little blue-green planet whose ape-descended life forms are so amazingly primitive that they still think digital watches are a pretty neat idea. This planet has—or rather had—a problem, which was this: most of the people living on it were unhappy for pretty much of the time. Many solutions were suggested for this problem, but most of these were largely concerned with the movements of small green pieces of paper, which is odd because on the whole it wasn’t the small green pieces of paper that were unhappy''' ```
Et
extrait = texte[:100]pour obtenir un texte de taille 100 -
est-ce que, dans cet exemple, à partir de la première valeur où la compression devient "rentable", toutes les tailles de texte supérieures sont "rentables" ?
# Tests(insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)