Unix spell ejecutado con 64 kB de RAM

Cómo logró ejecutarse Unix Spell con 64 kB de RAM

¿Cómo se puede hacer caber un diccionario en 64 kB de RAM?

• Los ingenieros de Unix resolvieron el problema de hacer caber un diccionario de 250 kB en 64 kB de RAM usando estructuras de datos y técnicas de compresión.
• En la década de 1970, Douglas McIlroy se enfrentó a este problema al implementar el corrector ortográfico de Unix en AT&T.
• Aprovechó las características de los datos para desarrollar un algoritmo de compresión que se acercaba al límite teórico de compresión.

TL;DR

• El corrector ortográfico de Unix comenzó como un prototipo creado por Steve Johnson de AT&T en la década de 1970.
• McIlroy desarrolló un algoritmo de stemming basado en el lenguaje para reducir el diccionario a 25,000 palabras.
• Para búsquedas rápidas se usó un filtro de Bloom, con una implementación proporcionada por Dennis Ritchie.
• Cuando el diccionario creció a 30,000 palabras, el enfoque con filtro de Bloom se volvió ineficiente y se introdujo una técnica de compresión por hashing.
• Usando códigos hash de 27 bits para reducir la probabilidad de colisiones y el código de Golomb, se logró una compresión de 13.60 bits por palabra.

El origen del comando de ortografía de Unix

• Unix fue propuesto al departamento de patentes de AT&T como un sistema de procesamiento de texto, y se necesitaba un corrector ortográfico.
• La versión inicial fue escrita por Steve Johnson en 1975, pero su precisión era baja.
• Douglas McIlroy reescribió el proyecto para mejorar la precisión y el rendimiento.

Algoritmo de eliminación de prefijos

• McIlroy desarrolló un algoritmo que eliminaba prefijos y sufijos comunes de las palabras para consultar el diccionario.
• Este método no era 100% preciso, pero en ese momento se consideraba aceptable.

Búsqueda basada en filtros de Bloom

• El filtro de Bloom ahorraba memoria y permitía búsquedas rápidas.
• Se utilizó para cargar en 64 kB de RAM un diccionario de 25,000 palabras.
• El filtro de Bloom se ajustó para mantener una baja tasa de falsos positivos.

Técnica de hashing comprimido para consultar el diccionario

• Cuando el tamaño del diccionario aumentó a 30,000 palabras, hizo falta una estructura de datos más eficiente en memoria.
• McIlroy usó un método que ahorraba memoria almacenando las diferencias entre códigos hash.
• Comprimió las diferencias de hash usando el código de Golomb.

Conclusión

• El comando de ortografía de Unix es una historia de ingeniería fascinante nacida de las limitaciones de memoria del PDP-11.
• Ofreció una solución elegante que combinaba filtros de Bloom, teoría de la información, teoría de la probabilidad y algoritmos de compresión.
• Demuestra que, cuando hay restricciones de recursos, es posible resolver problemas con gran profundidad.

[GN⁺]

Comentarios en Hacker News

• El filtro de Bloom originalmente se llamaba "superimposed code scheme", y es un tipo específico de superimposed code

  • Calvin Mooers desarrolló la codificación superpuesta aleatoria en el MIT en la década de 1940, influenciado por el trabajo de Shannon
  • El libro de Bourne de 1963, "Methods of Information Handling", ofrece los detalles matemáticos
  • Es muy probable que Douglas conociera esta técnica

• Es posible implementar un corrector ortográfico con memoria externa usando poca RAM

  • Funciona ordenando las palabras del documento, eliminando las duplicadas y luego mezclándolas con el diccionario para conservar solo las palabras faltantes
  • Lo hicieron funcionar en una TRS-80 Color Computer con menos de 32k de RAM
  • Turbo Lightning hacía corrección ortográfica mientras se escribía en PC usando un diccionario comprimido

• El ancho de banda de memoria y el del disco eran similares, y el trabajo podía hacerse en varias pasadas

  • Usar un filtro de Bloom era una buena forma de hacerlo

• Había correctores ortográficos por hardware para IBM PC en la década de 1980

  • Se conectaban entre el teclado y la PC, y emitían un pitido cuando escribías una palabra que no reconocían

• Unix fue propuesto a AT&T como un sistema de procesamiento de texto, y necesitaba un corrector ortográfico

  • UNIX se usaba principalmente para procesamiento de texto

• Un artículo de Byte de principios de la década de 1980 explicaba cómo hacer el corrector ortográfico de Unix

  • Las PC de 8 bits no tenían este tipo de funciones

• Puede haber errores tipográficos comunes que se escapen debido al hashing

  • Existe una competencia sobre compresión de diccionarios de Wordle

• A mediados de la década de 1980, se procesaban datos con 640KB de RAM y 64KB de heap y stack

  • Extraer y combinar los datos tomaba horas, y se hacía en un sistema de un solo hilo

• Alrededor de 1983, Grammatik en CP/M corría con menos de 64k e incluía revisión gramatical y reglas de sistema experto

  • Estaba escrito en Forth y era muy compacto

• La primera versión de UNIX requería 24kB, de los cuales la mitad la ocupaba el kernel