Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 150
Текст из файла (страница 150)
4. Для образа Х длины и = 0 и текста длины т 000, используя теорему 22.6, определите верхнюю границу вероятности ошибочного соответствия для к = 1,2,3 и 4. 6. Предположим, что задан образ длины п битов, количество простых чисел й и такое число М, что все идентифицирующие простые числа и их вычеты имеют не более, чем 32 бита. Кроме того, будет использована описанная в данном разделе корректировка.
Определите количество 32-битовых компьютерных слов информационной памяти, необходимых для реализации алгоритма Карпа и Рабина. РДЭ11ЕЛ 22.2. Приложение; функции хеширования 837 22.2. ПРИЛОЖЕНИЕ: ФУНКЦИИ ХЕШИРОВАНИЯ В компьютерных приложениях часто возникает ситуация, когда имеется и наборов информации 1ы1з,...,1„, где каждый набор идентифицирован ключом, например, йы кз,..., й„, соответственно. При этом желательно иметь возможность быстро находить информацию 1,, если известен ключ к . Ключи можно рассматривать как целые числа, хотя они могут иметь вид конечных последовательностей символов алфавита. Просмотр списков ключей может занимать достаточно много времени; более того, если поиск с использованием ключей необходимо проводить неоднократно, то вычислительные затраты могут быть значительными.
Компилятор — это компьютерная программа, преобразующая другую компьютерную программу, написанную на языке программирования высокого уровня (напрмер, ФОРТРАН или Паскаль), в эквивалентную программу на машинном языке. В течение процесса трансляции компилятор должен генерировать таблицы и неоднократно обращаться к ячейкам таблиц для получения информации. Важным моментом здесь является то, что поисковая таблица создается один раз, а используется многократно.
Поскольку таких таблиц может быть достаточно много, необходимо также использовать как можно меньше памяти для хранения. Одно из решений проблемы "размещения" состоит в использовании функции хешиРованиЯ и: К вЂ” (О, 1,..., т), где К = (йы йш..., Рт) и т + 1 > и. Таким образом, мы обеспечиваем гп+ 1 компьютерных ячеек для хранения п наборов информации. Итак, чтобы найти 1, нужно вычислить 6(й ) и перейти в ячейку Ь(Л,), где хранится 1,. Вообще, найти идеальную функцию хеширования, т.е. такую что п(к„) ф- 6(1,), когда й„ф к, и т + 1 = п, достаточно трудно. Наиболее широко используемые функции хеширования отображают множество К во множество, содержащее более, чем и элементов, поэтому не являются инъективными. Для функции 6, которая не является взаимно однозначным отображением, должно быть выработано соглашение поведения при возникновении коллизии, т.е.
в ситуации, когда к, и 1, — разные ключи, но 6(йк) = 6(й,), Дональд Э. Кнут в томе 3 книги Искусство программирования ]64] рассматривал различные способы выбора функций хеширования и методы разрешения коллизий. Яэшке в книге йес1ргоса1 НазЫлд: А Ме1пог( 1ог СепегаНад М1а1та! Рег1ес1 Назй1лу ГилсИопз [51] описывает особый тип минимальной функции хеширования, т.е. такой функции хеширования, которая является инъективной и использует минимальный объем памяти (минимальная совершенная функция хеширования) . Для функции хеширования, которую ввел Яэшке, необходима возможность отображения ключей (Уы йз,..., йе), которые могут не быть попарно взаимно простыми, во множество попарно взаимно простых целых чисел (1'(кг), 1'()гз),..., 1(й„)).
Он доказал следующую теорему. ТЕОРЕМА 22.7. Пусть К = (1:ы/сз, й„) — множество п различных положительных целых чисел. Пусть существуют целые числа Р и Е такие, что если функция 1(х) определена соотношением 1(х) = Рх + Е, то элементы набора положительных целых чисел (У(йг),1(1з),...,1'(Рт)) являются попарно взаимно простыми. Таким образом, целые числа Рй~+Е, Рка+Е,, и Рй„+Е являются попарно взаимно простыми. ДОКАЗАТЕЛЬСТВО. Доказательство теоремы является слишком длинным и при- 838 ГЛАВА 22 Лрилоясения теории чисел водиться не будет (см. (51)).
Тем не менее, далее рассмотрим специальный случай, вполне адекватный нашим целям. Основной результат, который получил Яэшке, сформулирован в приведенной ниже теореме. В ней |си) — набольшее положительное целое число, которое меньше или равно и. ТЕОРЕМА 22.8. Если множество К = (йы !сз,..., !с„) содержит различные целые положительные ключи, то в нем существуют целые числа С, Р и Е такие, что 6(х) =: — (шос1 п), где х е К является минимальной совершенной функцией хеширования. ДОКАЗАТЕЛЬСТВО. Пусть йг < кз « й„и пусть целые числа Р и Е заданы в соответствии с теоремой 22.7, так что 7'(й ) = Р!су+ Е и НОДЦ(!сс), Дйу)) = 1 для ! ф ~.
Поскольку Р и Е могут быть выбраны таким образом, что 7"(к ) > и для каждого ), имеется возможность выбрать п целых чисел аы аз,..., а„таких, что сч ф аз (пюс1 п) и таких, что (! — 1) (Рйс + Е) < ас < ! (Р!сс + Е). Тогда, согласно обобшенной китайской теореме об остатках, применимой к модулям, не являющимся взаимно простыми (теорема 10.14), существует такое число С, что С = а1 (пюс( п(Рйс + Е)), С ее аз (шос! п(Р/сз + Е)), С в— э а„(пюс1 п(Рй„+ Е)).
Поэтому, существуют целые числа с!с такие, что С = с7с|п(Рйс+Е)~!+ос для всех с'. Следовательно, | = рип+ (! — 1) = ! — 1 (пюс1 п). С Р!5 +Е Из этого следует, что функция Ь, определенная в теореме, обладает тем свойством, что 6(к,) ~ Ь(!с!), когда ! ~ 1, поэтому функция Ь является инъективной. Более того, множеством значений функции Ь является (0,1,..., (и — 1)). ° Яэшке привел алгоритмы вычисления чисел С, Р и Е; однако, эти методы не являются конструктивными.
С другой стропы, Чанг и Ши в работе Ра!гш7зе йе!аг!ое!у Ргсте Оелегаг!лр Ро!улот!а!з алс! Тйе!г Арр!!са!!олз (19) дают способ вычисления требуемых многочленов вида г"(х) = Рх + 1, где Е = 1. Доказательство приведенной ниже леммы предоставляется читателю. ЛЕММА 22.9. Если а и Ь положительные целые числа, а > Ь и с! кратно а — Ь, то с!(а — 6) и с!а+ 1 — взаимно простые числа. РАЗДЕЛ 22.2. Г!риложение: функции хеширования 839 ТЕОРЕМА 22.10. Пусть К = (Ьы /сз,..., )с„) — множество, содержащее п различных положительных целых чисел, для которых Ь, < й,~ы Если (ты !з,..., с,) = (й, — Ьу; 1 < ! < ! < и) — множество, содержащее е = п(п — 1)/2 разностей, то Р = ш НОК(ты!а,...,Ь,), где ш — произвольное положительное целое число, обладает тем свойством, что РИ-, + 1, Рйа + 1,..., РЬ„+ 1 являются попарно взаимно простыми числами.
ДОКАЗАТЕЛЬСТВО. Поскольку НОД(а, Ь) = НОД(а — Ь,а), где а и Ь вЂ” целые числа, для которых НОД(а, Ь) и НОД(а — Ь,Ь) определены, получаем, что НОД(РЬ +1, Р!5+1) = НОД(Р(й, — Ь ), Рй +1) для ! > ), где Р задано согласно теореме. По определению, Р кратно (Ь, — Ьу), следовательно, из леммы 22.9 следует, что НОД(Р)с, + 1, РЬ + 1) = 1 для ! > !.
Заметим, что для доказательства теоремы требуется только, чтобы Р было кратно всем ты!а,..., т,. Естественно, можно было бы выбирать Р как можно меньшим (и = 1); однако, для доказательства теоремы 22.8 необходимо, чтобы Р было таким, чтобы 7" (1ч) = РЬ, + 1 > п. Такое Р может быть всегда получено за счет выбора ш достаточно большим. ПРИМЕР 22.11. Предположим, что К = (3,6,7,12). Тогда (!ч — !3: 1 < ! < ! < 4) = (6 — 3, 7 — 3, 12 — 3, 7 — 6, 12 — 6, 12 — 7) = (3,4,9,1,6,5), так что Р = НОК(3,4,9,1.,6,5) = 180. Таким образом, 1(х) = 180х+ 1 и Проверка показывает, что любые два из чисел 541, 1081, 1261 и 2161 являются взаимно простыми. П Для реализации алгоритма обратного хеширования, предложенного Яэшке, необходимо иметь возможность вычислять целое число С.
К счастью, Чанг и Ши в работе А Раз! А)доп!Ьт 7ог Сопя!гис!улй )!есургоса! Нас)илд Гипс!сола [18] представили алгоритм вычисления целого числа С. В оставшейся части этого раздела мы будем использовать как функцию целой части (ш~, описанную ранее, так и функцию округления (ш), равную наименьшему положительному целому числу, большему или равному и.
Таким образом, (5.231 = 6 и (8~ = 8. ТЕОРЕМА 22.12. Если а) гпыта,...,т„— попарно взаимно простые целые числа; б) т;>пдлявсех!,1<!<и; 840 ГЛАВА 22. Приложения теории чисел в) М=й 1=1 пм г) М, = п П ту = — для всех г; вя д) Ь, является таковым, что М;Ь; = п (шой пт;), и Г (г — 1)т;1 е) Х; = 1 1 для каждого г, п тогда : — (1 — 1) (пюс) и) для всех г, [[У;,", муьР,~~ 2. С= — наименьшее положительное целое число такое, еМ ~С( что ~ — ~— : (г — 1) (пюг) и) для всех 1. ~т,~ ДОКАЗАТЕЛЬСТВО. Пусть а, = Аг, и, тогда а; — наименьшее число, кратное п, так что (1 — 1) т; < а; < г т, для всех 1 и а, ф а (шос) и), когда 1 ф ~.
Сумма ,М Ь Х~ является решением и сравнений х = аг (пюг) пта1): х = аэ (пюг) птг); х = а„(пюд пт„), ~~) М,6,Ц вЂ” = М,Ь)ч', (шог) пт;) = 1=1 = пгчь = а; (пюг( пт,), Поэтому, м,ь;л; м,ь;м, ~. -Муь,л, тФ т1 т, Иг. — е $ т; для соответствующего целого числа У,. Поскольку МА = и (пюг) пт,), то су- шествует целое число 1, такое, что М;Ь; = г,(птг) + и, поэтому п)у, Игг = п ч + с'пу' + —. т, потому что, если 2 ф 1, то М содержит множитель пт,. Поэтому М Ь Х.
= 0 (пюг( птп,) и РЯ377ЕЛ 22.2. Приложение: функции хеширование 841 Таким образом, учитывая (! — 1) . т, < а, < ! т,, имеем !пХ,! (а,! (И'г) = ~ — ~ = ~ — ~ = (г — 1) (той и), ~т; ~ 1т;~ что доказывает часть ! Пусть С = [~~,". М Ь 7т'11 . Нам нужно показать, что ~ ~ ~ = (г — 1) (щог! п) 3пМ для 1 < 1 < п.
Согласно алгоритму деления, существует целое число,7 такое, что н 2.' ЛтуЬ !Уу =,7(пМ) + С. Для 1 < ! < п, опять согласно алгоритму деления, 7=1 существуют целые числа д, и го где О < г, < т; такие, что и М Ь; 7У = дгт; + г;, 7=1 поэтому ~- М7Ь,Л, 7=1 = Ди т; Согласно результату части 1 существует целое число г, такое, что д; = (г — 1) + т;и; д;т; = (! — 1)т; + 1,пт;; дт;+г, = (1 — 1)т, + тпт, + т;; .7(пМ) + С = (г — 1)т, + г;пт; + г„ поэтому С /,7М'~ г, — =(; — )+ ~тг — — )~.+— тг — =(! — 1)+ т,— — п, так что | С! — ~ = (1 — 1) (пюс! п).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
