Hacher une chaîne de caractères en octets

Question

Je travaille sur un projet personnel, un programme de compression de fichiers, et j'ai des problèmes avec mon dictionnaire de symboles. J'ai besoin de stocker des chaînes de caractères d'octets déjà rencontrées dans une structure de manière à pouvoir rapidement vérifier leur existence et les récupérer. J'ai travaillé sous l'hypothèse qu'une table de hachage serait la mieux adaptée à cette fin, donc ma question portera sur les fonctions de hachage. Cependant, si quelqu'un peut suggérer une meilleure alternative à une table de hachage, je suis tout ouïe. Bon. Le problème est que je n'arrive pas à trouver une bonne clé de hachage pour ces chaînes d'octets. Tout ce à quoi je pense a soit une distribution très inégale, soit prend trop de temps. Voici une liste de la situation avec laquelle je travaille :

1. Toutes les chaînes d'octets auront au moins deux octets de longueur.
2. La table de hachage aura une taille maximale de 3839, et il est très probable qu'elle se remplisse.
3. Des tests ont montré que, avec n'importe quel octet donné, le bit d'ordre le plus élevé est beaucoup moins susceptible d'être défini, par rapport aux sept bits inférieurs.
4. Sinon, les octets dans la chaîne peuvent avoir n'importe quelle valeur de 0 à 255 (je travaille avec des données brutes d'octets de n'importe quel format).
5. Je travaille avec le langage C dans un environnement UNIX. Je préférerais rester avec les bibliothèques standard, mais cela n'a pas besoin d'être portable vers d'autres OS. (par exemple, unistd.h est bien).
6. La sécurité n'est d'aucune importance.
7. La vitesse est d'une importance ÉLEVÉE.
8. La taille n'est pas d'une importance intense, car elle NE sera PAS écrite sur un fichier. Cependant, vu la taille potentielle des chaînes d'octets stockées, l'espace mémoire pourrait poser problème pendant la compression.

Answer 1

Un trie est mieux adapté à ce genre de choses car il vous permet de stocker vos symboles sous forme d'arbre et de les analyser rapidement pour faire correspondre des valeurs (ou les rejeter).

Et en bonus, vous n'avez pas besoin du tout d'une table de hachage. Vous stockez/récupérez/comparez la séquence entière en une seule fois, tout en n'occupant qu'une quantité minimale de mémoire.

Édition : Et en bonus supplémentaire, avec seulement une deuxième analyse, vous pouvez rechercher des séquences "proches" de votre séquence actuelle, afin de vous débarrasser d'une séquence et d'utiliser la précédente pour les deux, avec une notation interne pour retenir les différences. Cela vous aidera à compresser les fichiers de manière plus efficace car :

1. un dictionnaire plus petit signifie des fichiers plus petits, vous devez écrire le dictionnaire dans votre fichier
2. un nombre plus petit d'éléments peut libérer de l'espace pour stocker d'autres séquences plus rares si vous ajoutez une limite de population et que vous la dépassez avec un fichier volumineux.