Cómo cabía el corrector ortográfico de Unix en 64 kB de RAM
En la década de 1970, los ingenieros de los Laboratorios Bell de AT&T enfrentaron un reto técnico que parecía imposible: desarrollar un corrector ortográfico funcional para Unix que pudiera operar con apenas 64 kB de memoria RAM, una limitación propia de los computadores PDP-11 de la época. La solución, obra del ingeniero Douglas McIlroy, se convirtió en un hito de la ingeniería de software y un precedente en el uso de técnicas de compresión y estructuras de datos eficientes.
El contexto es clave para entender la magnitud del desafío. Cuando Ken Thompson y Dennis Ritchie promocionaron Unix ante el departamento de patentes de AT&T como un sistema de procesamiento de textos, resultaba indispensable contar con una herramienta de revisión ortográfica. La primera versión, escrita por Steve Johnson en 1975 —según relata Jon Bentley, en una sola tarde—, era funcional pero imprecisa y lenta, ya que realizaba las búsquedas del diccionario directamente en disco.
McIlroy asumió la tarea de reescribir el programa con un doble objetivo: mejorar la precisión y acelerar las consultas. Su primera gran innovación fue un algoritmo de eliminación de afijos (prefijos y sufijos) que reducía las palabras a sus raíces antes de consultarlas. De este modo, una palabra como "misrepresented" se reducía a "present" al quitarle los afijos "mis", "re" y "ed". Aunque no era infalible, el sistema redujo el diccionario completo a apenas 25.000 palabras, una fracción del original, con una precisión aceptable para la época.
El segundo frente fue el diseño de una estructura de datos compacta para almacenar ese diccionario en memoria y permitir búsquedas rápidas. La primera aproximación de McIlroy fue un filtro de Bloom —aunque en su artículo original lo denominó "esquema de código superpuesto"—, una estructura probabilística descrita por Burton Bloom en 1970. Curiosamente, la implementación concreta del filtro que utilizó fue proporcionada por el propio Dennis Ritchie, lo que convierte al corrector de Unix en uno de los primeros usos productivos de esta estructura de datos.
El filtro de Bloom permitía descartar rápidamente las palabras que no estaban en el diccionario con una tasa de falsos positivos tan baja que, en la práctica, resultaba viable saltarse las búsquedas reales en el diccionario para las palabras más comunes. Sin embargo, cuando el diccionario creció hasta las 30.000 palabras, el filtro dejó de ser práctico por el excesivo consumo de memoria.
Fue entonces cuando McIlroy desarrolló su contribución más trascendente: un esquema de compresión de códigos hash prácticamente óptimo desde el punto de vista teórico. Calcularon que un hash de 27 bits por palabra ofrecía una probabilidad de colisión aceptablemente baja, pero almacenar 30.000 hashes de 27 bits habría requerido unos 100 kB, muy por encima de la capacidad disponible. McIlroy descubrió que las diferencias entre los códigos hash ordenados seguían una distribución geométrica. Aplicando el código de Golomb —un esquema de compresión diseñado específicamente para ese tipo de distribuciones—, logró reducir cada palabra a 13,60 bits, apenas 0,03 bits por encima del mínimo teórico posible de 13,57 bits. Ningún algoritmo posterior ha conseguido superar esa marca.
Finalmente, añadió una partición de los datos comprimidos que permitía acelerar las búsquedas a costa de un ligero aumento de memoria, situando el tamaño final en torno a los 14 bits por palabra.
El legado de este trabajo trasciende la historia de Unix. Demuestra cómo el análisis desde primeros principios, la combinación de conocimientos lingüísticos y matemáticos, y el diseño de estructuras de datos a medida pueden convertir una limitación técnica aparentemente insalvable en una solución elegante. En palabras del propio análisis técnico publicado en el blog Coding Confessions, se trata de "una clase magistral de ingeniería bajo restricciones".
Más de cinco décadas después, con memorias millones de veces mayores y algoritmos de compresión genéricos como gzip incapaces de comprimir el diccionario por debajo de los 85 kB, la solución ideada por McIlroy sigue siendo referente obligado en cualquier discusión sobre eficiencia computacional extrema.