WDM 55:Various Dictionary Compression Techniques Part2

Nous avons commencé par calculer l'espace occupé par le dictionnaire sur le corpus RCV sans compression, qui était d'environ 11,2 Mo. Nous avons ensuite appliqué des techniques de compression pour réduire cette taille, d'abord en maintenant une chaîne de concatelation globale des termes du dictionnaire, réduisant l'espace moyen par terme à 8 octets par rapport aux 20 octets initialement alloués. Cela a permis de réduire la taille du dictionnaire à environ 7,6 Mo, sans affecter les performances de recherche utilisant la recherche binaire.

Pour économiser encore plus d'espace, nous avons décidé de conserver des pointeurs seulement pour chaque quatrième terme, en groupant les termes par blocs de quatre. Bien que cela ait réduit le nombre de pointeurs, il fallait désormais effectuer une recherche linéaire au sein du bloc, augmentant ainsi légèrement le temps de traitement. Une approche plus extrême consisterait à regrouper plus de termes, mais cela augmenterait le coût de traitement pour chaque recherche dans le bloc.

Nous avons exploré une autre technique de compression en utilisant un codage préfixé, où seulement la partie variable des chaînes était stockée séparément après un préfixe commun. Ceci a permis de réduire la taille globale nécessaire pour stocker le dictionnaire, cependant, la complexité du calcul de l’économie exacte d’espace rend cette méthode empirique. Cependant, elle a démontré une réduction notable de 7,1 Mo à 5,9 Mo sur le corpus RCV.

Le codage par devant commun (front coding) a été appliqué, où un préfixe commun est stocké une seule fois et les différences sont ajoutées ensuite. Cela a permis de réduire encore la taille du fichier, atteignant finalement 5,9 Mo. Cette méthode montre de bons résultats en termes d'économie d'espace, même si le processus de recherche prend légèrement plus de temps à cause de la décompression nécessaire.

L'implémentation de la compression a prouvé que malgré une augmentation du temps de recherche dû à la décompression, l'économie d'espace est substantielle puisque la taille a été réduite de moitié par rapport au départ. Les algorithmes de recherche, même avec la compression, restent raisonnablement rapides grâce aux recherches binaires couplées au décodage des termes stockés compactement.

Une autre compression est suggérée en optimisant la structure de l'arbre de recherche en fonction de la fréquence probable des occurrences. Le concept de Huffman Coding est introduit, suggérant que des fréquences d'accès différentes pourraient être utilisées pour construire une structure de recherche optimisée, bien que cela soit conceptuel dans ce cas spécifique.