Présentation
Le logiciel Unix spell a été conçu pour fonctionner avec seulement 64 ko de RAM. Les ingénieurs de Unix ont résolu ce défi en utilisant des structures de données et des techniques de compression astucieuses.
Contexte technique
Dans les années 1970, Douglas McIlroy a développé l'algorithme de compression pour le logiciel Unix spell. Il a créé un algorithme qui réduisait la taille du dictionnaire à 25 000 mots, tout en améliorant la précision. Pour les recherches rapides, il a utilisé un filtre de Bloom, qui a été mis en œuvre par Dennis Ritchie.
Fonctionnement
Le filtre de Bloom est une structure de données qui utilise plusieurs fonctions de hachage pour déterminer si un élément est présent dans un ensemble. Dans le cas de Unix spell, le filtre de Bloom a été utilisé pour déterminer si un mot est présent dans le dictionnaire. Cependant, lorsque le dictionnaire a grandi à 30 000 mots, l'approche du filtre de Bloom est devenue impraticable, ce qui a conduit à des techniques de compression de hachage innovantes.
Implications et limites
Douglas McIlroy a calculé que des codes de hachage de 27 bits seraient nécessaires pour maintenir une faible probabilité de collision, mais il a également besoin de compression. Il a découvert que les différences entre les codes de hachage triés suivaient une distribution géométrique et a utilisé le code de Golomb, un schéma de compression conçu pour les distributions géométriques, pour atteindre 13,60 bits par mot, ce qui est remarquablement proche de la limite théorique de 13,57 bits.
