Unix spell rodando em 64 kB de RAM

Como o Unix Spell rodava em 64 kB de RAM

Como encaixar um dicionário em 64 kB de RAM?

• Engenheiros do Unix resolveram o problema de encaixar um dicionário de 250 kB em 64 kB de RAM usando estruturas de dados e técnicas de compressão.
• Na década de 1970, Douglas McIlroy se deparou com esse problema ao implementar o verificador ortográfico do Unix na AT&T.
• Ele desenvolveu um algoritmo de compressão que se aproximava do limite teórico de compressão ao explorar as características dos dados.

TL;DR

• O verificador ortográfico do Unix começou como um protótipo feito por Steve Johnson na AT&T nos anos 1970.
• McIlroy desenvolveu um algoritmo de radicalização baseado na língua para reduzir o dicionário a 25.000 palavras.
• Um filtro de Bloom foi usado para buscas rápidas, com implementação fornecida por Dennis Ritchie.
• Quando o dicionário cresceu para 30.000 palavras, a abordagem com filtro de Bloom se tornou ineficiente e uma técnica de compressão por hashing foi adotada.
• Com códigos hash de 27 bits para reduzir a probabilidade de colisões, e usando o código de Golomb, foi alcançada uma compressão de 13,60 bits por palavra.

A origem do comando de ortografia do Unix

• O Unix foi proposto ao departamento de patentes da AT&T como um sistema de processamento de texto, e era necessário um verificador ortográfico.
• A versão inicial foi escrita por Steve Johnson em 1975, mas tinha baixa precisão.
• Douglas McIlroy reescreveu o projeto para melhorar a precisão e o desempenho.

Algoritmo de remoção de prefixos

• McIlroy desenvolveu um algoritmo que removia prefixos e sufixos comuns das palavras para consultar o dicionário.
• Esse método não era 100% preciso, mas era aceitável para a época.

Busca baseada em filtro de Bloom

• O filtro de Bloom economizava memória e permitia buscas rápidas.
• Ele foi usado para carregar um dicionário de 25.000 palavras em 64 kB de RAM.
• O filtro de Bloom foi ajustado para manter uma baixa taxa de falsos positivos.

Técnica de hashing comprimido para consulta ao dicionário

• Quando o tamanho do dicionário aumentou para 30.000 palavras, foi necessária uma estrutura de dados mais eficiente em memória.
• McIlroy usou um método de economizar memória armazenando as diferenças entre códigos hash.
• O código de Golomb foi usado para comprimir essas diferenças de hash.

Conclusão

• O comando de ortografia do Unix é uma história fascinante de engenharia nascida das restrições de memória do PDP-11.
• Ele ofereceu uma solução elegante ao combinar filtro de Bloom, teoria da informação, teoria das probabilidades e algoritmos de compressão.
• Mostra que é possível fazer uma resolução profunda de problemas quando há restrições de recursos.

[GN⁺]

Comentários do Hacker News

• O filtro de Bloom era originalmente chamado de "superimposed code scheme", e é um tipo específico de superimposed code

  • Calvin Mooers desenvolveu a codificação superimposta aleatória no MIT nos anos 1940, influenciado pelo trabalho de Shannon
  • O livro de Bourne de 1963, "Methods of Information Handling", fornece os detalhes matemáticos
  • É bem provável que Douglas conhecesse essa técnica

• É possível implementar um corretor ortográfico com memória externa usando pouca RAM

  • A abordagem consiste em ordenar as palavras do documento, remover as palavras únicas e depois mesclar com o dicionário para manter apenas as palavras ausentes
  • Foi feito funcionar no TRS-80 Color Computer com menos de 32k de RAM
  • O Turbo Lightning fazia verificação ortográfica enquanto se digitava no PC usando um dicionário comprimido

• A largura de banda da memória e a do disco eram parecidas, e era possível fazer o trabalho com várias passadas

  • Usar um filtro de Bloom é uma boa forma de fazer isso

• Havia um corretor ortográfico em hardware para IBM PC nos anos 1980

  • Ele ficava entre o teclado e o PC, e emitia um bip ao digitar uma palavra que não reconhecia

• O Unix foi proposto à AT&T como um sistema de processamento de texto, e precisava de um corretor ortográfico

  • O UNIX era usado principalmente para processamento de texto

• Um artigo da Byte no início dos anos 1980 explicava como criar o corretor ortográfico do Unix

  • PCs de 8 bits não tinham esse tipo de recurso

• Pode haver erros de digitação comuns que passam despercebidos por causa do hashing

  • Existe uma competição sobre compressão de dicionário do Wordle

• Em meados dos anos 1980, os dados eram processados com 640KB de RAM e 64KB de heap e stack

  • Levaram horas para extrair e combinar os dados, em um sistema single-thread

• Por volta de 1983, no CP/M, o Grammatik rodava com menos de 64k e incluía verificação gramatical e regras de sistema especialista

  • Foi escrito em Forth e era muito compacto

• A primeira versão do UNIX precisava de 24kB, e metade disso era ocupada pelo kernel