Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 56
Текст из файла (страница 56)
Предположим, что имеется Ю 2" записей, в каждой из которых содержится т вторичных ключей. Каждая запись отображается в и-битовый хеш-адрес таким образом, что запрос, оставляющий неопределенными значения Ь ключей, соответствует примерно Х" 7 хеш-адресам. Все другие методы, обсуждавшиеся ранее в этом разделе (за исключением метода Густафсона), требуют порядка Х шагов для получения информации, хотя и с малым коэффициентом пропорциональности; для больших значений Х метод Рнвеста более быстр и не требует инвертированных файлов.
Но прежде чем прилшнять эту технологию, следует определить подходящее отображение. Ниже рассматривается пример с небольшими параметрамн, с пт = 4 и и = 3 н вторичными ключами, принимающими два значения. Можно отобразить 4-битовые записи в восемь адресов следующим образом. «001-+О «1 1 0 -+ 4 0*00-+1 1«11-+5 (13) 1 О « О -+ 2 О 1 « 1 - 6 1 1 О « -+ 3 0 0 1 « -+ 7 Исследование этой таблицы показывает, что все записи, соответствующие запросу 0 * * «, отображаются в позиции О, 1, 4, б и 7.
Точно так же любой базовый запрос с тремя символами "*" соответствует в точности пяти позициям, базовый запрос с двумя "*" — трем позициям н с одной "«« — одной или двум позициям, (8 х 1+ 24 х 2)/32 = 1.75 в среднем. Таким образом, имеем следующее, Количество неопределенных битов в запроге 4 3 г 1 0 Количество позиций поиска 8 8»7» 5 ш8з!» 3 = 8'7» 1,75 = 8'~» 1 80/» (14) Конечно, зто всего лишь маленький пример, и в таких сяучаях гораздо проще осуществлять поиск "в лоб". Этот метод приводит к появлению нетривиальных приложений, поскольку его можно использовать и тогда, когда т = 4г и и = Зг, отображая 4г-битовые записи на 2з" = 7«позиций путем разделения вторичных ключей на г групп по 4 бит и применяя (13) к каждой группе.
Получающееся отображение имеет требуемое свойство: запрос, оставляющий Ь из т бит неопределенными, соответствует примерно №Р«позициям (см. упр. 6). В 1997 году А. Э. Брувер (А. В. Вгопжег) нашел привлекательный способ сжатии 8 бит до 5 бит прн помощи отображения, аналогичного (13).
Каждый 8-битовый байт принадлежит в точности одному из следующих 32 классов. 0«ООО«0« 01«0««11 00«11*«1 *11««101 1«000«0« 11«0**11 10«11««1 «11««010 0«010«0« 01«1*«11 00«О«01« «10«0«10 1«010«0« 11«1««11 10«0«01« «10«1«01 (15) о.10.1.о о.1«ооа. *о1.01.1 *о.1оо1* 1«10«1«0 1«1«000« «10«10*0 «0*0100* 0«11«1«0 0«0«11*0 «00«011« «0«011«1 1«11«1.0 1«0«11«0 «11«100« .О«110«0 Звездочки в этой конструкции расположены таким образом, что в каждой строке нх по 3, а в каждом столбце — по 12, В упр. 18 поясняется, каким образом строятся подобные схемы, сжимающие записи с и» = 4' бит в и = 3'-битовые адреса. На практике используются блоки размером Ь и»»~ ж 2"Ь; случай, когда Ь = 1, использовался выше для упрощения изложения материала. Ривест предложил также другой простой путь обработки базовых запросов, Предположил», имеется Х е 2'е записей по ЗО бит и необходимо ответить на произвольный Зо.битовый базовый запрос, подобный (10).
В этом случае мы можем просто поделить ЗО бит на три 10-битовых поля и поддерживать три отдельные хеш-таблицы размером М = 2»е. Каждая запись хранится в трех местах, в списках, соответствующих битовым конфигурациям трех полей. При соответствующих усло- виях в каждом списке будет содержаться около одного элемента. В данном базовом запросе с Ь неопределенными битами как минимум одно из полей будет иметь 1Ь/3) или меньше неопределенных битов.
Следовательно, потребуется просмотреть не более 21"~з1 17"~зе списков для поиска всех ответов на запрос. Впрочем, можно использовать н любую другую технологию для обработки базовых запросов в выбранных полях. Обобщенные лучи (сг)ев). Ривест предложил еще один подход, который основан на структурах данных, подобных использованным в разделе 6.3 лучам. Можно предположить, что каждый внутренний узел обобщенного бинарного луча определяет представленные в записи биты. Например, используя приведенные в табл. 1 данные, можно положить корнем луча Влнилян. Тогда левый подлуч будет соответствовать тем 16 рецептам, в которых ванилин не нужен, в то время как в правом подлуче собираются 15 рецептов с ваннлином.
Такое разбиение 16-15 удачно делит файл практически пополам; каждый из подфайлов обрабатывается аналогично, и когда на некоторой стадии подфайл становится достаточно мал, его можно представить и качестве конечного узла. Для поиска по обобщенному лучу с корнем, определяющим атрибут, которому в запросе соответствует О или 1, переходим к поиску в левом или правом подлуче соответственно; если этому атрибуту в запросе соответствует "э", просматриваем оба подлуча.
Предположим, что атрибуты не бинарны, но представлены в бинарной записи. Можно построить луч, рассматривая сначала первый бит атрибута 1, затем — первый бит атрибута 2,..., первый бнт атрибута ш, второй бит атрибута 1 и т. д. Такая структура называется гл-д-лучом, по аналогии с гл-д-деревьями (которые ветвятся в результате сравнения, а не проверки битов). Ф. Флажоле (Р. Г1а)о1ег) н К. Пуч (С. РпесЬ) показали, что среднее время ответа на частично определенный запрос по случайному гп-о-лучу с Х узлами составляет 9()7ь~ ), если й/т атрибутов не определены 1.7АСМ 33 (1986), 371-407, 54.1). Дисперсия втой величины была вычислена В.
Шахингером (%'. ЗсЬасЫпйег), Велйэи БГгцссигея лпИ А!яог1ГЬпм 7 (1995), 81-95. Подобный алгоритм может быть распространен на т-мерные версии цифровых деревьев поиска и деревья метода "Патриция" из раздела 6.3. Эти структуры, которые обычно несколько лучше сбалансированы, чем пьд-лучи, были проанализированы в работе Р. К)гвсЬепЬоГег апд Н. Ргобйпйег, Вллдош БГгистигев агк1 Л18огВЬшя 6 (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,5), (1,6), (5,6) (6,0,2) (0,2), (0,6), (2,6) (О, 1, 3) (О, Ц, (О, 3), (1,3) Поскольку существует Ьи(е — 1) пар объектов и трн пары в одной тройке, всего 2 должно быть ее(с — 1) троек; а так как каждый объект может быть в паре с с — 1 объектами, каждый объект должен содержаться ровно в 12(е — 1) тройках. из этих условий следует, что Штейнеровская система троек может существовать тогда и только тогда, когда -'и(е — 1) н -'(е — 1) представляют собой целые числа.
Это эквивалентно тому, что е должно быть нечетно и не быть равным 2 по модулю 3; таким образом, (17) епюд6 = 1 или 3. И обратно, в 1847 году Т. П. Киркман (Т. Р. К(г)анап) доказал, что Штейнеровская система троек существует для всех е > 1, удовлетворяющих (17), Его интересное построение приведено в упр. 10. Штейнеровскне системы троек могут использоваться для снижения избыточности индексов комбинированных инвертированных файлов. Вернемся, например, к рассматривавшимся ранее рецептам печенья из табл.
1 и конвертируем крайний справа столбец в тридцать первый атрибут, который равен 1, если требуется какой- либо специальный ингредиент, н равен О в противном случае. Предположим, что необходимо ответить на все включающие запросы о парах атрибутов наподобие "В каких рецептах используются и кокосовый орех, и изюм?". Можно было бы построить инвертированные файлы для всех ( ) — 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). Для поиска шестерки, содержащей пару (я,у), выберем ! и у такими, что а; - а ш я - 9 (по модулю 31). Теперь, если Ь ж (х — а;) шоб 31, имеем (а; + Ь) шог! 31 = х и (ау + й) шос1 31 = 9.) Можно использовать конструкцию, приведенную выше, для хранения инвертированных списков таким образом, чтобы ни одна запись не появилась более 31 раза.
Каждая шестерка (а,б,с,й,е,7') ассоциирована с 57 списками всех возможных для записей, имеющих два или более атрибутов а, Ь, с, г(, е, у, а именно— (а,б,с,й,е,у), (а,Ь,с,г(„е,7), ..., (а,Ь,с,г(,е,у). Ответом на любой включающий запрос по двум атрибутам является объединение без пересечений 16 подходящих списков соответствующей шестерки. Так, "Печенье с перцем" войдет в 29 блоков из 31, поскольку эта запись имеет по два из шести атрибутов во всех шестерках, кроме (19, 23, 4, 9, 10, 12) и (13, 17, 29, 3, 4, 6), если перенумеровать столбцы от 0 до 30.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
