How Unix Spell Ran in 64kB RAM.
Подсмотрел прекрасное в Полезняшки от «Разбора Полетов» спасибо Абашеву Алексею за его дозор.
Как можно разместить словарь объемом 250 КБ в 64 КБ оперативной памяти и при этом выполнять быстрый поиск? Для справки, даже с использованием современных методов сжатия, таких как gzip -9, вы не сможете сжать этот файл меньше 85 КБ.
В 1970-х Дуглас Макилрой (Douglas McIlroy) столкнулся именно с этой проблемой при внедрении программы проверки орфографии для Unix в AT&T. Ограничения компьютера PDP-11 означали, что весь словарь должен был поместиться всего в 64 КБ оперативной памяти. Казалось бы, невыполнимая задача.
Ну что, интересно? Ныряем в первоисточник:
