Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 38
Текст из файла (страница 38)
Пусть а = Ьп., Ь, — данный элемент из С; если г = О, то и, разумеется, принадлежит Н. В противном случае ищем и, опреде тая самый длинный префикс Ьг... Ьь, который соответствует ключу. Если имеется несколько ключей, начинающихся с Ьг... Ью то а не прнналлежит Н. Иначе обозначим этот единственный ключ через Ьг... Ьь сг...
сг = В;. н заменим а ключом В,. 'а = с, ...с, Ьэ+,...Ь„. Если новое значение и длиннее старого (т. е. если! > Й), а не принадлежит Н; в противном случае повторяем процесс с новым значением а. Иэ свойства Нильсена вытекает конечность этого алгоритма. Если а сводится к пустой строке, можно восстановить исходное представление и в виде произведений В.
Например, пусть (Впдэ,Вэ) = (ЬЬЬ, Ь о Ь, Ьа Ь) н а = ЬЬоЬаоЬ, Лес В, В- В Вг Вэ вместе с описанным алгоритмом позволяет вывести, что и = В, Вэ В, Вэ Вэ . Реализуйте этот алгоритм, используя в качестве входных данных вашей программы Вь 42. [ВЯ] (Сэсапгие спереди и сзади.) Если множество бинарных ключей используется в качестве индекса для раздеэения большого файла, можно не хранить полные ключи.
Например, 16 ключей, показанных на рис. 34, могут быть урезаны справа так, чтобы оставалось достаточное количество цифр для их однозначной идентификации: 0000, 0001, 00100, 00101, 010, ..., 1110001. Такие урезанные ключи могут использоэатыя для разделения файла на 17 частей, и, например, в пятой части могут содержаться все ключи, начинающиеся с ООП или 010, а в последней части -- ключи, начинающиеся с 111001, 11101 или Ш1.
Урезанные ключи можно представить в более компактной форме, если опустить все лидирующие цифры, совпадающие с цифрамн предыдущего ключа; 0000, оео1, оо100, оооо1, о10, ..., оос жо1. Бит, следующий за символом "о", всегда равен 1, поэтому он также может быть опущен. В большом файле будет содержаться много символов "о", и мы должны хранить только их количество и значения последующих битов. Покажите, что общее количество битов в сжатом файле с исключенными символами "оэ и последующим одним битом, всегда равно количеству узлов в бинарном луче с этими ключами, (Следовательно, среднее общее количество таких битов ао всем индексе составзяет около Х/)п2, 1.44 бит на ключ.
Этот способ сжатия был показан автору Э, Геллером (А. Нейег) и Р. Л. Джонсеном (К. 1,. Яоппееп). Возможно н дальнейшее сжатие, поскольку нам необходимо только представление структуры луча; см. теорему 2,3.1А.) 43. [НМ42] Проанализируйте высоту случайного М-арного луча, имеющего Аг ключей и параметр обрезки э, как в упр.
20 (когда э = 1, эта величина представляет собой длину самого длинного общего префикса случайных слов длиной М в вХ-эрном алфавите), ь 44. [30] (Дж. Л. Бентли (3. 1,. Веас)еу) и Р. Седгевнк (В., Яеббекйск).) Исследуйте тер- нарное представление лучей, при котором левая и правая ссылки соответствуют горизон- тальным ветвям (2), в то время как средняя ссылка соответствует ветви, идущей вниз. ь 43. [Мйо] Если семь ключей, которые показаны на рис. 33, вставлены в случайном по- рядке с помощью а.чгоритма, описанного в упр. 15, то чему равна вероятность получения показанного дерева? 6,4.
ХЕШИРОВАНИЕ До сих пар мы рлссмлтривлли методы поиска, основанные на сравнении данного аргумента К с ключами в таблице или на использовании его цифр для управлении процессом разветвления. Третий путь заключается в том, чтобы отказаться от поиска по данным и выполнить арифметические действия над К, позволяющие вьгчислить некоторую функцию у(К).
Последняя укажет адрес в таблице, где хранится К и связанная с ним информация. Например, рассмотрим хорошо известное нам множество из 31 английского слова, которое приводилось в разделах 6.2.2 и 6.3. В табл. 1 показана небольшая й1Х-программа, взаимно однозначно преобразующая 31 ключ в числа у(К) между — 10 и 30. Если сравнить этот метод с й1Х-программами для других рассматривавшихся методов (например, для бинарного поиска, оптимального поиска по дереву, "лучевого" поиска, цифрового поиска по дереву), то можно обнаружить, что новый способ превосходит старые как с точки зрения быстродействия, тйк и с точки зрения количества используемой памяти (за исключением бинарного поиска, для которого необходим несколько меньший объем памяти). В самом деле, среднее время успешного поиска с помощью программы из табл.
1 составляет около 17.8и и требует для хранения 31 ключа таблицу из 41 элемента. К сожалению, поиск таких функций у(К) — - довольно сложная задача. Имеется 41э' 10во возможных функций, отображающих 31-элементное множество в 41-элементное; однако только 41 . 40 . 11 = 41!/1О! 10аэ из них дают различные значения для различных аргументов; следовательно, только одна из десяти миллионов функций подходит для достижения нашей цели.
Функции, дающие неповторяющиеся значения, встречаются на удивление редко (даже для больших таблиц). Например, в соответствии со знаменитым "парадоксом дней рождения" получается, что в компании из 23 человек более вероятно совпадение дней рождения у двух из них, чем то, что у всех дни рождения окажутся различными. Иными словами, если выбрать случайную функцию, отображающую 23 клк>ча в таблицу размером 365, вероятность того, что никакие два ключа не будут отображены в одно и то же место таблицы, составляет 0.4927, т.
е. менее половины. Скептики могут проверить парадокс на ближайшей многолюдной вечернике", [Парадокс дней рождения нефорьгально обсуждался математиками в 30-е годы; происхождение этого парадокса неизвестно. См. !. 3. Соог(, РгоЬаЬ!!!!у апг! гЬе Же!864пй ог" ЕтЫепсе (Сг!!Еп, 1950), 38, а также Н. топ М!эегь 1ээдпбы! Ёгнл егэ!геэ! Реп Ра(гй!геэ! Местивэ! 4 (1939), 145-163; %.
Еейег, Ап 1пггос(псэ!оп го РгоЬаЬ!!!!у ТЬеогу (и!е» т'ог)г: %'!!еу, 1950), Яест!оп 2.3,) С другой стороны, использованный в табл. 1 подход весьма гибок [см. М. Сгеи!е» эЫ апг1 %. ТпгэЫ., САСМ 6 (1963), 322-323), и для таблиц небольшого размера подходящая функция может быть найдена за день-другой. Решать такого рода головоломки весьма занятно! Вопросы поиска подходящих функций рассматривались многими исследователями, включая, например, Н, 8ргпйпо!1„САСМ 20 (1977), 841-850, 22 (1979), 104, 553; Н. Л. С!сЬе1!1, САСМ 23 (1980), 17-19; Т. Л. 8айег, САСМ 28 (1985), 523-532, 29 (1986), 557; В.
Б, Ма!ешвЫ, ЬЬ С. Жогша!д, О. Начав " Любитеди математики могут обратиться за подробностями, иаприлгер, к книге У. Ьовда и Г. Коксюера Математические эссе и развлечения [Мс Мнр, !эбб. — 474 с.!. Скептикам-кеяюдилгам рекомендуется вспомнить свой класс в школе иди группу в институте, — 11ре.м. персе. Таблица 1 ВЗАИМНО ОДНОЗНАЧНОЕ ПРЕОЬРАЗОВАНИЕ МНОЖЕСТВА КЛЮЧЕЙ В АДРЕСА -1 -1 -2 -2 -1 -1 -2 -2 13 14 -5 14 13 14 -5 14 16 13 14 16 14 13 14 16 14 9 9 -2 -6 -2 -б 18 2 18 -1 -1 -1 -1 б 10 б 10 18 2 18 2 -7 -7 23 23 23 7 -3 3 7 -3 3 7 -3 3 13 14 16 9 18 23 13 14 16 9 18 23 13 14 16 9 18 23 апс) Е.
3. СзесЬ, Сошр. Х 39 (1996), 547-554; Свеса, Навез, апб Ма)егввЫ, Тйеогепса1 Сагир. Яс( 182 (1997), 1-143. См. также статью Л. Когпег апд К. Маг(он, Кагор. Х СогпЫпагопсз 9 (1988), 523-530, о теоретических ограничениях идеальных хешфункций, Конечно, этот метод имеет очень существенный недостаток, заключающийся в том, что содержимое таблицы должно быть заранее известно. Добавив всего один ключ, можно все испортить, и придется начинать всю работу с нуля. Впрочем, можно получить гораздо более гибкий метод, отбрасывая требование однозначности и используя специальные методы разрешения возникающих яеоднозначных ситуаций после вычисления У(К).
Итак, мы вплотную приблизились к популярному классу методов поиска с общим названием хзгиироеамие (Лазй(пу) или рассеянная налгать (зсаг(ег згогоуе). Глагол "го Ьазпв означает "крошить, рубить и делать из этого месиво"". Идея хеширования состоит в использовании некоторой частичной информации, полученной из ключа, в качестве основы поиска. Мы вычисляем хаги-адрес Ь(К) и используем его для проведения поиска. Парадокс дней рождения предостерегает нас, что, вероятно, найдутся различные ключи К; ~ К), имеющие одинаковое значение хеш-функцни )г(Кг) = Ь(К,).
Такое событие именуется коллизиеб (со((гзюп); для разрешения коллизий разработаны некоторые интересные подходы. Для использования хеширования программист должен решать две практически независимые задачи — выбрать хеш-функцию в В свнвв с вгнм бмл очень вслмк соблазн нслользоввть лля тврммвв лсгиировзмив русское слово вкроиим. — ))ризи мерси. Команда Ц)1И К(1:1) Ы2 К(2г2) 1ИС1 -8,2 11Р в+2 РКС1 16,2 Ц)2 К(З,З) 122 9Р 1ИС1 -28,2 11Р 9Р РКС1 21,2 йва К(4:4) 112 9Р 0801 -5,2 11И 9Р 1КС1 10 9Н ЫМ К сира тав)д, 1 ЗИЕ РАПЛВЕ -1 -1 -9 -9 7 7 б 10 7 б 10 . -18 -13 -18 -13 -3 3 -3 3 -3 3 -б -8 -6 -8 5 -15 5 -15 2 5 2 5 2 -7 -22 -7 — 22 20 -7 20 -7 20 -7 9 9 19 19 -7 19 — 7 19 -7 -8 -8 -8 -8 -8 -8 -15 -11 -11 -15 -11 -11 2 10 10 2 10 10 2 10 10 -1 . -1 -1 . — 1 35 35 35 15 15 25 25 25 2о после с оп -23 -23 -15 -15 17 1Т 17 -16 -16 -9 -9 22 22 22 30 -10 30 -10 30 — 10 22 22 22 -6 -2 -б -2 -6 -2 и н и М н н -8 -9 — 9 -8 -9 -9 -7 — 17 -2 -7 -17 -2 18 -1 29 18 -1 29 18 -1 29 12 12 12 -1 29 12 -1 29 12 -1 29 м ь Ь Содержимое г11 -9 — 9 -15 — 16 -9 -9 -15 -16 5 б -7 -18 5 6 -7 -18 25 4 5 6 2л 4 5 6 25 4 20 20 5 6 20 4 5 6 20 4 5 б 20 4 выполнения команды -16 -23 -23 -23 -16 — 23 -23 -23 -5 -23 -23 -23 -5 -23 -23 -23 30 1 1 1 30 1 1 1 30 1 1 1 -26 -22 -18 -26 -22 -18 — 14 -б 2 -14 -б 2 -14 — б 2 -10 .
-2 -10 . -2 ределе иным -26 -26 -26 -26 -33 -26 -33 -26 -16 -2 -16 -2 -16 -2 -22 -21 -22 -21 11 -1 11 -1 П -1 -5 -5 1Т 11 -5 17 11 -5 11 -5 ключом К вЂ” 26 -28 -26 -28 — 25 -20 -25 -20 0 12 0 12 0 12 -5 8 -5 8 29 29 29 11 11 21 21 8 21 8 21 8 й(К) и способ разрешения коллизий. В этом разделе будут рассмотрены обе этп задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
