AOP_Tom3 (1021738), страница 143
Текст из файла (страница 143)
Название четревья теперь стало общим термином для любой иерархической декомпозиции геометрических данных. Составные атрибуты. Два или более атрибутов могут быть скомбинированы в один суператрибут. Например, атрибут '(КУРС, СПЕЦИАЛИЗАЦИЯ)" может быть создан путем комбинирования полей КУРС и СПЕЦИАЛИЗАЦИЯ в университетском файле регистрации. Таким образом, запрос зачастую можно выполнить, объединяя короткие списки вместо пересечения длинных.
Идея комбинирования атрибутов была развита В. Ю. Лумом (Ч. т'. Бит) (САСМ 13 (1970), 660-665], который предложил упорядочение инвертированных списков комбинированных атрибутов в лексикографическом порядке слева направо и создание нескольких копий с перестановкой индивидуальных атрибутов надлежащим способом. Например, предположим, что имеется три атрибута — А, В н С.
Можно сформировать составные атрибуты (А,В,С), (В,С,А), (С,А,В) (7) и построить упорядоченные инвертированные списки для каждого нз них. (Так, в первом списке записи упорядочены по их значениям А; записи с одинаковыми значениями А упорядочены по значениям В, а затем — по С.) Такая организация позволяет выполнять запросы, основанные на комбинации этих трех атрибутов; например, все записи, имеющие определенные значения А и С, будут располагатьси в третьем списке последовательно. Аналогично из атрибутов А, В, С и О можно сформировать шесть составных атрибутов: (А, В, С, О), (В, С, О.
А), (В, О, А, С), (С, А, О, В), (С, и, А, В), (О, А, В, С). (В) Они позволяют выполнять все комбинации простых запросов с фиксированными значениями одного, двух, трех или четырех атрибутов. Существует общая процедура построения („) комбинированных атрибутов нз и отдельных атрибутов при А < 1~п, такая, что все записи, имеющие определенные комбинации не более чем нз А или не менее и — А значений атрибутов, будут последовательно расположены в одном из списков комбинированных атрибутов (см. упр.
1). Можно обойтись и меньшим количеством комбинаций, если некоторые атрибуты имеют ограниченное множество значений. Например, если О представляет собой атрибут с двумя возможными значениями, то комбинации (9) (О,А,В,С), (О,В,С,А), (О,С,А,В), полученные в результате помещения О в (7), будут так же хороши, как и (8), с половинной избыточностью, поскольку запросы, не зависящие от О, могут быть обработаны путем просмотра в двух местах одного из списков. Бинарные атрибуты.
Поучительно рассмотреть частный случай, когда все атрибуты могут иметь только два значения. По сути, это противоположность комбинированных атрибутов, поскольку любое значение можно представить как двоичное число и рассматривать индивидуальные биты этого числа квк отдельные атрибуты.
В табл. 1 показан типичный файл с атрибутами "Да"-"Нет". В этом примере записи содержат рецепты домашнего леченья, а атрибуты определяют используемые ингредиенты. Например, миндальные вафли с ромом сделаны нэ масла, муки, молока, орехов и сахарного песка. Если рассматривать табл. 1 как матрицу нз нулей и единиц, то транспонированная матрица будет представлять собой инвертированный файл в виде битовых строк. Правый столбец табл.
1 используется для указания специальных, редко используемых продуктов. Они могут быть закодированы более эффективно, без отдельного столбца для каждого из них. То же самое справедливо для столбца "Кукурузный крахмал". Кроме того, можно найти более эффективный путь кодирования столбца "Мука", поскольку мука встречается во всех рецептах, кроме рецепта приготовления меренги. Однако пока оставим этот вопрос и просто проигнорируем столбец "Специальные ингредиенты".
Будем определять базовый запрос к файлу бинарных атрибутов как запрос на все записи, в одних столбцах которых содержатся нули, в других — единицы и в остальных столбцах — произвольные величины. Используя символ "ь" для обозначения любого значения, базовый запрос можно представить в виде последовательностей символов О, 1 и "*". Например, представим человека, который захотел печенья с кокосом и у которого аллергия на шоколад, который ненавидит анис и у которого дома закончился ванилин.
Тогда его запрос может быть сформулирован так: ьОььььОьч1ь~ьэх~ьь~ь~~ ьььььььО. (10) Из табл. 1 становится понятно, что его желания совпадают с его возможностями в случае ароматных палочек с черносливом. Р 3 и 3 и О и О о ж О и зз ц с о с с ~зй х 8 3 Д <~ ~ ~ 4 О х~ „" Оа'хао и ххахц ж ><ОО.
;из! о о о о оьо о о-о оь о о о о о а ь а оаоооооао ооо о о -оо оооооооо аьо а оо о о оо-о о И о Я ь с ианаииэданн эинчиеинэнд нииинед мнило 'дехед моэае 'дехед цянажж' 'бехед чход наеИ онмоиод иха«О мадо цянаемэКр~ емохеП ж омоиоае Й иохан хенноииП < моа циииониП чцнциИ РЭ Ф емзее Р мох иаж «иньип Е~ ° е моха« цжнаип иминиф иеихеом «3чиекбамХИ эфоИ хаоо цжиооомон еминеоид еии«РИ и ееиомоП1 ио иоиеицеИ ~7 оиое аз миоэ хева1пиП 'й мовооон цянбемаП е наине енбаП надои цеааэитХП о оо- ооа ааааа о оо оо ь ооооааооо оооо о ььо оь ааааа о о ооо о о оо оооооо о оо оо о о ооьаоооооо оооаооооооооооооооь ос ооооооааьосооооо соса ооооаоо о оо о о ооо аооооь ооооьооаооа сооооо ьооооооаооооо ооооаооооо оооо ооооассоооо оо асьаооооо оооос1 аооооо оо ааааа оаьсосьоо оооооа оо аасооаоооаос оооьосооооа аооооь ооооооооооооо оооооооьо ооооооо о ьооооооооаао о о а о о с - о о о о о о о о а о ь о о о о а о о а о а о о о о оооооооооооь оооооооооо оооооаоо оооо о о ооооооооооооьаааооооооо о оооааоооо оооо о оооо оооооооо а оооооооо- о о о оооо ааааа оо оьо а а аоооооооосооо соооооса а оооооооьоооьаоа оаооооь ьоооооао о а о о ооо ооо ооо о ьаоаосооа оооо ооо о ааоааьаа оь оо оооо ооооооооосоооаоосоооооо оо ааааа ооаоаооооооооооо о оооо оооооььо > ц к эа о Ф о Р.
х х с и с О х х О О Р. С х х и х 3 О О с Ф Ха Лй х о 3 х" с 3 ф;О с Ос О 3 хо си 5 с с Й й РО и о О Х О охх х 5", о ч Ззс С СО с х$о < с~ Е О ,р Х Х СО хна. 3 со С О ОО С. О,ЕЧ 2„ ~16 хна с О х Х с х О О О О О Л и О О х х ~~ '3' ец Хсх 4=.' , 2 О'ЦС хс о х О О 'и' ~ ОО а О О о 2 О А схс и ас сии х М Р. 3 з с х Осоа О Ососи аонои схс с х ххс,о О 2 3 ц 1 3 о с х с х ьББ жоа Прежде чем приступить к органиэации файла для базовых запросов, рассмотрим один важный специальный момент, когда в запросе отсутствуют нули, а есть только 1 и <и".
Такой запрос можно назвать включающим (тс!пете цвету), поскольку ан запрашивает записи, которые екмючают некоторое множества атрибутов (если предположить, что 1 означает наличие определенного атрибута, а Π— ега отсутствие). Например, в табл. 1 два рецепта одновременно содержат и пекарный порошок, и пищевую соду — глазированные имбирные пряники и старинное сахарное печенье. В некоторых приложениях достаточно использовать специальные включающие запросы, например в ручных карточных системах наподобие карт с перфорацией по краям или карт свойств. Система карт с перфорацией по краям для табл. 1 будет иметь по одной карточке на каждый рецепт с вырезами, соответствующими каждому ингредиенту (рис.
46). Обработка включающего запроса сводится к складыванию карточек аккуратной стопкой и введению спиц в положениях, соответствующих конкретным ингредиентам. После ввода спиц все карточки с определенными атрибутами выпадают из стопки. ОО ш < < шаш аоь йиь я е О О ш> О Х д < „- ш < ш ОО ш е о Р. О < а< о < ьни <о„- О О ОООООО О О О и>ш ш>ш > оо~ шиа "о" н ОО хиш О Ш М Ь х бой и О О е о О ООО и О и шшЬ И ХО и ь > си х ОО ши> < ш и Х и и а 0 < < М « ООО З > > и и и Мех е<х о< ш О ш 0 хе ш .2 > ш ООО >ше ш О О ш ОО шшх и ш -ш- Я е е ос ш ш < 4 -" о и ш < ш > и 55555"СРММАМЕУ СЯГЯР5 Система, основанная на картах свойств, работает с инвертированным файлом аналогичным образом: имеется по одной карте для каждого атрибута и отверстия в карте пробиваются в позициях, которые соответствуют записям, содержащим этот атрибут.
Таким образом, одна стандартнан перфокарта шириной 80 позиций мажет использоваться для хранения информации о том, какие из 12 х 60 = 960 записей имеют данный атрибут. Для обработки включающего запроса отбираются карты свойств для определенных атрибутов и накладываются одна на другую. Луч света, проходя через позиции, в которых на всех картах имеются отверстия, покажет искомый результат. Это напоминает обработку логического запроса путем пересечения инвертированных битовых строк, как объяснялось выше.
Кодирование методам наложения. Причина, па которой нас (вооруженнгях современными компьютерами) интересу.ют методы поиска по карточкам вручную, заключается в том, что в свое время было разработано много хитроумных способов ООО Ошш 9 и Од д о~и< О < О О 0 О 0 0 0 О О 0 О О О О О О О О О О О О О О О О О О О О О О О О О О О О О О О О О О О О О Рис. 46. Карта с перфорацией по краям. хранения места на картах с перфорацией по краям, принципы которых применимы и для представления компьютерных файлов. Кодирование методом наложения представляет собой технологию, схожую с хешированием. хотя оно было разработано за несколько лет до изобретения хеширования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
