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