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

1. Mot "NAT" :
2. 1er sous-mot: 01110
3. 2e sous-mot: 00001
4. 3e sous-mot: 10100
5. 4e sous-mot: 11011

6. Calcul : 01110 XOR 00001 XOR 10100 XOR 11011 = 11111 (En décimal, cela donne 27)

7. Mot "CARO" :

8. 1er sous-mot: 00011
9. 2e sous-mot: 00001
10. 3e sous-mot: 10010
11. 4e sous-mot: 01111

12. Calcul : 00011 XOR 00001 XOR 10010 XOR 01111 = 11111 (En décimal, cela donne 31)

13. Mot "REDA" :

14. 1er sous-mot: 10010
15. 2e sous-mot: 00101
16. 3e sous-mot: 00100
17. 4e sous-mot: 00001

18. Calcul : 10010 XOR 00101 XOR 00100 XOR 00001 = 10010 (En décimal, cela donne 18)

19. Mot "KRIS" :

20. 1er sous-mot: 01011
21. 2e sous-mot: 10010
22. 3e sous-mot: 01001
23. 4e sous-mot: 10011
24. 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

Complète le code suivant pour implémenter en Python les fonctions compress et decompress avec l'algorithme LZ78

Python

def compress(texte):
    current = ''
    tailledict=0
    datac = []
    dict = {'': 0}
    for c in texte:
        if (current+c) in dict:
            current+=c
        else:
            datac.append(....) # ajout du couple (tuple) valeur dans dictionnaire, caractère supplémentaire
            tailledict+=1
            ... # ajout d'une nouvelle entrée dans le dictionnaire
            current = '' # Retour à la chaîne vide
    return datac

def decompress(datac):
    dict = {0: ''} # on inverse le sens clé-valeur pour simplifier les recherches
    ... # à compléter