AOP_Tom3 (1021738), страница 211
Текст из файла (страница 211)
31. Для получения дисперсии среднего количества проб в случае успешного поиска разделим эту величину на Ач и вычтем -'(Оо(М,Ач — 1)— 1)в: асимптотически это равно чв((1+ 2а)/(1 — а) — 1)/Ач -~- 0(Ач в). (См. Р. Р1а)о!ес, Р. Ч РоЫеое, апб А, Ио!а, А18опобтчса 22 (1998), 490 — о15; П. Е. КппвЬ, .418огйбибса 22 (1998), 561-568. Вычисленная дисперсия должна отличаться от общей дисперсии, которая равна Е 2 ч4ч7Ач — -'(Оо(Мч А' — 1) — 1); см, ответы к упр.
37 и 67.) Если все записи имеют приблизительно одинаковое перемещение ч4 и если успешный поиск осуществляется значительно чаще, чем неудачный, то выгодно начинать с позиции Ь' = Ь(К) + бч а затем опробовать позиции Ь' — 1, Ь' + 1, Ь' — 2 и т. д. П. В. Поблете (Р. Ъ'. РоЫеое), А. Виола (А. Ччо!а) и Д Я. Мунро (,1. 1.
Мппго) показали (Валч1опч Ясгпсвпгев апч4 А(8опйбтв 10 (1997), 221 — 255], что 2 ч(ч может быть сделана стояь же малой, как и в методе Робин Гуда, при помощи более простого подхода, называемого хешированием "последним пришел — первым обслужен" (1авс-соте-бгвс-вегтед), при котором каждый вновь вставляемый ключ помещается в свою начальную позицию; все другие ключи перемещаются иа один шаг, пока не будет найдено пустое место. Оба эти подхода применимы как к двойному хешированию, так и к линейному исследованию, но уменьшение количества проб не компенсирует увеличения времени, требуемого для одной пробы с учетом двойного хеширования, пока таблица не заполнитса почти до отказа (см.
РоЫе1е апч) Манго, Х А18опйбтв 10 (1989), 228-248). 68. Среднее значение (бч + + ч(л) равно 89. Пусть йь = р! + рье! +; тогда неравенство йь > шах(0, 1 — (Ь вЂ” 1)(М вЂ” п)/М) дает нижнюю границу Сл = Еь>! 9ю 70. Люкер (1 пе1сег) и Молодович (Мо1одо»чссЬ) [СошЫпасог!са 13 (1993), 83-96] привели замечательно простое доказательство подобного результата,но у них появляется дополнительный множитель (1об М) под знаком О; указанный результат получается тем же путем с помощью определенных трюков при оценке вероятностей. А. Р. Сигель (А. )1. Б!ебе1) и Ж.
П. Шмидт (2. Р. ЯсЬш!б!) показали, что в действительности ожидаемое количество проб при двойном хешировании составляет 1/(1 — и) + О(1/М) для фиксированного и = А!/М. [Сошрпсег яс!енсе Тесй. Веро!с 687 (Ме» '!огре Со»галс 1пясйвге, 1995).] 72. [Х Согпр. Яуза Яс!'. 18 (1979), 143 — 154.] (а) При данных ключах К!, ..., Кл и К вероятность того, что К, находится в том же списке, что и К, равна < 1/М, если К ~ К,. Следовательно, ожидаемый размер списка равен < 1 + (Х вЂ” 1)/М.
(Ь) Предположим, что существуег Я возможных символов и имеется М~ возможных вариантов выбора для каждого Ь;. Случайный выбор каждого Ь; эквивалентен выбору случайной строки из матрицы Н из Мч! строк и Я' столбцов с элементом Ь(х!... х!) = (Ь!(х!) + + Ь!(х!)) шо!4М в столбце х!... х!. В столбцах К = х!... х! и К' = х', х[ с х; ~ х!. для некоторого !' имеем Ь(К) = (э + Ь!(х!)) шос1 М и Ь(К ) = (э + Ьд(х',)) пюд М, где э = 2, Ь;(х;) и в' = Я,, Ь,(х',) независимы от Ь!. Значения Л„(х,)— Ьд(х ) равномерно распределены по модулю М; следовательно, мы имеем Ь(К) = Ь(К ) с вероятностью 1/М без учета значений э и э'. (с) Да; добавление любой константы к Ь.(х!) прибавляет к Л(х) константу по модулю М. 73. (1) Это специальный вариант упражнения 72, (с), в котором каждый ключ рассматривается как последовательность битов, а не символов. (8) Из доказательства (Ь) следует, что достаточно показать равномерность распределения Ь!(х!) — Ь (х,) по модулю М при х, ф х,.
В действительности вероятность того, что Ь,(х;) = у и Ь,(х,) = у, равна 1/М для любых данных у и у', поскольку уравнения а,х! + 8 и у и а х,' + 6! га у' по модулю с простым М имеют единственное решение (а,, Ь!) для любых данных (у, у'). Если М не является простым и р — простое число, большее, чем М, подобный результат имеет место, если предположить Ь! (х!) = ((агх! + Ьр) шод р) шо!4 М, где а, и Ь! выбраны случайныч образом по модулю р. В этом случае семейство не является полностью универсальным, но достаточно близкб к таковому для достижения практических целей: вероятность коллизии различных ключей не превышает 1/М+ г(М вЂ” !.)/Мр < 1/М+ М/4р', где г =.р шос) М. 74.
В и~лом зго утверждение лежню Иапрнмер предполо з рассмотрим матрицу Н с („) строками, по одной для каждого варианта размещения и нулей в различных столбцах; ненулевыми являются элементы 1, 2, ..., А! — и слева направо в каждой строке, Эта матрица универсальна, потому что в каждой паре столбцов имеется („э) = („) — —, < („) (л) = гс/М совпадений; однако число нулей в каждой строке составляет !/х7тт Р О(1) + О(7!7/М). Примечание. Этот пример указывает, что ожидаемый размер списка существенно отличается от ожидаемого количества коллизий при вставке нового ключа, рассмотрим предположение Ь(к!...
х!) = Ь! (х!), где Ь! выбрано случайным образом. Такое семейство хеш-функций делает ожидаемый размер каждого списка равным Ь!/М; конечно, это еще не универсальное семейство, потому что множество из Х ключей, имеющих один и тот же первый символ х!, приведет к образованию одного списка размером А! и пустых прочих списков. Ожидаемое количество коллизий будет равно Ь!(Ф вЂ” 1)/2, однако для универсального хеш-семейства это число не превышает А!(Ь! — 1)/2М независимо от множества ключей. С другой стороны, могьсно показать, что ожидаемый размер каждого списка в универсальном семействе равен 0(1) Ч-0(Х/ъь М ). Предположим, что в строке 5 имеется гь нулей.
Тогда в ней содержится как минимум ( ') пар одинаковых элементов. 54аксимум 2 ь ь хл при условии 2 л, ('") < (г ) Я/М достигается, когда каждое гь равно а, где (*) = (г ) /йь, а именно 1 1 ьз7(Х вЂ” 1) ьг'(ьт" — 1) г= — + — + <1+ 2 75. (а) Очевидно, что утверждение истинно, да'ке если Ьг, . Ьь тождественно равны нулю. (Ь) Верно в соответствии с ответом к 72, (Ь) (с) Верно. Результат ясен, если все К, К и К' отличаются в некоторой позиции символа.
В противном случае примем, что х = х„' Р х," и к„ф х'„= хь. Тогда величины йь(х,) + йь(хг), Ьь(хг) + Ьь(хь) и 1ьь(хь') + 7ь„(хь) независимы одна от другой, равномерно распределены и не зависят от других 1 — 2 символов ключей. (ь1) Неверно. Рассмотрим, например, случаи для М = 1 = 2 с однобитовыми символами. Тогда все четыре ключа хешируются в одну и ту же позицию с вероятностью 1/4. 78. Используем 6(К) = (1ье(1)+йь(хь)+. +1ьь(хь)) шоь4 М, где каждая функция 6 выбирается, как в упр. 73. Случайные коэффициенты для Ьь (и при желании предварительно вычисленный массив значений) генерируются при первом появлении ключа длиной > 1.
Поскольку 1 не ограничено, матрица Н бесконечна; однако в реальной работе программы будет использоваться только ее конечная часть. 77. Пусть р < 2 — вероятность того, что два 32-битовых ключа имеют один и тот же — ьв образ в Н. Наихудшая ситуация склалываетсн, когда два данных ключа совпадают в семи из их восьми 32-битовых подключей; значит, вероятность коллизии равна 1 — (1 — р) < 4р.
(См. %ейьпап апь1 Саггег, Х Соьпр. Яуэь Ясь'. 22 (1981), 265 — 279.] РАЗДЕЛ 6.5 1. Путь, описанный в указании, может быть преобразован посредством замены каждого идущего вниз шага иэ точки (ь-1, г) к "новому рекордно низкому" значению (г,2-1) шагом, идущим вверх. Если предпринимается с таких изменений, путь заканчивается в (гп, и — 21+ 2с), где с > 0 и с > 21 — и; гледовательно, и — 21+ 2с > и — 2Е В перестановке, соответствующей измененному пути, наименьшие с элементов списка В отвечают изльененным шагам вниз, а в списке А содержится 1 — с элементов, соответствующих неизмененным шагам вниз. Нетрудно увидеть, что при г = й построение обратимо; следовательно, строится в точности (") перестановок. Заметим, что в соответствии с этим доказательством содержимое списков А и С может располагаться в произвольном порядке.
Примечеиае. Мы сосчитали эти пути в упр. 2.2.1-4 нескалько иным способом. При 5 = (и/2) данное построение доказывает лемму Спернере, которая гласит, что невозльожно иметь более ( ", ) подмножеств множества (1,2,...,и), таких, что ни одно подльножество не содержится в другом. [Эмануэль Спернер (Ешапве! Брегпег), Маьб. Уе1шсЬПЕ 27 (1928), 544-548.) Если бы существовал такой набор подмножеств, каждая из (") перестановок могла бы иметь не более одного из подмножеств в начальных позициях; в то же время каждое подмножество появляется в некоторой перестановке. Построение, использованное здесь, представляет скрытую форму более общей конструкции, с помощью которой Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
