Хеширование: рандомизированная реализация словарей - Рандомизированные алгоритмы

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

Задача

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

Во всех перечисленных примерах существует очень большое универсальное множествоU возможных элементов: множество всех возможных людей, всех возможных абзацев (допустим, до определенной длины в символах) или всех возможных решений вычислительно сложной задачи. Структура данных организует хранение информации о множестве S ⊆ U, размер которого обычно составляет ничтожную часть U; при этом структура данных обеспечивает возможность вставки и удаления элементов из S, а также быстрой проверки того, принадлежит ли заданный элемент S.

Словарь представляет собой структуру данных, которая поддерживает следующие операции:

♦ MakeDictionary инициализирует словарь, способный хранить подмножество S универсального множества U; только что созданный словарь пуст.

♦ Insert(w) добавляет элемент u ∈ U в множество S. Во многих случаях с u также связывается дополнительная информация (например, u может быть именем или табельным номером работника, а в структуре данных также сохраняется личная информация о работнике); будем считать, что эта информация сохраняется в словаре как часть записи вместе с u. (Таким образом, в общем случае под “элементом u” будет пониматься u вместе с дополнительной информацией).

♦ Delete(u) удаляет элемент u из множества S, если он там хранится.

♦ Lookup(u) проверяет, принадлежит ли элемент u множеству S (и если принадлежит читает дополнительную информацию, сохраненную вместе с u).

Многие реализации, рассмотренные ранее в книге, используют эти операции (или часть из них): например, в реализациях алгоритмов обхода графа BFS и DFS велись множества S уже посещенных узлов. Тем не менее между теми задачами и текущей ситуацией существует принципиальное различие — размер U. Универсальное множество U в BFS и DFS представляет собой множество узлов V, уже явно заданное как часть входных данных. В таких случаях вполне допустимо хранить множество S ⊆ U так, как это делалось: определение массива с позициями |U|, по одной для каждого возможного элемента, и присваивание элементу в позиции, соответствующей u, 1 для u ∈ S или 0 для u ∉ S. Такая реализация позволяет выполнять операции вставки, удаления и проверки с постоянным временем простым обращением к элементу массива.

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

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

Разработка структуры данных

Для примера рассмотрим задачу, с которой сталкивается автоматизированный сервис обработки новостей. Предположим, вы получаете постоянный поток коротких статей от разных информагентств, публикаций в блогах и т. д. и сохраняете начальный абзац каждой статьи (который усекается до 1000 символов). Ради полноты охвата используется множество источников информации, поэтому возникает значительная избыточность: одна статья может встречаться многократно.

При появлении новой статьи нужно быстро проверить, не встречался ли такой начальный абзац ранее. Таким образом, словарь — именно та структура данных, которая нужна в этой задаче: универсальное множество U представляет собой множество всех строк длины до 1000 символов (или ровно 1000, если дополнить их пробелами); структура данных поддерживает множество S ⊆U, состоящее из строк (то есть начальных абзацев), встречавшихся ранее.

Одно из возможных решений — ведение связанного списка всех абзацев с просмотром его при каждом появлении нового абзаца. Однако операция Lookup в этом случае занимает время, пропорциональное |S|. Как вернуться к характеристикам, близким к решению на базе массива?

Хеш-функции

Основная идея хеширования заключается в том, чтобы работать с массивом размера |S| (вместо размера, сравнимого с астрономическим размером U).

Предположим, требуется организовать хранение множества S с размером до n. Для хранения информации создается массив H размера n, а функция h: U → {0, 1, ..., n - 1} отображает элементы U на позиции массива. Такая функция называется хеш-функцией, а массив H называется хеш-таблицей. Если потребуется добавить элемент u в множество S, u просто сохраняется в позиции h(u) массива H. В случае сортировки абзацев текста h(∙) может рассматриваться как вычисление некоторой числовой сигнатуры или “контрольной суммы” абзаца u; результат определяет позицию массива для хранения u.

Хеширование превосходно работает, если для всех разных u и v в множестве S выполняется условие h(u) ≠ h(v). В таком случае проверка и выполняется за постоянное время: вы проверяете позицию массива H[h(u)], которая либо пуста, либо содержит только u.

Однако в общем случае на такое везение рассчитывать не приходится: могут встретиться два элемента u, v ∈ S, для которых h(u) = h(v). Возникает коллизия: два элемента отображаются на одну позицию в H. Существуют разные методы разрешения коллизий. Мы будем считать, что в каждой позиции H[i] хеш-таблицы хранится связанный список всех элементов u ∈ S с h(u) = i. Операция Lookup(u) работает по следующей схеме:

♦ вычислить хеш-функцию h(u);

♦ проверить связанный список в позиции H[h(u)] и проверить, присутствует ли u в списке.

Отсюда следует, что время, необходимое для Lookup(u), пропорционально сумме времени вычисления h(u) и длине связанного списка в позиции H[h(u)]. В свою очередь, последняя величина представляет собой количество элементов в S, находящихся в коллизии с u. Операции Insert и Delete работают аналогично: Insert добавляет u в связанный список в позиции H[h(u)], а Deleteпросматривает этот список и удаляет элемент u, если он присутствует.

Теперь цель ясна: нужно найти хеш-функцию, которая “равномерно распределяет” добавляемые элементы, чтобы ни один элемент хеш-таблицы H не содержал слишком много позиций. В задачах такого рода анализ худшего случая не слишком информативен. В самом деле, допустим, что |U| ≥ n² (а в некоторых случаях намного больше). Тогда для любой выбранной хеш-функции h существует некоторое множество S из n элементов, которые отображаются на одну позицию. В худшем случае будут вставлены все элементы множества, и тогда в операции Lookupбудет задействован перебор связанного списка длины n. Мы стремимся показать, что рандомизация способна оказать существенную помощь в таких задачах. Как обычно, мы не делаем никаких предположений относительно случайности множества элементов S, а просто применяем рандомизацию при планировании хеш-функции. Коллизии не предотвращаются полностью, но становятся относительно редкими, так что списки получаются достаточно короткими.

Выбор хорошей хеш-функции

Итак, эффективность словаря зависит от выбора хеш-функции h. Как правило, мы будем рассматривать U как большое множество чисел, а затем применять легко вычислимую функцию h, которая отображает каждое число u ∈ U на некоторое значение из меньшего целочисленного диапазона {0, 1, ..., n - 1}. Это можно сделать многими простыми способами: например, использовать несколько первых или последних цифр u или просто вычислить остаток от деления u на п. Хотя эти простые решения хорошо работают во многих ситуациях, они также могут привести к многочисленным коллизиям. В самом деле, фиксированный выбор хеш-функции может создать проблемы из-за особенностей элементов u в приложении: может быть, в конкретных цифрах, используемых в определении хеш-функции, кодируется некоторое свойство u, поэтому количество возможных вариантов невелико. Вычисление остатка от деления u на n может привести к аналогичной проблеме, особенно если n является степенью 2. Рассмотрим конкретный пример: допустим, хеш-функция берет абзац английского текста, использует стандартную кодировку символов (например, ASCII) для преобразования его в последовательность битов, а затем оставляет только несколько начальных битов этой последовательности. Можно предполагать большое количество коллизий в элементах массивов, соответствующих битовым строкам для кодирования часто встречающихся слов (например, “The”), тогда как большие части массива могут быть заняты только абзацами, начинающимися со строк вида “qxf”, а следовательно, останутся пустыми.

На практике лучше использовать величину (u mod р) для простого числа р, близкого к n. Хотя в некоторых случаях этот метод порождает хорошие хеш-функции, он не универсален, а некоторые простые числа работают намного лучше других (например, простые числа, очень близкие к степеням 2, работают не так хорошо).

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

Основная идея, как говорилось ранее, заключается в использовании рандомизации при построении h. Начнем с крайнего случая: для каждого элемента u ∈ U при вставке в S значение h(u) выбирается случайно с равномерным распределением из множества {0, 1, ..., n - 1}, независимо от всех предшествующих вариантов выбора. В этом случае вероятность того, что два случайно выбранных значения h(u) и h(v) совпадут (а следовательно, вызовут коллизию), достаточно мала.

(13.22) В схеме случайного равномерного хеширования вероятность того, что два случайно выбранных значения h(u) и h(v) образуют конфликт (то есть h(u) = h(v)), равна точно 1/n.

Доказательство. Все n² возможных вариантов выбора пар (h(u), h(v)) имеют одинаковую вероятность, и ровно п из этих вариантов приводят к коллизии. ■

Тем не менее использовать хеш-функцию с независимыми случайными равномерными значениями не получится. Чтобы понять почему, предположим, что элемент u вставляется в S, а потом потребовалось выполнить операцию Delete(u) или Lookup(u). Спрашивается, где его искать? Нужно знать случайное значение h(u), использованное при вставке, поэтому значение h(u) необходимо где-то сохранить для быстрой выборки. Но ведь это именно та задача, которую мы пытались изначально решить!

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

Универсальные классы хеш-функций

Ключевая идея заключается в том, что хеш-функция случайно выбирается не из набора всех возможных функций со значениями [0, n - 1], а из особого семейства функций. Каждая функция h в классе функций H отображает универсальное множество U на множество {0, 1, ..., n - 1}, а включаемые функции должны обладать двумя свойствами. Во-первых, они должны предоставлять гарантии из (13.22):

♦ для любой пары элементов u, v ∈ U вероятность того, что для случайно выбранной функции h ∈ H выполняется h(u) = h(v), не более 1/n.

Класс функций H называется универсальным, если для него выполняется первое свойство. Таким образом, (13.22) можно рассматривать как утверждение о том, что класс всех возможных функций, отображающих U на {0, 1, ..., n - 1}, является универсальным.

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

♦ каждая функция h ∈ H имеет компактное представление, и для заданных h ∈ H и u ∈ U значение h(u) может быть вычислено эффективно.

Класс всех возможных функций этим свойством не обладает: фактически единственным способом представления произвольной функции из U в {0, 1, ..., n - 1} является запись ее значений для каждого элемента U.

В оставшейся части этого раздела мы продемонстрируем удивительный факт: существуют классы H, обладающие обоими свойствами. Но перед этим необходимо сначала точно сформулировать базовое свойство, которым должен обладать универсальный класс хеш-функций. Если функция h выбирается случайным образом из универсального класса хеш-функций, то для любого множества S ⊂ U, размер которого не превышает n, и любого u ∈ U, ожидаемое количество элементов S, создающих коллизию с u, является константой.

(13.23) Пусть H — универсальный класс хеш-функций, отображающих универсальное множество U на множество {0, 1, ..., n - 1}, S — произвольное подмножество U размера не более n, а u — любой элемент U. Определим X как случайную переменную, равную количеству элементов s ∈ S, для которых h(s) = h(u), для случайно выбранной хеш-функции h ∈ H. (Здесь S и uфиксированны, а случайность проявляется в выборе h ∈ H). Тогда Е [X] ≤ 1.

Доказательство. Для элемента s ∈ S определяется случайная переменная X_s, которая равна 1, если h(s) = h(u), или 0 в противном случае E[X_s] = Pr[X_s - 1] ≤ 1/n, так как класс функций универсален.

Затем и вследствие линейности ожидания имеем

Разработка универсального класса хеш-функций

Переходим к созданию универсального класса хеш-функций. В качестве размера хеш-таблицы H будет использоваться простое число p ≈ n. Чтобы иметь возможность использовать целочисленную арифметику при создании хеш-функций, универсальное множество будет определяться векторами вида х = (х₁, х₂, ..., x_r) для некоторого целого r, где 0 ≤ х_i ≤ p для каждого i. Например, можно сначала идентифицировать U целыми числами из диапазона [0,N-1] для некоторого N, а затем воспользоваться смежными блоками из [log p] битов u для определения соответствующих координат х_i. Если U ⊆ [0, N - 1], то необходимое количество координат составит r ≈ log N Λ log n.

Пусть A — множество всех векторов вида a = (a₁, ..., a_r), где a_i — целое число из диапазона [0, р - 1] для каждого i = 1, ..., r. Для каждого a ∈ A определяется линейная функция

Случайная реализация словарей завершена. Семейство хеш-функций определяется в виде H = {h_a : a ∈ A}. Чтобы выполнить операцию MakeDictionary, мы выбираем случайную хеш-функцию из H; иначе говоря, выбирается случайный вектор из A (случайным равномерным выбором каждой координаты), и формируется функция h_a. Заметим, что для определения A необходимо найти простое число p ≥ n. Методы быстрого генерирования целых чисел известны, но мы здесь в эту тему не углубляемся. (На практике можно воспользоваться таблицами известных простых чисел даже для относительно больших n.)

Затем результат используется как хеш-функция для реализации операций Insert, Delete и Lookup. Семейство H = {h_a : a ∈ A} удовлетворяет формальному определению второго свойства: оно имеет компактное представление, так как простым выбором и сохранением случайного a ∈ A мы можем вычислить h_a(u) для всех элементов u ∈ U. Следовательно, чтобы показать, что H ведет к эффективной реализации словарей на базе хеширования, достаточно показать, что H — универсальное семейство хеш-функций.

Анализ структуры данных

При использовании хеш-функции h_a из определенного ранее класса H коллизия h_a(x) = h_a(y) определяет линейное уравнение с вычислением остатка от деления на простое число р. Для анализа таких уравнений полезно знать следующий “закон сокращения”.

(13.24) Для любого простого числар и любого целого z ≠ 0 mod р и любых двух целых α, β, если αz = βz mod р, то α = β mod р.

Доказательство. Предположим, αz = βz mod р. Тогда при переносе составляющих получаем z(α - β) = 0 mod р, а следовательно, z(α - β) делится на р. Но z ≠ 0 mod р, поэтому z не делится на р. Так как р является простым числом, из этого следует, что α - β должно делиться на р; то есть α = β mod р, как и утверждалось. ■

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

(13.25) Класс линейных функций H, определенный выше, универсален.

Доказательство. Пусть х = (х₁, х₂, ... x_r) и y = (y₁, y₂, ... y_r) — два разных элемента U. Необходимо показать, что вероятность h_a(x) = h_a(y) для случайно выбранного a ∈ A не превышает 1/р.

Так как x = у, должен существовать индекс j, при котором х_j ≠ у_j. Рассмотрим следующий способ выбора случайного вектора a ∈ A. Сначала выбираются все координаты a_i, для которых i ≠ j, после чего выбираются координаты а_j. Покажем, что независимо от выбора всех остальных координат а_i вероятность h_a(x) = h_a(у), обусловленная завершающим выбором а_j, равна 1/р. Из этого следует, что вероятность h_a(x) = h_a(у) при случайном выборе полного вектора а также должна быть равна 1/р.

Этот вывод интуитивно понятен: если вероятность равна 1/p независимо от того, как выбираются остальные а_i, то она равна 1 /р в целом. Этот факт также можно доказать напрямую при помощи условных вероятностей. Пусть E — событие h_а(х) = h_a(y), а событие F_b — событие получения всеми координатами а_i (для i ≠ j) последовательности значений b. Ниже будет показано, что Рr[E | F_b] = 1/p для всех b. Из этого следует, что

Итак, чтобы завершить доказательство, мы предположим, что значения всех остальных координат a_i были выбраны произвольно, и рассмотрим вероятность такого выбора а_i, при котором h_a(x) = h_a(y). Перенося слагаемые, мы видим, что h_a(x) = h_a(у) в том и только в том случае, если

Так как варианты выбора для всех а_i (i ≠ j) были фиксированы, правая часть может рассматриваться как фиксированная величина m. Кроме того, определим z = у_j - x_j.

Теперь достаточно показать, что существует ровно одно значение 0 ≤ а_j ≤ р, при котором выполняется а_jZ = m mod р; действительно, если это так, то вероятность выбора этого значения а_jсоставляет ровно 1/р. Предположим, что существуют два таких значения а_j и а'_j. Тогда а_jZ = а'_jz mod р, и, согласно (13.24), должно быть а_j = а'_j, mod р. Но мы предположили, что а_j, а'_j < р, поэтому а_j и а'_j, должны совпадать. Следовательно, в этом диапазоне существует только одно а_j, при котором а_jZ = m mod р.

В частности, это означает, что вероятность выбора а_j, при котором h_a(x) = h_a(у), равна 1/р при любых назначениях других координат а_i в а; следовательно, вероятность коллизии между x и у равна 1/р. Таким образом, нам удалось показать, что H является универсальным классом хеш-функций. ■