Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 54
Текст из файла (страница 54)
Если рассматривать табл. 1 как матрицу из нулей и единиц, то транспонированная матрица будет представлять собой инвертированный файл в виде битовых строк. Правый столбец табл. 1 используется для указания специальных, редко используемых продуктов. Они могут быть закодированы более эффективно, без отдельного столбца для каждого из них. То же самое справедливо для столбца "Кукурузный крахмал".
Кроме того, можно найти более эффективный путь кодирования столбца "Мука", поскольку мука встречается во всех рецептах, кроме рецепта приготовления меренги. Однако пока оставим этот вопрос и просто проигнорируем столбец "Специальные ингредиенты". Будем определять базовый запрос к файлу бинарных атрибутов как запрос на все записи, в одних столбцах которых содержатся нули, в других — единицы и в остальных столбцах — произвольные величины. Используя символ "*" для обозначения любого значения, базовый запрос можно представить в виде последователыюстей символов О, 1 и "э'! Например, представим человека, который захотел печенья с кокосом и у которого аллергия на шоколад, который ненавидит анис и у которого дома закончился ванилнн. Тогда его запрос может быть сформулирован тпк: эОээээОээ1эээээээээээ«эээээ**О. (10) Из табл.
1 становится понятно, что его желания совпадают с его вазможностями в случае ароматных палочек с черносливом. Таблица 1 ФАЙЛ С БИНАРНММИ АТРИБУТАМИ ц в 3 еоф нии и йз3313$ жоООишо н $ а. 1Ы МЖй „х з5 п.ни лино нооо шзз и н и ж ~ )ц И Очно 6 «'и $ !Зло).
ко о ь бй зз низ ой йз МсСа)! "з Спой Воой (Хе» ЪЪг)с Капбош Нонне, )963), Саар)ег 9. Миндальные вафли с ромом Печенье с яблочным соусом Бананово-овсяное печенье Шоколадный хворост Миндальное печенье с кокосами Печенье со гливочиым сыром Ароматнме палочки с черносливом Драже в шоколаде Райские палочки Пирог с начинкой Фннсквй квкор Глазированные имбирные пряники Печенье с орехвмн Драгоценное печенье Перепутаница Малайский крендель Медовые пряники Меренги Моравское печенье со специями Овсяные палочки с финиками Старинное сахарное печенье Печенье с арахисовым маслом Юбочки Печенье с перцем Шотландские овсяные коржики Песочные змздочкв Анисовое печенье Воздушное печенье Шведский крендель Швейцарское рассыпчатое печенье с корицей Ириски Ванилыю ореховое мороженое 0000 0001 0001 000) 0010 0000 ОООР ООО) 0010 0010 ОООО 0011 0001 ОООО 0000 0000 1001 0000 1001 0001 0011 0001 0001 1110 оооо ОООО 0110 ОООО ОООО 0000 0000 0010 1000 100! 1001 1010 1000 1010 1000 О)а 1000 1000 1000 1001 1001 1000 1001 1100 0001 1000 ) 001 1000 1000 1010 1000 0101 1000 1ООО 0000 1000 1000 )РО) 1010 1000 000000 10000! 000001 000001 0)0001 000000 010101 000001 О)0001 000011 000001 )ОООО) 001001 000001 000001 000001 !ОООО 000011 !ОООО! 000010 000001 000001 000000 101001 000000 000000 000001 000000 00000 1 000001 Оааааа 000001 010 1 ) О 110 ! 1 О 110 1)О 110 110 110 ) 1 О 110 11 1 110 110 110 110 !)а 000 О ! 1 010 1)О 110 010 110 010 010 110 110 ))О ) 10 110 110 001 00 О 000 ОО 0 000 00 О 000 ООО 000 110 000 001 000 000 О О О 010 111 000 000 100 000 000 000 010 000 000 01 О 000 ОО! 001 000 000 001 011 011 001 001 О О О 001 001 001 001 001 100 010 001 000 001 Р1 1 0 О! 110 00 ! 0)О 000 ООО 011 000 000 000 000 000 000 001 ОО 1 О О О 010 10 1 001 001 000 001 00 1 Оа! 001 001 000 011 000 001 ОРО 001 000 001 101 001 001 001 001 101 000 001 001 Оаа О О! 000 001 010 011 010 010 010 0)О )00 010 100 010 0! 0 101 1ОО 100 010 010 101 010 101 110 о!а 100 001 101 010 100 011 010 010 110 100 010 0— 1 Яблочный соус 1 Бананы 1 1 1 Сливочный сыр 0 Апельсины, чернослив 0— 1 1 0 Экстракт миндаля 0 Уксус 0 Абриюк ) Сморсцвноаое желе 1 Растительное масло 0— 0 Мед 0 Засахаренная вишня 0— 0— 1 Сметана 1 Арахисовое масло 1 0 Цукаты, перец, мускат 1 0— 0— 1— 0— 0— 1 !в Прежде чем приступить к организации файла для базовых запросов, рассмотрим один важный специальный момент, когда в запросе отсутствуют нули, а есть только 1 и «*'! Такой запрос можно назвать включающим (1пс)клее диету), поскольку он запрашивает записи, которые еключакип некоторое множество атрибутов 1если предположить, что 1 означает наличие определенного атрибута, а 0 — его отсутствие).
Например, в табл. 1 два рецепта одновременно содержат и непарный порошок, и пищевую соду — глазированные имбирные пряники и старинное сахарное печенье. В некоторых приложениях достаточно использовать специальные включающие запросы, например в ручиых карточных системах наподобие карт с перфорацией по краям или карт свойств. Система карт с перфорацией по краям для табл. 1 будет иметь по одной карточке на каждый рецепт с вырезами, соответствующими каждому ицгредиеиту 1рис. 46). Обработка включающего запроса сводится к складыванию карточек аккуратпой стопкой и введению спиц в положениях, соответствующих конкретиым ипгредиеитам. После ввода спиц все карточки с опредеаениыми атрибутами выпадают из стопки.
Рис. 46. Карта с перфорацией по краям, Система, основанная на картах свойств, работает с инвертированиыи файлом аналогичным образом: имеется по одной карте для каждого атрибута и отверстия в карте пробиваются в позициях, которые соответствуют записям, содержаюииы этот атрибут. Таким образам, одна стандартная перфокарта шириной 80 позиций может использоваться для хранения информации о тои, какие из 12 х 80 = 960 записей имеют данный атрибут.
Для обработки включелощего запроса отбираются карты свойств для определенных атрибутов и накладываются одна па другую. Луч света, проходя через позиции, в которых на всех картах имеются отверстия, покажет искомый результат. Это папоминает обработку логического запроса путем пересечения инвертированных битовых строк, как объяснялось выше. Кодирование методом наложения. Причина, по которой нас (вооруженных современными компьютерами) интересуют методы поиска по карточкам вручиую, заключается в том, что в свое время было разработано много хитроумных способов хранения места па картах с перфорацией по краям, принципы которых применимы и для представления компьютерных файлов. Кодирование методом наложения представляет собой технологию, схожую с хешированием, хотя оно было разработано за несколько лет до изобретения хеширования.
Идея заключается в отображении атрибутов в случайные /г-битовые коды и и-битовых полях и наложении кодов каждого атрибута, имеющегося в записи. Включающий запрос для некоторого миожества атрибутов может быть конвертирован во включающий запрос для соответствующих наложенных битовых кодов. Такому запросу могут удовлетворять несколько дополнительных записей, но количество подобных "ложных выпадений" может быть статистически учтено !см. Са1гйп Х. Х!ооегз, Ашег. Слеш. Яос. Месс!л8 112 (Яерсешоех. 1947), 14Е-15Е; Ашепсал Поспшеигаиоп 2 (1951), 20 — 32). В качестве примера кодирования методом наложения вновь обратимся к табл. 1, но только к той ее части, которая относится к специям, не рассматривая осиовиые компоненты иаподобие пекариого порошка. яиц и муки.
В табл. 2 показаио, что произойдет, если назначить случайные двухбитовые коды в десятибитовых полях каждой из специй и использовать наложение. Например, "Шоколадный хворост" будет получен в результате наложения кодов шоколада, орехов и ваиилина: 0010001000 ~ 0000100100 ц 0000001001 = 0010101101. Наложение данных кодов даст также несколько ложных атрибутов; в нашем конкретном случае — дуплистый перец, засахареииую вишню, смородиновое желе, арахисовое масло и перец. Это вызовет ложвые выпадения при некоторых запросах (тем самым будет предложено разработать новый рецепт — "Ложиовыпадающее печенье"!:-) ) .
Для табл. 2 кодирование методом наложения работает не так уж хорошо, поскольку зта таблица представляет всего лишь маленький пример с большим количеством атрибутов. В самом деле, "'Печенье с яблочным соусом" будет выпадать при каждом запросе, поскольку оно получено наложением семи кодов, покрывающих все десять позиций. Еще хуже обстоят дела и случае рецепта печенья с перцем (впрочем, с точки зрения кодов и ложных выпадений совершенно все равно, как получена цепочка из десяти единиц: наложением семи или двенадцати кодов.
— Прим. перев.), полученного в результате наложения двенадцати кодов. С другой стороны, иногда табл. 2 работает на удивление неплохо; например, дав запрос "Ванилин", мы получим только одно ложное выпадение -- "Печенье с перцем". Более подходящий пример кодирования методом наложения получается при наличии, скажем, 32-битового поля и набора из ( з ) = 4960 различных атрибутов, где каждая запись может иметь до шести атрибутов и каждый атрибут кодируется тремя из 32 бит. В втой ситуации в предположении, что каждая запись имеет шесть случайно выбранных атрибутов, вероятности ложных выпадений в случае включающего запроса составляют: по одному атрибуту 0.079483э8 по двум атрибутам 0.00708659 по трем атрибутам 0.00067094 по четырем атрибутам О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
