В 1970-х Дуглас Макилрой решал невыполнимую на первый взгляд задачу: запихнуть 250-килобайтный словарь в 64kB RAM компьютера PDP-11, чтобы написать спелл-чекер для Unix. Даже современный gzip -9 не может сжать этот файл меньше чем до 85kB. Первую версию Unix spell собрал на коленке за полдня Стив Джонсон, но работала она медленно и криво: утилита просто искала слова на диске. Макилрой взялся за переделку.
Он выжал максимум из лингвистики, придумав алгоритм отсечения аффиксов, который превращал «misrepresented» в «present» и резал словарь до 25 тысяч стемов. Но даже этот огрызок не лез в оперативку напрямую. Тогда в ход пошёл Bloom-фильтр — вероятностная структура, которую для него реализовал Денис Ритчи. Это было одно из первых боевых применений фильтра, который тогда ещё даже не называли Bloom-фильтром. Таблицу раздули до 400 000 бит и подобрали 11 хеш-функций, чтобы ложные срабатывания случались лишь раз на 2000 проверок. При таком уровне ошибок можно было вовсе отказаться от прямого поиска по словарю.
Проблема нарисовалась, когда словарь разбух до 30 тысяч слов. Bloom-фильтр под такой объём потребовал бы слишком много памяти. Макилрой переключился на хранение одних лишь хешей, но 27-битные коды (выбранные ради низкой вероятности коллизий) всё равно оказались неподъёмными. Пришлось сжимать. Он высчитал по формулам теории информации теоретический предел — 13.57 бит на слово — и стал думать, как к нему подобраться. Инженер заметил, что разности между отсортированными хешами подчиняются геометрическому распределению. А для него Соломон Голомб ещё в 1965 году придумал элегантный код, который выдаёт короткие метки частым событиям и длинные — редким.
Макилрой разбил эти разности на блоки, использовав код Голомба, и получил 13.60 бит на слово — практически теоретический минимум. Поиск в сжатом массиве без распаковки всего подряд тормозил, поэтому таблицу разбили на сегменты. Лишние указатели подняли итоговый расход памяти до 14 бит на слово, что всё ещё влезало в 64kB RAM и давало быстрый поиск. Так из смеси вероятностных структур, теории информации и жёстких аппаратных ограничений родилось решение, оставшееся непревзойдённым по эффективности сжатия.