Ответ. (1) Не гарантируется, что если пустые места есть, то
мы их найдем. (2) При удалении неясно, как заполнять дыры. (На
практике во многих случаях удаление не нужно, так что такой спо-
соб также применяется. Считается, что удачный подбор r может
предотвратить образование "скоплений" занятых ячеек.)
11.1.4. Пусть для хранения множества всех правильных
русских слов в программе орфографии используется хеширование.
Что нужно добавить, чтобы к тому же уметь находить английский
перевод любого правильного слова?
Решение. Помимо массива val, элементы которого являются
русскими словами, нужен параллельный массив их английских пере-
водов.
11.2. Хеширование со списками
На хеш-функцию с m значениями можно смотреть как на способ
свести вопрос о хранении одного большого множества к вопросу о
хранении нескольких меньшим. Именно, если у нас есть хеш-функция
с m значениями, то любое множество разбивается на m подмножеств
(возможно, пустых), соответствующих возможных значениям
хэш-функции. Вопрос о проверке принадлежности, добавлении или
удалении для большого множества сводится к такому же вопросу для
одного из меньших (чтобы узнать, для какого, надо посмотреть на
значение хеш-функции).
В принципе, эти меньшие множества могут храниться любым
способом (раз они малы, это не очень важно), но удобно их хра-
нить с помощью ссылок, поскольку нам известен их суммарный раз-
мер (равный числу элементов хешируемого множества). Следующая
задача предлагает реализовать этот план.
11.2.1. Пусть хеш-функция принимает значения 1..k. Для каж-
дого значения хеш-функции рассмотрим список всех элементов мно-
жества с данным значением хеш-функции. Будем хранить эти k спис-
ков с помощью переменных
Содержание: array [1..n] of T;
Следующий: array [1..n] of 1..n;
ПервСвоб: 1..n;
Вершина: array [1..k] of 1..n;
так же, как мы это делали для k стеков ограниченной суммарной
длины. Напишите соответствующие программы. (Теперь с удалением
будет меньше проблем.)
Решение. Перед началом работы надо положить Вершина[i]=0
для всех i=1..k, и связать все места в список свободного
пространства, положив ПервСвоб=1 и Следующий[i]=i+1 для
i=1..n-1, а также Следующий[n]=0.
function принадлежит (t: T): boolean;
| var i: integer;
begin
| | i := Вершина[h(t)];
| i := Вершина[h(t)];
| {осталось искать в списке, начиная с i}
| while (i <> 0) and (Содержание[i] <> t) do begin
| | i := Следующий[i];
| end; {(i=0) or (Содержание [i] = t)}
| belong := Содержание[i]=t;
end;
procedure добавить (t: T);
| var i: integer;
begin
| if not принадлежит(t) then begin
| | i := ПервСвоб;
| | {ПервСвоб <> 0 - считаем, что не переполняется}
| | ПервСвоб := Следующий[ПервСвоб]
| | Содержание[i]:=t;
| | Следующий[i]:=Вершина[h(t)];
| | Вершина[h(t)]:=i;
| end;
end;
procedure исключить (t: T);
| var i, pred: integer;
begin
| i := Вершина[h(t)]; pred := 0;
| {осталось искать в списке, начиная с i; pred -
| предыдущий. если он есть, и 0, если нет}
| while (i <> 0) and (Содержание[i] <> t) do begin
| | pred := i; i := Следующий[i];
| end; {(i=0) or (Содержание [i] = t)}
| if Содержание[i]=t then begin
| | {элемент есть, надо удалить}
| | if pred = 0 then begin
| | | {элемент оказался первым в списке}
| | | Вершина[h(t)] := Следующий[i];
| | end else begin
| | | Следующий[pred] := Следующий[i]
| | end;
| | {осталось вернуть i в список свободных}
| | Следующий[i] := ПервСвоб;
| | ПервСвоб:=i;
| end;
end;
11.2.2. (Для знакомых с теорией вероятностей.) Пусть
хеш-функция с m значениями используется для хранения множества,
в котором в данный момент n элементов. Доказать, что математи-
ческое ожидание числа действий в предыдущей задаче не превосхо-
дит С*(1+n/m), если добавляемый (удаляемый, искомый) элемент t
выбран случайно, причем все значения h(t) имеют равные вероят-
ности (равные 1/m).
Решение. Если l(i) - длина списка, соответствующего
хеш-значению i, то число операцией не превосходит C*(1+l(h(i)));
усредняя, получаем искомый ответ, так как сумма всех l(i) равна
n.
Эта оценка основана на предположении о равных вероятностях.
Однако в конкретной ситуации всё может быть совсем не так, и
значения хеш-функции могут "скучиваться": для каждой конкретной
хеш-функции есть "неудачные" ситуации, когда число действий ока-
зывается большим. Приём, называемый "универсальным хешировани-
ем", позволяет обойти эту проблему. Идея состоит в том, что бе-
рётся семейство хеш-функций, причем любая ситуация оказывается
неудачной лишь для небольшой части этого семества.
Пусть H - семейство функций, каждая из которых отображает
множество T в множество из n элементов (например, 0..n-1). Гово-
рят, что H - универсальное семейство хеш-функций, если для любых
двух различных значений s и t из множества T вероятность события
"h(s)=h(t)" для случайной функции h из семейства H равна 1/n.
(Другими словами, те функции из H, для которых h(s)=h(t), сос-
тавляют 1/n-ую часть всех функций в H.)
Замечание. Более сильное требование к семейству H могло бы
состоять в том, чтобы для любых двух различных элементов s и t
множества T значения h(s) и h(t) случайной функции h являются
независимыми случайными величинами, равномерно распределенными
на 0..n-1.
11.2.3. Пусть t[1]..t[u] - произвольная последовательность
различных элементов множества T. Рассмотрим количество действий,
происходящих при помещении элементов t[1]..t[u] в множество, хе-
шируемое с помощью функции h из универсального семейства H. До-
казать, что среднее количество действий (усреднение - по всем h
из H) не превосходит C*u*(1+u/n).
Решение. Обозначим через m[i] количество элементов последо-
вательности, для которых хеш-функция равна i. (Числа
m[0]..m[n-1] зависят, конечно, от выбора хеш-функции.) Коли-
чество действий, которое мы хотим оценить, с точностью до посто-
янного множителя равно сумме квадратов чисел m[0]..m[n-1]. (Если
k чисел попадают в одну хеш-ячейку, то для этого требуется при-
мерно 1+2+...+k действий.) Эту же сумму квадратов можно записать
как число пар , для которых h[t[p]]=h[t[q]]. Последнее ра-
венство, если его рассматривать как событие при фиксированных p
и q, имеет вероятность 1/n при p<>q, поэтому среднее значение
соответствующего члена суммы равно 1/n, а для всей суммы получа-
ем оценку порядка u*u/n, а точнее u*u/n + u, если учесть члены с
p=q.
Оценка этой задачи показывает, что в на каждый добавляемый
элемент приходится в среднем C*(1+u/n) операций. В этой оценке
дробь u/n имеет смысл "коэффициента заполнения" хеш-таблицы.
11.2.4. Доказать аналогичное утверждение для произвольной
последовательности операций добавления, поиска и удаления (а не
только для добавления, как в предыдущей задаче).
Указание. Будем представлять себе, что в ходе поиска, до-
бавления и удаления элемент проталкивается по списку своих кол-
лег с тем же хеш-значением, пока не найдет своего двойника или
не дойдет до конца списка. Будем называть i-j-столкновением
столкновение t[i] с t[j]. Общее число действий примерно равно
числу всех столкновений плюс число элементов. При t[i]<>t[j] ве-
роятность i-j-столкновения равна 1/n. Осталось проследить за
столкновениями между равными элементами. Фиксируем некоторое
значение x из множества T и посмотрим на связанные с ним опера-
ции. Они идут по циклу: добавление - проверки - удаление - до-
бавление - проверки - удаление - ... Столкновения между ними
происходят между добавляемым элементом и следующими за ним про-
верками (до удаления включительно), поэтому общее их число не
превосходит числа элементов, равных x.
Теперь приведем примеры универсальных семейств. Очевидно,
для любых конечных множеств A и B семейство всех функций, отоб-
ражающих A в B, является универсальным. Однако этот пример с
практической точки зрения бесполезен: для запоминания случайной
функции из этого семейства нужен массив, число элементов в кото-
ром равно числу элементов в множестве A. (А если мы можем себе
позволить такой массив, то никакого хеширования нам не требует-
ся!)
Более практичные примеры универсальных семейств могут быть
построены с помощью несложных алгебраических конструкций. Через
Z[p] мы обозначаем множество вычетов по простому модулю p, т.е.
{0,1,...,p-1}; арифметические операции в этом множестве выполня-
ются по модулю p. Универсальное семейство образуют все линейные
функционалы на Z[p] в степени n со значениями в Z[p]. Более под-
робно, пусть a[1],...,a[n] - произвольные элементы Z[p];
рассмотрим отображение
h: |-> a[1]x{1]+...+a{n]z[n]
Мы получаем семейство из (p в степени n) отображений, параметри-
зованное наборами a[1]...a[n].
11.2.5. Доказать, что это семейство является универсальным.
Указание. Пусть x и y - различные точки пространства Z[p] в
степени n. Какова вероятность того, что случайный функционал
принимает на них одинаковые значения? Другими словами, какова
вероятность того, что он равен нулю на их разности x-y? Ответ
дается таким утверждением: пусть u - ненулевой вектор; тогда все
значения случайного функционала на нем равновероятны.
В следующей задаче множество B={0,1} рассматривается как
множество вычетов по модулю 2.
11.2.6. Семейство всех линейных отображений из (B в степени
m) в (B в степени n) является универсальным.
Родственные идеи неожиданно оказываются полезными в следу-
ющей ситуации (рассказал Д.Варсонофьев). Пусть мы хотим написать
программу, которая обнаруживала (большинство) опечаток в тексте,
но не хотим хранить список всех правильных словоформ. Предлага-
ется поступить так: выбрать некоторое N и набор функций
f[1],...,f[k], отображающих русские слова в 1..N. В массиве из N
битов положим все биты равными нулю, кроме тех, которые являются
значением какой-то функции набора на какой-то правильной слово-
форме. Теперь приближённый тест на правильность словоформы та-
ков: проверить, что значения всех функций набора на этой слово-
форме попадают на места, занятые единицами.
Глава 12. Множества и деревья.
12.1. Представление множеств с помощью деревьев.
Полное двоичное дерево. T-деревья.
Нарисуем точку. Из нее проведем две стрелки (влево вверх и
вправо вверх) в две другие точки. Из каждой из этих точек прове-
дем по две стрелки и так далее. Полученную картинку (в n-ом слое
будет (2 в степени (n - 1)) точек) называют полным двоичным де-
ревом. Нижнюю точку называют корнем. У каждой вершины есть два
сына (две вершины, в которые идут стрелки) - левый и правый. У
всякой вершины, кроме корня, есть единственный отец.
Пусть выбрано некоторое конечное множество вершин полного
двоичного дерева, содержащее вместе с каждой вершиной и всех ее
предков. Пусть на каждой вершине этого множества написано значе-
ние фиксированного типа T (то есть задано отображение множества
вершин в множество значений типа T). То, что получится, будем
называть T-деревом. Множество всех T-деревьев обозначим Tree(T).
Рекурсивное определение. Всякое непустое T-дерево разбива-
ется на три части: корень (несущий пометку из T), левое и правое
поддеревья (которые могут быть и пустыми). Это разбиение уста-
навливает взаимно однозначное соответствие между множеством не-
пустых T-деревьев и произведением T * Tree (T) * Tree (T). Обоз-
начив через empty пустое дерево, можно написать
Tree (T) = {empty} + T * Tree (T) * Tree (T).
Поддеревья. Высота.
