ВИЯХ в каждом списке будет содержаться около одного элемента. В данном базовом запросе с к неопределенными битами как минимум одно из полей будет иметь [A;/3J или меньше неопределенных битов. Следовательно, потребуется просмотреть не более 2l-*/J ss ЛГ*/" списков для поиска всех ответов на запрос. Впрочем, можно использовать и любую другую технологию для обработки базовых запросов в выбранных полях.

Обобщенные лучи (tries). Ривест предложил еще один подход, который основан на структурах данных, подобных использованным в разделе 6.3 лучам. Можно предположить, что каждый внутренний узел обобщенного бинарного луча определяет представленные в записи биты. Например, используя приведенные в табл. 1 данные, можно положить корнем луча Ванилин. Тогда левый подлуч будет соответствовать тем 16 рецептам, в которых ванилин не нужен, в то время как в правом подлуче собираются 15 рецептов с ванилином. Такое разбиение 16-15 удачно делит файл практически пополам; каждый из подфайлов обрабатывается аналогично, и когда на некоторой стадии подфайл становится достаточно мал, его можно представить в качестве конечного узла.

Для поиска по обобщенному лучу с корнем, определяющим атрибут, которому в запросе соответствует О или 1, переходим к поиску в левом или правом подлуче соответственно; если этому атрибуту в запросе соответствует просматриваем оба подлуча.

Предположим, что атрибуты не бинарны, но представлены в бинарной записи. Можно построить луч, рассматривая сначала первый бит атрибута 1, затем - первый бит атрибута 2, ..., первый бит атрибута т, второй бит атрибута 1 и т. д. Такая структура называется m-d-лучом, по аналогии с m-d-деревьями (которые ветвятся в результате сравнения, а не проверки битов). Ф. Флажоле (Р. Flajolet) и К. Пуч (С. Puech) показали, что среднее время ответа на частично определенный запрос по случайному m-d-лучу с N узлами составляет Q{N), если к/т атрибутов не определены [JACM 33 (1986), 371-407, §4.1]. Дисперсия этой величины была вычислена В. Шахингером (W. Schachinger), Random Structures and Algorithms 7 (1995), 81-95.

Подобный алгоритм может быть распространен на т-мерные версии цифровых деревьев поиска и деревья метода "Патриция" из раздела 6.3. Эти структуры, которые обычно несколько лучше сбалансированы, чем m-d-лучи, были проанализированы в работе Р. Kirschenhofer and Н. Prodinger, Random Structures and Algorithms 5 (1994), 123-134.

♦Сбалансированные схемы. Другой комбинаторный подход к получению информации, основанный на системах сбалансированных неполных блоков, был предметом множества исследований. Хотя предмет исследования весьма интересен с математической точки зрения, к сожалению, его преимущества перед другими описанными выше методами до сих пор не доказаны. Здесь будет представлено краткое введение в теорию, чтобы показать изящество результатов, в надежде, что читатели придумают, как внедрить теоретические идеи в практику.

Штейнеровская система троек представляет собой распределение v объектов в неупорядоченные тройки таким образом, что каждая пара объектов встречается ровно в одной тройке. Например, при v = 7 имеется ровно одна Штейнеровская система троек.

Тройки Содержащиеся пары

{1,2,4} {1,2}, {1,4}, {2,4}

{2,3,5} {2,3}, {2,5}, {3,5}

{3,4,6} {3,4}, {3,6}, {4,6} (16)

{4,5,0} {0,4}, {0,5}, {4,5}

{5,6,1} {1,5}, {1,6}, {5,6}

{6,0,2} {0,2}, {0,6}, {2,6}

{0,1,3} {0,1}, {0,3}, {1,3}

Поскольку существует - 1) пар объектов и три пары в одной тройке, всего должно быть v{v - 1) троек; а так как каждый объект может быть в паре с v - I объектами, каждый объект должен содержаться ровно в (и - 1) тройках. Из этих условий следует, что Штейнеровская система троек может существовать тогда и только тогда, когда - 1) и {v - 1) представляют собой целые числа. Это эквивалентно тому, что v должно быть нечетно и не быть равным 2 по модулю 3; таким образом,

V mod 6=1 или 3. (17)

И обратно, в 1847 году Т. П. Киркман (Т. Р. Kirkman) доказал, что Штейнеровская система троек существует для всех v > 1, удовлетворяющих (17). Его интересное построение приведено в упр. 10.

Штейнеровские системы троек могут использоваться для снижения избыточности индексов комбинированных инвертированных файлов. Вернемся, например, к рассматривавшимся ранее рецептам печенья из табл. 1 и конвертируем крайний справа столбец в тридцать первый атрибут, который равен 1, если требуется какой-либо специальный ингредиент, и равен О в противном случае. Предположим, что необходимо ответить на все включающие запросы о парах атрибутов наподобие "В каких рецептах используются и кокосовый орех, и изюм?" Можно было бы построить инвертированные файлы для всех (2) = 465 возможных запросов. Однако они займут очень много места, так как, например, "Печенье с перцем" будет содержаться в (У) = 136 списках, а запись, включающая 31 атрибут, будет содержаться в каждом списке! Штейнеровская система троек позволяет немного улучшить ситуацию. В случае 31 объекта существует Штейнеровская система из 155 троек, в которой каждая пара объектов встречается ровно в одной тройке. Каждой тройке {а, Ь, с) можно назначить четыре списка: первый - для всех записей с атрибутами {а, Ъ, с) (т. е. а, 6, но не с), второй - для {а,6,с}, третий - для {а, 6,с} и четвертый - для записей со всеми тремя атрибутами {а,6,с}. Таким образом гарантируется, что никакая запись не будет включена более чем в 155 инвертированных списков, и сохраняется пространство, когда запись имеет три атрибута, соответствующих тройке системы.

Системы троек представляют собой частный случай систем блоков из трех или более объектов. Например, тот же 31 объект может быть распределен по шестеркам так, чтобы каждая пара объектов оказывалась ровно в одной шестерке:

{0,4,16,21,22,24}, {1,5,17,22,23,25}, ..., {30,3,15,20,21,23}. (18)

(Эта конструкция создана из первого блока путем сложения по модулю 31. Чтобы проверить, что она обладает указанными свойствами, обратим внимание на еле-

дующий факт: 30 значений -Oj) mod31,г ф j различны при (ai,Ог,... ,аб) = (0,4,16,21,22,24). Для поиска шестерки, содержащей пару {х,у), выберем г и j такими, что Ui-aj = х-у (по модулю 31). Теперь, если к = {х - ai) mod 31, имеем (oi + к) mod 31 = а; и (oj + к) mod 31 = у.)

Можно использовать конструкцию, приведенную выше, для хранения инвертированных списков таким образом, чтобы ни одна запись не появилась более 31 раза. Каждая шестерка {а, Ь, с, d, е, /} ассоциирована с 57 списками всех возможных для записей, имеющих два или более атрибутов а, Ь, с, d, е, /, а именно - {a,b,c,d,e,f}, {a,b,c,d,e,f}, {a,b,c,d,e, f}. Ответом на любой включающий запрос по двум атрибутам является объединение без пересечений 16 подходящих списков соответствующей шестерки. Так, "Печенье с перцем" войдет в 29 блоков из 31, поскольку эта запись имеет по два из шести атрибутов во всех шестерках, кроме {19,23,4,9,10,12} и {13,17,29,3,4,6}, если перенумеровать столбцы от О до 30.

Теория построения блоков и связанные с ней вопросы детально рассмотрены в книге Маршалла Холла (мл.) (Marshall Hall, Jr.) Combinatorial Theory (Waltham, Mass.: Blaisdell, 1967). Хотя такие комбинаторные построения очень красивы, их основное приложение к задачам получения информации сводится к уменьшению избыточности при построении инвертированных списков. Однако в работе David К. Chow, Information and Control 15 (1969), 377-396, замечено, что такое уменьшение может быть достигнуто и без использования комбинаторных конструкций.

Краткая история и библиография. Первой опубликованной статьей, посвященной вопросам технологии получения информации по вторичным ключам, явилась статья L. R. Johnson, САСМ 4 (1961), 218-222. Многосписочная система была независимо разработана в то же время Ноа Ш. Прайзом (Noah S. Prywes), Г. Дж. Греем (Н. J. Gray), В. И. Ландауэром (W. I. Landauer), Д. Лефковицем (D. Lefkowitz) и С. Литвином (S. Litwin) (см. IEEE Trans, on Communication and Electronics 82 (1963), 488-492). Еще одна ранняя публикация, оказавшая влияние на более поздние работы, принадлежит Д. Р. Дэвису (D. R. Davis) и Э. Д. Лину (А. D. Lin), САСМ 8 (1965), 243-246.

С тех пор количество публикаций на данную тему быстро увеличивается, однако почти все они посвящены таким не имеющим отношения к нашей книге вопросам, как пользовательский интерфейс и использование тех или иных языков программирования. Кроме уже указанных статей, автор считает, что наиболее полезными при написании этого раздела (начиная с 1972 года - времени создания настоящего раздела) были следующие работы: Jack Minker and Jerome Sable, Ann. Rev. of Information Science and Technology 2 (1967), 123-160; Robert E. Bleier, Proc. ACM Nat. Conf. 22 (1967), 41-49; Jerome A. Feldman and Paul D. Rovner, CACM 12 (1969), 439-449; Burton H. Bloom, Proc. ACM Nat. Conf. 24 (1969), 83-95; H. S. Heaps and L. H. Thiel, Information Storage and Retrieval 6 (1970), 137-153; Vincent Y. Lum and Huei Ling, Proc. ACM Nat. Conf. 26 (1971), 349-356. Хороший обзор ручных картотек содержится в работе С. Р. Bourne, Methods of Information Handling (New York: Wiley, 1963), Chapter 5. Сбалансированные схемы были первоначально разработаны в 1965 году Ч. Т. Абрахамом (С. Т. Abraham), С. П. Гошем (S. Р. Ghosh) и Д. К. Рэй-Чаудури (D. К. Ray-Chaudhuri); см. статью R. С. Bose and Gary G. Koch, SIAM J. Appl Math. 17 (1969), 1203-1214.