Как уместить поиск по 30 тысячам слов в 64 КБ ОЗУ / forpes.ru

Главная
Как уместить поиск по 30 тысячам слов в 64 КБ ОЗУ

Как уместить поиск по 30 тысячам слов в 64 КБ ОЗУ +31

20.02.2025 06:21

PatientZero 6 4500 Источник

Как уместить словарь размером 250 КБ в 64 КБ ОЗУ с возможностью выполнения быстрого поиска? Для справки: даже современные методики сжатия наподобие gzip -9 не могут сжать этот файл до размера меньше 85 КБ.

В 1970-х Дуглас Макилрой столкнулся с этой непростой задачей при реализации проверки правописания для Unix в AT&T. Из-за ограничений компьютера PDP-11 весь словарь должен был умещаться всего в 64 КБ ОЗУ. Кажется, подобную задачу решить невозможно.

Вместо того, чтобы использовать стандартные методики сжатия, Дуглас воспользовался преимуществами свойств данных, разработав алгоритм сжатия, превышавший теоретический минимум сжатия всего на 0,03 бита. И по сей день этот рекорд остаётся непревзойдённым.

История spell в Unix — это не только любопытный исторический факт. Это мастер-класс по проектированию в условиях жёстких ограничений: анализа первооснов задачи, применения математических наблюдений и проектирования изящных решений, работающих в условиях строгого дефицита ресурсов.

TL;DR

Если у вас мало времени, можете прочитать краткое изложение статьи:

Прототип утилиты spell для Unix изначально был разработан за пару часов Стивом Джонсоном из AT&T, а позже Дуглас Макилрой переписал код, чтобы повысить его производительность и точность.
Первой инновацией Макилроя стал хитрый лингвистический алгоритм стемминга, позволивший уменьшить словарь всего до 25 тысяч слов, повысив при этом точность.
Для быстрого поиска он изначально использовал фильтр Блума — вероятно, это был он из первых примеров его реального применения. Любопытно, что реализацию создал Деннис Ритчи. Совместно они добились настолько низкой частоты ложноположительных срабатываний, что можно было избавиться от самого поиска по словарю.
Когда словарь разросся до 30 тысяч слов, решение с фильтром Блума потеряло практичность, приведя к реализации инновационных методик сжатия хэшей.
Они вычислили, что при 27-битных хэш-кодах вероятность коллизий будет находиться на приемлемо низком уровне, но всё равно требовалось сжатие.
Макилрой решил хранить различия между отсортированными хэш-кодами, так как обнаружил, что эти различия соответствуют геометрическому распределению.
Использовав код Голомба (схему сжатия, разработанную для геометрических распределений), он достиг уровня сжатия 13,60 бита на слово, что очень близко к теоретическому минимуму в 13,57 бита.
Далее он разбил сжатые данные, чтобы ускорить поиск, пожертвовав небольшим увеличением памяти (окончательный размер составил примерно 14 битов на слово) в пользу существенного повышения производительности.

В статье мы расскажем о каждом из пунктов с подробным объяснением всей математики и логики.

A PDP-11 machine, source: Wikipedia — Машина PDP-11

Происхождение команды Unix Spell

Чтобы обеспечить финансирование Unix, Кен Томпсон и Деннис Ритчи представили компании AT&T Unix как систему обработки текста для отдела патентов. Естественно, системе обработки текста требовалась функция проверки правописания.

Первая версия (прототип) spell для Unix была написана Стивом Джонсом в 1975 году. По словам Джона Бентли, Стив написал её за один вечер. Утилита работала, но была не особо точной.

Она была довольно простой: разбивала входной файл на поток слов, выполняла небольшую предобработку, например удаляла числа и специальные символы, выполняла преобразование в нижний регистр, затем сортировала, выбирала уникальные вхождения и, наконец передавала список программе проверки правописания, которая просто проверяла существование этих слов в словаре на диске.

Из-за простоты реализации она была не особо точной, а ещё медленной из-за поиска по дисковому словарю.

Понаблюдав за использованием первой версии, Дуглас Макилрой взялся за проект, решив переписать его, чтобы повысить точность и производительность инструмента. Он работал на двух фронтах, требовавших тщательно продуманной реализации:

Создание алгоритма удаления аффиксов для редуцирования слов до их основ, а также получение компактного словаря, состоящего из основ
Разработка компактной структуры данных для загрузки словаря в память с целью выполнения быстрых операций поиска

В статье мы в первую очередь рассмотрим разработку структуры данных, но уделим один раздел и краткому обзору алгоритма удаления аффиксов.

Алгоритм удаления аффиксов

Выполнение поиска по полному словарю оказалось медленным, потому что у компьютеров в те времена было лишь несколько килобайтов основной памяти, а поиск по диску ещё больше замедлял процесс.

У Дугласа Макилроя возникла идея алгоритма, который итеративно будет удалять общие префиксы и суффиксы из слова и искать в словаре редуцированное слово. Алгоритм повторяет процесс удаления аффиксов до тех пор, пока не останется аффиксов для удаления; если и после этого слово не будет найдено в словаре, то оно считается написанным неправильно.

Например, алгоритм редуцирует слово «misrepresented» до «present», удалив префиксы «mis» и «re», а также суффикс «ed». А поскольку слово «present» присутствует в словаре, оно не будет помечено как ошибка.

Эта методика удаления аффиксов точна не на 100% и иногда пропускает неправильно написанные слова. Но такие случаи в то время считались приемлемыми. Дуглас также реализовал множество исключений из этих правил, чтобы избежать самых распространённых ошибок.

В целом, применение этого алгоритма привело к созданию очень компактного словаря. Итоговый словарь состоял из 25 тысяч слов, то есть его вполне можно было уместить в памяти, если тщательно продумать структуру данных.

Давайте перейдём к объяснению того, как Макилрою удалось реализовать поиск по словарю в памяти всего в 64 КБ ОЗУ.

Поиск на основе фильтра Блума

Блум опубликовал свою статью о фильтре в 1970 году, а разработка spell для Unix велась в середине 1970-х. В то время фильтр Блума даже так не назывался. В своей статье Дуглас называет его «superimposed code scheme».

Любопытно, что использованная им реализация фильтра Блума была передана ему Деннисом Ритчи.

Хоть словарь состоял из 25 тысяч слов, его всё равно невозможно было уместить всего в 64 КБ ОЗУ. Кроме того, требовались быстрые операции поиска по нему.

Изначально в качестве структуры данных Дуглас использовал фильтр Блума. В своей статье он называет его «superimposed coding scheme», как и в научной статье Блума 1970 года.

Фильтр Блума состоит из битовой таблицы, инициализированной одними нулями. Для добавления элемента в фильтр Блума к элементу применяются различные хэш-функции. Каждая хэш-функция генерирует индекс в таблице, и этому битовому индексу задаётся значение 1. Если используется k хэш-функций, то в таблице будет задано k битовых индексов.

Для поиска элемента в таблице требуется та же самая процедура. Необходимо применить k хэш-функций, и для каждой из них проверять, имеет ли соответствующий бит в таблице значение 1. Если хотя бы один из битов не задан, то это значит, что элемент отсутствует в датасете. Однако если все биты заданы, то это свидетельствует о возможности его присутствия, но это всё равно может быть ложноположительным срабатыванием.

Ложноположительные срабатывания могут возникать из-за коллизий хэшей. После запроса элемента мы не можем быть уверенными на 100%, что бит задан в таблице из-за запрашиваемого элемента или из-за коллизии хэша с другим элементом.

При работе с фильтром Блума необходимо реализовать стратегию для обработки ложноположительных срабатываний. Например, в нашем случае для этого можно выполнять поиск по словарю целиком. Но тогда потеряет весь смысл применения фильтра Блума, который мы используем ради экономии памяти и ускорения поиска по словарю. В случае проверки правописания большинство слов существует в словаре и только доля слов написана неправильно, поэтому мы достаточно часто будем проверять весь словарь.

Однако фильтр Блума можно настраивать, получая нужную частоту ложноположительных срабатываний. Показанная ниже формула вычисляет вероятность ложноположительных срабатываний для фильтра Блума размера n, количества вставленных элементов m и количества хэш-функций k.

$\begin{align*} &\text{q} \approx \left( 1 - e^{-\frac{kn}{m}} \right) \\ &\text{где:} & \\ &\text{q}:\ \text{вероятность того, что бит имеет значение 1} \\ &m: \ \text{количество битов в фильтре Блума} \\ &k: \ \text{количество использованных хэш-функций} \\ &n: \ \text{количество вставленных элементов} \end{align*}$

В своей статье Макилрой говорит, что для него приемлема вероятность ложноположительных срабатываний 1 к 2000, то есть при такой низкой частоте ложноположительных срабатываний ему не нужно обращаться к словарю.

Так как словарь состоял из 25 тысяч элементов, количество битов было постоянным. Из-за малого размера памяти он ограничил размер битовой таблицы 400000 битами. Исходя из этих факторов, для обеспечения частоты ложноположительных срабатываний примерно 1/2000 достаточно было одиннадцати хэш-функций.

Результаты применения фильтра Блума

Какое-то время разработчики пользовались утилитой spell на основе фильтра Блума. В своей статье Дуглас упоминает, что несмотря на приемлемость частоты ложноположительных срабатываний, в реальности они сталкивались со множеством новых слов, которые нужно было добавить в словарь. Это привело к тому, что размер словаря вырос с 25 тысяч до 30 тысяч слов.

Однако для словаря таких размеров фильтр Блума требовал гораздо большего размера битовой таблицы, что в их условиях было недопустимо. Поэтому Дуглас начал искать альтернативные структуры данных, позволившие бы уместить 30 тысяч слов в памяти со сравнимым уровнем производительности и точности поиска.

Схема сжатого хэширования для поиска по словарю

Привлекательным решением оказалась хэш-таблица, но она требовала гораздо больше памяти, чем фильтр Блума, поскольку для обработки коллизий необходимо было хранить и хэш, и слова.

Вместо реализации полной хэш-таблицы Дуглас решил хранить только хэши слов. Для поиска нужно было вычислить хэш входного слова, а затем при помощи сканирования проверить его наличие в хэшах.

Для этого можно воспользоваться следующим наблюдением: слова имеют варьирующуюся длину, но хэш-функция естественным образом сожмёт их до фиксированного количества битов, что, вероятно, позволит уместить хэши в памяти.

Но у хэшей может возникать коллизия, поэтому для обеспечения приемлемо низкой вероятности коллизий необходим достаточно большой хэш-код.

Вычисление оптимального размера хэш-кода

Если каждое слово в словаре хэшируется в хэш-код размером b битов, то в этом пространстве существует 2^b возможных хэш-кодов. Если словарь имеет размер v слов, тогда вероятность коллизии хэшей можно вычислить так:

$\begin{align*} \text{P(hash collision)} = \frac{v}{2^b} \end{align*}$

Словарь имел размер 30 тысяч слов, то есть примерно 2¹⁵ слов. Кроме того, Макилрой писал, что для него была приемлема вероятность коллизий 1 к 2¹². Таким образом, хэш-код должен был иметь размер 27 битов.

Но 27-битные хэш-коды слишком длинны: при 2¹⁵ слов им понадобится 2¹⁵ * 27 битов памяти, а PDP-11 имел всего 2¹⁵ * 16 битов (64 КБ) ОЗУ. То есть необходимо использовать сжатие.

Теоретический предел минимума сжатия хэш-кодов

Перед реализацией алгоритма сжатия нам нужно знать, в какое теоретически минимальное количество битов мы можем ужать эти данные. Это будет бенчмарком, по которому мы сможем судить о качестве сжатия данных.

Этот теоретический минимум вычисляется по объёму информации события, сгенерировавшего данные, которые мы хотим сжать. Это концепция из теории информации, лежащая в основе всех методик сжатия данных.

Объём информации события

В основе понятия объёма информации лежит использование вероятности события для определения количества битов, необходимых для его кодирования без утери информации.

Событие с высокой степенью вероятности содержит меньше информации (например, вероятное на 100% событие не содержит информации и требует для кодирования 0 битов), а менее вероятное событие содержит гораздо больше информации и требует больше битов. Существует обратная связь между вероятностью события и объёмом информации, что приводит нас к следующей формуле:

$\begin{align*} &\text{I(E)} = \log_2\left(\frac{1}{P(E)}\right) \\ &\text{или I(E) = } -\log_2{P(E)} \\ &\text{где P(E) — } \text{вероятность события E} \end{align*}$

Для вычисления объёма информации множества хэш-кодов нам нужно вычислить вероятность их генерации.

Если хэш-код имеет размер b битов, то в этом пространстве суммарно есть 2^b возможных хэш-кодов. Из них мы выбираем множество из v уникальных хэш-кодов. Суммарное количество способов выбора таких множеств:

$\begin{align*}\binom{2^b}{v} \end{align*}$

Следовательно, вероятность генерации любого из этих множеств:

$\begin{align*} \text{P} = \frac{1}{\binom{2^b}{v}} \end{align*}$

Следовательно, объём информации этих хэш-кодов:

$\begin{align*} &I(E) = - \log_2\left(\frac{1}{\binom{2^b}{v}}\right) \\ &= \log_2\left(\binom{2^b}{v}\right) \\ &= \log_2\left(\frac{(2^b)!}{v! \, (2^b - v)!}\right) \end{align*}$

Чтобы упростить вычисления, можно использовать формулу Стирлинга:

$\begin{align*}\quad \log_2(n!) \approx n \log_2(n) - n \log_2(e), \\ \end{align*}$

В статье приводится ещё одно допущение: количество слов в словаре (30 тысяч) гораздо меньше, чем общее количество хэш-кодов (2²⁷), то есть v « 2^b, что позволяет упростить (2^b - v) в приведённой выше формуле до 2^b.

Применив эти приближения, мы получим следующую формулу объёма информации:

$\begin{align*} &I(E) \approx v\left[b - \log_2\left(\frac{v}{e}\right)\right] \end{align*}$

Подставив v=30000 и b=27, получим, что минимальное количество битов, необходимое для кодирования одного хэш-кода, равно 13,57, что примерно на 50% меньше, чем исходные хэш-коды, и вполне умещается в память PDP-11.

Схема сжатия на основе дельты

На этом этапе разработчики знали, какого сжатия могут достичь, но оставался более важный вопрос: как его реализовать? Что если вместо сжатия сырых хэш-кодов вычислять и хранить разницу между идущими по порядку хэш-кодами (в отсортированном порядке)? Это похоже на дельта-кодирование, но не полностью совпадает с ним.

При работе с разностью хэшей мы получаем пару преимуществ.

Разность по умолчанию меньше, чем сырые хэш-коды
Многие значения разности будут повторяться, потому что разность множества хэш-кодов может быть одинаковой.

Из этого можно сделать вывод, что разности сжимать проще, чем хэш-коды.

Вычисление разностей хэшей

Разности хэшей вычислялись сортировкой хэш-кодов и вычислением разности между идущими по порядку значениями.

Например:

отсортированные хэш-коды: 5, 14, 21, 32, 55, 67
разности хэшей: 5, 9, 7, 11, 23, 12

Давайте разберёмся, как работает поиск слова, когда мы храним вместо значения разность хэшей.

Поиск существования слова

Чтобы проверить, существует ли слово в словаре, разработчики вычисляли хэш слова и при помощи простого алгоритма проверяли его наличие в словаре.

lookup(input_hashcode) -> bool:
  sum = hash_differences[0]
  i = 1
  while True:
    sum += hash_differences[i]
    if sum == input_hashcode:
      return True
    if sum > input_hashcode:
      return False
    i += 1

А теперь давайте поговорим о том, как они придумали схему сжатия этих данных.

Математическое моделирование разностей хэш-кодов

Базовый принцип сжатия без потерь заключается в присвоении коротких кодов символам с повышенными вероятностями и более длинных кодов — символам с низкой вероятностью. Это логично, ведь символы с высокой вероятностью будут встречаться в данных чаще, и присвоение им коротких кодов повышает степень сжатия.

Но для этого понадобится вычислить распределение вероятностей всех символов в данных, а затем использовать его для генерации сжатых кодов. Также для выполнения декодирования на этапе распаковки потребуется таблица распределения вероятностей.

Это представляло для Дугласа две проблемы:

Из-за хранения таблицы распределения вероятностей для 30 тысяч символов теряются все преимущества сжатия, получаемые от самого сжатия. Поэтому требуется схема, не имеющая этого требования.
Вычисление вероятностей разностей хэшей будет времязатратным процессом. Все 30 тысяч значений разностей хэшей, их сумм и количеств невозможно было хранить в памяти для вычисления их вероятностей. Поэтому для вычисления этих вероятностей понадобится затратная структура данных, хранящаяся на диске.

Но Макилрой придумал изящное решение: он заметил, что разности хэшей соответствуют геометрическому распределению, что позволяло реализовать эффективную схему сжатия. Давайте для начала разберёмся, что же такое геометрическое распределение этих значений разностей хэшей.

Моделирование разностей хэшей как геометрического распределения

Геометрическое распределение — это дискретная вероятность, используемая для моделирования ситуаций, в которых мы проводим эксперимент, пока не достигнем успеха. Например, бросание шестигранной кости до выпадения единицы образует геометрическое распределение с вероятностью успеха 1/6. Более простой пример: бросание монетки до выпадения «орла».

Если вероятность неудачи равна p, вероятность успеха равна q и если мы достигаем успеха на k-той попытке, то производящая функция вероятностей геометрического распределения задаётся следующей формулой:

$\begin{align*} &P = p^kq \end{align*}$

Давайте теперь разберёмся, как значения разностей хэшей соотносится с этим распределением.

Так как каждый хэш-код имеет ширину b битов, у нас есть пространство из 2^b точек. И в этом пространстве распределено v хэш-кодов. Вероятность того, что произвольная точка в этом пространстве содержит хэш-код, равна аq=v/2^b, а вероятность того, что точка будет пустой — p=1-(v/2^b).

$\begin{align*} &\text{P(точки, содержащей хэш-код)} = q = \frac{v}{2^b} \\ &\text{P(пустой точки)} = p = 1 - \left(\frac{v}{2^b}\right) \end{align*}$

Но нас интересует моделирование распределения значений разностей хэшей, а не самих хэш-кодов. Разность хэшей k возникает, когда два последовательных значения хэшей в отсортированной последовательности разделены k позициями. Например, если у нас есть два последовательных значения хэш-кодов 20 и 25, то разность хэшей будет равна 5.

Какова вероятность встретить разность хэшей k? Для каждого значения хэша h в нашем пространстве:

Нужно, чтобы следующие k-1 позиций после h были пустыми
Затем значение хэша должно находиться в позиции h+k
Вероятность k-1 пустых позиций равна p^(k-1)
Вероятность наличия значения хэша в позиции h+k равна q

Следовательно, вероятность разности хэшей k равна:

$\begin{align*} &\text{P(difference=k) =} p^\left(k-1\right)q \end{align*}$

И это выражение точно соответствует геометрическому распределению!

Если прочитать научную статью про spell, то можно узнать, что для этого получения вывода автор пошёл по другому пути. Он моделирует генерацию хэш-кодов как процесс Пуассона, а потом двигается дальше.

Но в чём смысл моделирования в виде геометрического распределения? Оказывается, для геометрически распределённых целых чисел существует очень простая и эффективная схема кодирования длин серий, изложенная Голомбом в его статье 1965 года. Давайте разберёмся, как она работает.

Схема сжатия геометрически распределённых целых чисел (код Голомба)

Код Голомба — это простая схема кодирования длин серий (run-length encoding, RLE) для геометрически распределённых целых чисел, которую Макилрой использовал для сжатия разностей хэшей. В ней используется тот факт, что геометрически распределённые значения имеют экспоненциально снижающуюся вероятность успеха, что можно применить для сжатия.

Что под этим подразумевается? Вспомним, что в случае геометрического распределения вероятность успеха после k попыток определяется так:

Допустим, мы находим целочисленное m, такое, что p^m = 1/2. Это значит, что вероятность успеха после k + m попыток равна:

$\begin{align*} &\text{P(успеха после k + m попыток)} = p^\left(k + m\right)q = \frac{1}{2}p^kq \end{align*}$

Иными словами, вероятность получения успеха за k + m попыток вдвое меньше, чем вероятность получения за m попыток. И эта вероятность продолжает уменьшаться вдвое каждые m последовательных попыток. Это экспоненциально затухающее распределение вероятностей.

Разбираем экспоненциально затухающие вероятности на примере

Давайте рассмотрим пример с симметричной монетой. Будем бросать её, пока не выпадет «орёл». Для симметричной монеты p = q = 1/2.

Здесь m = 1, поскольку p¹ = 1/2. Это значит, что при каждой попытке вероятности затухают вдвое:

$\begin{align*} &P(k=1) = \frac{1}{2} \\ &P(k=2) = \frac{1}{4} \\ &P(k=3) = \frac{1}{8} \\ &P(k=4) = \frac{1}{16} \end{align*}$

Давайте возьмём пример перекошенной монеты, такой, что p=1/sqrt(2) = 0,707 и q=0,293.

Здесь m=2, так как p² = 1/2. В этом случае вероятности затухают после каждого блока размером 2.

$\begin{align*} &P(k=1) = 0.293 \\ &P(k=2) = 0.207 \\ &P(k=3) = 0.116 \\ &P(k=4) = 0.104 \\ &P(k=5) = 0.073 \\ &P(k=6) = 0.051 \end{align*}$

Мы видим, что вероятности затухают вдвое с каждым чётным значением k. Например:

$\frac{P(k=2)}{P(k=4)} = \frac{P(K=4)}{P(k=6)} \approx 0.5$

Важность экспоненциально затухающих вероятностей

Такой паттерн экспоненциального затухания позволяет нам группировать значения разностей хэшей в блоки размером m. Каждое значение в блоке получает код размером k битов, а следующий блок получает коды размером k + 1 битов. Причины этого заложены в теории информации.

Минимальное количество битов, необходимое для кодирования результат события, определяется его объёмом информации, который равен -log₂(p), где p — вероятность этого события.

Это значит, что если событие имеет вероятность 1/2, то оно требует 1-битного кода, событие с вероятностью 1/4 — 2-битного, событие с вероятностью 1/8 — 3-битного, и так далее.

Мы можем использовать это для геометрически распределённых значений, скомбинировав их в блоки размером m. Значениям внутри отдельных блоков можно присвоить коды одинаковой длины, а значениям в последующем блоке — на один бит шире для их значений m.

Arranging hash code differences in blocks of sizes m, where each block’s probability is half of that of its predecessor. If the predecessor block gets k bit wide codes, the next block gets k+1 bit wide codes. — Выстраиваем разности хэш-кодов в блоки размером m, где вероятность каждого блока вдвое меньше вероятности его предшественника. Если предшествующий блок получает коды шириной k битов, то следующий блок получит коды шириной k+1 битов.

Оказалось, формирование блоков со всё увеличивающимися кодами также приводит к красивому самоподобному битовому паттерну со свойствами, позволяющими очень легко генерировать такие коды. Давайте посмотрим, как образуется такой самоподобный паттерн.

Самоподобные паттерны

По сути, под самоподобием паттернов подразумевается, что коды по конкретным кодам внутри блока повторяют себя по тому же индексу в следующем блоке с одним добавленным слева битом-заполнителем.

Например, если код во второй позиции первого блока имеет значение 0001, то второй код во втором блоке будет равен 10001. Аналогично, код во второй позиции третьего блока будет равен 110001 и так далее.

Такой самоподобный паттерн возникает естественным образом благодаря тому, что в каждом последующем блоке коды становятся на один бит длиннее. Давайте рассмотрим конкретный пример.

Пример самоподобных кодов

Допустим блок имеет размер m=5, а коды в первом блоке имеют ширину k=4 бита.

Если первый код в первом блоке имеет значение 0110, то мы можем сгенерировать коды для остальной части блока, прибавляя 1 к предыдущему значению кода. Коды для первого блока будут выглядеть так:

коды блока 1: 0110 0111 1000 1001 1010

Как видите, первый блок заканчивается кодом 1010. Естественным значением для следующего кода должно быть 1011, но поскольку этот код находится в следующем блоке, его значение должно быть на 1 бит шире. В результате нам нужно выполнить сдвиг влево на один бит, получив 10110. Можно заметить, что младшие 4 бита этого кода такие же, как в первом коде первого блока. Это визуализировано на показанной ниже диаграмме.

An example of self-similar codes. The first code in the first block are same as least 4 bits of the first code in the 2nd block — Пример самоподобных кодов. Первый код в первом блоке такой же, как младшие 4 бита первого кода во втором блоке

Здесь стоит также отметить то, что мы получаем первое значение второго блока, выполнив сдвиг влево на 1 бит, то есть самый младший бит (least significant bit, LSB) всегда равен 0.

Для образования самоподобных паттернов нужно, чтобы у первого кода в первом блоке LSB было значение 0. Из этого следует, что первый код всегда оказывается чётным числом вида 2x.

Самоподобный код обладает парой дополнительных свойств, позволяющих интуитивно определить минимальную битовую ширину k кодов в первом блоке. Давайте разбираться.

Битовая ширина кодов

Чтобы вычислить минимальное количество битов, необходимых для кодирования первого блока, предположим, что первое закодированное значение в первом блоке — это 2x.

Тогда первый код во втором блоке должен быть 2x + m. Однако поскольку коды в следующем блоке должны быть на 1 бит шире, это значение сдвигается влево на 1 бит, что делает его 2(2x + m).

Сдвиг значения влево на 1 бит удваивает его.

Благодаря самоподобному паттерну мы можем рассуждать об этих кодах с ещё одной точки зрения. Если первый код в первом блоке — это 2x, то в следующем блоке:

Нам нужен тот же паттерн (2x)
Но с дополнительным битом слева
Добавление бита слева эквивалентно прибавлению 2^k
То есть код превращается в 2^k + 2x

Соединив эти два соотношения, мы получим следующее уравнение:

$\begin{align*} &2^k + 2x = 2(2x + m) \\ &\text{или } 2^k = 2m + 2x \\ &\text{Здесь x — неотрицательное число, поэтому можно упростить это до} \\ &2^k \ge 2m \end{align*}$

Вычислив наименьшее целочисленное значение k, мы можем получить ширину кода первого блока.

То же уравнение также даёт нам значение x:

$\begin{align*} x = 2^{(k-1)} - m = 2^{\lceil \log_2 m \rceil} - m \end{align*}$

Если мы знаем значения m, k и x, это позволит нам создать простой алгоритм кодирования.

Алгоритм кодирования

В статье Голомба представлен другой алгоритм кодирования и декодирования, но в коде spell для Unix используется чуть более сложный, но и более эффективный алгоритм. Ниже я объясню алгоритм, реализованный в spell.

Давайте поймём, как кодировать значение кодом Голомба. Вспомним, что у нас есть:

Начальная битовая ширина k
Размер блока m
Первый код в первом блоке — это 2x, где x = 2^(k-1) - m

Вот алгоритм кодирования:

def encode(value):
    # Случай 1: значения меньше x
    # Они получают короткие коды длиной k-1
    # Потому что у нас имеются неиспользованные битовые паттерны
    if value < x:
        return value, k-1  # return (code, length)
    
    # Случай 2: значения >= x
    # Нужно определить, к какому блоку они относятся
    value = value - x     # регулируем относительно первого кода
    y = 1                 # отслеживаем номер блока при помощи битовых сдвигов
    length = k           # начинаем с k битов
    
    # Находим блок, многократно вычитая размер блокаock size
    while value >= m:    # m - размер блока
        value -= m       # переходим к следующему блоку
        y = y << 1      # добавляем бит-заполнитель для следующего блока
        length += 1     # каждому блоку нужен ещё один бит
    
    # Генерируем окончательный код:
    # (y-1) << k создаёт биты-заполнители на основании номера блока
    # x*2 добавляет смещение для первого кода
    # значение добавляет позицию внутри текущего блока
    code = ((y-1) << k) + (x*2) + value
    return code, length

На рисунке ниже показаны два примера, демонстрирующие, как это работает на практике:

Examples of how the encoding algorithm works for values 2 and 8 — Примеры того, как работает алгоритм кодирования для значений 2 и 8

Исходную реализацию этого алгоритма для svr4 из Unix можно найти здесь.

Алгоритм декодирования

Процесс декодирования тоже не так сложен. Если у нас есть код, то нужно:

Сначала посмотреть на k-1 его старших битов (обозначим их w):
- Если w меньше x, то это более короткий код
- Декодированное значение — это просто само w
Если w ≥ x, то нам нужно
- Добавить в w ещё один бит
- Посмотреть на k самых младших битов w: обозначим их u
- если u < 2x + m:
  - значение = x + u + (s - 1)m
  - где s — это количество дополнительных битов, добавленных в w
- иначе:
  - продолжаем добавлять новые биты в w пока не получим u < 2x + m

Исходную реализацию алгоритма декодирования для svr4 из Unix можно найти здесь.

Эффективность сжатия кодов Голомба

Так насколько же хорошо эта методика способна сжимать разности хэшей?

Вспомним, что теоретический предел сжатия — это 13,57 бита на слово. Коды Голомба позволяют достичь ожидаемой длины кода 13,60 бита, что очень близко к теоретическому минимуму.

Однако поиск значения в таком сжатом словаре был довольно медленным. Необходимо начинать с его начала, декодировать и суммировать значения, пока не будет найден или превышен нужный хэш-код.

Для ускорения процесса окончательная реализация spell в Unix разбивала таблицу разностей на M ячеек. Это позволяло ей сначала найти нужную ячейку, а затем выполнять сканирование только в ней, ускоряя поиск на коэффициент M.

При такой схеме разбиения требовалось хранить дополнительные указатели на ячейки, увеличивая требования к хранилищу на log₂M для каждого слова. Общий размер хранилища увеличился примерно до 14 битов на слово, но такой компромисс был приемлемым: он по-прежнему позволял оставаться в рамках бюджета памяти, обеспечивая гораздо более высокую скорость поиска.

Заключение

Команда spell из Unix — потрясающая страница истории разработки ПО, написанная благодаря серьёзным ограничениям памяти PDP-11. Особенно интересна она тем, что эволюционировала из простого поиска по дисковому словарю до изящного решения, сочетающего в себе множество концепций computer science:

Вероятностные структуры данных (фильтры Блума)
Теорию информации (вычисления оптимальной битовой ширины)
Теорию вероятностей (геометрическое распределение)
Алгоритмы сжатия (код Голомба)

Процесс разработки был крайне познавательным:

Он начался с фильтров Блума и обеспечения приемлемой частоты ложноположительных срабатываний
С ростом размера словаря реализация перешла к сжатому хэшированию, при котором разработчики:
- Вычислили теоретический минимум требуемых битов
- Выявили паттерны в разностях хэшей
- Использовали код Голомба, чтобы добиться почти оптимального сжатия
- Добавили разбиение на ячейки для ускорения операций поиска, при этом задействовали минимальное дополнительное пространство

Несмотря на то, что современные алгоритмы проверки правописания используют другие методики, например редакционное расстояние и языковые модели, инженерные достижения, полученные при разработке spell для Unix, не теряют своей ценности. Они показывают, что глубокое понимание теоретических концепций в условиях практических ограничений может привести к созданию эффективных и изящных решений.

А самое важное — это демонстрация того, что лучшие инновации возникают в случае ограниченных ресурсов, заставляющих нас глубже задумываться о задачах, а не просто экстенсивно наращивать мощь оборудования.

Ссылки

Комментарии (6)

Javian
20.02.2025 06:42
#27945424
64кБ в 1970х имхо мощная машина.

Sadok
20.02.2025 06:42
#27947154
наш ВПК улыбается в усы. уж как там умеют в "впихнуть невпихуемое" - это классика.
1. AKudinov
  20.02.2025 06:42
  #27947472
  С нетерпением ждём захватывающих примеров.
  1. Javian
    20.02.2025 06:42
    #27947612
    Скорее всего имеются ввиду блоки управления советских/российских ракет, которые продают из Украины в Европу/США и там любители проводят обзор. Железо там 70-80-е. При этом содержит навигационную карту полета с высотами местности.
    
    Как пример такой публикации
    
    AKudinov
    20.02.2025 06:42
    #27950216
    На фотографии вижу контроллер 1867ВМ2, достаточно современный, у него 40 МГц тактовой частоты и 16-битная DSP на борту. Далеко не "70-е - 80-е".
    
    CrashLogger
    20.02.2025 06:42
    #27950724
    Цельнотянутый с буржуйского TMS320C10, разработка 83 года