- En la década de 1970,
spell de Unix de AT&T necesitaba consultar rápidamente un diccionario de 250KB dentro de los 64KB de RAM de la PDP-11, y Douglas McIlroy lo resolvió aprovechando las características de los datos en lugar de usar compresión genérica
- El prototipo inicial de Steve Johnson estaba basado en disco, por lo que era lento y poco preciso, pero McIlroy mejoró el rendimiento y la precisión al reducir el diccionario a unas 25,000 palabras mediante stemming
- La primera estructura en memoria fue un Bloom filter implementado por Dennis Ritchie, con una tabla de 400,000 bits y 11 funciones hash para lograr una tasa de falsos positivos de aproximadamente 1/2000 y evitar una consulta adicional al diccionario
- Cuando el diccionario creció a 30,000 palabras, se volvió difícil mantener las restricciones de memoria usando solo un Bloom filter, así que ordenaron hashes de 27 bits y comprimieron las diferencias entre hashes con código de Golomb
- La implementación final dividió la tabla comprimida de diferencias en varios bins para acelerar las consultas, y con un almacenamiento de unas 14 bits por palabra hizo posible una corrección ortográfica rápida dentro de 64KB
La restricción de memoria que enfrentó Unix spell
- El problema central era consultar rápidamente un diccionario de 250KB en un entorno con 64KB de RAM
- Incluso aplicando compresión moderna como
gzip -9, este archivo no baja de 85KB
- En la PDP-11 de los años 70 no era posible cargar todo el diccionario en memoria, y las consultas basadas en disco eran lentas
- En vez de usar compresión genérica, McIlroy diseñó una estructura de datos especializada que aprovechaba la estructura y la distribución probabilística de los datos del diccionario
El Unix spell inicial y la reducción del diccionario basada en raíces
- Cuando AT&T propuso Unix como un sistema de procesamiento de texto para su departamento de patentes, se volvió necesario contar con un corrector ortográfico
- Steve Johnson escribió el primer prototipo de Unix
spell en 1975, y Jon Bentley contó que ese trabajo se hizo en una sola tarde
- La versión inicial dividía el archivo de entrada en un flujo de palabras y luego eliminaba números y caracteres especiales, convertía a minúsculas, ordenaba, eliminaba duplicados y verificaba la existencia de cada palabra en un diccionario en disco
- Ese método simple de consulta en disco era lento y también poco preciso
- Para mejorar rendimiento y precisión, McIlroy rediseñó dos partes
- un algoritmo que eliminaba prefijos y sufijos para reducir las palabras a su raíz
- una estructura de datos comprimida para cargar el diccionario en memoria y consultarlo rápidamente
Algoritmo para eliminar prefijos y sufijos
- El enfoque de stemming de McIlroy eliminaba repetidamente prefijos y sufijos comunes de una palabra y luego comprobaba si la palabra reducida existía en el diccionario
- Por ejemplo,
misrepresented se reduce a present al eliminar los prefijos mis, re y el sufijo ed
- Si
present estaba en el diccionario, la palabra original no se marcaba como error ortográfico
- Este método no era 100% preciso y podía dejar pasar algunos errores, pero en ese momento se consideró un nivel aceptable
- También se implementaron reglas de excepción para evitar errores frecuentes
- El diccionario final se redujo a 25,000 palabras, un tamaño que podía cargarse en memoria si la estructura de datos estaba bien diseñada
Consultas basadas en Bloom filter
- La primera estructura en memoria que usó McIlroy fue un Bloom filter, descrito en los artículos de la época como un “superimposed code scheme”
- El artículo sobre Bloom filters se publicó en 1970, y Unix
spell fue desarrollado a mediados de esa década
- Dennis Ritchie aportó esta implementación
- Un Bloom filter inicializa en 0 una tabla de bits y, para cada elemento, aplica varias funciones hash para poner en 1 los bits correspondientes
- Al consultar, se aplican las mismas funciones hash
- si хотя sea un bit está en 0, el elemento no existe
- si todos los bits están en 1, puede existir, pero sigue habiendo posibilidad de falso positivo (false positive)
- En un Bloom filter común, manejar falsos positivos requiere consultar el diccionario real, pero en un corrector ortográfico la mayoría de las palabras sí existen en el diccionario, así que eso podía provocar consultas muy frecuentes al diccionario completo
- McIlroy bajó lo suficiente la tasa de falsos positivos como para omitir la consulta real al diccionario
- tasa de falsos positivos permitida: 1/2000
- número de palabras del diccionario: 25,000
- tamaño de la tabla de bits: 400,000 bits
- funciones hash: 11
- Con esa combinación se logró una tasa de falsos positivos cercana a 1/2000
Los límites del Bloom filter y el enfoque de hashes comprimidos
- El método con Bloom filter se usó por un tiempo, pero a medida que se agregaban nuevas palabras el diccionario creció de 25,000 a 30,000 palabras
- Para mantener la misma tasa de falsos positivos hacía falta una tabla de bits más grande, pero eso era difícil por la restricción de memoria
- McIlroy cambió entonces a un enfoque que guardaba solo los valores hash de las palabras, en vez de una tabla hash completa
- La consulta funcionaba calculando el hash de la palabra de entrada y verificando si existía en la lista de hashes almacenados
- Para reducir la posibilidad de colisiones hacía falta un código hash suficientemente grande
- el tamaño del diccionario
v era de unas 30,000 entradas, es decir, cerca de 2^15
- la probabilidad de colisión permitida era
1 / 2^12
- el tamaño hash necesario era de 27 bits
- Guardar 30,000 hashes de 27 bits no cabía en los 64KB de RAM de la PDP-11, así que la compresión era indispensable
Límite teórico de compresión
- McIlroy primero calculó el número mínimo teórico de bits necesario para almacenar el conjunto de códigos hash
- Si el tamaño del hash es de
b bits, existen 2^b hashes posibles, y la cantidad de información puede expresarse como el número de formas de elegir v códigos hash únicos entre ellos
- En el cálculo se usaron la aproximación de Stirling y la suposición simplificada de que
v « 2^b
- Sustituyendo
v=30,000 y b=27, el mínimo necesario para almacenar un solo código hash resultó ser de 13.57 bits
- Eso es casi 50% menos que el hash original de 27 bits y ya estaba dentro de la capacidad de memoria de la PDP-11
Almacenamiento y consulta con diferencias de hash
- McIlroy no comprimió directamente los códigos hash originales, sino que almacenó las diferencias entre códigos hash ordenados
- El ejemplo es el siguiente
sorted hash codes: 5, 14, 21, 32, 55, 67
hash differences: 5, 9, 7, 11, 23, 12
- Guardar diferencias tenía dos ventajas
- los valores de diferencia eran más pequeños que los códigos hash originales
- el mismo valor de diferencia podía repetirse entre varios pares de hashes
- La consulta funcionaba calculando el hash de la palabra de entrada y acumulando las diferencias desde el principio
- si la suma acumulada coincidía con el hash de entrada, existía
- si la suma acumulada superaba el hash de entrada, no existía
- Esto reducía el espacio de almacenamiento, pero podía volver lentas las consultas porque había que decodificar y acumular valores comprimidos desde el inicio
Modelado de las diferencias de hash con distribución geométrica
- La compresión sin pérdida es más eficiente cuando asigna códigos cortos a los valores frecuentes y códigos largos a los poco frecuentes
- La compresión general basada en una tabla de distribución de probabilidades no se ajustaba a las restricciones de McIlroy
- mantener en memoria una tabla de probabilidades para unos 30,000 símbolos anulaba la ganancia de compresión
- calcular la frecuencia y probabilidad de los valores de diferencia requería una estructura costosa basada en disco
- McIlroy aprovechó que las diferencias entre hashes seguían una distribución geométrica
- El espacio hash tiene
2^b posiciones, y en él se distribuyen v códigos hash
- la probabilidad de que una posición tenga un hash es
q = v / 2^b
- la probabilidad de que esté vacía es
p = 1 - v / 2^b
- Una diferencia
k ocurre cuando las k-1 posiciones después de cierto hash están vacías y la siguiente posición contiene el siguiente hash
- Por lo tanto, la probabilidad de una diferencia
k es p^(k-1)q, lo que coincide con la forma de una distribución geométrica
Compresión de diferencias con código de Golomb
- McIlroy comprimió las diferencias de hash con código de Golomb, adecuado para enteros con distribución geométrica
- El artículo de Golomb de 1965 ofrecía un método simple de codificación por longitud de corrida para valores con distribución geométrica
- En una distribución geométrica, como la probabilidad decrece exponencialmente, se puede construir una estructura donde los valores se agrupan en bloques de tamaño
m y la longitud del código aumenta en 1 bit al pasar al siguiente bloque
- La implementación de Unix
spell usó un algoritmo de codificación y decodificación distinto del descrito en el artículo de Golomb, algo más complejo pero más eficiente
- La implementación original de SVR4 puede verse en las siguientes ubicaciones
- El código de Golomb comprimía las diferencias de hash hasta una longitud esperada de 13.60 bits por palabra
- Ese resultado estaba muy cerca del mínimo teórico de 13.57 bits
División en bins para acelerar las consultas
- Si solo se usa la tabla comprimida de diferencias, en cada consulta hay que decodificar y acumular desde el principio, por lo que resulta lenta
- La implementación final de Unix
spell dividía la tabla de diferencias en M bins
- Al consultar, primero se localiza el bin correspondiente y solo se recorre ese segmento
- Este método multiplica por
M la velocidad de búsqueda
- A cambio, es necesario almacenar punteros a los bins, lo que requiere un espacio adicional de
log₂M bits por palabra
- El almacenamiento total subió a unas 14 bits por palabra, pero fue una concesión razonable para obtener consultas mucho más rápidas dentro del presupuesto de memoria
El diseño guiado por restricciones que mostró Unix spell
- Unix
spell es un caso de diseño que combina Bloom filters, teoría de la información, teoría de probabilidad y compresión de Golomb
- El proceso de desarrollo siguió este flujo
- lograr una baja tasa de falsos positivos con Bloom filters
- cambiar al enfoque de hashes comprimidos cuando el diccionario creció
- calcular el mínimo teórico de bits para almacenar hashes
- reconocer la distribución de las diferencias entre hashes
- lograr una compresión casi óptima con código de Golomb
- acelerar las consultas con división en bins añadiendo solo una pequeña sobrecarga de espacio
- Los correctores ortográficos modernos usan otras técnicas, como edit distance o modelos de lenguaje, pero Unix
spell sigue siendo un ejemplo de cómo combinar comprensión teórica y restricciones reales para construir un sistema eficiente
1 comentarios
Opiniones en Hacker News
Se puede crear un corrector ortográfico con memoria externa usando muy poca RAM: se ordenan las palabras del documento, se eliminan las palabras únicas y luego se fusionan con un diccionario ordenado para que solo queden las palabras que no existen.
Vi este enfoque como ejemplo en BASIC de Creative Computing, y como lo hice funcionar en una TRS-80 Color Computer que tenía bastante menos de 32 KB de RAM disponible, fue lo primero que me vino a la mente apenas vi el título.
En esa época, Turbo Lightning sorprendió a la gente: su diccionario comprimido cabía junto con otros programas que estaban ejecutándose en la PC y revisaba la ortografía mientras escribías.
Aunque la PC tenía el límite de 640 KB, para no interferir con otros programas solo podía usar una parte de eso, y en los primeros tiempos de la PC tampoco era fácil, por costo, llenar toda esa memoria.
También habría sido posible guardar primero la copia de trabajo en disco, ordenarla, compararla y luego volver a cargarla, pero creo que los desarrolladores de C=64 habrían evitado esa estrategia porque la interfaz de disco era demasiado lenta.
Hay un pasaje que dice que en ese momento los filtros de Bloom todavía no se llamaban filtros de Bloom y que Douglas los llamó “superimposed code scheme” en su paper, pero un filtro de Bloom es un tipo específico de código superpuesto.
Calvin Mooers desarrolló el superimposed coding aleatorio en su tesis de maestría en el MIT en la década de 1940, directamente influido por Shannon.
El excelente libro de Bourne de 1963, “Methods of Information Handling”, incluye los detalles matemáticos.
Estoy convencido de que Douglas conocía la técnica más amplia. Por ejemplo, el autor de “The Large Data Base File Structure Dilemma” (1975) también la describió en http://dx.doi.org/10.1021/ci60001a005 como “una técnica antigua llamada super-imposed coding”.
Aquí el calificativo “aleatorio” es importante, porque antes de Mooers ya existían los códigos superpuestos, pero no eran matemáticamente interesantes ni prácticamente importantes.
Para ser “worse is better”, es demasiado inteligente. Hay que pensar en algo más malo.
El ancho de banda de la memoria principal y el del disco eran casi iguales, ambos apenas por encima de 1 MB/s.
Yo probablemente lo habría hecho con varias pasadas, pero aun así habría usado un filtro de Bloom porque es genial.
https://github.com/arnoldrobbins/v10spell
https://code.google.com/archive/p/unix-spell/
El paper original también es excelente: https://www.semanticscholar.org/paper/Development-of-a-Spelling-List-McIlroy/e08c8a4c17f23c41616649ca73a908d06828d67f
También está en su página web: https://www.cs.dartmouth.edu/~doug/
https://en.wikipedia.org/wiki/Douglas_McIlroy
Si eres fanático de las palabras, al buscar “obovate” también acabarás viendo este gráfico de formas de hojas.
https://upload.wikimedia.org/wikipedia/commons/e/e8/Leaf_morphology.svg
No recuerdo el nombre del producto, pero en los 80 había un corrector ortográfico por hardware para IBM PC. Era una caja que se conectaba entre el teclado y la PC, y si escribías una cadena que no reconocía como palabra del diccionario, avisaba con un pitido.
Hay una reseña en la página 237 de https://vintageapple.org/pcworld/pdf/PC_World_8711_November_1987.pdf. Ojo, es un PDF grande.
Una de las cosas que me despertó el interés por Unix fue un artículo de Byte de principios de los 80, más o menos. Mostraba cómo crear un corrector ortográfico con un pipeline de split/sort/comm, de unos 7 comandos aproximadamente.
En las PC de 8 bits no había nada de eso, pero al verlo tampoco parecía requerir una complejidad tan impresionante.
https://youtu.be/tc4ROCJYbm0?t=4m56s
Recién terminé de leer el artículo y creo que la idea central es esta: hay un “diccionario” de 30,000 palabras y, si se acepta una tasa de falsos positivos de alrededor de 1/4000, cada palabra se puede hashear como una cadena de 27 bits, es decir, como un entero, tirar el diccionario y convertir el problema en guardar un conjunto de 30,000 cadenas de 27 bits
De forma algo sorprendente, según la teoría de la información, 30,000 cadenas de 27 bits pueden almacenarse no con 27 bits por palabra, sino con apenas unos 13.57 bits. Entiendo las matemáticas (https://www.wolframalpha.com/input?i=log_2%282%5E27+choose+30000%29%2F30000), pero como 30,000 es muy pequeño comparado con 2^27, es decir, unos 134 millones, creo que me va a tomar tiempo aceptar intuitivamente de dónde sale la ganancia
Para codificar este subconjunto de 30,000 hashes de 27 bits usaron las diferencias entre hashes y, como esas diferencias siguen una distribución geométrica, con codificación Golomb ajustada a entradas con distribución geométrica lograron en la práctica unos 13.6 bits por palabra
Estuve pensando si en principio se podría hacerlo mejor con algo en la línea de “hashing perfecto”. Se me ocurrió que quizá podría haber una función que tome palabras alfabéticas, les aplique alguna transformación y luego permita verificar fácilmente si el hash resultante pertenece a un buen conjunto
Pero, pensándolo de nuevo, como se necesita una tasa de falsos positivos, para evitar que una palabra que no está en el diccionario se mapee al conjunto “bueno”, el hash necesita al menos 27 bits. Este método básicamente parece óptimo desde el punto de vista teórico. ¿O existirá alguna forma de mapear cada palabra a un entero de 27 bits haciendo que las cadenas buenas sean, por ejemplo, las que tienen un valor menor que 30000?
Como referencia, hacia 1983 Grammatik para CP/M funcionaba con menos de 64 KB e hacía “revisión gramatical” en sistemas de 8 bits. En realidad era una revisión ortográfica con reglas de sistema experto añadidas
Lo recuerdo porque investigué la parte interesante: la razón por la que podía ser tan pequeño era que estaba escrito en Forth, y el producto incluía suficiente intérprete externo como para que, con un poco de edición hexadecimal, pudiera usarse casi como un intérprete Forth con funciones especializadas precargadas
No lo descompilé para ver cómo funciona, pero es pequeño, rápido y funciona bien
Me da curiosidad qué errores tipográficos comunes deja pasar por culpa del hashing
Relacionado con eso, también está el concurso de compresión del diccionario de Wordle: http://golf.horse/wordle/
A mediados de los 80 me tocó hacer algo parecido. “Rápido” es un término relativo
Había muchos datos, la RAM era de 640 KB, el heap de 64 KB y el stack de 64 KB. Teníamos que buscar y extraer datos de cientos de MB y combinar una parte
Experimenté con convertir los datos en una estructura de índice en forma de árbol ternario. Conceptualmente tenía sentido, pero al implementarlo, solo las relaciones y la información de rutas ya eran demasiado grandes para caber en 64 KB
En vez de comprimir, opté por hacer swapping. Escribí código TSR, algo parecido a un servicio hoy en día, que procesaba un bloque de datos, extraía los resultados y los guardaba en el stack, luego descartaba los datos originales y enviaba una llamada de interrupción al TSR. Entonces el TSR eliminaba el heap, leía el siguiente bloque desde el almacenamiento y devolvía el control al programa; el programa procesaba, combinaba con los datos del stack y repetía hasta terminar todo
Originalmente, este trabajo requería alrededor de una semana de tres personas encargadas de captura de datos, además de un especialista que combinara la información. Imaginen unas doce carpetas de anillos de 3 pulgadas llenas de tablas. El programa terminaba en unas horas y era sorprendentemente “rápido”
Todo esto se hizo en un sistema de un solo hilo
https://en.wikipedia.org/wiki/Terminate-and-stay-resident_program
Recuerdo haber usado la opción
-ben UNIX spell para usar ortografía británica. Solo había dos opciones de idioma, y me pregunto por qué se decidió así, cómo lo manejaba el código y de dónde venía cada diccionario¿La gente de Australia y Nueva Zelanda usaba ortografía británica o estadounidense?
UNIX spell era como el ajedrez ZX81 1K de la ortografía, y en las computadoras hogareñas no había muchos correctores ortográficos hasta que salió MS Word para Windows 3.1. Antes de eso, en la oficina las secretarias escribían en WordPerfect y actuaban como correctoras ortográficas humanas para cada gerente y equipo
Mientras tanto, en casa, con una impresora de matriz de puntos y una pantalla parpadeante, me las arreglé durante toda la era temprana de la computación dependiendo de diccionarios de papel. No recuerdo que los correctores ortográficos fueran tan importantes entonces, porque todo el mundo sabía deletrear. En una escuela de mil estudiantes, solo había un chico que decía tener dislexia, y era una excusa verosímil para no saber deletrear
Tal vez los años 80 fueron la edad de oro de la alfabetización, y la fecha clara del inicio del declive de la capacidad ortográfica fue el día en que se escribió UNIX spell
Me gusta Scrabble. Es un problema muy distinto al de la corrección ortográfica, pero su procesamiento comparte algunos pasos con UNIX spell. Busca prefijos y sufijos comunes de palabras y los une con otros componentes del rack o del tablero
El diccionario de Scrabble también se parece un poco a UNIX spell en que no es más que una gran lista de palabras sin definiciones. Lo importante es si una palabra dada está o no en el libro. También hay algunas tablas especiales de consulta, como las 102 palabras de dos letras
Como iba leyendo el diccionario desde el disco para hacer la revisión, tardaba varios minutos, y después uno podía revisar las palabras que no coincidían