Большинство классических алгоритмов для многоатрнбутных данных, практическая важность которых общеизвестна, обсуждались в этом разделе; однако в следующее издание настоящей книги планируется добавить еще несколько тем, включая следующие.

• Э. М. Мак-Крейт (Е. М. McCreight) ввел понятие приоритетные деревья поиска (priority search trees) [SICOMP 14 (1985), 257-276], которые разработаны специально для представления пересечений динамически изменяющихся семейств интервалов и обработки запросов диапазонов в форме "Найти все записи с Хо < X < XI и у < yi (заметьте, что нижняя грань у должна быть равной -оо, но а; может быть ограничен с обеих сторон).

• М. Л. Фредман (М. L. Fredman) нашел ряд фундаментальных нижних граней, показывающих, что последовательность iV смешанных вставок, удалений и А;-мерных запросов диапазонов требуют в худшем случае вьшолнения П (iV (log Л) *) операций, независимо от используемых структур данных. См. JACM 28 (1981), 696-705; SICOMP 10 (1981), 1-10; J. Algorithms 1 (1981), 77-87.

Базовые алгоритмы поиска соответствий шаблону (pattern matching) и приближенных соответствий шаблону в текстовых строках будут обсуждаться в главе 9.

Интересно отметить, что мозг человека гораздо лучше компьютера справляется с поиском информации по вторичным ключам. Люди достаточно легко распознают лица, мелодии и т. п. по фрагментам информации, в то время как для компьютера это практически непосильная задача. Таким образом, вполне вероятно, что в один прекрасный день будет найден совершенно новый подход к решению задач, связанных с поиском информации по вторичным ключам, который сделает это примечание, да и весь текущий раздел, безнадежно устаревшим.

УПРАЖНЕНИЯ

► 1. [М27] Пусть О < к < п/2. Докажите, что следующая конструкция дает (]J) перестановок множества {1,2,... ,п}, таких, что каждое t-элементное подмножество множества {1,2,..., п} встречается в качестве первых t элементов как минимум одной перестановки при t < к или t > п - к. Рассмотрим путь на плоскости из точки (0,0) в точку (п,г), где г >п - 2к, в котором г-й шаг выполняется из точки (i-l,j) в точку (i,j-\-l) или (г, j-1); последняя возможность разрешена только при j > 1, так что путь никогда не проходит ниже оси X. Существует ровно () таких путей. Для каждого из них соответствующая перестановка строится с использованием трех первоначально пустых списков следующим образом: для г = 1,2,..., п, если г-й шаг идет вверх, поместим число i в список В; если шаг идет вниз, поместим i в список А и переместим максимальный на текущий момент список В в список С. Результирующая перестановка представляет собой содержимое списка А, затем списков В и С, причем содержимое каждого списка приводится в порядке возрастания. Например, при п = 4и к - 2 такая процедура определяет шесть путей и перестановок.

1 2 3 4 23 41 2 413 31 42 3 41 2 41 23

(Вертикальные линии отделяют списки А, В и С. Эти шесть перестановок соответствуют составным атрибутам в (8).)

Указание. Представьте каждое t-элементное подмножество 5 в виде пути, который идет из (0,0) в (п, n-2t), г-ый шаг которого идет из (г -1, j) в (г, j+l) при г 5 и в (г, при i 6 S. Преобразуйте каждый такой путь в путь описанного выше вида.

2. [М25] (Сакти П. Гош (Sakti Р. Ghosh).) Найдите минимально возможную длину I списка Г1Г2...г( ссылок на записи, такого, что множество всех ответов на любой из включающих запросов 1**, 1*1, 11*, 111 по трем вторичным ключам с двумя возможными значениями оказывается расположенным в последовательных позициях ri...rj.

3. [19] Какие включающие запросы к табл. 2 вызовут ложное выпадение (а) старинного сахарного печенья, (Ь) овсяных палочек с финиками?

4. [МЗО] Найдите точные формулы для вероятностей в (И), предполагая, что каждая запись имеет г различных атрибутов, случайным образом выбираемых из () fc-битовых кодов в п-битовом поле, и что запрос включает q различных (но в остальном случайных) атрибутов (не волнуйтесь, если формулы не будут упрощаться).

5. [40] Проэкспериментируйте с различными путями снижения избыточности текста при использовании метода Харрисона для поиска подстрок.

► 6. [М20] Общее количество т-битовых базовых запросов с t определенными битами составляет s = (7)2- Если комбинаторная хеш-функция наподобие (13) конвертирует такие запросы в позиции i, h, .. •, h соответственно, то среднее количество позиций на

запрос составляет L{t) = {h + h-----1- ls)/s (например, в (13) получим L(3) = 1.75).

Рассмотрим теперь составную хеш-функцию над (mi -I-т2)-битовым полем, построенную путем отображения первых mi бит с помощью одной хеш-функции и оставшихся т2 с помощью другой, а Li{t) и L2{t) - соответствующие средние количества позиций на запрос. Найдите формулу, выражающую значение L{t) в случае составной функции через Ll и L2.

7. [М24] (Р. Л. Ривест (R. L. Rivest).) Найдите функции L{t), определенные в предыдущем упражнении, для следующих комбинаторных хеш-функций.

(а) m = 3, п = 2 (Ь) m = 4, п = 2

00*->0 00**->0

1*0-1 * 1 * О -> 1

* 1 1 -> 2 * 1 1 1 -> 2

10 1-3 1 О 1 * -> 2

010->3 *101->3

100*->3

8. [М32] (Р. Л. Ривест.) Рассмотрим множество Qt,m всех 2(J) базовых т-битовых запросов типа (10), в которых определено ровно t бит. Дано множество т-битовых записей 5. Пусть ft{S) описывает количество запросов в Qt,m, в ответах на которые содержатся члены множества 5, а ft{s,m) представляет собой минимум ft{S) по всем таким множествам S с 3 элементами при О < s < 2". По определению ft{0,0) = О и /t(l,0) = Sto.

a) Докажите, что для всех < > 1 и m > 1 при О < s < г"

ft{s,m) = ft{\s/2],m - 1) + ft-i{\s/2lm- 1) + ft-i{[s/2\,Tn - 1).

b) Рассмотрим некоторую комбинаторную хеш-функцию h, отображающую 2" возможных записей на 2" списков, причем каждый список соответствует 2""" записям. Если все запросы Qt,m равновероятны, то среднее количество проверяемых списков на запрос составляет 1/2(J), умноженное на

= (запросы Qf,m> относящиеся к 5) > 2"/f(2"~",m).

списки S

Покажите, что h оптимальна в том смысле, что нижняя грань достигается, когда каждый из списков представляет собой "субкуб"; другими словами, покажите, что в случае, когда каждый список соответствует множеству записей, удовлетворяющих базовому запросу с ровно п определенными битами, неравенство превращается в равенство.

9. [М20] Докажите, что если d = 3", то множество всех троек вида

{(oi.. .0(b i 06i . ..Ь„-к)з, (ai.. .flfc-i Ici .. .Сп-*:)з, (ai ... ak-\2di . ..йп-к)з},

1 < к < n, где a, b, с и d принимает значения О, 1 или 2 и bj + Cj + dj = О (по модулю 3) при 1 < j < п - к образует Штейнеровскую систему троек.

10. [М32] (Томас П. Киркман (Thomas Р. Kirkman), Cambridge and Dublin Math. Journal 2 (1847), 191-204.) Назовем системой троек Киркмана порядка v такое упорядочение v + 1 объектов {xo,xi,..., Xv} в тройки, при котором каждая пара {xi,Xj},i / j встречается ровно в одной тройке, за исключение.м v пар {ж,, X(i+i)niodij},0 < г < v, которые не встречаются в тройках. Например,

{Х0,Х2,Х4}, {Х1,Хз,Х4}

представляет собой систему троек Киркмана порядка 4.

a) Докажите, что система троек Киркмана может существовать только для v mod 6 = О или 4.

b) Дана Штейнеровская система троек S над v объектами {xi,..., Xv}. Докажите, что следующее построение дает другую Штейнеровскую систему троек S над 2и + 1 объектами и систему троек Киркмана К порядка 2d - 2. Тройки S представляют собой все тройки из S плюс

i) {xi, У],Ук}, где j + k = i (по модулю v) и j < к, 1 < i,j, к < v;

") {i Vj,}, где 2j = i (по модулю v), 1 <i,j <v. Тройки системы К представляют собой множество троек S минус все тройки, содержащие J/1 и/или yv.

c) Дана система троек Киркмана К на множестве {xo,xi,..., где v = 2и. Докажите, что следующее построение дает Штейнеровскую систему троек S пал 2v+l объектами и систему троек Киркмана К порядка 2d - 2. Тройки S представляют собой тройки К плюс

i) {xi,X(i+i)modi,,!/t+i}, О < г < d;

ii) {xi, yj,yk}, j + k = 2i + l (no модулю d-1), l<j<fc-l<d-2, l<i<d-2;

iii) {xi, j/j, ?/„}, 2j = 2i -I-1 (no модулю d-1), l<j<d-l, l<i<d-2;

iv) {X0,y2j,y2j + l}, J/2J-1, J/2;}. {Xv, У] , yv-j}, 1 < j < U] V) {Xv,yu,yv}.

Тройки К представляют собой множество троек S минус все тройки, содержащие yi и/или у„-1.

d) Используйте предыдущие результаты для доказательства того, что система троек Киркмана порядка d существует для всех d > О вида 6к или 6fc -I- 4 и Штейнеровская система троек над d объектами существует для всех w > 1 вида 6к + 1 или 6к + 3.