Unix spell rodou em 64KB de RAM

• Na década de 1970, o spell do Unix da AT&T precisava consultar rapidamente um dicionário de 250KB dentro dos 64KB de RAM do PDP-11, e Douglas McIlroy resolveu isso explorando as características dos dados em vez de usar compressão genérica
• O protótipo inicial de Steve Johnson era baseado em disco, então era lento e pouco preciso, mas McIlroy melhorou desempenho e precisão ao reduzir o dicionário para cerca de 25.000 palavras com radicalização
• A primeira estrutura em memória foi um Bloom filter implementado por Dennis Ritchie, com uma tabela de 400.000 bits e 11 funções de hash, alcançando uma taxa de falso positivo de cerca de 1/2000 e eliminando a necessidade de consultar um dicionário separado
• Quando o dicionário cresceu para 30.000 palavras, ficou difícil manter as restrições de memória usando apenas Bloom filter, então os hashes de 27 bits passaram a ser ordenados e os deltas de hash comprimidos com código de Golomb
• A implementação final dividiu a tabela comprimida de deltas em vários bins para acelerar as buscas, permitindo verificação ortográfica rápida dentro de 64KB com cerca de 14 bits de armazenamento por palavra

---

A limitação de memória enfrentada pelo Unix spell

• O problema central era consultar rapidamente um dicionário de 250KB em um ambiente com 64KB de RAM
• Mesmo aplicando uma compressão moderna como gzip -9, esse arquivo não fica abaixo de 85KB
• No PDP-11 dos anos 1970, não era possível colocar o dicionário inteiro na memória, e consultas baseadas em disco eram lentas
• Em vez de compressão genérica, McIlroy projetou uma estrutura de dados especializada que aproveitava a estrutura e a distribuição de probabilidade dos dados do dicionário

O Unix spell inicial e a redução do dicionário com base em radicais

• Quando a AT&T propôs o Unix como um sistema de processamento de texto para o departamento de patentes, surgiu a necessidade de um verificador ortográfico
• Steve Johnson escreveu o primeiro protótipo do Unix spell em 1975, e Jon Bentley relata que esse trabalho foi feito em uma tarde
• A versão inicial dividia o arquivo de entrada em um fluxo de palavras, removia números e caracteres especiais, convertia para minúsculas, ordenava, removia duplicatas e então verificava a existência das palavras em um dicionário em disco
• Essa abordagem simples de consulta em disco era lenta e também tinha baixa precisão
• Para melhorar desempenho e precisão, McIlroy redesenhou duas partes
  • um algoritmo que removia prefixos e sufixos para reduzir palavras ao radical
  • uma estrutura de dados comprimida para manter o dicionário em memória e consultá-lo rapidamente

Algoritmo de remoção de prefixos e sufixos

• O método de radicalização de McIlroy removia repetidamente prefixos e sufixos comuns de uma palavra e então verificava se a forma reduzida existia no dicionário
• Por exemplo, misrepresented vira present após remover os prefixos mis, re e o sufixo ed
• Se present estivesse no dicionário, a palavra original não seria marcada como erro de digitação
• Esse método não era 100% preciso e podia deixar alguns erros passarem, mas na época isso foi considerado aceitável
• Regras de exceção também foram implementadas para evitar erros comuns
• O dicionário final foi reduzido para 25.000 palavras, um tamanho que podia caber na memória com uma estrutura de dados bem projetada

Consultas com Bloom filter

• A primeira estrutura em memória usada por McIlroy foi o Bloom filter, chamado no artigo da época de “superimposed code scheme”
• O artigo sobre Bloom filter foi publicado em 1970, e o Unix spell foi desenvolvido em meados dos anos 1970
• Essa implementação foi fornecida por Dennis Ritchie
• O Bloom filter inicializa uma tabela de bits com zeros e, para cada item, aplica várias funções de hash para marcar os bits correspondentes com 1
• Na consulta, as mesmas funções de hash são aplicadas
  • se ao menos um bit estiver em 0, o item não existe
  • se todos os bits estiverem em 1, ele pode existir, mas ainda há possibilidade de falso positivo
• Em um Bloom filter comum, seria necessário consultar o dicionário real para tratar falsos positivos, mas em um verificador ortográfico a maioria das palavras está no dicionário, então isso poderia exigir muitas consultas ao dicionário completo
• McIlroy reduziu a taxa de falso positivo o suficiente para eliminar a consulta ao dicionário real
  • taxa de falso positivo aceitável: 1/2000
  • número de palavras no dicionário: 25.000
  • tamanho da tabela de bits: 400.000 bits
  • número de funções de hash: 11
• Essa combinação levou a taxa de falso positivo para cerca de 1/2000

Limites do Bloom filter e o método de hashes comprimidos

• A abordagem com Bloom filter foi usada por um tempo, mas o dicionário continuou crescendo, passando de 25.000 para 30.000 palavras
• Para manter a mesma taxa de falso positivo, seria necessária uma tabela de bits maior, o que era difícil por causa das restrições de memória
• McIlroy então mudou para uma abordagem que armazenava apenas os valores de hash das palavras, em vez de uma tabela de hash completa
• A consulta funcionava calculando o hash da palavra de entrada e verificando se ele existia na lista de hashes armazenados
• Para reduzir a chance de colisão de hash, era necessário usar códigos de hash suficientemente grandes
  • o tamanho do dicionário v era cerca de 30.000, isto é, aproximadamente 2^15
  • a probabilidade de colisão aceitável era 1 / 2^12
  • o tamanho de hash necessário era de 27 bits
• Armazenar 30.000 hashes de 27 bits não cabia nos 64KB de RAM do PDP-11, então a compressão era indispensável

Limite teórico de compressão

• McIlroy começou calculando o número mínimo teórico de bits necessário para armazenar o conjunto de códigos de hash
• Se o tamanho do hash fosse b bits, haveria 2^b hashes possíveis, e a quantidade de informação podia ser obtida a partir do número de formas de escolher v códigos de hash distintos entre eles
• O cálculo usava a aproximação de Stirling e a suposição simplificadora v « 2^b
• Substituindo v=30.000 e b=27, o valor mínimo necessário para armazenar um único código de hash era de 13,57 bits
• Isso era cerca de 50% menor que o hash original de 27 bits e já ficava dentro da capacidade de memória do PDP-11

Armazenamento de deltas de hash e consulta

• McIlroy não comprimiu diretamente os códigos de hash originais; em vez disso, armazenou os deltas entre hashes ordenados
• O exemplo é o seguinte

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

• Armazenar deltas tinha duas vantagens
  • os valores de delta eram menores que os códigos de hash originais
  • o mesmo valor de delta podia se repetir entre vários pares de hashes
• A consulta funcionava calculando o hash da palavra de entrada e acumulando os deltas a partir do início
  • se a soma acumulada fosse igual ao hash de entrada, ele existia
  • se a soma acumulada ultrapassasse o hash de entrada, ele não existia
• Isso reduzia o espaço de armazenamento, mas podia deixar a consulta mais lenta, já que era preciso decodificar e acumular os valores comprimidos desde o início

Modelagem dos deltas de hash com distribuição geométrica

• Compressão sem perdas tende a ser mais eficiente quando atribui códigos curtos a valores frequentes e códigos longos a valores raros
• Uma compressão genérica baseada em tabela de distribuição de probabilidades não se encaixava nas restrições de McIlroy
  • manter na memória uma tabela de distribuição de probabilidade para cerca de 30.000 símbolos eliminaria o ganho de compressão
  • calcular frequências e probabilidades dos deltas exigiria uma estrutura cara baseada em disco
• McIlroy aproveitou o fato de que os deltas de hash seguem uma distribuição geométrica
• O espaço de hashes tem 2^b posições, distribuídas com v códigos de hash dentro dele
  • a probabilidade de existir um hash em uma posição é q = v / 2^b
  • a probabilidade de a posição estar vazia é p = 1 - v / 2^b
• Um delta k ocorre quando as k-1 posições após um hash estão vazias e a posição k contém o próximo hash
• Portanto, a probabilidade de um delta k é p^(k-1)q, exatamente a forma de uma distribuição geométrica

Compressão dos deltas com código de Golomb

• McIlroy comprimiu os deltas de hash usando código de Golomb, adequado para inteiros com distribuição geométrica
• O artigo de Golomb de 1965 apresentou um método simples de codificação por comprimento de execução para valores com distribuição geométrica
• Como, em uma distribuição geométrica, a probabilidade diminui exponencialmente, é possível agrupar valores em blocos de tamanho m e aumentar o comprimento do código em 1 bit a cada bloco seguinte
• A implementação do Unix spell usava um algoritmo de codificação e decodificação diferente do do artigo original de Golomb: um pouco mais complexo, mas mais eficiente
• A implementação original do SVR4 pode ser vista nos links abaixo
  • Implementação da codificação
  • Implementação da decodificação
• O código de Golomb comprimia os deltas de hash para um comprimento esperado de 13,60 bits por palavra
• Esse resultado ficou muito próximo do mínimo teórico de 13,57 bits

Divisão em bins para acelerar a consulta

• Usar apenas a tabela comprimida de deltas tornava a consulta lenta, porque era necessário decodificar e acumular desde o começo
• A implementação final do Unix spell dividia a tabela de deltas em M bins
• Na consulta, primeiro localizava-se o bin correspondente e depois fazia-se a varredura apenas dentro dele
• Esse método aumentava a velocidade de busca em M vezes
• Em contrapartida, era necessário armazenar ponteiros para os bins, o que acrescentava log₂M bits por palavra
• O armazenamento total subiu para cerca de 14 bits por palavra, mas isso representou um bom compromisso, oferecendo consultas muito mais rápidas dentro do orçamento de memória

O design orientado por restrições mostrado pelo Unix spell

• O Unix spell é um exemplo de projeto que combinou Bloom filter, teoria da informação, teoria das probabilidades e compressão de Golomb
• O processo de desenvolvimento seguiu este fluxo
  • alcançar baixa taxa de falso positivo com Bloom filter
  • migrar para hashes comprimidos quando o dicionário cresceu
  • calcular o mínimo teórico de bits para armazenar hashes
  • reconhecer a distribuição dos deltas de hash
  • alcançar compressão quase ótima com código de Golomb
  • acelerar a consulta com divisão em bins, adicionando apenas um pequeno overhead de espaço
• Verificadores ortográficos modernos usam outras técnicas, como edit distance ou modelos de linguagem, mas o Unix spell continua sendo um exemplo de como combinar entendimento teórico e restrições práticas para criar um sistema eficiente

[GN⁺]

Comentários do Hacker News

• É possível criar um corretor ortográfico com memória externa mesmo com pouquíssima RAM: ordenar as palavras do documento, remover as palavras únicas e depois mesclar com um dicionário ordenado, deixando apenas as palavras ausentes.
  Vi esse método em um exemplo em BASIC da Creative Computing e o fiz funcionar em um TRS-80 Color Computer, que tinha bem menos de 32 KB de RAM disponível; por isso, assim que vi o título, foi a primeira coisa que me veio à cabeça.
  Na época, o Turbo Lightning impressionava as pessoas: ele verificava a ortografia enquanto você digitava, com um dicionário comprimido que cabia junto com outros programas em execução no PC.
  O PC tinha o limite de 640 KB, mas, para não atrapalhar outros programas, era preciso usar só uma parte disso; e, no começo da era do PC, nem era barato preencher toda essa memória.

  • O texto também trata essa alternativa como a primeira prova de conceito e aponta suas desvantagens: “por causa da implementação simples, a precisão não era alta, e era lento porque precisava fazer consultas ao dicionário no disco”
  • Parece que eles aproveitaram o fato de haver muitas palavras repetidas para manter a contagem de bytes sob controle. No antigo C=64, quando um texto passava de 1 ou 2 páginas, já havia o risco de só o corpo do documento estourar a memória, e manter uma segunda cópia ordenada parecia um luxo e tanto.
    Também seria possível salvar primeiro uma cópia de trabalho no disco, ordenar, comparar e depois recarregar, mas imagino que os desenvolvedores do C=64 evitassem essa estratégia porque a interface de disco era lenta demais.

• Há um trecho dizendo que, na época, filtros de Bloom ainda não eram chamados de filtros de Bloom, e que Douglas os chamou no artigo de “superimposed code scheme”; mas um filtro de Bloom é um tipo específico de superimposed code.
  Calvin Mooers, em sua dissertação de mestrado no MIT nos anos 1940, desenvolveu a codificação superimposta aleatória diretamente sob influência de Shannon.
  O excelente livro de Bourne de 1963, “Methods of Information Handling”, traz os detalhes matemáticos.
  Tenho certeza de que Douglas conhecia a técnica mais ampla. Por exemplo, o autor de “The Large Data Base File Structure Dilemma” (1975) também a descreveu em http://dx.doi.org/10.1021/ci60001a005 como “uma técnica antiga chamada super-imposed coding”.
  Aqui, o qualificativo “aleatória” é importante, porque superimposed codes já existiam antes de Mooers, mas não eram matematicamente interessantes nem praticamente importantes.

• Para “worse is better”, isso é inteligente demais. É preciso pensar em algo pior.
  A largura de banda da memória principal e a do disco eram quase iguais, ambas pouco acima de 1 MB/s.
  Eu provavelmente teria feito em várias passagens, mas, ainda assim, filtros de Bloom são legais, então talvez os usasse.
  https://github.com/arnoldrobbins/v10spell
  https://code.google.com/archive/p/unix-spell/
  O artigo original também é excelente: https://www.semanticscholar.org/paper/Development-of-a-Spelling-List-McIlroy/e08c8a4c17f23c41616649ca73a908d06828d67f
  Também está na página dele: https://www.cs.dartmouth.edu/~doug/
  https://en.wikipedia.org/wiki/Douglas_McIlroy
  Se você é fissurado por palavras, ao procurar “obovate” provavelmente também vai acabar vendo este gráfico de formas de folhas:
  https://upload.wikimedia.org/wikipedia/commons/e/e8/Leaf_morphology.svg

• Não lembro o nome do produto, mas nos anos 80 havia um corretor ortográfico em hardware para IBM PC. Era uma caixa conectada entre o teclado e o PC, e apitava quando você digitava uma sequência de caracteres que ele não reconhecia como uma palavra do dicionário.

  • Era o Xerox PC Type Right.
    Há uma análise na página 237 de https://vintageapple.org/pcworld/pdf/PC_World_8711_November_1987.pdf. Atenção: PDF grande.

• Uma das coisas que despertou meu interesse por Unix foi um artigo da Byte, por volta do começo dos anos 1980. Ele mostrava como criar um corretor ortográfico com um pipeline de split/sort/comm, em algo como 7 comandos.
  PCs de 8 bits não tinham nada disso, mas, olhando para aquilo, não parecia exigir uma complexidade tão grande assim.

  • De forma parecida, há um vídeo da época em que Brian Kernighan mostra como criar um corretor ortográfico com um comando de uma linha no shell do UNIX.
    https://youtu.be/tc4ROCJYbm0?t=4m56s

• Só terminei de ler o texto agora e vejo o ponto central assim: existe um “dicionário” de 30.000 palavras e, se aceitarmos uma taxa de falsos positivos de cerca de 1/4000, dá para transformar o problema em hashear cada palavra para uma string de 27 bits, ou seja, um inteiro, descartar o dicionário e armazenar o conjunto de 30.000 strings de 27 bits
  De modo um tanto surpreendente, segundo a teoria da informação, 30.000 strings de 27 bits podem ser armazenadas não com 27 bits por palavra, mas com apenas cerca de 13,57 bits. Eu entendo a matemática (https://www.wolframalpha.com/input?i=log_2%282%5E27+choose+30000%29%2F30000), mas 30.000 é tão pequeno em comparação com 2^27, ou seja, cerca de 134 milhões, que acho que vai levar um tempo para aceitar intuitivamente de onde vem o ganho
  Para codificar esse subconjunto de 30.000 hashes de 27 bits, usaram as diferenças entre hashes e, como essas diferenças seguem uma distribuição geométrica, conseguiram na prática cerca de 13,6 bits por palavra com codificação de Golomb ajustada para entradas com distribuição geométrica
  Fiquei pensando se, em princípio, daria para fazer melhor em uma direção tipo “hashing perfeito”. Talvez pudesse haver uma função que recebesse uma palavra alfabética, aplicasse alguma transformação e depois permitisse verificar facilmente se o hash resultante pertence a um conjunto bom
  Mas, pensando de novo, como é necessária uma taxa de falsos positivos, para impedir que uma palavra fora do dicionário seja mapeada para o conjunto “bom”, o hash precisa ter no mínimo 27 bits. Esse método basicamente parece ótimo em termos teóricos. Ou será que existe alguma forma de mapear cada palavra para um inteiro de 27 bits, mas fazer com que as strings boas sejam, por exemplo, aquelas com valor abaixo de 30000?

• Como referência, por volta de 1983, o Grammatik para CP/M rodava em menos de 64 KB e fazia “verificação gramatical” em sistemas de 8 bits. Na prática, era uma verificação ortográfica acrescida de regras de sistema especialista
  O que ficou na memória foi que eu fucei a parte interessante: ele conseguia ser tão pequeno porque tinha sido escrito em Forth, e vinha com intérprete externo suficiente dentro do produto para que, com um pouco de edição hexadecimal, desse para usá-lo como um interpretador Forth com funções especializadas pré-carregadas

  • No editor WordStar que rodo no meu sistema CP/M com 64 KB de RAM, há um corretor ortográfico SPELL.COM de 2023 bytes
    Não o descompilei para ver como funciona, mas é pequeno, rápido e funciona bem

• Fico curioso para saber quais erros de digitação comuns ele deixa passar por causa do hashing
  Relacionado a isso, também há uma competição de compressão do dicionário do Wordle: http://golf.horse/wordle/

• Passei por algo parecido em meados dos anos 80. “Rápido” é uma palavra relativa
  Havia muitos dados, a RAM era de 640 KB, o heap de 64 KB e a stack de 64 KB. Era preciso pesquisar e extrair dados de centenas de MB e combinar parte deles
  Fiz experimentos transformando os dados em uma estrutura de índice na forma de uma árvore ternária. Conceitualmente fazia sentido, mas, ao implementar, só as informações de relações e caminhos já eram grandes demais para caber em 64 KB
  Em vez de compressão, optei por swapping. Escrevi código TSR, algo como um serviço nos termos de hoje, que processava um bloco de dados, extraía os resultados, salvava-os na stack e descartava os dados originais; depois, enviava uma chamada de interrupção ao TSR. Então o TSR apagava o heap, lia o próximo bloco do armazenamento e devolvia o controle ao programa; o programa processava, combinava com os dados da stack e repetia até terminar tudo
  Originalmente, esse trabalho exigia cerca de uma semana de três operadores de entrada de dados, além de um especialista para combinar as informações. Imagine algo como uma dúzia de fichários de argolas de 3 polegadas cheios de tabelas. O programa terminava em algumas horas e era surpreendentemente “rápido”
  Foi algo feito em um sistema single-thread
  https://en.wikipedia.org/wiki/Terminate-and-stay-resident_program

• Lembro de usar a opção -b no UNIX spell para usar a grafia britânica. Havia só duas opções de idioma, e fico curioso sobre por que decidiram assim, como o código lidava com isso e de onde vieram os respectivos dicionários
  Será que australianos e neozelandeses usavam grafia britânica ou americana?
  O UNIX spell era uma espécie de xadrez ZX81 1K da área de correção ortográfica, e nos computadores domésticos não havia tantos corretores ortográficos até o MS Word para Windows 3.1. Antes disso, nos escritórios, as secretárias digitavam no WordPerfect e serviam como revisoras ortográficas humanas para cada gerente e equipe
  Enquanto isso, em casa, usando uma impressora matricial e uma tela piscante, fui levando durante os primórdios da computação contando com dicionários de papel. Naquela época, todo mundo sabia soletrar, então não lembro de corretores ortográficos serem tão importantes. Numa escola com mil alunos, havia só uma criança que dizia ter dislexia, o que servia como uma desculpa plausível para não saber escrever corretamente
  Talvez os anos 1980 tenham sido a era de ouro da alfabetização, e a data clara do início do declínio da capacidade de soletrar tenha sido o dia em que o UNIX spell foi escrito
  Gosto de Scrabble. É um problema bem diferente da correção ortográfica, mas o processamento compartilha algumas etapas com o UNIX spell. Encontrar prefixos e sufixos comuns de palavras e juntá-los a outros componentes no rack ou no tabuleiro
  O dicionário do Scrabble também se parece um pouco com o UNIX spell no sentido de ser apenas uma grande lista de palavras, sem fornecer significados. O que importa é se uma dada palavra está no livro. Também há algumas tabelas especiais de consulta, como as 102 palavras de duas letras

  • Lembro de fazer verificação ortográfica de redações do ensino médio em 1984, num Commodore 64 com Paperclip 64. Foi antes do Microsoft Windows
    Como ele verificava lendo o dicionário a partir do disco, levava alguns minutos, e depois era possível revisar as palavras que não tinham correspondência