Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 57
Текст из файла (страница 57)
Теория построения блоков и связанные с ней вопросы детально рассмотрены в книге Маршалла Холла (мл.) (МагэЬаИ Най, Зг.) СошЬ!пагоНа! ТЬеогу (Ъта!!Ьатп, 81аэа.: В!швее)1, 1967). Хотя такие комбинаторные построения очень красивы, их основное приложение к задачам получения информации сводится к уменьшению избыточности при построении инвертированных списков. Однако в работе Пагк! К. СЬогг, 1пгогша!!оп аш! Сон!го! 15 (1969), 377 — 396, замечено, что такое уменьшение может быть достигнуто и без использования комбинаторных конструкций. Краткая история и библиография. Первой опубликованной статьей, посвященной вопросам технологии получения информации по вторичным ключам, явилась статья Ь. Н.
3оЬпеоп, САСМ 4 (1961), 218-222. Многосписочная система была независимо разработана в то же время Ноа Ш. Прайзом (НоаЬ Б. Ргужеэ), Г. Дж. Греем (Н. 3. Оглу), В. И. Ландауэром (%. 1. 1лпг!ацег), Д. Лефковицем (П. 1.е(Ьоп!!х) и С. Литвином (8. Ыгэг!и) (см. 1ЕЕЕ 2)апа оп Сотпшшсабоп апс! Е!ес!гоп!св 82 (1963), 488-492). Еще одна ранняя публикация, оказавшая влияние на более поздние работы, принадлежит Д. Р. Дэвису (П. Н.
Пач!э) и Э. Д. Лину (А. П. Ып), САСМ 8 (1965), 243-246. С тех пор количество публикаций на данную тему быстро увеличивается, однако почти все они посвящены таким не имеющим отношения к нашей книге вопросам, как пользовательский интерфейс и использование тех или иных языков программирования. Кроме уже указанных статей, автор считает, что наиболее полезными при написании этого раздела (начиная с 1972 года — времени создания настоящего раздела) были следующие работы: 1асЬ Мшйег апг! дегоше БаЫе, Апп. Нею ог" 1пйгшаг!оп Яс!енсе аЫ Тесйпо!ойу 2 (1967), 123-160; НоЬег! Е.
В!е!ег, Ргос. АСМ №а СовЕ 22 (1967), 41-49;. Зегоше А. Ре!гЬпап апб Рац! П. Во пег, САСМ 12 (1969), 439-449; Виг!оп Н. В!оош, Ргос. АСМ Ь!ак СовЕ 24 (1969), 83-95; Н. Б. Неарэ апг( 1,. Н. ТЬ!е1, Хпйгша!!оп Я!огайо аль~ Негг!ега! 6 (1970), 137-153; Ъ'!псепг г. 1лпп аль Нпе! ! шй, Ргос. АСМг(ап Сопб 26 (1971), 349-356. Хороший обзор ручных картотек содержится в работе С. Р. Воцгпе, МегЬогЬ о! 1пгогшаг(оп Напгйшд (Нем г'огро байеу, 1963), СЬаргег 5. Сбалансированные схемы были первоначально разработаны в 1965 году Ч. Т. Абрахамом (С. Т. АЬгаЬаш), С.
П. Гошем (Б. Р. ОЬоэЬ) и Д. К. РэйЧаудури (П. К. Вау-СЬапсйшг!); см. статью Н. С. Вове апс1 Сагу О. КосЬ, ЯХАМ э. Арр!. МаГЬ. 17 (1969), 1203-1214. Большинство классических алгоритмов для многоатрнбутных данных, практн- Ф ческая важность которых общеизвестна, обсуждалясь в этом разделе; однако в следующее издание настоящей книги планируется добавить еще несколько тем, включая следующие. ° Э, М. Мак-Крейт (Е. М. МсСге18)п) ввел понятие нрнорищеглнме деревья поиска (рНоН1у зеагсл 1геез) ~Б1СОМР 14 (1985), 257-276), которые разработаны специально для представления пересечений динамически изл1еняющихся семейств интервалов н обработки запросов диапазонов в форме "Найти все записи с хо < х < х| и у < у1" (заметьте, что нижняя грань у должна быть равной -оо, но х может быть ограничен с обеих сторон). ° М.
Л. Фредмав (М. Ь. ггебшап) нашел ряд фундаментальных нижних граней, показывающих, что последовательность А' смешанных вставок, удалений и а- мерных запросов диапазонов требуют в худшем случае выполнения П(1т(! ой Х)") операций, независимо от используемых структур данных. См. Х4СМ 28 (1981), 696 — 705; В1СОМР 10 (1981), 1-10; Х А18ог1гйшз 1 (1981), 77 — 87.
Базовые алгоритмы пояска соответствий шаблону (расгегп шагсл1пд) н приближенных соответствий шаблону в текстовых строках будут обсуждаться в главе 9. Интересно отметить, что мозг человека гораздо лучше компьютера справляется с поиском информации по вторичным ключам. Люди достаточно легко распознают лица, мелодии и т. и. по фрагментам информации, в то время как для компьютера зто практически непосильная задача. Таким образом, вполне вероятно, что в один прекрасный день будет найден совершенно новый подход к решению задач, связанных с поиском информации по вторичным ключам, который сделает это примечание, да и весь текущий раздел, безнадежно устаревшим.
УПРАЖНЕНИЯ ° 1. (М27) Пусть О < к < н/2, Докажите, что следующая конструкция дшт (") пересщновок множества (1,2,...,я), таких, что каждое Ьзлементное подмножество множества (1, 2,..., я) встречается в качестве первых 1 элементов кмс минимум одной перестановки при 1 < и или 1 > и - к. Рассмотрим путь на плоскости из точки (О, О) в точку (и, г), где г > я — 21, в котором 1-й шаг выполняется вз точки (1-1„у) в точку (Ь 1+Ц нли (Ь 1-1); последняя возможность разрешена толька при 1 > 1, так что путь никогда ие проходит ниже осн х.
Существует ровно (ь) таких путей. Для каждого из них соответствующая перестановка строится с использованием трех первоначально пустых списков следующим образом: для 1 = 1, 2,..., и, если 1-й шаг идет вверх, поместим число 1 в список В; «ели шаг идет вниз, поместим 1 в список А и переместим максимальный на текущий момент список В в список С. Результирующак перестановка предсшвэяет собой содержимое списка А, затем списков В в С, причем содержимое каждого списка приводится в порядке возрастания. Например, при и = 4 и л = 2 такая процедура определяет шесть путей и перестановок.
)1 2 3 4) 2)3 4)1 4)1 2)3 24Ц1 3 3)1 4)2 3 4()1 2 (Вертикальные линии отделяют списки А, В и С. Эти шесть перестановок соответствуют составным атрибутам в (8).) (а)гп=З,п=2 0 0 « -+ 0 1»0-+1 «1 1 -+ 2 101-+3 0 1 0 -+ 3 (Ь) тж4,пж2 ОО»«-+О «1»0-»1 «111»2 101»-»2 «101-»3 100 ° -+3 6. [Муй] (Р.
Л. Рнвест.) Рассмотрим множество Ць всех 2'(, ) базовых т-битовых запросов типа (10), в которых определено ровно 1 бнт. Дано множество т-битовых записей Я. Пусгь /~(Я) описывает колнчеспю запршюв в 1,1ь„„в ответах на которые содержатся члены множества Ю, а /с(о., т) представляет собой минимум /~(Ю) по всем таким множествам Я с в элементшкн прн О < о < 2 . По определению /у(0, О) = 0 и /о(1, О) = боо. а) Докажите, что для всех 1>1 н т >1 при 0 < о < 2 /ю(е, гп) = /о([о/2],«п — 1) + /ю 1([з/2],«п — 1) +/о-о([е/2],гп — 1). Ь) Рассмотрим некоторую комбннаторную хеш-функцию й, отобралапощую 2™ возможных записей на 2" списков, причем каждый список соответствует 2 "" записям. Если все запросы ( Ь„п равновероятны, то среднее количество проверяемых списков нл запрас составляет 1/2' (, ), умноженное на Указание.
Представьте каждое 1-элементное подмножество з в виде пути, который идет из (О О) в (и, п-21), 1 ый шаг которого идет нз (1-1, 1) в («, 2 +1) прн 1 к Я и в (1, 1-1) прн 1 б 5. Преобразуйте каж,лый такой путь в путь опксанного выше вида, 2. [Мйб] (Сактн П. Гош (Ба)сй Р. СЬовЬ).) Найдите минимально возможную длину 1 списка г~~о... г~ ссылок на запися, такого, что множество всех ответов на любой нз включающих запросов «»1, «1«, 1«», «11. 1»1, 11», 111 по трем вторичным ключам с дву- мя возможными значениями оказывается расположенным в последовательных позициях г;...гл 3. [1Р] Какие включающие запросы к табл.
2 вьоовут ложное выпадение (а) старинного сахарного печенья, (Ь) овсяных палочек с фнннкамиу 4. [МЯО] Найдите точные формулы для вероятностей в (11), предполагая, что каждая запись имеет г различных атрибутов, случайным образом выбираемых нз (") й-бнтовмх кодов в и-битовом поле, н что запрос включает а различных (но в остальном случайных) атрибутов (не волнуйтесь, если формулы не будут упрощаться). б. [4 0] Проэкспернментнруйте с разлнчнымн путями снижения нзбыточностя текста при использовании метода Харрисона для поиска подстрок, ° 6.
[Мйд] Общее количество т-бнтовых базовых запросов с 1 определеннымн битами составляет в = (,)2'. Если комбннаторная хеш-функция наподобие (13) конвертирует такие запросы в познцнн 1о, 1з, ..., 1, соответственно, то среднее количество позиций на запрос составляет 1(1) = (11 + 1г+" + 1*)/» (например, в (13) получим ЦЗ) = 1.75). Рассмотрим теперь составную хеш-функцию над (т~ + то)-битовым полем, вктроен- ную путем отображения первых т«бит с помощью одной хеш-функция н оставшихся то с помощью другой, а Б~(1) н Ьз(1) — соответствующие средние количества позиций на запрос. найдите формулу, выражающую значение 1 (1) в случае сосшвной функции через Ь1 н Ьо.
у. [М23] (Р. Л. Рнвест (Н. 1.. Н)тезо).) Найдите функции 1(1), определенные в предыду- щем упражнении, для еле,оующнх комбннаторных хеш-функций. (списки, проверяемые для Я) ж аеас (запросы б)сзю относящиеся к Я) > 2"/с(2~ ", ес). сззсзл 3 Покажите, что Ь оптимальна в том сммсле, что вижикя грань достигаетск, когда каждый из списков представляет собой "субкуб"; другими словами, покажите, что в случае, когда каждый список соответствует множеству записей, удовлетворяющих базовому запросу с ровно и определенными битами, неравенство превращается в равенство, 9.
[МОО) Докажите, что если в = 3", то множество всех троек вида ((ас...аз сОЬс ..Ь«-з)з, (ас...аз-с 1сс...с„-з)з,(ас... аз-з 2А ...О -*)з), 1 < Й < я, где а, Ь, с и И принимает зиачеиия О, 1 или 2 и Ь + сз + с11 щ 0 (по модулю 3) при 1 < у < а — Ь образует Штейиеровскую систему троек. 10. ~М32) (Томас П. Киркмаи (ТЬопны Р. К!г)сщаа), СаслЬпс18е аас1ТЗиЫса Маей. зоцгла1 2 (1847), 191-204.) Назовем сисслемва троек Киркмаиа порядка в такое упорядочение в + 1 объектов (ке,ям...,я„) в тройки, при котором каждая пара (х;,тт),з р' у встречается Ровно в едкой тРойке, за исключением в пзР (к;,Яь+и„, з„),0 < 1 < е, котоРые ие встречаются в тройках. Например, (кз,яз,кс), (кпкзсяс) представляет собой систему троек Киркмана порядка 4. а) Докажите, что система троек Киркмзна может существовать только для е саодб = 0 или 4. Ъ) Дана Штейиеровская система троек Я изд е объектами (кс,..., е ). Докажите, что следующее построение дает другую Штейиеровскую систему троек Я' иад 2в + 1 объектами и систему троек Киркмана К' порядка 2е — 2.
Тройки Ь представляют собой все тройки из Я плюс с) (х;, у,, уз), где у + Ь и з (по модулю в) и ) < Ь, 1 < с, у, Ь < е; й) (хп Ум з), где 21 Ж з (по модулю е), 1 ( з, у < е. Тройки системы К' представляют собой миожеспю троек У минус все тройки, содержащие ус и/или у„. с) Дана система троек Киркмаиа К на множестве (хз,км...,к,), где в = 2и. Докажите, что слесб'ющее построение дает Штейиеровскую систему троек 5' иад 2е+1 объектами и систему троек Киркмаиа К' порядка 2е — 2. Тройки К представляют собой тройки К плсос з) (хо хи+О „., Умы), 0 < з < е; и) (зс,ум уз), Я+Ь щ 2з+ 1 (по модулю в-1), 1 < 1 ( й — 1 < е — 2, 1( с < е — 2; ш) (кс„уу, Уз), 2/ щ 2с+ 1 (по модулю е-1), 1 < у < е — 1, 1 < с ( в — 2; ст) (вес узз узс ы)1 (кл-1 уф 1 узз), (яэ,ум ус-у), 1 () ( и; в) (к„у„„у„).
Тройки К' представляют собой множество троек о' минус все тройки, содержащие ус и/или у -с с1) Используйте предыдущие результаты для доказательства того, что система троек Киркмвна порядка е существует для всех в > О вида бй или бй+ 4 и Штейиеровсссая система троек иад в объектами существует для всех е > 1 вида ОЬ+ 1 или ОЬ+ 3. 11. (Мйб] В тексте раздела описано использование Штейиеровских систем троек в связи с включающими запросами. Для расширения их применения на все базовые запросы естественно определить следующую концепцию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
