Unix spell exécuté avec 64 KB de RAM

• Dans les années 1970, spell d’Unix chez AT&T devait interroger rapidement un dictionnaire de 250 KB dans les 64 KB de RAM d’un PDP-11, et Douglas McIlroy a résolu le problème en exploitant les caractéristiques des données plutôt qu’une compression générique
• Le premier prototype de Steve Johnson, basé sur le disque, était lent et peu précis, mais McIlroy a amélioré les performances et la précision en réduisant le dictionnaire à environ 25 000 mots grâce à la racination
• La première structure en mémoire était un Bloom filter implémenté par Dennis Ritchie, avec une table de 400 000 bits et 11 fonctions de hachage, pour un taux de faux positifs d’environ 1/2000, ce qui permettait d’éviter une consultation séparée du dictionnaire
• Quand le dictionnaire est passé à 30 000 mots, le Bloom filter seul ne suffisait plus face aux contraintes mémoire ; les hachages sur 27 bits ont alors été triés puis les différences de hachage compressées avec un code de Golomb
• L’implémentation finale a découpé la table compressée des différences en plusieurs bins pour accélérer les recherches, avec environ 14 bits stockés par mot, rendant possible une vérification orthographique rapide dans 64 KB

---

Les contraintes mémoire auxquelles spell d’Unix a été confronté

• Le problème central était d’interroger rapidement un dictionnaire de 250 KB dans un environnement limité à 64 KB de RAM
• Même avec une compression moderne comme gzip -9, ce fichier ne descend pas sous 85 KB
• Sur un PDP-11 des années 1970, il était impossible de charger tout le dictionnaire en mémoire, et les consultations sur disque étaient lentes
• Au lieu d’une compression générique, McIlroy a conçu une structure de données spécialisée exploitant la structure et la distribution probabiliste des données du dictionnaire

Les débuts de spell sur Unix et la réduction du dictionnaire par racines

• Quand AT&T a proposé Unix comme système de traitement de texte pour son service brevets, un correcteur orthographique est devenu nécessaire
• Steve Johnson a écrit le premier prototype de spell pour Unix en 1975, et Jon Bentley raconte que cela a été fait en un après-midi
• La première version découpait le fichier d’entrée en un flux de mots, supprimait les nombres et caractères spéciaux, convertissait en minuscules, triait, supprimait les doublons, puis vérifiait la présence de chaque mot dans un dictionnaire sur disque
• Cette approche simple fondée sur des accès disque était lente et manquait aussi de précision
• Pour améliorer les performances et la précision, McIlroy a repensé deux éléments
  • un algorithme réduisant les mots à leur racine en supprimant préfixes et suffixes
  • une structure de données compressée permettant de charger le dictionnaire en mémoire et de l’interroger rapidement

Algorithme de suppression des préfixes et suffixes

• La méthode de racination de McIlroy supprimait de manière répétée les préfixes et suffixes fréquents d’un mot, puis vérifiait si la forme réduite était présente dans le dictionnaire
• Par exemple, misrepresented devient present après suppression des préfixes mis, re et du suffixe ed
• Si present est dans le dictionnaire, le mot d’origine n’est pas signalé comme faute de frappe
• Cette méthode n’était pas exacte à 100 % et pouvait laisser passer certaines erreurs, mais cela était jugé acceptable à l’époque
• Des règles d’exception ont aussi été implémentées pour éviter les erreurs fréquentes
• Le dictionnaire final a été réduit à 25 000 mots, une taille qui pouvait tenir en mémoire avec une structure bien conçue

Recherche basée sur un Bloom filter

• La première structure en mémoire utilisée par McIlroy était le Bloom filter, appelé dans les articles de l’époque « superimposed code scheme »
• L’article sur le Bloom filter a été publié en 1970, et spell d’Unix a été développé au milieu des années 1970
• Cette implémentation a été fournie par Dennis Ritchie
• Un Bloom filter initialise une table de bits à 0, puis applique plusieurs fonctions de hachage à chaque élément pour positionner les bits correspondants à 1
• Lors d’une recherche, les mêmes fonctions de hachage sont appliquées
  • si un seul bit vaut 0, l’élément n’existe pas
  • si tous les bits valent 1, il peut exister, mais il reste un risque de faux positif
• Un Bloom filter classique nécessite ensuite une consultation du vrai dictionnaire pour traiter les faux positifs, mais dans un correcteur orthographique, la plupart des mots existent dans le dictionnaire, ce qui peut rendre ces consultations très fréquentes
• McIlroy a donc abaissé suffisamment le taux de faux positifs pour supprimer complètement cette consultation supplémentaire
  • taux de faux positifs visé : 1/2000
  • nombre de mots du dictionnaire : 25 000
  • taille de la table de bits : 400 000 bits
  • nombre de fonctions de hachage : 11
• Cette combinaison permettait d’atteindre un taux de faux positifs d’environ 1/2000

Les limites du Bloom filter et l’approche par hachages compressés

• L’approche Bloom filter a été utilisée pendant un temps, mais le dictionnaire a continué à s’enrichir, passant de 25 000 à 30 000 mots
• Pour conserver le même taux de faux positifs, il aurait fallu une table de bits plus grande, ce qui était difficile avec les contraintes mémoire
• McIlroy est alors passé à une méthode consistant à stocker uniquement les valeurs de hachage des mots plutôt qu’une table de hachage complète
• La recherche fonctionnait en calculant le hachage du mot d’entrée, puis en vérifiant sa présence dans la liste des hachages stockés
• Pour réduire le risque de collision, il fallait un code de hachage suffisamment grand
  • la taille du dictionnaire v était d’environ 30 000, soit environ 2^15
  • la probabilité de collision acceptable était 1 / 2^12
  • la taille de hachage nécessaire était de 27 bits
• Stocker 30 000 hachages de 27 bits ne tenait pas dans les 64 KB de RAM du PDP-11, ce qui rendait la compression indispensable

Limite théorique de compression

• McIlroy a d’abord calculé le nombre minimal théorique de bits nécessaire pour stocker l’ensemble des codes de hachage
• Si un code de hachage a une taille de b bits, il existe 2^b hachages possibles, et l’on convertit en quantité d’information le nombre de façons d’en choisir v distincts
• Le calcul utilise l’approximation de Stirling et l’hypothèse simplificatrice v « 2^b
• En remplaçant v=30 000 et b=27, on obtient un minimum de 13,57 bits pour stocker un seul code de hachage
• C’est environ 50 % plus court que les 27 bits d’origine, et suffisamment compact pour tenir dans la mémoire du PDP-11

Stockage des différences de hachage et recherche

• Au lieu de compresser directement les codes de hachage bruts, McIlroy a stocké les différences entre codes de hachage triés
• Exemple :

sorted hash codes: 5, 14, 21, 32, 55, 67
hash differences: 5, 9, 7, 11, 23, 12

• Cette méthode avait deux avantages
  • les différences sont plus petites que les codes de hachage d’origine
  • une même différence peut se répéter entre plusieurs paires de hachages
• Pour rechercher un mot, on calcule son hachage puis on additionne les différences depuis le début
  • si la somme cumulée est égale au hachage recherché, il est présent
  • si la somme cumulée dépasse ce hachage, il est absent
• Cette méthode réduit l’espace occupé, mais la recherche peut devenir plus lente, car il faut décoder et accumuler les valeurs compressées depuis le début

Modélisation des différences de hachage par une loi géométrique

• Une compression sans perte est plus efficace quand les valeurs fréquentes reçoivent des codes courts et les valeurs rares des codes plus longs
• Une compression classique fondée sur une table de distribution de probabilités ne convenait pas aux contraintes de McIlroy
  • conserver en mémoire une table de distribution pour environ 30 000 symboles aurait annulé le gain de compression
  • calculer les fréquences et probabilités des différences aurait nécessité une structure sur disque coûteuse
• McIlroy a exploité le fait que les différences de hachage suivent une loi géométrique
• L’espace de hachage contient 2^b positions, dans lesquelles se répartissent v codes de hachage
  • la probabilité qu’une position contienne un hachage est q = v / 2^b
  • la probabilité qu’elle soit vide est p = 1 - v / 2^b
• Une différence k apparaît quand les k-1 positions après un hachage sont vides, et que le hachage suivant se trouve à la k-ième position
• La probabilité de la différence k vaut donc p^(k-1)q, ce qui correspond à une loi géométrique

Compression des différences avec un code de Golomb

• McIlroy a compressé les différences de hachage avec un code de Golomb, bien adapté aux entiers suivant une loi géométrique
• L’article de Golomb publié en 1965 proposait une méthode simple de codage par longueur d’exécution pour ce type de valeurs
• Dans une loi géométrique, la probabilité décroît exponentiellement ; on peut donc regrouper les valeurs par blocs de taille m et augmenter la longueur du code d’un bit à chaque bloc suivant
• L’implémentation de spell sur Unix utilisait un algorithme d’encodage et de décodage différent de celui de l’article de Golomb, un peu plus complexe mais plus efficace
• L’implémentation d’origine de SVR4 peut être consultée ici
  • implémentation de l’encodage
  • implémentation du décodage
• Le code de Golomb comprimait les différences de hachage à une longueur de code espérée de 13,60 bits par mot
• C’est très proche du minimum théorique de 13,57 bits

Découpage en bins pour accélérer la recherche

• Utiliser uniquement la table compressée des différences oblige à décoder et accumuler depuis le début à chaque recherche, ce qui est lent
• L’implémentation finale de spell sur Unix divisait la table des différences en M bins
• Lors d’une recherche, on localisait d’abord le bon bin, puis on ne balayait que celui-ci
• Cette méthode multipliait la vitesse de recherche par M
• En contrepartie, il fallait stocker des pointeurs vers les bins, soit un surcoût de log₂M bits par mot
• Le stockage total montait ainsi à environ 14 bits par mot, un compromis offrant des recherches bien plus rapides tout en restant dans le budget mémoire

Une conception guidée par les contraintes

• spell sur Unix est un exemple de conception combinant Bloom filter, théorie de l’information, théorie des probabilités et compression de Golomb
• Le développement a suivi la progression suivante
  • atteindre un faible taux de faux positifs avec un Bloom filter
  • passer à une approche par hachages compressés quand le dictionnaire a grandi
  • calculer le minimum théorique de bits nécessaire pour stocker les hachages
  • reconnaître la distribution des différences de hachage
  • obtenir une compression presque optimale avec un code de Golomb
  • accélérer la recherche via le découpage en bins avec un faible surcoût mémoire
• Les correcteurs orthographiques modernes utilisent d’autres techniques comme l’edit distance ou les modèles de langue, mais spell sur Unix reste un exemple marquant de système efficace né de la combinaison entre compréhension théorique et contraintes pratiques

[GN⁺]

Avis sur Hacker News

• On peut créer un correcteur orthographique à mémoire externe avec très peu de RAM : il suffit de trier les mots du document, d’éliminer les doublons, puis de fusionner le tout avec un dictionnaire trié pour ne garder que les mots absents
  J’avais vu cette méthode dans un exemple en BASIC de Creative Computing, et comme je l’avais fait tourner sur un TRS-80 Color Computer qui disposait de bien moins de 32 KB de RAM utilisable, c’est à ça que j’ai pensé en voyant le titre
  À l’époque, Turbo Lightning impressionnait beaucoup de monde : son dictionnaire compressé tenait en mémoire à côté des autres programmes sur PC et vérifiait l’orthographe pendant la saisie
  Le PC avait la limite des 640 KB, mais pour ne pas gêner les autres programmes, il fallait n’en utiliser qu’une partie, et au début de l’ère PC, remplir complètement cette mémoire n’était pas non plus facile financièrement

  • L’article traite aussi cette alternative comme première preuve de concept et en souligne les limites : « À cause d’une implémentation simple, la précision n’était pas très élevée, et c’était lent car il fallait faire des consultations du dictionnaire sur disque »
  • J’ai l’impression qu’ils profitaient du grand nombre de mots répétés pour contenir le nombre d’octets. Sur le C=64 à l’époque, dès qu’on dépassait un texte d’une ou deux pages, le seul corps du document risquait déjà de saturer la mémoire, donc conserver une seconde copie triée semblait assez luxueux
    On aurait pu imaginer une stratégie consistant à enregistrer d’abord une copie de travail sur disque, à la trier, à la comparer, puis à la recharger, mais j’imagine que les développeurs sur C=64 évitaient ce genre d’approche parce que l’interface disque était bien trop lente

• Il y a ce passage expliquant qu’à l’époque, les Bloom filters ne s’appelaient pas encore ainsi et que Douglas parlait dans son article de « superimposed code scheme », mais un filtre de Bloom n’est qu’un type particulier de superimposed code
  Calvin Mooers a développé le codage superposé aléatoire dans son mémoire de master au MIT dans les années 1940, directement sous l’influence de Shannon
  L’excellent livre de Bourne de 1963, “Methods of Information Handling”, en donne les détails mathématiques
  Je suis sûr que Douglas connaissait la technique plus générale. Par exemple, l’auteur de “The Large Data Base File Structure Dilemma” (1975) la qualifiait aussi de http://dx.doi.org/10.1021/ci60001a005 « vieille technique appelée super-imposed coding »
  Le qualificatif « aléatoire » est important ici, car il existait déjà des superimposed codes avant Mooers, mais ils n’étaient ni très intéressants mathématiquement ni très importants en pratique

• C’est trop intelligent pour du “worse is better”. Il faut penser plus mauvais encore
  La bande passante de la mémoire principale et celle du disque étaient presque identiques, toutes deux à un peu plus de 1 MB/s
  À leur place, j’aurais sans doute choisi une approche en plusieurs passes, mais j’aurais probablement quand même utilisé un filtre de Bloom, parce que c’est élégant
  https://github.com/arnoldrobbins/v10spell
  https://code.google.com/archive/p/unix-spell/
  L’article d’origine est excellent aussi : https://www.semanticscholar.org/paper/Development-of-a-Spelling-List-McIlroy/e08c8a4c17f23c41616649ca73a908d06828d67f
  Il est aussi disponible sur sa page web : https://www.cs.dartmouth.edu/~doug/
  https://en.wikipedia.org/wiki/Douglas_McIlroy
  Si vous êtes passionné de mots, vous finirez peut-être aussi sur ce tableau des formes de feuilles en cherchant “obovate”
  https://upload.wikimedia.org/wikipedia/commons/e/e8/Leaf_morphology.svg

• Je ne me souviens plus du nom du produit, mais il existait dans les années 1980 un correcteur orthographique matériel pour IBM PC. C’était un boîtier branché entre le clavier et le PC, qui émettait un bip dès qu’on tapait une chaîne qu’il ne reconnaissait pas comme un mot du dictionnaire

  • Il s’agissait de Xerox PC Type Right
    Il y a un test page 237 de https://vintageapple.org/pcworld/pdf/PC_World_8711_November_1987.pdf. Attention, gros PDF

• L’un des éléments qui m’ont donné envie de m’intéresser à Unix, c’était un article de Byte au début des années 1980. Il montrait comment construire un correcteur orthographique avec une pipeline split/sort/comm, en gros avec sept commandes
  Les PC 8 bits n’avaient absolument rien de tel, mais une fois qu’on le voit, on a l’impression que ça ne demandait pas une complexité si extraordinaire

  • Dans le même esprit, il existe une vidéo d’époque où Brian Kernighan montre comment construire un correcteur orthographique avec une ligne de commande du shell UNIX
    https://youtu.be/tc4ROCJYbm0?t=4m56s

• Je viens seulement de finir l’article, et voilà ce qui me semble être l’essentiel : il y a un « dictionnaire » de 30 000 mots et, si l’on accepte un taux de faux positifs d’environ 1/4000, on peut hacher chaque mot en une chaîne de 27 bits, c’est-à-dire un entier, jeter le dictionnaire et ramener le problème au stockage d’un ensemble de 30 000 chaînes de 27 bits
  De manière assez surprenante, la théorie de l’information dit que 30 000 chaînes de 27 bits peuvent être stockées non pas avec 27 bits par mot, mais avec seulement environ 13,57 bits. Je comprends les maths (https://www.wolframalpha.com/input?i=log_2%282%5E27+choose+30000%29%2F30000), mais comme 30 000 est minuscule par rapport à 2^27, soit environ 134 millions, il me faudrait sans doute du temps pour accepter intuitivement d’où vient ce gain
  Pour encoder ce sous-ensemble de 30 000 hachages de 27 bits, ils ont utilisé les écarts entre hachages, et comme ces écarts suivent une loi géométrique, ils ont obtenu environ 13,6 bits réels par mot avec un codage de Golomb adapté à une entrée géométriquement distribuée
  Je me suis demandé s’il serait possible de faire mieux en principe, dans une direction du type « hachage parfait ». Peut-être pourrait-il exister une fonction qui prend des mots alphabétiques, leur applique une transformation, puis permet de vérifier facilement si le hachage obtenu appartient à un bon ensemble
  Mais en y repensant, puisqu’il faut un taux de faux positifs, le hachage doit faire au moins 27 bits pour éviter qu’un mot absent du dictionnaire ne soit mappé vers un ensemble « bon ». Cette approche semble donc fondamentalement optimale en théorie. À moins qu’il n’existe un moyen de mapper chaque mot sur un entier de 27 bits tout en faisant en sorte que les bonnes chaînes soient, par exemple, celles dont la valeur est inférieure à 30000 ?

• À titre indicatif, vers 1983, Grammatik sur CP/M tournait avec moins de 64 KB et faisait de la « vérification grammaticale » sur des systèmes 8 bits. En réalité, c’était plutôt un correcteur orthographique enrichi de règles de système expert
  Ce qui m’a marqué, c’est que j’avais creusé les parties intéressantes et que c’était écrit en Forth, ce qui expliquait en partie pourquoi ça pouvait être si petit ; il y avait suffisamment d’interpréteur externe dans le produit pour qu’avec un peu d’édition hexadécimale on puisse s’en servir comme d’un interpréteur Forth avec des fonctions spécialisées préchargées

  • Sur mon système CP/M avec 64 KB de RAM, l’éditeur WordStar incluait un correcteur orthographique SPELL.COM de 2023 octets
    Je ne l’ai pas décompilé pour voir comment il fonctionnait, mais il est petit, rapide et marche bien

• Je me demande quelles fautes de frappe courantes sont ratées à cause du hachage
  À ce sujet, il existe aussi un concours de compression du dictionnaire de Wordle : http://golf.horse/wordle/

• J’ai vécu quelque chose de similaire au milieu des années 80. Rapide est une notion relative
  Il y avait beaucoup de données, 640 KB de RAM, un heap de 64 KB et une pile de 64 KB. Il fallait chercher et extraire des données dans plusieurs centaines de Mo, puis en fusionner une partie
  J’ai expérimenté avec une structure d’index sous forme d’arbre ternaire. En théorie, cela avait du sens, mais à l’implémentation, rien que les relations et les informations de chemin prenaient trop de place pour tenir dans 64 KB
  J’ai choisi le swapping plutôt que la compression. J’ai écrit un TSR, en gros l’équivalent d’un service aujourd’hui, pour traiter un bloc de données, extraire les résultats et les stocker dans la pile, puis jeter les données sources et envoyer un appel d’interruption au TSR. Le TSR vidait alors le heap, lisait le bloc suivant depuis le stockage, puis rendait la main au programme, qui le traitait, le combinait avec les données de la pile, et répétait jusqu’à la fin
  À l’origine, ce travail demandait environ une semaine à 3 opérateurs de saisie, plus un expert pour recouper les informations. Imaginez une douzaine de classeurs à anneaux de 3 pouces remplis de tableaux. Le programme terminait en quelques heures et c’était étonnamment « rapide »
  Tout cela sur un système monothread
  https://en.wikipedia.org/wiki/Terminate-and-stay-resident_program

• Je me souviens avoir utilisé l’option -b dans UNIX spell pour obtenir l’orthographe britannique. Il n’y avait que deux options de langue, et je me demande pourquoi ce choix a été fait, comment le code le gérait, et d’où venaient les dictionnaires respectifs
  Les Australiens et les Néo-Zélandais utilisaient-ils l’orthographe britannique ou américaine ?
  UNIX spell, c’était un peu le ZX81 1K Chess de la correction orthographique, et sur les ordinateurs domestiques il n’y avait pas tant de correcteurs que ça avant l’arrivée de MS Word pour Windows 3.1. Avant cela, au bureau, les secrétaires tapaient sous WordPerfect et servaient de correcteurs orthographiques humains pour chaque manager et chaque équipe
  À la maison, en revanche, avec une imprimante matricielle et un écran qui clignotait, j’ai traversé les débuts de l’informatique en m’en sortant à peu près avec un dictionnaire papier. Tout le monde savait orthographier à l’époque, donc je n’ai pas le souvenir que la correction orthographique était si importante. Dans une école de mille élèves, il n’y avait qu’un seul enfant qui prétendait être dyslexique, et cela donnait une excuse plausible pour ne pas savoir écrire correctement
  Peut-être que les années 1980 ont été l’âge d’or de la littératie, et que la date précise du début du déclin en orthographe est le jour où UNIX spell a été écrit
  J’aime le Scrabble. C’est un problème très différent de la correction orthographique, mais le traitement partage quelques étapes avec UNIX spell. On cherche des préfixes et suffixes fréquents pour les accrocher à d’autres éléments sur le chevalet ou le plateau
  Le dictionnaire du Scrabble ressemble aussi un peu à UNIX spell, dans le sens où ce n’est qu’une grande liste de mots sans définition. La seule chose importante, c’est de savoir si un mot donné est dans le livre. Il existe aussi quelques tables de consultation spéciales, comme les 102 mots de deux lettres

  • Je me souviens avoir fait vérifier l’orthographe de dissertations au lycée en 1984 sur Commodore 64 avec Paperclip 64. C’était avant Microsoft Windows
    Comme le dictionnaire était lu depuis le disque pendant la vérification, cela prenait quelques minutes, après quoi on pouvait parcourir les mots non reconnus