Unix `spell` exécuté avec 64 kB de RAM

Comment Unix spell a pu fonctionner avec 64 kB de RAM

Comment faire tenir un dictionnaire dans 64 kB de RAM ?

• Les ingénieurs Unix ont résolu le problème consistant à faire tenir un dictionnaire de 250 kB dans 64 kB de RAM en s’appuyant sur des structures de données et des techniques de compression.
• Dans les années 1970, Douglas McIlroy s’est heurté à ce problème en implémentant le correcteur orthographique Unix d’AT&T.
• Il a développé un algorithme de compression proche de la limite théorique en exploitant les caractéristiques des données.

TL;DR

• Le correcteur orthographique Unix a commencé dans les années 1970 comme un prototype de Steve Johnson chez AT&T.
• McIlroy a développé un algorithme de racinisation fondé sur la langue, réduisant le dictionnaire à 25 000 mots.
• Un filtre de Bloom a été utilisé pour permettre des recherches rapides, avec une implémentation fournie par Dennis Ritchie.
• Quand le dictionnaire est passé à 30 000 mots, l’approche par filtre de Bloom est devenue inefficace, ce qui a conduit à l’adoption d’une technique de compression par hachage.
• En utilisant des codes de hachage sur 27 bits pour réduire la probabilité de collision, et le code de Golomb, ils ont atteint une compression de 13,60 bits par mot.

Origine de la commande de correction orthographique Unix

• Unix a été proposé au département des brevets d’AT&T comme système de traitement de texte, et un correcteur orthographique était nécessaire.
• La première version a été écrite par Steve Johnson en 1975, mais sa précision était faible.
• Douglas McIlroy a réécrit le projet pour en améliorer la précision et les performances.

Algorithme de suppression des préfixes

• McIlroy a conçu un algorithme qui retire des mots les préfixes et suffixes courants avant d’interroger le dictionnaire.
• Cette méthode n’était pas exacte à 100 %, mais elle était jugée acceptable à l’époque.

Recherche basée sur un filtre de Bloom

• Le filtre de Bloom permettait d’économiser de la mémoire tout en rendant les recherches rapides.
• Il a été utilisé pour charger dans 64 kB de RAM un dictionnaire de 25 000 mots.
• Le filtre de Bloom a été ajusté pour conserver un faible taux de faux positifs.

Technique de hachage compressé pour la recherche dans le dictionnaire

• Quand la taille du dictionnaire est montée à 30 000 mots, une structure de données plus efficace en mémoire est devenue nécessaire.
• McIlroy a utilisé une méthode consistant à stocker les écarts entre les codes de hachage afin d’économiser la mémoire.
• Le code de Golomb a été utilisé pour compresser ces écarts de hachage.

Conclusion

• La commande de correction orthographique Unix constitue un épisode fascinant de l’histoire de l’ingénierie né des contraintes mémoire du PDP-11.
• Elle a apporté une solution élégante combinant filtre de Bloom, théorie de l’information, théorie des probabilités et algorithmes de compression.
• Elle montre qu’un travail de résolution de problèmes en profondeur est possible même sous de fortes contraintes de ressources.

[GN⁺]

Commentaires Hacker News

• Le filtre de Bloom était à l’origine appelé « superimposed code scheme », et il s’agit d’un type particulier de superimposed code

  • Calvin Mooers a développé le codage aléatoire par superimposed coding au MIT dans les années 1940, sous l’influence des travaux de Shannon
  • Le livre de Bourne de 1963, "Methods of Information Handling", en donne les détails mathématiques
  • Il est très probable que Douglas connaissait cette technique

• Il était possible d’implémenter un correcteur orthographique sur mémoire externe avec peu de RAM

  • Le principe consistait à trier les mots du document, supprimer les doublons, puis les fusionner avec le dictionnaire pour ne conserver que les mots manquants
  • Cela fonctionnait sur un TRS-80 Color Computer avec moins de 32k de RAM
  • Turbo Lightning effectuait la vérification orthographique à la saisie sur PC en utilisant un dictionnaire compressé

• La bande passante mémoire et la bande passante disque étaient comparables, et il était donc possible d’effectuer le travail en plusieurs passes

  • Utiliser un filtre de Bloom était une bonne approche pour cela

• Il existait dans les années 1980 un correcteur orthographique matériel pour IBM PC

  • Il se branchait entre le clavier et le PC et émettait un bip lorsqu’on tapait un mot qu’il ne reconnaissait pas

• Unix a été proposé à AT&T comme système de traitement de texte, et un correcteur orthographique était nécessaire

  • UNIX était utilisé principalement pour le traitement de texte

• Un article de Byte du début des années 1980 expliquait comment créer le correcteur orthographique d’Unix

  • Les PC 8 bits ne disposaient pas de ce type de fonctionnalité

• À cause du hachage, certaines fautes de frappe courantes pouvaient passer inaperçues

  • Il existe un concours sur la compression du dictionnaire de Wordle

• Au milieu des années 1980, on traitait les données avec 640 KB de RAM et 64 KB pour le tas et la pile

  • Il fallait des heures pour extraire et combiner les données, le tout sur un système monothread

• Vers 1983, sur CP/M, Grammatik fonctionnait avec moins de 64k et incluait un correcteur grammatical ainsi que des règles de système expert

  • Écrit en Forth, il était très compact

• La première version d’UNIX nécessitait 24 kB, dont la moitié était occupée par le noyau