\input style
\chapno=6\subchno=4\chapnotrue

\subchap{выборка по вторичным ключам} %%6.5
мЫ ЗАВЕРШИЛИ ИЗУЧЕНИЕ ПОИСКА ПО "ПЕРВИЧНЫМ КЛЮЧАМ", Т.~Е.
ПО КЛЮЧАМ, ОДНОЗНАЧНО ОПРЕДЕЛЯЮЩИМ ЗАПИСЬ В ФАЙЛЕ. нО ИНОГДА
НЕОБХОДИМО ВЕСТИ ПОИСК, ОСНОВЫВАЯСЬ НЕ НА ПЕРВИЧНЫХ КЛЮЧАХ, А НА ЗНАЧЕНИЯХ
ДРУГИХ ПОЛЕЙ ЗАПИСИ, КОТОРЫЕ ЧАСТО НАЗЫВАЮТСЯ "ВТОРИЧНЫМИ КЛЮЧАМИ" ИЛИ
"АТРИБУТАМИ" ЗАПИСИ. нАПРИМЕР, В РЕГИСТРАЦИОННОМ ФАЙЛЕ, СОДЕРЖАЩЕМ
ИНФОРМАЦИЮ О СТУДЕНТАХ УНИВЕРСИТЕТА, МОЖЕТ ПОНАДОБИТЬСЯ НАЙТИ ВСЕХ
СТУДЕНТОВ-ВТОРОКУРСНИКОВ ИЗ оГАЙО, НЕ СПЕЦИАЛИЗИРУЮЩИХСЯ ПО
МАТЕМАТИКЕ ИЛИ СТАТИСТИКЕ, ИЛИ МОЖЕТ ПОНАДОБИТЬСЯ НАЙТИ ВСЕХ НЕЗАМУЖНИХ
АСПИРАНТОК, ГОВОРЯЩИХ ПО-ФРАНЦУЗСКИ, И Т.~Д.

вООБЩЕ ПРЕДПОЛОЖИМ, ЧТО КАЖДАЯ ЗАПИСЬ ИМЕЕТ НЕСКОЛЬКО АТРИБУТОВ И МЫ ХОТИМ
НАЙТИ ВСЕ ЗАПИСИ С ОПРЕДЕЛЕННЫМИ ЗНАЧЕНИЯМИ ОПРЕДЕЛЕННЫХ АТРИБУТОВ.
сПЕЦИФИКАЦИЯ ИСКОМЫХ ЗАПИСЕЙ НАЗЫВАЕТСЯ \dfn{ЗАПРОСОМ}. оБЫЧНО ДОПУСКАЕТСЯ
НЕ БОЛЕЕ ТРЕХ СЛЕДУЮЩИХ ТИПОВ ЗАПРОСОВ.
\medskip
\item{a)}~\dfn{пРОСТОЙ ЗАПРОС}, КОГДА ОПРЕДЕЛЕННОМУ АТРИБУТУ
ЗАДАЕТСЯ КОНКРЕТНОЕ ЗНАЧЕНИЕ, НАПРИМЕР $|специальность|=|математика|$ ИЛИ
$|местожительство|.|штат| = |огайо|$.

\item{b)}~\dfn{зАПРОС ПО ОБЛАСТИ ЗНАЧЕНИЙ}, КОГДА ДЛЯ
ОПРЕДЕЛЕННОГО АТРИБУТА ЗАДАЕТСЯ КОНКРЕТНАЯ ОБЛАСТЬ ЗНАЧЕНИЙ, НАПРИМЕР
$|цена|<18.00\$$; ИЛИ $21 \le |возраст| \le 23$.

\item{c)}~\dfn{бУЛЕВ ЗАПРОС} СОСТОИТ ИЗ ЗАПРОСОВ ДВУХ ПЕРВЫХ ТИПОВ,
 СОЕДИНЕННЫХ ОПЕРАЦИЯМИ |и|, |или|, |не|; НАПРИМЕР,
$$
\displaylines{
(|курс|=|второкурсник|) \mathbin{|и|} (|местожительство.штат|=|огайо|) \cr
\mathbin{|и|} \mathop{|не|}\nolimits
((|специальность|=|математика|)\mathbin{|или|} (|специальность|=|статистика|)).\cr
}
$$

зАДАЧА РАЗРАБОТКИ ЭФФЕКТИВНЫХ МЕТОДОВ ПОИСКА ДОСТАТОЧНО ТРУДНА УЖЕ ДЛЯ
ЭТИХ ТРЕХ ТИПОВ ЗАПРОСОВ, ПОЭТОМУ ЗАПРОСЫ БОЛЕЕ СЛОЖНЫХ ТИПОВ ОБЫЧНО НЕ
РАССМАТРИВАЮТСЯ. нАПРИМЕР, ЖЕЛЕЗНОДОРОЖНАЯ КОМПАНИЯ МОГЛА БЫ ИМЕТЬ ФАЙЛ,
ОПИСЫВАЮЩИЙ ТЕКУЩЕЕ СОСТОЯНИЕ ВСЕХ ПРИНАДЛЕЖАЩИХ ЕЙ ТОВАРНЫХ
ВАГОНОВ. зАПРОС ТИПА "НАЙДИ ВСЕ СВОБОДНЫЕ ВАГОНЫ-ХОЛОДИЛЬНИКИ В ПРЕДЕЛАХ
500~МИЛЬ ОТ сИЭТЛА" В ЯВНОМ ВИДЕ БЫЛ БЫ НЕДОПУСТИМ, ЕСЛИ БЫ "РАССТОЯНИЕ ОТ
сИЭТЛА" БЫЛО НЕ АТРИБУТОМ КАЖДОЙ ЗАПИСИ, А СЛОЖНОЙ ФУНКЦИЕЙ НЕСКОЛЬКИХ
АТРИБУТОВ. иСПОЛЬЗОВАНИЕ ЖЕ ЛОГИЧЕСКИХ КВАНТОРОВ В ДОПОЛНЕНИЕ К |и|,
|или| И~|не| ВЕДЕТ К ДАЛЬНЕЙШИМ УСЛОЖНЕНИЯМ, СТЕПЕНЬ КОТОРЫХ ОГРАНИЧЕНА
%% 652
ЛИШЬ ФАНТАЗИЕЙ АВТОРА ЗАПРОСА. нАПРИМЕР, ИМЕЯ ФАЙЛ БЕЙСБОЛЬНОЙ
СТАТИСТИКИ, МЫ МОГЛИ БЫ ЗАПРОСИТЬ ДАННЫЕ О САМОЙ ДЛИННОЙ СЕРИИ УДАЧНЫХ
УДАРОВ В ВЕЧЕРНИХ ИГРАХ. эТИ ЗАПРОСЫ СЛОЖНЫ, НО НА НИХ ВСЕ ЖЕ МОЖНО
ОТВЕТИТЬ, ВЫПОЛНИВ ОДИН ПРОХОД ПО ДОЛЖНЫМ ОБРАЗОМ ОРГАНИЗОВАННОМУ ФАЙЛУ.
еСТЬ И ЕЩЕ БОЛЕЕ ТРУДНЫЕ ЗАПРОСЫ; НАПРИМЕР, НАЙТИ ВСЕ ПАРЫ ЗАПИСЕЙ,
ИМЕЮЩИХ ОДИНАКОВЫЕ ЗНАЧЕНИЯ ПЯТИ ИЛИ БОЛЕЕ АТРИБУТОВ (БЕЗ ОПРЕДЕЛЕНИЯ
ТОГО, КАКИЕ ИМЕННО АТРИБУТЫ ДОЛЖНЫ СОВПАДАТЬ). пОДОБНЫЕ ЗАПРОСЫ МОЖНО
РАССМАТРИВАТЬ КАК ОБЩИЕ ЗАДАЧИ ПРОГРАММИРОВАНИЯ, ВЫХОДЯЩИЕ ЗА РАМКИ
ДАННОЙ РАБОТЫ, ХОТЯ ЧАСТО ИХ МОЖНО РАЗБИТЬ НА ПОДЗАДАЧИ РАССМАТРИВАЕМЫХ
НАМИ ТИПОВ.

пРЕЖДЕ ЧЕМ ПЕРЕХОДИТЬ К ИЗУЧЕНИЮ РАЗЛИЧНЫХ МЕТОДОВ ВЫБОРКИ ПО ВТОРИЧНЫМ
КЛЮЧАМ, УМЕСТНО РАССМОТРЕТЬ ЭКОНОМИЧЕСКУЮ СТОРОНУ ВОПРОСА. хОТЯ ДОВОЛЬНО
ОБШИРНАЯ ОБЛАСТЬ ПРИЛОЖЕНИЙ ПОПАДАЕТ В ЖЕСТКИЕ РАМКИ ТРЕХ ТИПОВ ЗАПРОСОВ,
СЛОЖНЫЕ МЕТОДЫ, КОТОРЫЕ МЫ БУДЕМ ИЗУЧАТЬ, ДАЛЕКО НЕ ВСЕГДА
ЯВЛЯЮТСЯ УДОВЛЕТВОРИТЕЛЬНЫМИ; ИНУЮ РАБОТУ МОЖНО БЫСТРЕЕ СДЕЛАТЬ ВРУЧНУЮ!
эвм УВЕЛИЧИЛИ СКОРОСТЬ НАУЧНЫХ ВЫЧИСЛЕНИЙ ПРИБЛИЗИТЕЛЬНО В
$10^7$--$10^8$~РАЗ; ПОВЫШЕНИЕ ЖЕ ЭФФЕКТИВНОСТИ В ДЕЛЕ УПРАВЛЕНИЯ
ИНФОРМАЦИЕЙ НЕИЗМЕРИМО МЕНЬШЕ. пРИ ОПЕРАЦИЯХ С БОЛЬШИМ КОЛИЧЕСТВОМ ДАННЫХ
СОВРЕМЕННЫЕ эвм РАБОТАЮТ ВСЕ ЕЩЕ С МЕХАНИЧЕСКИМИ (А НЕ ЭЛЕКТРОННЫМИ)
СКОРОСТЯМИ, ПОЭТОМУ, ЗАМЕНЯЯ РУЧНУЮ СИСТЕМУ НА эвм, МЫ НЕ ПОЛУЧАЕМ РЕЗКОГО
УЛУЧШЕНИЯ ХАРАКТЕРИСТИК НА ЕДИНИЦУ ЗАТРАТ. нЕ СЛЕДУЕТ ОЖИДАТЬ ОТ эвм
СЛИШКОМ МНОГОГО ТОЛЬКО ПОТОМУ, ЧТО ОНИ ЗДОРОВО РЕШАЮТ НЕКОТОРЫЕ ЗАДАЧИ\dots

лЮДИ ПОКОРИЛИ эВЕРЕСТ "ПОТОМУ, ЧТО ОН СУЩЕСТВУЕТ", И ПОТОМУ, ЧТО БЫЛО
СОЗДАНО ОБОРУДОВАНИЕ, СДЕЛАВШЕЕ ВОСХОЖДЕНИЕ ВОЗМОЖНЫМ; ТОЧНО ТАК ЖЕ,
ВСТРЕТИВШИСЬ С ГОРОЙ ИНФОРМАЦИИ, ЛЮДИ ПОПЫТАЛИСЬ ИСПОЛЬЗОВАТЬ эвм ДЛЯ
ОТВЕТОВ НА САМЫЕ ТРУДНЫЕ МЫСЛИМЫЕ И НЕМЫСЛИМЫЕ ВОПРОСЫ В ОПЕРАТИВНОМ
РЕЖИМЕ И РЕАЛЬНОМ МАСШТАБЕ ВРЕМЕНИ, НЕ УЧИТЫВАЯ ДОЛЖНЫМ ОБРАЗОМ СТОИМОСТИ
РАБОТЫ. тРЕБУЕМЫЕ ВЫЧИСЛЕНИЯ ВОЗМОЖНЫ, НО СЛИШКОМ ДОРОГИ ДЛЯ КАЖДОДНЕВНОГО
ИСПОЛЬЗОВАНИЯ.

рАССМОТРИМ, НАПРИМЕР, СЛЕДУЮЩИЙ ПРОСТОЙ СПОСОБ ВЫБОРКИ ПО ВТОРИЧНЫМ
КЛЮЧАМ: ПОСЛЕ "\emph{БУФЕРИЗАЦИИ}" РЯДА ЗАПРОСОВ МОЖНО ПРОИЗВЕСТИ
ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК ВО ВСЕМ ФАЙЛЕ, ВЫБИРАЯ ВСЕ НУЖНЫЕ ЗАПИСИ.
("бУФЕРИЗАЦИЯ" ОЗНАЧАЕТ, ЧТО МЫ НАКАПЛИВАЕМ ЗАПРОСЫ, ПРЕЖДЕ ЧЕМ НАЧАТЬ
ИХ ОБРАБОТКУ.) эТОТ МЕТОД ВПОЛНЕ УДОВЛЕТВОРИТЕЛЕН, ЕСЛИ ФАЙЛ НЕ СЛИШКОМ
ВЕЛИК, А НА ЗАПРОСЫ НЕ НАДО ОТВЕЧАТЬ НЕМЕДЛЕННО. оН ГОДИТСЯ ДАЖЕ
ДЛЯ ФАЙЛОВ НА ЛЕНТАХ И ЛИШЬ ВРЕМЯ ОТ ВРЕМЕНИ ТРЕБУЕТ ВНИМАНИЯ эвм, ЧТО
ДЕЛАЕТ ЕГО ОЧЕНЬ ЭКОНОМИЧНЫМ В СМЫСЛЕ СТОИМОСТИ ОБОРУДОВАНИЯ. бОЛЕЕ ТОГО,
ПРЕДЛАГАЕМЫЙ ПОДХОД ПРИМЕНИМ ДАЖЕ ДЛЯ ОБРАБОТКИ ВЫЧИСЛИТЕЛЬНЫХ ЗАПРОСОВ
ТИПА "РАССТОЯНИЯ ОТ сИЭТЛА".

%%653

дРУГОЙ СПОСОБ ОБЛЕГЧИТЬ ВЫБОРКУ ПО ВТОРИЧНЫМ КЛЮЧАМ---ПОРУЧИТЬ
\emph{ЧЕЛОВЕКУ} ЧАСТЬ РАБОТЫ, ОБЕСПЕЧИВ ЕГО ДОЛЖНЫМ ОБРАЗОМ ОФОРМЛЕННЫМИ
УКАЗАТЕЛЯМИ ИНФОРМАЦИИ. чАСТО ТАКОЙ ПОДХОД ОКАЗЫВАЕТСЯ НАИБОЛЕЕ РАЗУМНЫМ
И ЭКОНОМИЧНЫМ (РАЗУМЕЕТСЯ, ПРИ ТОМ УСЛОВИИ, ЧТО ПОСЛЕ ВЫХОДА В СВЕТ НОВОГО
УКАЗАТЕЛЯ СТАРАЯ БУМАГА ПЕРЕРАБАТЫВАЕТСЯ).

оДНАКО ОПИСАННЫЕ ПРОСТЫЕ СХЕМЫ НЕ ЯВЛЯЮТСЯ УДОВЛЕТВОРИТЕЛЬНЫМИ, ЕСЛИ
ВАЖНЫ БЫСТРЫЕ ОТВЕТЫ НА ЗАПРОСЫ, А ФАЙЛЫ ОЧЕНЬ ВЕЛИКИ. тАКАЯ СИТУАЦИЯ
ИМЕЕТ МЕСТО, НАПРИМЕР, ЕСЛИ ФАЙЛ ПРЕДСТАВЛЯЕТ СОБОЙ ОБоЕКТ НЕПРЕРЫВНЫХ
ЗАПРОСОВ ОТ РЯДА ОДНОВРЕМЕННЫХ, ПОЛЬЗОВАТЕЛЕЙ ИЛИ ЕСЛИ ЗАПРОСЫ
ПОРОЖДАЮТСЯ НЕ ЧЕЛОВЕКОМ, А МАШИНОЙ. цЕЛЬ НАСТОЯЩЕГО ПАРАГРАФА---ПОНЯТЬ,
НАСКОЛЬКО ХОРОШО МОЖНО ПРОИЗВОДИТЬ ВЫБОРКУ ПО ВТОРИЧНЫМ КЛЮЧАМ, ИСПОЛЬЗУЯ
ОБЫЧНЫЕ эвм, ПРИ РАЗЛИЧНЫХ ПРЕДПОЛОЖЕНИЯХ О СТРУКТУРЕ ФАЙЛА.

бЫЛО ВЫДВИНУТО НЕМАЛО ХОРОШИХ ИДЕЙ ДЛЯ РЕШЕНИЯ ЭТОЙ ЗАДАЧИ, НО (КАК
ЧИТАТЕЛЬ НАВЕРНЯКА УЖЕ ДОГАДАЛСЯ) ЭТИ АЛГОРИТМЫ ОКАЗАЛИСЬ НЕИЗМЕРИМО
ХУЖЕ ИМЕЮЩИХСЯ АЛГОРИТМОВ ВЫБОРКИ ПО ПЕРВИЧНЫМ КЛЮЧАМ. вСЛЕДСТВИЕ
БОЛЬШОГО РАЗНООБРАЗИЯ ФАЙЛОВ И ПРИЛОЖЕНИЙ МЫ НЕ СМОЖЕМ ДАТЬ
ИСЧЕРПЫВАЮЩЕГО ОБСУЖДЕНИЯ ВСЕХ ИМЕЮЩИХСЯ ВОЗМОЖНОСТЕЙ, КАК И НЕ
СМОЖЕМ ПРОАНАЛИЗИРОВАТЬ ПОВЕДЕНИЕ КАЖДОГО АЛГОРИТМА В ТИПИЧНЫХ УСЛОВИЯХ. в
НАСТОЯЩЕМ ПАРАГРАФЕ СОДЕРЖАТСЯ ЛИШЬ ОСНОВНЫЕ ИЗ ПРЕДЛАГАВШИХСЯ ПОДХОДОВ;
ДЕЛО ЧИТАТЕЛЯ РЕШАТЬ, КАКАЯ КОМБИНАЦИЯ МЕТОДОВ БОЛЬШЕ ВСЕГО ПОДХОДЯТ В
КАЖДОМ КОНКРЕТНОМ СЛУЧАЕ.

\section иНВЕРТИРОВАННЫЕ ФАЙЛЫ. пЕРВЫЙ ВАЖНЫЙ КЛАСС МЕТОДОВ ВЫБОРКИ ПО
ВТОРИЧНЫМ КЛЮЧАМ ОСНОВАН НА ИДЕЕ "ИНВЕРТИРОВАННОГО ФАЙЛА". эТОТ ТЕРМИН НЕ
ОЗНАЧАЕТ, ЧТО ФАЙЛ ПЕРЕВЕРНУТ ВВЕРХ ДНОМ, ОН ОЗНАЧАЕТ, ЧТО ЗАПИСИ И
АТРИБУТЫ ПОМЕНЯЛИСЬ РОЛЯМИ. вМЕСТО ПЕРЕЧИСЛЕНИЯ АТРИБУТОВ ДАННОЙ ЗАПИСИ
ПЕРЕЧИСЛЯЮТСЯ ЗАПИСИ, ИМЕЮЩИЕ ДАННОЕ ЗНАЧЕНИЕ АТРИБУТА.

в ПОВСЕДНЕВНОЙ ЖИЗНИ МЫ ДОВОЛЬНО ЧАСТО (ПРАВДА, ПОД ДРУГИМИ ИМЕНАМИ)
СТАЛКИВАЕМСЯ С ИНВЕРТИРОВАННЫМИ ФАЙЛАМИ. нАПРИМЕР, ИНВЕРТИРОВАННЫМ ФАЙЛОМ,
СООТВЕТСТВУЮЩИМ РУССКО-АНГЛИЙСКОМУ СЛОВАРЮ, ЯВЛЯЕТСЯ АНГЛО-РУССКИЙ
СЛОВАРЬ. иНВЕРТИРОВАННЫМ ФАЙЛОМ, СООТВЕТСТВУЮЩИМ ЭТОЙ КНИГЕ,
ЯВЛЯЮТСЯ УКАЗАТЕЛИ, ПОМЕЩЕННЫЕ НА ПОСЛЕДНИХ СТРАНИЦАХ.
бУХГАЛТЕРЫ ТРАДИЦИОННО ИСПОЛЬЗУЮТ "ДВОЙНУЮ БУХГАЛТЕРИЮ", КОГДА ВСЕ
ДЕЛОВЫЕ СОГЛАШЕНИЯ РЕГИСТРИРУЮТСЯ КАК В СЧЕТЕ КАССЫ, ТАК И В СЧЕТЕ
КЛИЕНТА, ЧТО ПОЗВОЛЯЕТ ЛЕГКО КОНТРОЛИРОВАТЬ НАЛИЧНУЮ СУММУ ДЕНЕГ И ДОЛГ
КЛИЕНТА.

вООБЩЕ ИНВЕРТИРОВАННЫЙ ФАЙЛ ОБЫЧНО НЕ СУЩЕСТВУЕТ САМ ПО СЕБЕ, ЕГО НУЖНО
ИСПОЛЬЗОВАТЬ ВМЕСТЕ С ПЕРВОНАЧАЛЬНЫМ, НЕИНВЕРТИРОВАННЫМ ФАЙЛОМ ДЛЯ
УСКОРЕНИЯ ПОИСКА С ПОМОЩЬЮ СОДЕРЖАЩЕЙСЯ
%%654
В НЕМ ИЗБЫТОЧНОЙ ИНФОРМАЦИИ. кОМПОНЕНТЫ ИНВЕРТИРОВАННОГО ФАЙЛА,
Т.~Е.~СПИСКИ ВСЕХ ЗАПИСЕЙ, ИМЕЮЩИХ ДАННОЕ ЗНАЧЕНИЕ НЕКОТОРОГО АТРИБУТА,
НАЗЫВАЮТСЯ \dfn{ИНВЕРТИРОВАННЫМИ СПИСКАМИ}.

кАК И ВСЕ СПИСКИ ВООБЩЕ, ИНВЕРТИРОВАННЫЕ СПИСКИ МОЖНО ПРЕДСТАВЛЯТЬ В
ПАМЯТИ эвм РАЗЛИЧНЫМИ СПОСОБАМИ, И ДЛЯ РАЗНЫХ ПРИЛОЖЕНИЙ ПОДХОДЯТ РАЗНЫЕ
ПРЕДСТАВЛЕНИЯ. нЕКОТОРЫЕ ПОЛЯ ВТОРИЧНЫХ КЛЮЧЕЙ МОГУТ ИМЕТЬ ЛИШЬ ДВА
ЗНАЧЕНИЯ (НАПРИМЕР, АТРИБУТ "ПОЛ"), А СООТВЕТСТВУЮЩИЕ
ИНВЕРТИРОВАННЫЕ СПИСКИ ОЧЕНЬ ДЛИННЫ, НО ДРУГИЕ ПОЛЯ ОБЫЧНО ИМЕЮТ ОЧЕНЬ
МНОГО ЗНАЧЕНИЙ С РЕДКИМИ ПОВТОРЕНИЯМИ (НАПРИМЕР, АТРИБУТ "НОМЕР ТЕЛЕФОНА").

пРЕДСТАВИМ СЕБЕ, ЧТО МЫ ХОТИМ ХРАНИТЬ ИНФОРМАЦИЮ В ТЕЛЕФОННОЙ КНИГЕ
ТАКИМ ОБРАЗОМ, ЧТОБЫ ВСЕ ЭЛЕМЕНТЫ МОЖНО БЫЛО ВЫБИРАТЬ ЛИБО ПО ИМЕНИ, ЛИБО
ПО НОМЕРУ ТЕЛЕФОНА, ЛИБО ПО МЕСТУ ЖИТЕЛЬСТВА. оДНО ИЗ РЕШЕНИЙ СОСТОИТ В
ТОМ, ЧТОБЫ ПРОСТО ИМЕТЬ ТРИ ОТДЕЛЬНЫХ ФАЙЛА, ОРИЕНТИРОВАННЫХ НА КАЖДЫЙ
ТИП КЛЮЧЕЙ. дРУГАЯ ИДЕЯ ЗАКЛЮЧАЕТСЯ В ОБоЕДИНЕНИИ ЭТИХ ФАЙЛОВ, НАПРИМЕР, С
ПОМОЩЬЮ ПОСТРОЕНИЯ ТРЕХ РАССЕЯННЫХ ТАБЛИЦ, СЛУЖАЩИХ В МЕТОДЕ ЦЕПОЧЕК
ГОЛОВНЫМИ УЗЛАМИ СПИСКОВ. в ЭТОЙ ПОСЛЕДНЕЙ СХЕМЕ КАЖДАЯ ЗАПИСЬ ДОЛЖНА БЫТЬ
ЭЛЕМЕНТОМ ТРЕХ СПИСКОВ И ДОЛЖНА ПОЭТОМУ СОДЕРЖАТЬ ТРИ ПОЛЯ ССЫЛКИ; ТАКОЙ
МЕТОД НАЗЫВАЕТСЯ \dfn{мНОГОСПИСОЧНЫМ} И ОБСУЖДАЕТСЯ НИЖЕ. еЩЕ ОДНА
ВОЗМОЖНОСТЬ---ОБоЕДИНИТЬ ТРИ ФАЙЛА В ОДИН СУПЕРФАЙЛ ПО АНАЛОГИИ С
БИБЛИОТЕЧНЫМ КАТАЛОГОМ, В КОТОРОМ КАРТОЧКИ С ФАМИЛИЯМИ АВТОРОВ, КАРТОЧКИ С
НАЗВАНИЯМИ КНИГ И КАРТОЧКИ С ТЕМАМИ КНИГ ВСЕ ВМЕСТЕ УПОРЯДОЧЕНЫ ПО АЛФАВИТУ.

иЗУЧЕНИЕ ФОРМАТА, ИСПОЛЬЗОВАННОГО В УКАЗАТЕЛЯХ К ДАННОЙ КНИГЕ, НАТАЛКИВАЕТ
НА ДРУГИЕ ИДЕИ О ПРЕДСТАВЛЕНИИ ИНВЕРТИРОВАННЫХ СПИСКОВ. еСЛИ
ОПРЕДЕЛЕННОМУ ЗНАЧЕНИЮ АТРИБУТА СООТВЕТСТВУЕТ ОКОЛО ПЯТИ ЭЛЕМЕНТОВ,
МОЖНО ОРГАНИЗОВАТЬ ОБЫЧНЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ СПИСОК АДРЕСОВ ЗАПИСЕЙ
(АНАЛОГИЧНО НОМЕРАМ СТРАНИЦ В УКАЗАТЕЛЕ К КНИГЕ), ИМЕЮЩИХ ДАННОЕ ЗНАЧЕНИЕ
ВТОРИЧНОГО КЛЮЧА. еСЛИ СООТВЕТСТВУЮЩИЕ ЗАПИСИ
РАСПОЛАГАЮТСЯ ПОСЛЕДОВАТЕЛЬНО, МОЖЕТ БЫТЬ ПОЛЕЗНЫМ УКАЗАНИЕ
ДИАПАЗОНА (НАПРИМЕР, СО СТРАНИЦЫ~200 ПО~214). еСЛИ ИЗВЕСТНО, ЧТО
ЗАПИСИ ФАЙЛА ДОВОЛЬНО ЧАСТО ПЕРЕМЕЩАЮТСЯ, ВМЕСТО АДРЕСОВ ЗАПИСЕЙ В
ИНВЕРТИРОВАННОМ ФАЙЛЕ, ПОЖАЛУЙ, ЛУЧШЕ ИСПОЛЬЗОВАТЬ ПЕРВИЧНЫЕ КЛЮЧИ;
ТОГДА ПРИ СМЕНЕ АДРЕСОВ ЗАПИСЕЙ НЕ НУЖНО БУДЕТ ПРОИЗВОДИТЬ НИКАКИХ
ИЗМЕНЕНИЙ. нАПРИМЕР, ПРИ ССЫЛКАХ НА бИБЛИЮ ВСЕГДА УКАЗЫВАЕТСЯ ГЛАВА И СТИХ,
 А УКАЗАТЕЛИ В НЕКОТОРЫХ КНИГАХ ОСНОВАНЫ НЕ НА НУМЕРАЦИИ СТРАНИЦ, А НА НОМЕРАХ ПАРАГРАФОВ.

оДНАКО ПРЕДЛОЖЕННЫЕ ИДЕИ НЕ ОЧЕНЬ ПОДХОДЯТ ДЛЯ СЛУЧАЯ АТРИБУТА С ДВУМЯ
ВОЗМОЖНЫМИ ЗНАЧЕНИЯМИ, ТИПА АТРИБУТА "|пол|". в ТАКОЙ СИТУАЦИИ НУЖЕН ЛИШЬ
ОДИН ИНВЕРТИРОВАННЫЙ СПИСОК,
%%655
ИБО НЕ МУЖЧИНА ЕСТЬ ЖЕНЩИНА И ОБРАТНО. еСЛИ КАЖДОЕ ЗНАЧЕНИЕ СООТВЕТСТВУЕТ
ПРИМЕРНО ПОЛОВИНЕ ЭЛЕМЕНТОВ ФАЙЛА, ИНВЕРТИРОВАННЫЕ СПИСКИ БУДУТ УЖАСНО
ДЛИННЫМИ, ОДНАКО НА ДВОИЧНОЙ эвм ЭТУ ТРУДНОСТЬ МОЖНО РАЗРЕШИТЬ ВЕСЬМА
ИЗЯЩНО, ИСПОЛЬЗУЯ ПРЕДСТАВЛЕНИЕ В ВИДЕ ЦЕПОЧКИ БИТОВ, ГДЕ КАЖДЫЙ
БИТ ОПРЕДЕЛЯЕТ ЗНАЧЕНИЕ АТРИБУТА ОПРЕДЕЛЕННОЙ ЗАПИСИ. тАК, ЦЕПОЧКА
БИТОВ~$01001011101\ldots$ МОГЛА БЫ ОЗНАЧАТЬ, ЧТО ПЕРВАЯ ЗАПИСЬ
ФАЙЛА ОПИСЫВАЕТ МУЖЧИНУ, ВТОРАЯ---ЖЕНЩИНУ, СЛЕДУЮЩИЕ ДВЕ---МУЖЧИН И Т.~Д.
(сР.~ТАКЖЕ С ОБСУЖДЕНИЕМ ПРЕДСТАВЛЕНИЯ ПРОСТЫХ ЧИСЕЛ В КОНЦЕ~\S~6.1.)

пРИВЕДЕННЫЕ МЕТОДЫ УДОВЛЕТВОРИТЕЛЬНЫ ДЛЯ ОБРАБОТКИ ЗАПРОСОВ ПО
КОНКРЕТНЫМ ЗНАЧЕНИЯМ АТРИБУТОВ. нЕКОТОРОЕ ОБОБЩЕНИЕ ЭТИХ МЕТОДОВ
ПОЗВОЛИТ ОБРАБАТЫВАТЬ ЗАПРОСЫ ПО ОБЛАСТИ ЗНАЧЕНИЙ. пРИ ЭТОМ ВМЕСТО
ХЕШИРОВАНИЯ НУЖНО ИСПОЛЬЗОВАТЬ СХЕМУ ПОИСКА, ОСНОВАННУЮ НА СРАВНЕНИЯХ (\S~6.2).

дЛЯ БУЛЕВЫХ ЗАПРОСОВ ТИПА
"$(|специальность| = |математика|) \mathbin{|и|}
(|местожительство|.|штат|= |огайо|)$"
 НУЖНО ПЕРЕСЕЧЬ ДВА ИНВЕРТИРОВАННЫХ СПИСКА. эТО МОЖНО СДЕЛАТЬ
НЕСКОЛЬКИМИ СПОСОБАМИ; НАПРИМЕР, ЕСЛИ ОБА СПИСКА УПОРЯДОЧЕНЫ, ОДИН
ПРОХОД ПО КАЖДОМУ ИЗ НИХ ПОЗВОЛЯЕТ ВЫЯВИТЬ ВСЕ ОБЩИЕ ЭЛЕМЕНТЫ. иЛИ ЖЕ
МОЖНО ВЗЯТЬ \emph{КРАТЧАЙШИЙ} СПИСОК И ПРОСМАТРИВАТЬ ЕГО ЭЛЕМЕНТЫ,
ПРОВЕРЯЯ ЗНАЧЕНИЯ ДРУГИХ АТРИБУТОВ;
ОДНАКО ТАКОЙ МЕТОД ПРИМЕНИМ К ОПЕРАЦИИ~|и| И НЕ ПРИМЕНИМ К ОПЕРАЦИИ~|или|.
кРОМЕ ТОГО, ОН НЕ ГОДИТСЯ ДЛЯ ВНЕШНИХ ФАЙЛОВ, ИБО ВЕДЕТ К БОЛЬШОМУ ЧИСЛУ
ОБРАЩЕНИЙ К ЗАПИСЯМ, НЕ УДОВЛЕТВОРЯЮЩИМ ЗАПРОСУ.

аНАЛОГИЧНЫЕ РАССУЖДЕНИЯ ПОКАЗЫВАЮТ, ЧТО УПОМЯНУТАЯ ВЫШЕ мНОГОСПИСОЧНАЯ
ОРГАНИЗАЦИЯ НЕЭФФЕКТИВНА ДЛЯ БУЛЕВЫХ ЗАПРОСОВ, ЕСЛИ ФАЙЛ ВНЕШНИЙ,
ПОСКОЛЬКУ ОНА ТРЕБУЕТ МНОГО НЕНУЖНЫХ ОБРАЩЕНИЙ. пРЕДСТАВИМ СЕБЕ, НАПРИМЕР,
ЧТО ПРОИЗОЙДЕТ, ЕСЛИ УКАЗАТЕЛЬ К ЭТОЙ КНИГЕ ОРГАНИЗОВАТЬ мНОГОСПИСОЧНЫМ
ОБРАЗОМ. кАЖДЫЙ ЭЛЕМЕНТ УКАЗАТЕЛЯ БУДЕТ ССЫЛАТЬСЯ ЛИШЬ НА ПОСЛЕДНЮЮ ИЗ ТЕХ
СТРАНИЦ, ГДЕ РАСПОЛАГАЕТСЯ ОПИСЫВАЕМЫЙ ОБоЕКТ; НА КАЖДОЙ СТРАНИЦЕ ДЛЯ
КАЖДОГО ОБоЕКТА ДОЛЖНА ИМЕТЬСЯ ССЫЛКА НА МЕСТО ЕГО ПРЕДЫДУЩЕГО ПОЯВЛЕНИЯ.
в ТАКОМ СЛУЧАЕ ПРИДЕТСЯ ПЕРЕЛИСТАТЬ МНОГО СТРАНИЦ, ЧТОБЫ НАЙТИ ВЕСЬ
МАТЕРИАЛ, ОТНОСЯЩИЙСЯ К ТЕМЕ "[аНАЛИЗ АЛГОРИТМОВ] И [(вНЕШНЯЯ СОРТИРОВКА)
ИЛИ (вНУТРЕННЯЯ СОРТИРОВКА)]". с ДРУГОЙ СТОРОНЫ, ТОТ ЖЕ ЗАПРОС
МОЖНО ОБРАБОТАТЬ, ВЗГЛЯНУВ ВСЕГО НА ДВЕ СТРАНИЦЫ ОБЫЧНОГО УКАЗАТЕЛЯ И
ПРОИЗВЕДЯ НЕСЛОЖНЫЕ ОПЕРАЦИИ НАД ИНВЕРТИРОВАННЫМИ СПИСКАМИ ДЛЯ
НАХОЖДЕНИЯ НЕБОЛЬШОГО ПОДМНОЖЕСТВА СТРАНИЦ, УДОВЛЕТВОРЯЮЩИХ ЗАПРОСУ.

еСЛИ ИНВЕРТИРОВАННЫЙ СПИСОК ПРЕДСТАВЛЕН В ВИДЕ ЦЕПОЧКИ БИТОВ, НЕ
СОСТАВЛЯЕТ БОЛЬШОГО ТРУДА ВЫПОЛНИТЬ БУЛЕВЫ КОМБИНАЦИИ ЗАПРОСОВ,
ПОСКОЛЬКУ эвм МОГУТ МАНИПУЛИРОВАТЬ ЦЕПОЧКАМИ БИТОВ СО СРАВНИТЕЛЬНО
ВЫСОКОЙ СКОРОСТЬЮ. в СЛУЧАЕ СМЕШАННЫХ
%%656
ЗАПРОСОВ, КОГДА НЕКОТОРЫЕ АТРИБУТЫ ПРЕДСТАВЛЕНЫ ПОСРЕДСТВОМ
ПОСЛЕДОВАТЕЛЬНЫХ СПИСКОВ НОМЕРОВ ЗАПИСЕЙ, А ДРУГИЕ ПОСРЕДСТВОМ ЦЕПОЧЕК
БИТОВ, НЕТРУДНО ПРЕОБРАЗОВАТЬ ПОСЛЕДОВАТЕЛЬНЫЕ СПИСКИ В ЦЕПОЧКИ БИТОВ И
ПРОИЗВЕСТИ НАД НИМИ БУЛЕВЫ ОПЕРАЦИИ.

в ЭТОМ МЕСТЕ ПОЛЕЗНО ПРИВЕСТИ КОЛИЧЕСТВЕННЫЙ ПРИМЕР ГИПОТЕТИЧЕСКОГО
ПРИЛОЖЕНИЯ. пРЕДПОЛОЖИМ, ИМЕЕТСЯ 1000000~ЗАПИСЕЙ ПО 40~ЛИТЕР В КАЖДОЙ, И
ПУСТЬ ФАЙЛ ХРАНИТСЯ НА ДИСКАХ \MIXTEC (СМ.~П.~5.4.9). сАМ ФАЙЛ ЗАНИМАЕТ
ДВА ДИСКОВЫХ ПАКЕТА;
ИНВЕРТИРОВАННЫЕ СПИСКИ ЗАЙМУТ, ВЕРОЯТНО, НЕСКОЛЬКО БОЛЬШЕ МЕСТА. кАЖДАЯ
ДОРОЖКА СОДЕРЖИТ
$5000\hbox{~ЛИТЕР}=30\ 000\hbox{~БИТОВ}$, ПОЭТОМУ ИНВЕРТИРОВАННЫЙ СПИСОК
ДЛЯ НЕКОТОРОГО АТРИБУТА ЗАЙМЕТ НЕ БОЛЕЕ 34~ДОРОЖЕК. (мАКСИМАЛЬНОЕ ЧИСЛО
ДОРОЖЕК СООТВЕТСТВУЕТ СЛУЧАЮ, КОГДА ПРЕДСТАВЛЕНИЕ В ВИДЕ ЦЕПОЧЕК БИТОВ
НАИБОЛЕЕ КОРОТКОЕ.) пРЕДПОЛОЖИМ, ИМЕЕТСЯ ДОВОЛЬНО СЛОЖНЫЙ ЗАПРОС,
СОСТОЯЩИЙ ИЗ БУЛЕВОЙ КОМБИНАЦИИ 10~ИНВЕРТИРОВАННЫХ СПИСКОВ; В
ХУДШЕМ СЛУЧАЕ НАМ ПРИДЕТСЯ ПЕРЕСЕЧЬ 340~ДОРОЖЕК ИНФОРМАЦИИ ИЗ
ИНВЕРТИРОВАННОГО ФАЙЛА. пОЛНОЕ ВРЕМЯ ЧТЕНИЯ СОСТАВИТ
$340\times 25\hbox{~МС} =8.5\hbox{~С.}$
сРЕДНЕЕ ВРЕМЯ ЗАДЕРЖКИ РАВНО ПРИБЛИЗИТЕЛЬНО ПОЛОВИНЕ ЭТОГО КОЛИЧЕСТВА, НО
ЕСЛИ ИСКУСНО СОСТАВИТЬ ПРОГРАММУ, ЗАДЕРЖКУ МОЖНО ИСКЛЮЧИТЬ. еСЛИ ХРАНИТЬ
ПЕРВЫЕ ДОРОЖКИ ЦЕПОЧЕК НА ОДНОМ ЦИЛИНДРЕ, ВТОРЫЕ НА СЛЕДУЮЩЕМ И Т.~П., ТО
ВРЕМЯ ПОИСКА МОЖНО ОЦЕНИТЬ
ВЕЛИЧИНОЙ~$34\times26\hbox{~МС}\approx0.9\hbox{~С}$ (ИЛИ 1.8~С, ЕСЛИ
ЧТЕНИЕ ПРОИЗВОДИТСЯ С ДВУХ ДИСКОВ). нАКОНЕЦ, ЕСЛИ ЗАПРОСУ УДОВЛЕТВОРЯЕТ
$k$~ЗАПИСЕЙ, ТО ПОТРЕБУЕТСЯ
$k\times (60\hbox{~МС (ПОИСК)}+12.5\hbox{~МС(ЗАДЕРЖКА)}+0.2\hbox{~МС (ЧТЕНИЕ)})$
ДОПОЛНИТЕЛЬНОГО ВРЕМЕНИ, ЧТОБЫ ДОСТАТЬ ИХ ДЛЯ ПОСЛЕДУЮЩЕЙ
ОБРАБОТКИ. тАКИМ ОБРАЗОМ, ОПТИМИСТИЧЕСКАЯ ОЦЕНКА ПОЛНОГО ВРЕМЕНИ ОБРАБОТКИ
ЭТОГО ДОВОЛЬНО СЛОЖНОГО ЗАПРОСА ДАЕТ ЧИСЛО~$(10+0.073kt)\hbox{~С}$.
пОЛУЧЕННЫЙ РЕЗУЛЬТАТ МОЖНО СОПОСТАВИТЬ С 210~С, НУЖНЫМИ НА ЧТЕНИЕ
ВСЕГО ФАЙЛА С МАКСИМАЛЬНОЙ СКОРОСТЬЮ.

рАССМОТРЕННЫЙ ПРИМЕР ПОКАЗЫВАЕТ, ЧТО ДЛЯ ДИСКОВОЙ ПАМЯТИ ОПТИМИЗАЦИЯ ПО
ПРОСТРАНСТВУ ТЕСНО СВЯЗАНА С ОПТИМИЗАЦИЕЙ ПО ВРЕМЕНИ; ВРЕМЯ ОБРАБОТКИ
ИНВЕРТИРОВАННЫХ СПИСКОВ ПРИБЛИЗИТЕЛЬНО РАВНО ВРЕМЕНИ, ЗАТРАЧИВАЕМОМУ НА
ИХ ПОИСК И ЧТЕНИЕ.

дО СИХ ПОР В БОЛЬШЕЙ ИЛИ МЕНЬШЕЙ СТЕПЕНИ ПРЕДПОЛАГАЛОСЬ, ЧТО В ПРОЦЕССЕ
ОБРАБОТКИ ЗАПРОСА ФАЙЛ НЕ РАСТЕТ И НЕ СОКРАЩАЕТСЯ; НО ЧТО ДЕЛАТЬ, ЕСЛИ
НЕОБХОДИМЫ ЧАСТЫЕ ИЗМЕНЕНИЯ? вО МНОГИХ ПРИЛОЖЕНИЯХ ДОСТАТОЧНО БУФЕРИЗОВАТЬ
РЯД ТРЕБУЕМЫХ ИЗМЕНЕНИЙ И ПОЗАБОТИТЬСЯ О НИХ В СВОБОДНУЮ МИНУТУ, КОГДА
НЕ НУЖНО ОТВЕЧАТЬ НА ЗАПРОСЫ. еСЛИ ЖЕ ИЗМЕНЕНИЯ ФАЙЛА ИМЕЮТ ВЫСОКИЙ
ПРИОРИТЕТ, НАПРАШИВАЕТСЯ ИСПОЛЬЗОВАНИЕ $B\hbox{-ДЕРЕВЬЕВ}$ (П.~6.2.4). вСЕ
МНОЖЕСТВО ИНВЕРТИРОВАННЫХ СПИСКОВ МОЖНО БЫЛО БЫ ПОМЕСТИТЬ В ОДНО
ГИГАНТСКОЕ $B\hbox{-ДЕРЕВО}$, ПРИЧЕМ НЕТЕРМИНАЛЬНЫЕ УЗЛЫ ДОЛЖНЫ
СОДЕРЖАТЬ ЗНАЧЕНИЯ КЛЮЧЕЙ, А ЛИСТЬЯ---И КЛЮЧИ, И СПИСКИ УКАЗАТЕЛЕЙ НА ЗАПИСИ.

%%657
%% 657

в ПРЕДЫДУЩЕМ ОБСУЖДЕНИИ МЫ УМОЛЧАЛИ ЕЩЕ ОБ ОДНОМ ТРУДНОМ ВОПРОСЕ---О ЗАДАЧЕ
БУЛЕВЫХ КОМБИНАЦИЙ ЗАПРОСОВ ПО ОБЛАСТИ ЗНАЧЕНИЙ. пРЕДПОЛОЖИМ, НАПРИМЕР,
ЧТО ЗАПИСИ ФАЙЛА ОПИСЫВАЮТ ГОРОДА сЕВЕРНОЙ аМЕРИКИ И ЧТО ЗАПРАШИВАЮТСЯ
НАЗВАНИЯ ВСЕХ ГОРОДОВ С КООРДИНАТАМИ
$$
(21.49^\circ<|широта|\le 37.41^\circ)\mathbin{|и|} (70.34^\circ\le
|долгота| \le  75.72^\circ).
$$
сКОРЕЕ ВСЕГО, НИ ОДНА СТРУКТУРА ДАННЫХ ПО-НАСТОЯЩЕМУ НЕ ГОДИТСЯ ДЛЯ
ПОДОБНЫХ "ЗАПРОСОВ ПО ПРЯМОУГОЛЬНОЙ ОБЛАСТИ ЗНАЧЕНИЙ". (вЗГЛЯНУВ НА
КАРТУ, МЫ ВИДИМ, ЧТО МНОГИЕ ГОРОДА УДОВЛЕТВОРЯЮТ ОГРАНИЧЕНИЮ НА ШИРОТУ,
МНОГИЕ---НА ДОЛГОТУ, НО ЕДВА ЛИ НАЙДЕТСЯ ГОРОД, УДОВЛЕТВОРЯЮЩИЙ ОБОИМ
ОГРАНИЧЕНИЯМ.) пОЖАЛУЙ, НАИЛУЧШИЙ ПОДХОД СОСТОИТ В ДОВОЛЬНО
ГРУБОМ РАСЧЛЕНЕНИИ МНОЖЕСТВА ВСЕХ ВОЗМОЖНЫХ ЗНАЧЕНИЙ |широты| И |долготы|,
ЧТОБЫ НА КАЖДЫЙ АТРИБУТ ПРИХОДИЛОСЬ ЛИШЬ НЕСКОЛЬКО КЛАССОВ (НАПРИМЕР,
МОЖНО ОКРУГЛЯТЬ С НЕДОСТАТКОМ ДО ЧИСЛА, КРАТНОГО~$5^\circ$), И В
ПОСЛЕДУЮЩЕМ ПОСТРОЕНИИ ИНВЕРТИРОВАННОГО СПИСКА ДЛЯ КАЖДОГО
КОМБИНИРОВАННОГО $(|широта|, |долгота|)$~КЛАССА. эТО ВСЕ РАВНО, ЧТО ИМЕТЬ
КАРТЫ, ГДЕ ДЛЯ КАЖДОГО НЕБОЛЬШОГО РАЙОНА ОТВЕДЕНА ОТДЕЛЬНАЯ СТРАНИЦА.
пРИ ИСПОЛЬЗОВАНИИ ИНТЕРВАЛОВ В~$5^\circ$ К ЗАПРОСУ ИМЕЮТ ОТНОШЕНИЕ ВОСЕМЬ
СТРАНИЦ, А ИМЕННО $(20^\circ, 70^\circ)$, $(25^\circ, 70^\circ)$,~\dots,
$(35^\circ, 75^\circ)$. зАПРОС НЕОБХОДИМО ОБРАБОТАТЬ ДЛЯ КАЖДОЙ ИЗ НИХ,
ЛИБО ПРОИЗВОДЯ БОЛЕЕ ТОНКОЕ РАСЧЛЕНЕНИЕ ВНУТРИ СТРАНИЦЫ, ЛИБО
НЕПОСРЕДСТВЕННО ОБРАЩАЯСЬ К ЗАПИСЯМ В ЗАВИСИМОСТИ ОТ ЧИСЛА ЗАПИСЕЙ,
СООТВЕТСТВУЮЩИХ ЭТОЙ СТРАНИЦЕ. пО СУЩЕСТВУ, ПОЛУЧАЕТСЯ СТРУКТУРА ДЕРЕВА С
ДВУМЕРНЫМИ РАЗВЕТВЛЕНИЯМИ ВО ВНУТРЕННИХ УЗЛАХ.

дРУГОЙ ПОДХОД К ЗАПРОСАМ ПО ПРЯМОУГОЛЬНОЙ ОБЛАСТИ, ТАКЖЕ ОСНОВАННЫЙ НА
СТРУКТУРЕ ДЕРЕВА, ПРЕДЛОЖИЛ бРЮС мАК-нАТТ. пУСТЬ, НАПРИМЕР, НУЖНО
ОБРАБОТАТЬ ЗАПРОС ТИПА "кАКОЙ ГОРОД БЛИЖЕ ВСЕГО К ТОЧКЕ~$x$?", ЕСЛИ ДАНО
ЗНАЧЕНИЕ~$x$. кАЖДЫЙ УЗЕЛ ПРЕДЛАГАЕМОГО мАК-нАТТОМ БИНАРНОГО ДЕРЕВА ПОИСКА
СООТВЕТСТВУЕТ ГОРОДУ~$y$ И "КОНТРОЛЬНОМУ РАДИУСУ"~$r$; ЛЕВОЕ
ПОДДЕРЕВО ЭТОГО УЗЛА СООТВЕТСТВУЕТ ВСЕМ ГОРОДАМ~$z$, ПОЗДНЕЕ ВСТАВЛЕННЫМ В
ДЕРЕВО, ПРИЧЕМ РАССТОЯНИЕ ОТ~$y$ ДО~$z$ ДОЛЖНО БЫТЬ $\le r+\delta$;
АНАЛОГИЧНО ПРАВОЕ ПОДДЕРЕВО ПРЕДНАЗНАЧЕНО ДЛЯ РАССТОЯНИЙ $\ge r-\delta$.
зДЕСЬ $\delta$---ДАННЫЙ ДОПУСК; ГОРОДА, ОТСТОЯЩИЕ ОТ~$y$ МЕНЬШЕ, ЧЕМ
НА~$r+\delta$, И БОЛЬШЕ, ЧЕМ НА~$r-\delta$, ДОЛЖНЫ ВХОДИТЬ В ОБА ПОДДЕРЕВА.
 пОИСК В ТАКОМ "ПОЧТОВОМ ДЕРЕВЕ" ПОЗВОЛЯЕТ ВЫЯВИТЬ ВСЕ ГОРОДА, ОТСТОЯЩИЕ
ОТ ДАННОЙ ТОЧКИ МЕНЕЕ, ЧЕМ НА~$\delta$. (сМ.~РИС.~45.)

в 1972~Г. мАК-нАТТ И эДВАРД пРИНГ, ОСНОВЫВАЯСЬ НА ЭТОЙ ИДЕЕ, ПРОВЕЛИ
НЕСКОЛЬКО ЭКСПЕРИМЕНТОВ. в КАЧЕСТВЕ БАЗЫ ДАННЫХ ОНИ ИСПОЛЬЗОВАЛИ
231~НАИБОЛЕЕ НАСЕЛЕННЫЙ ГОРОД КОНТИНЕНТАЛЬНЫХ
%% 658
\picture{рИС 45. вЕРХНИЕ УРОВНИ "ПОЧТОВОГО ДЕРЕВА". чТОБЫ НАЙТИ ВСЕ ГОРОДА,
 РАСПОЛОЖЕННЫЕ ВБЛИЗИ ДАННОЙ ТОЧКИ~$x$, НАЧНЕМ С КОРНЯ: ЕСЛИ $x$ НЕ ДАЛЕЕ
1800 МИЛЬ ОТ лАС-вЕГАСА, ИДЕМ ВЛЕВО, В ПРОТИВНОМ СЛУЧАЕ--- ВПРАВО; ЗАТЕМ
ПОВТОРЯЕМ ЭТОМ ПРОЦЕСС, ПОКА НЕ ДОСТИГНЕМ КОНЦЕВОГО УЗЛА. мЕТОД ПОСТРОЕНИЯ
ДЕРЕВА ГАРАНТИРУЕТ, ЧТО В ПРОЦЕССЕ ПОИСКА МЫ ДОСТИГНЕМ ВСЕХ ГОРОДОВ,
ОТСТОЯЩИХ ОТ~$x$ НЕ БОЛЕЕ ЧЕМ НА 20~МИЛЬ.
}
%%659
сОЕДИНЕННЫХ шТАТОВ, ВЗЯТЫЙ В СЛУЧАЙНОМ ПОРЯДКЕ. кОНТРОЛЬНЫЙ
РАДИУС~$r$ УМЕНЬШАЛСЯ РЕГУЛЯРНЫМ ОБРАЗОМ: ПРИ ШАГЕ ВЛЕВО $r$~ЗАМЕНЯЛИ
НА~$0.67r$, А ПРИ ШАГЕ ВПРАВО---НА~$0.57r$. еСЛИ ЖЕ ВЫБИРАЛАСЬ ВТОРАЯ ИЗ
ДВУХ ПОСЛЕДОВАТЕЛЬНЫХ ПРАВЫХ ВЕТВЕЙ, РАДИУС ОСТАВАЛСЯ НЕИЗМЕННЫМ. в
РЕЗУЛЬТАТЕ ПОЛУЧИЛОСЬ, ЧТО ПРИ $\delta = 20\hbox{~МИЛЬ}$ В ДЕРЕВЕ БЫЛО
610~УЗЛОВ, А ПРИ $\delta=35\hbox{~МИЛЬ}$---1600~УЗЛОВ. нА РИС.~45 ИЗОБРАЖЕНЫ
ВЕРХНИЕ УРОВНИ МЕНЬШЕГО ДЕРЕВА. (в ОСТАВШИХСЯ УРОВНЯХ оРЛАНДО (ШТАТ
фЛОРИДА) ПОЯВЛЯЕТСЯ И НИЖЕ дЖЕКСОНВИЛА, И НИЖЕ мАЙАМИ. нЕКОТОРЫЕ ГОРОДА
ВСТРЕЧАЮТСЯ ДОВОЛЬНО ЧАСТО; ТАК, 17~УЗЛОВ ПРЕДНАЗНАЧЕНЫ ДЛЯ бРОКТОНА
(ШТАТ мАССАЧУСЕТС)!)

\section сОСТАВНЫЕ АТРИБУТЫ. мОЖНО СКОМБИНИРОВАТЬ ДВА ИЛИ БОЛЕЕ АТРИБУТОВ
В ОДИН СУПЕРАТРИБУТ. нАПРИМЕР, АТРИБУТ
"$(|курс|, |специальность|)$" В УНИВЕРСИТЕТСКОМ РЕГИСТРАЦИОННОМ ФАЙЛЕ
МОЖНО СОЗДАТЬ, КОМБИНИРУЯ ПОЛЯ |курс| И~|специальность|. пРИ ТАКОМ ПОДХОДЕ
НА ЗАПРОС ЧАСТО МОЖНО ОТВЕТИТЬ С ПОМОЩЬЮ ОБоЕДИНЕНИЯ НЕСКОЛЬКИХ КОРОТКИХ
СПИСКОВ, А НЕ С ПОМОЩЬЮ ПЕРЕСЕЧЕНИЯ БОЛЕЕ ДЛИННЫХ СПИСКОВ.

иДЕЮ КОМБИНАЦИИ АТРИБУТОВ РАЗВИЛ в.~лУМ [{\sl CACM,\/} {\bf 13} (1970),
660--665]. оН ПРЕДЛОЖИЛ УПОРЯДОЧИВАТЬ ИНВЕРТИРОВАННЫЕ СПИСКИ,
 СООТВЕТСТВУЮЩИЕ СОСТАВНЫМ АТРИБУТАМ, ЛЕКСИКОГРАФИЧЕСКИ СЛЕВА НАПРАВО И
ИЗГОТОВЛЯТЬ НЕСКОЛЬКО КОПИЙ, В КОТОРЫХ ОТДЕЛЬНЫЕ АТРИБУТЫ ПЕРЕСТАВЛЕНЫ
НАДЛЕЖАЩИМ ОБРАЗОМ. пРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО ИМЕЮТСЯ ТРИ АТРИБУТА |A|,
|B|, |C|; МОЖНО ОБРАЗОВАТЬ ТРИ КОМБИНИРОВАННЫХ АТРИБУТА
$$
(|A|, |B|, |C|),   (|B|, |C|, |A|),   (|C|, |A|, |B|)
\eqno (1)
$$
И ДЛЯ КАЖДОГО ИЗ НИХ ПОСТРОИТЬ УПОРЯДОЧЕННЫЙ ИНВЕРТИРОВАННЫЙ СПИСОК.
(тАК, В ПЕРВОМ СПИСКЕ ЗАПИСИ УПОРЯДОЧЕНЫ ПО ЗНАЧЕНИЮ ПОЛЯ~|A|; ВСЕ
ЗАПИСИ С ОДНИМ И ТЕМ ЖЕ ЗНАЧЕНИЕМ~|A| УПОРЯДОЧЕНЫ ПО~|B|, А ЗАТЕМ И
ПО~|C|.) пОДОБНАЯ ОРГАНИЗАЦИЯ ПОЗВОЛЯЕТ ОТВЕЧАТЬ НА ЗАПРОСЫ, СОСТОЯЩИЕ ИЗ
ЛЮБОЙ КОМБИНАЦИИ ЭТИХ ТРЕХ АТРИБУТОВ; НАПРИМЕР, ВСЕ ЗАПИСИ, ИМЕЮЩИЕ
ОПРЕДЕЛЕННЫЕ ЗНАЧЕНИЯ~|A| И~|C|, РАСПОЛОЖЕНЫ В ТРЕТЬЕМ СПИСКЕ ДРУГ ЗА ДРУГОМ.

аНАЛОГИЧНО ИЗ ЧЕТЫРЕХ АТРИБУТОВ |A|, |B|, |C|, |D| МОЖНО ОБРАЗОВАТЬ
ШЕСТЬ КОМБИНИРОВАННЫХ АТРИБУТОВ
$$
\matrix{
(|A|,  |B|, |C|, |D|), &  (|B|, |C|, |D|, |A|), & (|B|, |D|, |A|, |C|), \cr
(|C|, |A|, |D|, |B|), &(|C|, |D|, |A|, |B|), &(|D|, |A|, |B|, |C|),\cr
}
\eqno(2)
$$
ЧТО ПОЗВОЛЯЕТ ОТВЕЧАТЬ НА ВСЕ КОМБИНАЦИЙ ПРОСТЫХ ЗАПРОСОВ, В КОТОРЫХ
ФИКСИРОВАНЫ, ЗНАЧЕНИЯ ОДНОГО, ДВУХ, ТРЕХ ИЛИ ЧЕТЫРЕХ АТРИБУТОВ.
сУЩЕСТВУЕТ ОБЩАЯ ПРОЦЕДУРА ПОСТРОЕНИЯ $\perm{n}{k}$~КОМБИНИРОВАННЫХ
АТРИБУТОВ ИЗ $n$~АТРИБУТОВ, ГДЕ $k\le{1\over2}n$; ПРИ ЭТОМ ВСЕ ЗАПИСИ,
ИМЕЮЩИЕ ОПРЕДЕЛЕННЫЕ КОМБИНАЦИИ $\le k$ ИЛИ
%% 660
$\ge n-k$~ЗНАЧЕНИЙ АТРИБУТОВ, РАСПОЛОЖАТСЯ ПОСЛЕДОВАТЕЛЬНО В ОДНОМ ИЗ
ИНВЕРТИРОВАННЫХ СПИСКОВ (СМ.~УПР.~1). иЛИ ЖЕ МОЖНО  ОБОЙТИСЬ МЕНЬШИМ
ЧИСЛОМ КОМБИНАЦИЙ, ЕСЛИ НЕКОТОРЫЕ АТРИБУТЫ ИМЕЮТ ОГРАНИЧЕННОЕ КОЛИЧЕСТВО
ЗНАЧЕНИЙ. нАПРИМЕР, ЕСЛИ  АТРИБУТ~$|D|$ МОЖЕТ ПРИНИМАТЬ ЛИШЬ ДВА ЗНАЧЕНИЯ,
ТО ТРИ КОМБИНАЦИИ
$$
\matrix{
(|D|, |A|, |B|, |C|),& (|D|, |B|, |C|, |A|),& (|D|, |C|, |A|, |B|),\cr
}
\eqno(3)
$$
ПОЛУЧЕННЫЕ ИЗ~(1) ВНЕСЕНИЕМ~$|D|$ В СКОБКИ, БУДУТ ПОЧТИ СТОЛЬ ЖЕ ХОРОШИ,
КАК И~(2), ИБО ДЛЯ ОТВЕТОВ НА ЗАПРОСЫ, НЕ ЗАВИСЯЩИЕ ОТ~|D|, ОДИН ИЗ
СПИСКОВ ДОСТАТОЧНО ПРОСМОТРЕТЬ ВСЕГО В ДВУХ МЕСТАХ. иЗБЫТОЧНОСТЬ ЖЕ
ИНФОРМАЦИИ УМЕНЬШИЛАСЬ ВДВОЕ.

\section бИНАРНЫЕ АТРИБУТЫ. пОЛЕЗНО РАССМОТРЕТЬ ЧАСТНЫЙ СЛУЧАЙ, КОГДА ВСЕ
АТРИБУТЫ МОГУТ ПРИНИМАТЬ ЛИШЬ ДВА ЗНАЧЕНИЯ. пО СУЩЕСТВУ, МЫ ИМЕЕМ
\emph{ПОЛНУЮ ПРОТИВОПОЛОЖНОСТЬ} КОМБИНИРОВАНИЮ АТРИБУТОВ, ТАК КАК МОЖЕМ
ПРЕДСТАВИТЬ ЛЮБОЕ ЗНАЧЕНИЕ В ВИДЕ ДВОИЧНОГО ЧИСЛА И РАССМАТРИВАТЬ БИТЫ
ЭТОГО ЧИСЛА КАК ОТДЕЛЬНЫЕ АТРИБУТЫ. в ТАБЛ.~1 (СМ.~McCall, Cook Book (New
York: Random House (1963), Ch.~9) ПРИВЕДЕН ТИПИЧНЫЙ ФАЙЛ, СОДЕРЖАЩИЙ
АТРИБУТЫ "ДА-НЕТ"; В ДАННОМ СЛУЧАЕ ЗАПИСИ ОПИСЫВАЮТ ИЗБРАННЫЕ РЕЦЕПТЫ
ПЕЧЕНЬЯ, А АТРИБУТЫ ОПРЕДЕЛЯЮТ, КАКИЕ ИНГРЕДИЕНТЫ ИСПОЛЬЗУЮТСЯ. нАПРИМЕР,
ДЛЯ ПРИГОТОВЛЕНИЯ МИНДАЛЬНЫХ  ВАФЕЛЬ С РОМОМ НУЖНЫ МАСЛО, МУКА, МОЛОКО,
ОРЕХИ И САХАРНЫЙ
ПЕСОК. еСЛИ ТРАКТОВАТЬ ТАБЛ.~1 КАК МАТРИЦУ ИЗ НУЛЕЙ И ЕДИНИЦ, ТО
ТРАНСПОНИРОВАННАЯ МАТРИЦА ДАЕТ ИНВЕРТИРОВАННЫЙ ФАЙЛ В ВИДЕ ЦЕПОЧЕК БИТОВ.

в ПРАВОМ СТОЛБЦЕ ТАБЛ.~1 УКАЗАНЫ ОСОБЫЕ, РЕДКО УПОТРЕБЛЯЕМЫЕ ПРОДУКТЫ иХ
МОЖНО БЫЛО БЫ ЗАКОДИРОВАТЬ БОЛЕЕ ЭФФЕКТИВНО, НЕ ОТВОДЯ КАЖДОМУ ПО СТОЛБЦУ;
ТО ЖЕ СПРАВЕДЛИВО  И ДЛЯ СТОЛБЦА "МАИСОВЫЙ КРАХМАЛ". мОЖНО БЫЛО БЫ
ЭФФЕКТИВНЕЕ ЗАКОДИРОВАТЬ СТОЛБЕЦ "МУКА", ИБО МУКА ВХОДИТ ВО ВСЕ БЛЮДА,
 КРОМЕ МЕРЕНГИ. сЕЙЧАС, ОДНАКО, ДАВАЙТЕ ОСТАВИМ В СТОРОНЕ ЭТИ СООБРАЖЕНИЯ
И ПРОСТО ПРОИГНОРИРУЕМ СТОЛБЕЦ "ОСОБЫЕ ИНГРЕДИЕНТЫ".

оПРЕДЕЛИМ \emph{БАЗОВЫЙ ЗАПРОС} В ФАЙЛЕ С БИНАРНЫМИ АТРИБУТАМИ, КАК ЗАПРОС
НА ВСЕ ЗАПИСИ, ИМЕЮЩИЕ НУЛИ В ОПРЕДЕЛЕННЫХ СТОЛБЦАХ, ЕДИНИЦЫ---В НЕКОТОРЫХ
ДРУГИХ И ПРОИЗВОЛЬНЫЕ ЗНАЧЕНИЯ---В ОСТАВШИХСЯ СТОЛБЦАХ. иСПОЛЬЗУЯ "$*$" ДЛЯ
ОБОЗНАЧЕНИЯ ПРОИЗВОЛЬНОГО ЗНАЧЕНИЯ, ЛЮБОЙ БАЗОВЫЙ ЗАПРОС МОЖНО
ПРЕДСТАВИТЕ В ВИДЕ ПОСЛЕДОВАТЕЛЬНОСТИ НУЛЕЙ, ЕДИНИЦ И ЗВЕЗДОЧЕК.
пРЕДСТАВИМ СЕБЕ ЧЕЛОВЕКА, КОТОРОМУ ВДРУГ ОЧЕНЬ ЗАХОТЕЛОСЬ ПЕЧЕНЬЯ С
КОКОСОВЫМИ ОРЕХАМИ, ТОГДА КАК ШОКОЛАД ВЫЗЫВАЕТ У НЕГО АЛЛЕРГИЮ, АНИС ОН НЕ
ТЕРПИТ, А ВАНИЛИНА В ДОМЕ НЕТ. оН МОЖЕТ СФОРМУЛИРОВАТЬ ТАКОЙ ЗАПРОС:
$$
0 * * 0 * * * 1 * * * * * * * * * * * * * * * * * * * 0 * *
\eqno(4)
$$
%% 661
\picture{тАБЛИЦА 1 фАЙЛ С БИНАРНЫМН АТРИБУТАМИ}
%% 662
тАБЛИЦА~1 ПОКАЖЕТ, ЧТО НА САМОМ ДЕЛЕ ЕМУ ХОЧЕТСЯ ПАЛОЧЕК АРОМАТНЫХ С
ЧЕРНОСЛИВОМ.

пРЕЖДЕ ЧЕМ РАССМОТРЕТЬ ОБЩУЮ ЗАДАЧУ ОРГАНИЗАЦИИ ФАЙЛА  ДЛЯ ОБРАБОТКИ
БАЗОВЫХ ЗАПРОСОВ, ВАЖНО ИЗУЧИТЬ ЧАСТНЫЙ СЛУЧАЙ, КОГДА ЗАПРОС СОСТОИТ
ТОЛЬКО ИЗ ЕДИНИЦ И ЗВЕЗДОЧЕК. тАКОЙ
ЗАПРОС МОЖНО НАЗВАТЬ \emph{ВКЛЮЧАЮЩИМ}, ИБО ОН ЗАПРАШИВАЕТ ВСЕ;
ЗАПИСИ, ВКЛЮЧАЮЩИЕ В СЕБЯ НЕКОТОРОЕ МНОЖЕСТВО АТРИБУТОВ (ЕСТЕСТВЕННО
СЧИТАТЬ, ЧТО ЕДИНИЦА ОБОЗНАЧАЕТ ИМЕЮЩИЙСЯ АТРИБУТ, А НУЛЬ---ОТСУТСТВУЮЩИЙ).
 нАПРИМЕР, ИЗ РЕЦЕПТОВ ТАБЛ.~1
\picture{рИС. 46.  кАРТА С КРАЕВОЙ ПЕРФОРАЦИЕЙ.}
ТОЛЬКО ГЛАЗИРОВАННЫЕ ИМБИРНЫЕ ПРЯНИКИ И СТАРИННОЕ САХАРНОЕ ПЕЧЕНЬЕ
СОДЕРЖАТ И ПЕКАРНЫЙ ПОРОШОК, И ПИЩЕВУЮ СОДУ.

дЛЯ НЕКОТОРЫХ ПРИЛОЖЕНИЙ ДОСТАТОЧНО ОБЕСПЕЧИТЬ ЛИШЬ ОТВЕТЫ НА ВКЛЮЧАЮЩИЕ
ЗАПРОСЫ. эТО СПРАВЕДЛИВО, НАПРИМЕР, ДЛЯ РУЧНЫХ ФАЙЛОВЫХ СИСТЕМ "НА КАРТАХ
С КРАЕВОЙ ПЕРФОРАЦИЕЙ" ИЛИ "КАРТОТЕК ПРИЗНАКОВ". сИСТЕМА НА КАРТАХ С
КРАЕВОЙ ПЕРФОРАЦИЕЙ, СООТВЕТСТВУЮЩАЯ ТАБЛ.~1, СОДЕРЖАЛА БЫ ПО КАРТЕ НА
КАЖДЫЙ РЕЦЕПТ, ГДЕ КАЖДОМУ ИНГРЕДИЕНТУ СООТВЕТСТВУЕТ ВЫРЕЗ. (сМ.~РИС.~46.)
дЛЯ ОБРАБОТКИ ВКЛЮЧАЮЩЕГО ЗАПРОСА КАРТЫ СКЛАДЫВАЮТ В АККУРАТНУЮ СТОПКУ И
ВВОДЯТ СПИЦЫ В ПОЗИЦИИ, СООТВЕТСТВУЮЩИЕ ТРЕБУЕМЫМ АТРИБУТАМ. зАТЕМ СПИЦЫ
ПОДНИМАЮТ И КАРТЫ, ИМЕЮЩИЕ НУЖНЫЕ АТРИБУТЫ, ВЫПАДАЮТ.

"кАРТОТЕКА ПРИЗНАКОВ" АНАЛОГИЧНО РАБОТАЕТ С ИНВЕРТИРОВАННЫМ ФАЙЛОМ. в
ЭТОМ СЛУЧАЕ ИМЕЕТСЯ ПО КАРТЕ НА КАЖДЫЙ АТРИБУТ. дЛЯ КАЖДОЙ ЗАПИСИ НА
КАРТАХ ОТВОДИТСЯ ОПРЕДЕЛЕННАЯ ПОЗИЦИЯ, И ЕСЛИ ЗАПИСЬ ОБЛАДАЕТ НЕКОТОРЫМ
АТРИБУТОМ, ТО В СООТВЕТСТВУЮЩЕМ МЕСТЕ ДЕЛАЕТСЯ ПРОБИВКА. сЛЕДОВАТЕЛЬНО,
ОБЫЧНАЯ $80\hbox{-КОЛОННАЯ}$ ПЕРФОКАРТА МОЖЕТ СОДЕРЖАТЬ ИНФОРМАЦИЮ О
$12\times80=960\hbox{~ЗАПИСЯХ}$. дЛЯ ОБРАБОТКИ ВКЛЮЧАЮЩЕГО
ЗАПРОСА ОТБИРАЮТ КАРТЫ НУЖНЫХ АТРИБУТОВ, КЛАДУТ ИХ ВМЕСТЕ И ПРОСВЕЧИВАЮТ;
%%663
\htable{тАБЛИЦА 2}%
{пРИМЕР КОДИРОВАНИЯ НАЛОЖЕНИЕМ}%
{
#\bskip\hfill&\bskip$#$\bskip&#\bskip\hfill&\bskip$#$\bskip\cr
\noalign{\hbox{кОДЫ ОТДЕЛЬНЫХ СПЕЦИЙ}}
аБРИКОСЫ           & 1000010000 & лИМОННЫЙ СОК      & 1000100000\cr
аПЕЛЬСИНЫ          & 0100000100 & мЕД               & 0000000011\cr
аРАХИСОВОЕ МАСЛО   & 0000000101 & мЕЛАССА           & 1001000000\cr
бАНАНЫ             & 0000100010 & мУСКАТНЫЙ ОРЕХ    & 0000010010\cr
вАНИЛИН            & 0000001001 & мУСКАТНЫЙ "ЦВЕТ"  & 0000010100\cr
дУШИСТЫЙ ПЕРЕЦ     & 0000100001 & оРЕХИ             & 0000100100\cr
зАСАХАРЕННАЯ ВИШНЯ & 0000101000 & пЕРЕЦ             & 0010000100\cr
зЕРНА АНИСА        & 0000011000 & сМОРОДИНОВОЕ ЖЕЛЕ & 0010000001\cr
иЗЮМ               & 0101000000 & фИНИКИ            & 1000000100\cr
иМБИРЬ             & 0000110000 & цИТРОН            & 0100000010\cr
кАРДАМОН           & 1000000001 & чЕРНОСЛИВ         & 0010000010\cr
кОКОСОВЫЕ ОРЕХИ    & 0001010000 & чЕСНОК            & 0001100000\cr
кОРИЦА             & 1000000010 & шОКОЛАД           & 0010001000\cr
кОФЕ               & 0001000100 & эКСТРАКТ МИНДАЛЯ  & 0100000001\cr
лИМОННАЯ ЦЕДРА     & 0011000000 & яБЛОЧНЫЙ СОУС     & 0010010000\cr
\noalign{\hbox{нАЛОЖЕННЫЕ КОДЫ}}
бАНАНОВО-ОВСЯНОЕ ПЕЧЕНЬЕ       &\span\span 1000111111\cr
вАНИЛЬНО-ОРЕХОВОЕ МОРОЖЕНОЕ    &\span\span 0000101101\cr
вОЗДУШНОЕ ПЕЧЕНЬЕ              &\span\span 0000001001\cr
гЛАЗИРОВАННЫЕ ИМБИРНЫЕ ПРЯНИКИ &\span\span 1001110010\cr
дРАГОЦЕННОЕ ПЕЧЕНЬЕ            &\span\span 0010101101\cr
дРАЖЕ В ШОКОЛАДЕ               &\span\span 0010101100\cr
иРИСКИ                         &\span\span 0010111101\cr
мАЛАЙСКИЙ КРЕНДЕЛЬ             &\span\span 1011100101\cr
мЕДОВЫЕ ПРЯНИКИ                &\span\span 1011110111\cr
мЕРЕНГИ                        &\span\span 1000101100\cr
мИНДАЛЬНОЕ ПЕЧЕНЬЕ С КОКОСАМИ  &\span\span 0001111101\cr
мИНДАЛЬНЫЕ ВАФЛИ С РОМОМ       &\span\span 0000100100\cr
мОРАВСКОЕ ПЕЧЕНЬЕ СО СПЕЦИЯМИ  &\span\span 1001110011\cr
оВСЯНЫЕ ПАЛОЧКИ С ФИНИКАМИ     &\span\span 1000100100\cr
пАЛОЧКИ АРОМАТНЫЕ С ЧЕРНОСЛИВОМ&\span\span 0111110110\cr
пЕЧЕНЬЕ С АРАХИСОВЫМ МАСЛОМ    &\span\span 0010001101\cr
пЕЧЕНЬЕ С ОРЕХАМИ              &\span\span 1101010110\cr
пЕЧЕНЬЕ С ПЕРЦЕМ               &\span\span 1111111111\cr
пЕЧЕНЬЕ С ЯБЛОЧНЫМ СОУСОМ      &\span\span 1111111111\cr
пЕЧЕНЬЕ СО СЛИВОЧНЫМ СЫРОМ     &\span\span 0010001001\cr
пОЛУКРУГЛЫЙ ПИРОГ С НАЧИНКОЙ   &\span\span 1011101101\cr
пУТАНИЦА                       &\span\span 1000001011\cr
рАЙСКИЕ ПАЛОЧКИ                &\span\span 0001111101\cr
рОЖДЕСТВЕНСКОЕ АНИСОВОЕ ПЕЧЕНЬЕ&\span\span 0011011000\cr
сТАРИННОЕ САХАРНОЕ ПЕЧЕНЬЕ     &\span\span 0000011011\cr
фИГУРНЫЕ ПЕСОЧНЫЕ КОРЖИКИ      &\span\span 0000000000\cr
фИНСКИЙ КАКОР                  &\span\span 0100100101\cr
%% 664
шВЕДСКИЙ КРЕНДЕЛЬ                       &\span\span 0000000000\cr
шВЕЙЦАРСКОЕ РАССЫПНОЕ ПЕЧЕНЬЕ С КОРИЦЕЙ &\span\span 1000000010\cr
шОКОЛАДНЫЙ ХВОРОСТ                      &\span\span 0010101101\cr
шОТЛАНДСКИЕ ОВСЯНЫЕ КОРЖИКИ             &\span\span 0000001001\cr
юБОЧКИ                                  &\span\span 0000001001\cr
}%
ЛУЧИ СВЕТА ПРОЙДУТ ЧЕРЕЗ ВСЕ ПОЗИЦИИ, СООТВЕТСТВУЮЩИЕ ИСКОМЫМ
ЗАПИСЯМ эТА ОПЕРАЦИЯ АНАЛОГИЧНА ОБРАБОТКЕ БУЛЕВЫХ ЗАПРОСОВ ПУТЕМ
ПЕРЕСЕЧЕНИЯ ИНВЕРТИРОВАННЫХ ЦЕПОЧЕК БИТОВ.

\section кОДИРОВАНИЕ НАЛОЖЕНИЕМ. пРИЧИНА НАШЕГО ОСОБОГО ИНТЕРЕСА К РУЧНЫМ
КАРТОТЕКАМ КРОЕТСЯ В ТОМ, ЧТО БЫЛО ПРИДУМАНО МНОГО ОСТРОУМНЫХ СПОСОБОВ
ЭКОНОМИИ МЕСТА НА КАРТАХ С КРАЕВОЙ ПЕРФОРАЦИЕЙ; ТОТ ЖЕ ПОДХОД ПРИМЕНИМ К
ПРЕДСТАВЛЕНИЮ ФАЙЛОВ В ПАМЯТИ эвм. кОДИРОВАНИЕ НАЛОЖЕНИЕМ НАПОМИНАЕТ
ХЕШИРОВАНИЕ; В ДЕЙСТВИТЕЛЬНОСТИ ЕГО ИЗОБРЕЛИ ЗА НЕСКОЛЬКО ЛЕТ
ДО ОТКРЫТИЯ ХЕШИРОВАНИЯ. иДЕЯ СОСТОИТ В ТОМ, ЧТОБЫ ОТОБРАЗИТЬ АТРИБУТЫ В
СЛУЧАЙНЫЕ $k\hbox{-БИТОВЫЕ}$ КОДЫ В $n\hbox{-БИТОВЫХ}$ ПОЛЯХ И НАЛОЖИТЬ
КОДЫ ИМЕЮЩИХСЯ В ЗАПИСИ АТРИБУТОВ. вКЛЮЧАЮЩИЙ ЗАПРОС О НЕКОТОРОМ МНОЖЕСТВЕ
АТРИБУТОВ МОЖНО ПРЕОБРАЗОВАТЬ ВО ВКЛЮЧАЮЩИЙ ЗАПРОС О СООТВЕТСТВУЮЩИХ
НАЛОЖЕННЫХ ДВОИЧНЫХ КОДАХ. эТОМУ ЗАПРОСУ МОГУТ УДОВЛЕТВОРЯТЬ НЕСКОЛЬКО
ЛИШНИХ ЗАПИСЕЙ, НО КОЛИЧЕСТВО ТАКИХ "ЛОЖНЫХ ВЫПАДЕНИЙ"
МОЖНО СТАТИСТИЧЕСКИ УЧЕСТЬ. [сР. С Calvin N.~Mooers,
{\sl Amer.~Chem.~Soc.~Meeting\/}, {\bf 112} (September, 1947), 14E--15E;
{\sl American Documentation,\/} {\bf 2} (1951), 20--32.]
в КАЧЕСТВЕ ПРИМЕРА КОДИРОВАНИЯ НАЛОЖЕНИЕМ ВНОВЬ РАССМОТРИМ ТАБЛ.~1, НО
НЕ ВСЮ, А ТОЛЬКО ЧАСТЬ, КАСАЮЩУЮСЯ СПЕЦИЙ. в ТАБЛ.~2 ПОКАЗАНО, ЧТО
ПОЛУЧИТСЯ, ЕСЛИ ПРИСВОИТЬ АТРИБУТАМ СПЕЦИЙ СЛУЧАЙНЫЕ ДВУХБИТОВЫЕ КОДЫ В
ДЕСЯТИБИТОВОМ ПОЛЕ И НАЛОЖИТЬ ИХ. нАПРИМЕР, ЭЛЕМЕНТ "ШОКОЛАДНЫЙ
ХВОРОСТ" ПОЛУЧАЕТСЯ НАЛОЖЕНИЕМ КОДОВ ДЛЯ ШОКОЛАДА, ОРЕХОВ И ВАНИЛИНА:
$$
0010001000 \vee 0000100100 \vee 0000001001 = 0010101101.
$$
нАЛОЖЕНИЕ КОДОВ ПРИВНОСИТ ТАКЖЕ НЕСКОЛЬКО ЛИШНИХ АТРИБУТОВ, В ДАННОМ
СЛУЧАЕ ЭТО ДУШИСТЫЙ ПЕРЕЦ, ЗАСАХАРЕННАЯ ВИШНЯ, СМОРОДИНОВОЕ ЖЕЛЕ,
КОКОСОВОЕ МАСЛО И ПЕРЕЦ, ЧТО ПРИВЕДЕТ К "ЛОЖНЫМ ВЫПАДЕНИЯМ" ПРИ ОТВЕТАХ НА
НЕКОТОРЫЕ ЗАПРОСЫ (КРОМЕ ТОГО, У НАС ПОЯВИЛСЯ НОВЫЙ РЕЦЕПТ---ЛОЖНОГО ПЕЧЕНЬЯ!)
нА САМОМ ДЕЛЕ КОДИРОВАНИЕ НАЛОЖЕНИЕМ НЕ ОЧЕНЬ ХОРОШО РАБОТАЕТ ДЛЯ ТАБЛ.~2,
ЯВЛЯЮЩЕЙСЯ МАЛЕНЬКИМ ПРИМЕРОМ СО МНО-
%%665
ГИМИ АТРИБУТАМИ. дЕЙСТВИТЕЛЬНО, ПЕЧЕНЬЕ С ЯБЛОЧНЫМ СОУСОМ БУДЕТ ВЫПАДАТЬ
ПРИ \emph{КАЖДОМ} ЗАПРОСЕ, ИБО ЭТА ЗАПИСЬ ПОЛУЧЕНА НАЛОЖЕНИЕМ СЕМИ КОДОВ,
ПОКРЫВАЮЩИХ ВСЕ ДЕСЯТЬ ПОЗИЦИЙ; ЕЩЕ ХУЖЕ ОБСТОИТ ДЕЛО С ПЕЧЕНЬЕМ С ПЕРЦЕМ,
ПОЛУЧЕННЫМ НАЛОЖЕНИЕМ" ДВЕНАДЦАТИ КОДОВ! с ДРУГОЙ СТОРОНЫ, В НЕКОТОРЫХ
СЛУЧАЯХ ТАБЛ.~2 РАБОТАЕТ УДИВИТЕЛЬНО ХОРОШО; НАПРИМЕР, В ОТВЕТ НА ЗАПРОС
О ВАНИЛИНЕ ЗРЯ ВЫПАДЕТ ЛИШЬ ПЕЧЕНЬЕ С ПЕРЦЕМ.

бОЛЕЕ ПОДХОДЯЩИМ ЯВЛЯЕТСЯ ПРИМЕР, КОГДА У НАС ЕСТЬ, СКАЖЕМ, 32-БИТОВОЕ
ПОЛЕ И МНОЖЕСТВО ИЗ $\perm{32}{3}=4960$ РАЗЛИЧНЫХ АТРИБУТОВ. кАЖДАЯ ЗАПИСЬ
МОЖЕТ ИМЕТЬ ДО ШЕСТИ АТРИБУТОВ, И КАЖДЫЙ АТРИБУТ КОДИРУЕТСЯ СПЕЦИФИКАЦИЕЙ
3-Х ИЗ 32-Х БИТОВ. еСЛИ МЫ ПРЕДПОЛОЖИМ, ЧТО КАЖДАЯ ЗАПИСЬ ИМЕЕТ ШЕСТЬ
СЛУЧАЙНО ВЫБРАННЫХ АТРИБУТОВ, ТО ВЕРОЯТНОСТИ ЛОЖНОГО ВЫПАДЕНИЯ ПРИ
ВКЛЮЧАЮЩЕМ ЗАПРОСЕ ТАКОВЫ:
$$
\matrix{
\hbox{ПО ОДНОМУ АТРИБУТУ:}\hfill   & 0.07948358; \cr
\hbox{ПО ДВУМ АТРИБУТАМ:} \hfill   & 0.00708659;\cr
\hbox{ПО ТРЕМ АТРИБУТАМ:} \hfill   & 0.00067094;\cr
\hbox{ПО ЧЕТЫРЕМ АТРИБУТАМ:}\hfill & 0.00006786;\cr
\hbox{ПО ПЯТИ АТРИБУТАМ:} \hfill   & 0.00000728;\cr
\hbox{ПО ШЕСТИ АТРИБУТАМ:}\hfill   & 0.00000082.\cr
}
\eqno(5)
$$
тАКИМ ОБРАЗОМ, ЕСЛИ ЕСТЬ $M$~ЗАПИСЕЙ, НЕ УДОВЛЕТВОРЯЮЩИХ ЗАПРОСУ ПО ДВУМ
АТРИБУТАМ, ТО ПРИБЛИЗИТЕЛЬНО $0.007M$ ИМЕЮТ НАЛОЖЕННЫЕ КОДЫ, ПОКРЫВАЮЩИЕ
ВСЕ БИТЫ ЭТИХ ДВУХ АТРИБУТОВ. (вЕРОЯТНОСТИ ПОДСЧИТАНЫ В УПР.~4.) дЛЯ
ПРЕДСТАВЛЕНИЯ ИНВЕРТИРОВАННОГО ФАЙЛА ПОТРЕБУЕТСЯ $32\times
\hbox{(КОЛИЧЕСТВО ЗАПИСЕЙ)}$~БИТОВ, ЧТО СОСТАВЛЯЕТ МЕНЕЕ ПОЛОВИНЫ ОТ ЧИСЛА
БИТОВ, НЕОБХОДИМЫХ ДЛЯ ОПИСАНИЯ СОБСТВЕННО АТРИБУТОВ В ИСХОДНОМ ФАЙЛЕ.

мАЛЬКОЛЬМ~ч.~хАРРИСОН [{\sl CACM,\/} {\bf 14} (1971), 777--779] ЗАМЕТИЛ,
ЧТО КОДИРОВАНИЕ НАЛОЖЕНИЕМ МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ УСКОРЕНИЯ ПОИСКА ТЕКСТА.
пРЕДПОЛОЖИМ, ЧТО НАМ НУЖНО ОПРЕДЕЛИТЬ ВСЕ ВХОЖДЕНИЯ НЕКОТОРОЙ ЦЕПОЧКИ
ЛИТЕР В БОЛЬШОЙ ТЕКСТ БЕЗ ПОСТРОЕНИЯ ГРОМОЗДКОГО ДЕРЕВА пАТРИЦИИ.
пРЕДПОЛОЖИМ, КРОМЕ ТОГО, ЧТО ТЕКСТ ПОДЕЛЕН НА СТРОКИ $c_1$ $c_2$~\dots
$c_{50}$  ПО 50~ЛИТЕР В КАЖДОЙ. хАРРИСОН ПРЕДЛАГАЕТ КОДИРОВАТЬ КАЖДУЮ ИЗ
49~ПАР $c_1$~$c_2$, $c_2$~$c_3$,~\dots, $c_{49}~c_{50}$ ПУТЕМ ОТОБРАЖЕНИЯ
ЕЕ В ЧИСЛО ОТ~0 ДО, СКАЖЕМ,~127. зАТЕМ ПОДСЧИТАТЬ "СИГНАТУРУ" СТРОКИ $c_1$
$c_2$~\dots $c_{50}$---ЦЕПОЧКУ ИЗ 128 БИТОВ $b_0$ $b_1$~\dots $b_{127}$, ГДЕ
$b_i=1$ ТОГДА И ТОЛЬКО ТОГДА, КОГДА $h(c_j, c_{j+1})=i$ ПРИ НЕКОТОРОМ~$j$.


еСЛИ НАМ НУЖНО НАЙТИ ВСЕ ВХОЖДЕНИЯ СЛОВА |иголка| В БОЛЬШОЙ ТЕКСТОВОЙ ФАЙЛ
|стогсена|, МЫ ПРОСТО ОТЫСКИВАЕМ ВСЕ СТРОКИ, СИГНАТУРЫ КОТОРЫХ СОДЕРЖАТ~1
В ПОЗИЦИЯХ $h(|иг|)$, $h(|го|)$, $h(|ол|)$, $h(|лк|)$, $h(|KA|)$. пРИ
СЛУЧАЙНОЙ ХЕШ-ФУНКЦИИ ВЕРОЯТНОСТЬ ТОГО, ЧТО НЕКОТОРАЯ СЛУЧАЙНАЯ СТРОКА
СОДЕРЖИТ В
%%666
СИГНАТУРЕ ВСЕ ЭТИ ЕДИНИЦЫ, РАВНА ВСЕГО ЛИШЬ 0.00341 (СР.~С~УПР.~4);
СЛЕДОВАТЕЛЬНО, ПЕРЕСЕЧЕНИЕ ПЯТИ ИНВЕРТИРОВАННЫХ СПИСКОВ ЦЕПОЧЕК БИТОВ
ПОЗВОЛИТ БЫСТРО НАЙТИ ВСЕ СТРОКИ, СОДЕРЖАЩИЕ СЛОВО |иголка| (ХОТЯ,
ВЕРОЯТНО, БУДЕТ И НЕСКОЛЬКО ЛОЖНЫХ ВЫПАДЕНИЙ).

в ДАННОМ ПРИЛОЖЕНИИ ГИПОТЕЗА О СЛУЧАЙНОСТИ НА САМОМ ДЕЛЕ НЕСПРАВЕДЛИВА,
ПОСКОЛЬКУ ОБЫЧНЫЕ ТЕКСТЫ НЕСУТ В СЕБЕ БОЛЬШОЕ КОЛИЧЕСТВО ИЗБЫТОЧНОЙ
ИНФОРМАЦИИ; РАСПРЕДЕЛЕНИЕ ДВУХБУКВЕННЫХ КОМБИНАЦИЙ В СЛОВАХ ВЕСЬМА
НЕРАВНОМЕРНО. нАПРИМЕР, ПОЛЕЗНО ОТБРОСИТЬ ВСЕ ПАРЫ~$c_j$~$c_{j+1}$,
СОДЕРЖАЩИЕ ЛИТЕРУ "ПРОБЕЛ", ТАК КАК ОБЫЧНО ПРОБЕЛЫ ВСТРЕЧАЮТСЯ ГОРАЗДО
ЧАЩЕ ДРУГИХ ЛИТЕР.

дРУГОЕ ИНТЕРЕСНОЕ ПРИМЕНЕНИЕ КОДИРОВАНИЯ НАЛОЖЕНИЕМ К ЗАДАЧАМ ПОИСКА НАШЕЛ
бАРТОН бЛУМ [{\sl CACM,\/} {\bf 13} (1970), 422--426]; НА САМОМ ДЕЛЕ ЕГО
МЕТОД ПРЕДНАЗНАЧЕН ДЛЯ ВЫБОРКИ ПО \emph{ПЕРВИЧНЫМ} КЛЮЧАМ, НО НАМ УДОБНО
ОБСУДИТЬ ЕГО В ЭТОМ ПАРАГРАФЕ. пРЕДСТАВИМ СЕБЕ, ЧТО ПРОИЗВОДИТСЯ ПОИСК В
БОЛЬШОЙ СОВОКУПНОСТИ ДАННЫХ, ПРИЧЕМ, ЕСЛИ ОН ОКАЗАЛСЯ НЕУДАЧНЫМ, НИКАКИХ
ДЕЙСТВИЙ ВЫПОЛНЯТЬ НЕ НУЖНО. нАПРИМЕР, МЫ ХОТИМ ПРОВЕРИТЬ ЧЕЙ-ЛИБО НОМЕР
ПАСПОРТА ИЛИ СУММУ ВЫПЛАЧЕННЫХ НАЛОГОВ И Т.~П.; И ЕСЛИ В ФАЙЛЕ НЕТ
СООТВЕТСТВУЮЩЕЙ ЭТОМУ ЛИЦУ ЗАПИСИ, ТО ДАЛЬНЕЙШЕГО ИССЛЕДОВАНИЯ НЕ
ТРЕБУЕТСЯ. аНАЛОГИЧНО ПРИ ПРИМЕНЕНИИ эвм ДЛЯ ТИПОГРАФСКОГО НАБОРА ТЕКСТОВ
МОЖНО ПРИДУМАТЬ ПРОСТОЙ АЛГОРИТМ, КОТОРЫЙ ПОЗВОЛИТ ПРАВИЛЬНО ДЕЛАТЬ
ПЕРЕНОСЫ ДЛЯ БОЛЬШИНСТВА СЛОВ, НО БУДЕТ НЕПРИМЕНИМ К
50000~СЛОВАМ-ИСКЛЮЧЕНИЯМ. еСЛИ КАКОЕ-ЛИБО СЛОВО НЕ УДАСТСЯ НАЙТИ В ФАЙЛЕ
ИСКЛЮЧЕНИЙ, МОЖНО ИСПОЛЬЗОВАТЬ ЭТОТ ПРОСТОЙ АЛГОРИТМ.

в ПОДОБНОЙ СИТУАЦИИ МОЖНО ХРАНИТЬ ВО ВНУТРЕННЕЙ ПАМЯТИ ТАБЛИЦУ БИТОВ, ТАК
ЧТО В БОЛЬШИНСТВЕ СЛУЧАЕВ ОТСУТСТВИЕ КЛЮЧА БУДЕТ ОПОЗНАЛО БЕЗ ОБРАЩЕНИЙ
К ВНЕШНЕЙ ПАМЯТИ. вОТ КАК ЭТО ДЕЛАЕТСЯ. оБОЗНАЧИМ ВНУТРЕННЮЮ ТАБЛИЦУ БИТОВ
ЧЕРЕЗ $b_0$~$b_1$~\dots~$b_{M-1}$, ГДЕ $M$ ВЕСЬМА ВЕЛИКО. дЛЯ КАЖДОГО
КЛЮЧА~$K_j$ ФАЙЛА ВЫЧИСЛИМ $k$ НЕЗАВИСИМЫХ ХЕШ-ФУНКЦИЙ $h_1(K_j)$,~\dots,
$h_k(K_j)$ И УСТАНОВИМ СООТВЕТСТВУЮЩИЕ $k$~БИТОВ РАВНЫМИ~1. (эТИ
$k$~ЗНАЧЕНИЙ НЕ ОБЯЗАНЫ БЫТЬ РАЗЛИЧНЫМИ.) тАКИМ ОБРАЗОМ, $b_i=1$ ТОГДА И
ТОЛЬКО ТОГДА, КОГДА $h_l(K_j)=i$ ПРИ НЕКОТОРЫХ~$j$ И~$l$. тЕПЕРЬ ДЛЯ ТОГО,
ЧТОБЫ ОПРЕДЕЛИТЬ, СОДЕРЖИТСЯ ЛИ АРГУМЕНТ ПОИСКА~$K$ ВО ВНЕШНЕМ ФАЙЛЕ,
НУЖНО СНАЧАЛА ПРОВЕРИТЬ, ВЫПОЛНЯЕТСЯ ЛИ СООТНОШЕНИЕ $b_{h_l(K)}=1$ ПРИ
$1\le l\le k$: ЕСЛИ НЕТ, ТО НЕЗАЧЕМ ОБРАЩАТЬСЯ К ВНЕШНЕЙ ПАМЯТИ, ЕСЛИ ЖЕ
ДА, ТО ПРИ ПОДХОДЯЩЕМ ВЫБОРЕ~$K$ И~$M$ ОБЫЧНЫМИ МЕТОДАМИ ПОИСКА НАМ
СКОРЕЕ ВСЕГО УДАСТСЯ НАЙТИ~$K$. вЕРОЯТНОСТЬ ЛОЖНОГО ВЫПАДЕНИЯ ДЛЯ ФАЙЛА ИЗ
$N$~ЗАПИСЕЙ ПРИБЛИЖЕННО РАВНА~$(1-e^{-kN/M})^k$. пО СУЩЕСТВУ, В
МЕТОДЕ бЛУМА ВЕСЬ ФАЙЛ РАССМАТРИВАЕТСЯ КАК ОДНА ЗАПИСЬ, ПЕРВИЧНЫЕ
%%667
КЛЮЧИ ТРАКТУЮТСЯ КАК ИМЕЮЩИЕСЯ АТРИБУТЫ, А КОДИРОВАНИЕ НАЛОЖЕНИЕМ
ПРОИЗВОДИТСЯ В ОГРОМНОМ $M\hbox{-БИТОВОМ}$ ПОЛЕ.

еЩЕ ОДИН ВАРИАНТ КОДИРОВАНИЯ НАЛОЖЕНИЕМ В СВОЕЙ ДОКТОРСКОЙ ДИССЕРТАЦИИ
РАЗРАБОТАЛ рИЧАРД гУСТАФСОН (Univ. South Carolina, 1969). пРЕДПОЛОЖИМ,
ИМЕЕТСЯ $N$~ЗАПИСЕЙ И КАЖДАЯ ИЗ НИХ СОДЕРЖИТ~6 ИЗ 10000~ВОЗМОЖНЫХ
АТРИБУТОВ. нАПРИМЕР, ЗАПИСИ МОГЛИ БЫ ОПИСЫВАТЬ ТЕХНИЧЕСКИЕ СТАТЬИ, А
АТРИБУТЫ---ИМЕЮЩИЕСЯ В НИХ КЛЮЧЕВЫЕ СЛОВА. пУСТЬ $h$---ХЕШ-ФУНКЦИЯ,
ОТОБРАЖАЮЩАЯ КАЖДЫЙ АТРИБУТ В ЧИСЛО МЕЖДУ~0 И~15. еСЛИ ЗАПИСЬ
ОБЛАДАЕТ АТРИБУТАМИ $a_1$, $a_2$,~\dots, $a_6$, ТО ПО МЕТОДУ гУСТАФСОНА
ОНА ОТОБРАЖАЕТСЯ В 16-БИТОВОЕ ЧИСЛО $b_0$~$b_1$\dots$b_{15}$, ГДЕ $b_i=1$
ТОГДА И ТОЛЬКО ТОГДА, КОГДА $h(a_j)=i$ ПРИ НЕКОТОРОМ~$j$; ДАЛЕЕ, ЕСЛИ ЛИШЬ
$k$~БИТОВ СТАЛИ ЕДИНИЧНЫМИ, $k<6$, ТО ДРУГИЕ $6-k$~ЕДИНИЦ ДОБАВЛЯЮТСЯ
НЕКИМ СЛУЧАЙНЫМ ОБРАЗОМ (НЕ ОБЯЗАТЕЛЬНО ЗАВИСЯЩИМ ОТ
САМИХ ЗАПИСЕЙ). иМЕЕТСЯ $\perm{16}{9}=8008$ 16-БИТОВЫХ КОДОВ, СОДЕРЖАЩИХ
РОВНО ШЕСТЬ ЕДИНИЦ; ПРИ ИЗВЕСТНОЙ ДОЛЕ ВЕЗЕНИЯ ПРИБЛИЗИТЕЛЬНО
$N/8008$~ЗАПИСЕЙ ОТОБРАЗЯТСЯ В КАЖДОЕ ЗНАЧЕНИЕ. мОЖНО ХРАНИТЬ
8008~СПИСКОВ ЗАПИСЕЙ, С ПОМОЩЬЮ ПОДХОДЯЩЕЙ ФУНКЦИИ ВЫЧИСЛЯЯ АДРЕС,
СООТВЕТСТВУЮЩИЙ КОДУ $b_0$~$b_1$\dots$b_{15}$. в САМОМ ДЕЛЕ, ЕСЛИ ЕДИНИЦЫ
РАСПОЛОЖЕНЫ В ПОЗИЦИЯХ $0\le p_1<p_2<\ldots<p_6$, ФУНКЦИЯ
$$
\perm{p_1}{1}+\perm{p_2}{2}+\cdots+\perm{p_6}{6}
$$
ПРЕОБРАЗУЕТ КАЖДУЮ ЦЕПОЧКУ $b_0$~$b_1$\dots$b_{15}$ В ЧИСЛО МЕЖДУ~0 И~8007,
ПРИЧЕМ РАЗНЫЕ ЦЕПОЧКИ ПОРОЖДАЮТ РАЗНЫЕ АДРЕСА. (сМ.~УПР.~1.2.6-56 И~2.2.6-7.)

еСЛИ ТЕПЕРЬ МЫ ХОТИМ НАЙТИ ВСЕ ЗАПИСИ, ИМЕЮЩИЕ ТРИ ОПРЕДЕЛЕННЫХ АТРИБУТА
$A_1$, $A_2$, $A_3$, ТО СЛЕДУЕТ ВЫЧИСЛИТЬ $h(A_1)$, $h(A_2)$ И~$h(A_3)$;
ЕСЛИ ЭТИ ЗНАЧЕНИЯ РАЗЛИЧНЫ, НАМ ПРИДЕТСЯ ПРОСМОТРЕТЬ ЗАПИСИ, ХРАНЯЩИЕСЯ В
$\perm{13}{3}=286$~СПИСКАХ, КОДЫ КОТОРЫХ $b_0$~$b_1$\dots$b_{15}$ СОДЕРЖАТ
ЕДИНИЦЫ В ПОЗИЦИЯХ $h(A_1)$, $h(A_2)$ И~$h(A_3)$. иНЫМИ СЛОВАМИ,
ИССЛЕДОВАНИЮ ПОДВЕРГНУТСЯ ЛИШЬ $286\times100/8008\approx 3.5$\%~ЗАПИСЕЙ.

\section кОМБИНАТОРНОЕ ХЕШИРОВАНИЕ. оСНОВНАЯ ИДЕЯ ТОЛЬКО ЧТО ОПИСАННОГО
МЕТОДА гУСТАФСОНА СОСТОИТ В ТОМ, ЧТОБЫ НАЙТИ ТАКОЙ СПОСОБ ОТОБРАЖЕНИЯ
ЗАПИСЕЙ В АДРЕСА ПАМЯТИ, ЧТОБЫ ЛИШЬ НЕБОЛЬШОЕ КОЛИЧЕСТВО АДРЕСОВ БЫЛО
СВЯЗАНО С ОПРЕДЕЛЕННЫМ ЗАПРОСОМ. оДНАКО ЭТОТ МЕТОД ПРИМЕНИМ ЛИШЬ К
ВКЛЮЧАЮЩИМ ЗАПРОСАМ, КОГДА ОТДЕЛЬНЫЕ ЗАПИСИ ОБЛАДАЮТ МАЛЫМ ЧИСЛОМ
АТРИБУТОВ. дРУГОЙ ТИП ОТОБРАЖЕНИЙ, ПРЕДНАЗНАЧЕННЫХ ДЛЯ ОБРАБОТКИ
ПРОИЗВОЛЬНЫХ БАЗОВЫХ ЗАПРОСОВ ТИПА~(4), СОСТОЯЩИХ ИЗ НУЛЕЙ, ЕДИНИЦ И
ЗВЕЗДОЧЕК, ОТКРЫЛ В 1971~Г. рОНАЛЬД рАЙВЕСТ.

пРЕДПОЛОЖИМ СНАЧАЛА, ЧТО ИМЕЕТСЯ 1000000~ЗАПИСЕЙ И КАЖДАЯ ИЗ НИХ
СОДЕРЖИТ 10 ВТОРИЧНЫХ КЛЮЧЕЙ, ПРИЧЕМ КАЖДЫЙ ВТОРИЧНЫЙ
%%668
КЛЮЧ МОЖЕТ ПРИНИМАТЬ ДОВОЛЬНО МНОГО РАЗЛИЧНЫХ ЗНАЧЕНИЙ. зАПИСЬ СО
ВТОРИЧНЫМИ КЛЮЧАМИ ($K_1$, $K_2$,~\dots, $K_{10}$) МОЖНО ОТОБРАЗИТЬ В
20-БИТОВОЕ ЧИСЛО
$$
h(K_1) h(K_2) \ldots h(K_{10}),
\eqno(6)
$$
ГДЕ $h$---ХЕШ-ФУНКЦИЯ, ПРЕОБРАЗУЮЩАЯ ВТОРИЧНЫЙ КЛЮЧ В 2-БИТОВОЕ ЧИСЛО, А
(6) ОБРАЗОВАНО ПОСЛЕДОВАТЕЛЬНЫМ ВЫПИСЫВАНИЕМ ЭТИХ ДЕСЯТИ ПАР БИТОВ. пРИ
ТАКОЙ СХЕМЕ 1000000~ЗАПИСЕЙ ОТОБРАЖАЮТСЯ В МНОЖЕСТВО ИЗ
$2^{20}=1048576$~ЗНАЧЕНИЙ; ВСЕ ОТОБРАЖЕНИЕ МОЖНО РАССМАТРИВАТЬ КАК
ХЕШ-ФУНКЦИЮ С~$M=2^{20}$. дЛЯ РАЗРЕШЕНИЯ КОЛЛИЗИЙ ВОСПОЛЬЗУЕМСЯ МЕТОДОМ
ЦЕПОЧЕК. еСЛИ МЫ ХОТИМ ВЫБРАТЬ ВСЕ ЗАПИСИ, ИМЕЮЩИЕ ОПРЕДЕЛЕННЫЕ
ЗНАЧЕНИЯ ПЯТИ ВТОРИЧНЫХ КЛЮЧЕЙ, НАМ ПРИДЕТСЯ ПРОСМОТРЕТЬ ЛИШЬ
$2^{10}$~СПИСКОВ [СООТВЕТСТВУЮЩИХ ПЯТИ НЕСПЕЦИФИЦИРОВАННЫМ ПАРАМ В (6)],
Т.~Е.~В СРЕДНЕМ НУЖНО ПРОВЕРИТЬ ОКОЛО $1000=\sqrt{N}$~ЗАПИСЕЙ.
[аНАЛОГИЧНЫЙ ПОДХОД ПРЕДЛОЖИЛ аРИСАВА, {\sl J.~Inf.~Proc.~Soc.~Japan,\/}
{\bf 12} (1971), 163--167.]

рАЙВЕСТ РАЗВИЛ ЭТУ ИДЕЮ ДАЛЬШЕ, ТАК ЧТО ВО МНОГИХ СЛУЧАЯХ МЫ ИМЕЕМ
СЛЕДУЮЩУЮ СИТУАЦИЮ. пРЕДПОЛОЖИМ, СУЩЕСТВУЕТ $N\approx2^n$~ЗАПИСЕЙ И КАЖДАЯ
ИЗ НИХ СОДЕРЖИТ $m$~ВТОРИЧНЫХ КЛЮЧЕЙ. зАПИСИ ОТОБРАЖАЮТСЯ В
$n\hbox{-БИТОВЫЕ}$ ХЕШ-АДРЕСА ТАКИМ ОБРАЗОМ, ЧТО ЗАПРОС, НЕ
СПЕЦИФИЦИРУЮЩИЙ ЗНАЧЕНИЯ $k$~КЛЮЧЕЙ, ЗАТРАГИВАЕТ ПРИМЕРНО
$N^{k/m}$~АДРЕСОВ. вСЕ ОСТАЛЬНЫЕ ОБСУЖДАВШИЕСЯ В ЭТОМ ПАРАГРАФЕ МЕТОДЫ
(КРОМЕ МЕТОДА гУСТАФСОНА) ТРЕБУЮТ ДЛЯ ВЫБОРКИ ИНФОРМАЦИИ ПОРЯДКА $N$~ШАГОВ
(ПРАВДА, КОЭФФИЦИЕНТ ПРОПОРЦИОНАЛЬНОСТИ НЕВЕЛИК); ПРИ ДОСТАТОЧНО
БОЛЬШОМ~$N$ МЕТОД рАЙВЕСТА ОКАЖЕТСЯ БОЛЕЕ БЫСТРЫМ, К ТОМУ ЖЕ ОН НЕ
ТРЕБУЕТ ИНВЕРТИРОВАНИЯ ФАЙЛОВ.

нО, ПРЕЖДЕ ЧЕМ ПРИМЕНИТЬ ТАКОЙ ПОДХОД, НУЖНО ОПРЕДЕЛИТЬ ПОДХОДЯЩЕЕ
ОТОБРАЖЕНИЕ. рАССМОТРИМ ПРИМЕР С НЕБОЛЬШИМИ ЗНАЧЕНИЯМИ ПАРАМЕТРОВ, КОГДА
$m=4$ И~$n=3$, А ВСЕ ВТОРИЧНЫЕ КЛЮЧИ МОГУТ ПРИНИМАТЬ ЛИШЬ ДВА ЗНАЧЕНИЯ;
ОТОБРАЗИМ 4-БИТОВЫЕ ЗАПИСИ В ВОСЕМЬ АДРЕСОВ СЛЕДУЮЩИМ ОБРАЗОМ:
$$
\matrix{
*&0&0&0&\to& 1\cr
*&1&1&1&\to& 2\cr
0&*&0&1&\to& 3\cr
1&*&1&0&\to& 4\cr
}
\qquad
\matrix{
0&1&*&0&\to& 5\cr
1&0&*&1&\to& 6\cr
0&0&1&*&\to& 7\cr
1&1&0&*&\to& 8\cr
}
\eqno(7)
$$
иССЛЕДОВАНИЕ ЭТОЙ ТАБЛИЦЫ ПОКАЗЫВАЕТ, ЧТО ВСЕ ЗАПИСИ, СООТВЕТСТВУЮЩИЕ
ЗАПРОСУ~$0***$, ОТОБРАЖАЮТСЯ В ПЯТЬ АДРЕСОВ 1, 2, 3, 5 И~7; И ВООБЩЕ
\emph{ЛЮБОЙ} БАЗОВЫЙ ЗАПРОС С ТРЕМЯ ЗВЕЗДОЧКАМИ ЗАТРАГИВАЕТ РОВНО ПЯТЬ
АДРЕСОВ. бАЗОВЫЙ ЗАПРОС С ДВУМЯ ЗВЕЗДОЧКАМИ ЗАТРАГИВАЕТ ТРИ АДРЕСА, И,
НАКОНЕЦ, БАЗОВЫЙ ЗАПРОС С ОДНОЙ ЗВЕЗДОЧКОЙ ЗАТРАГИВАЕТ ЛИБО ОДИН, ЛИБО
ДВА, А В СРЕДНЕМ $(8\times1+24\times2)/32=1.75$~АДРЕСА. тАКИМ ОБРАЗОМ, ИМЕЕМ
%%669
{\def\hdr#1{\vbox{\dimen255=\hsize\divide\dimen255 by 3\hsize=\dimen255\leftskip=0pt plus 1fill\rightskip=0pt plus 1fill\noindent #1\par}}
$$
\matrix{
\hdr{кОЛИЧЕСТВО НЕСПЕЦИФИЦИРОВАННЫХ \goodbreak БИТОВ В ЗАПРОСЕ} & \hdr{кОЛИЧЕСТВО ЗАТРАГИВАЕМЫХ \goodbreak АДРЕСОВ}\cr
4 & 8 = 8^{4/4}\cr
3& 5\approx 8^{3/4}\cr
2& 3\approx 8^{2/4}\cr
1& 1.75\approx 8^{1/4}\cr
0& 1= 8^{0/4}\cr
}
\eqno(8)
$$
}

рАЗУМЕЕТСЯ, ЭТО ЛИШЬ МАЛЕНЬКИЙ ПРИМЕР; ТАБЛИЦЫ ПОДОБНОГО РАЗМЕРА ПРОЩЕ
ОБРАБАТЫВАТЬ БЕЗ ВСЯКИХ УХИЩРЕНИЙ. нО ОН ПОЛЕЗЕН И ДЛЯ НЕТРИВИАЛЬНЫХ
ПРИЛОЖЕНИЙ, КОГДА $m=4r$ И~$n=3r$, ВЕДЬ $4r\hbox{-БИТОВЫЕ}$ ЗАПИСИ МОЖНО
ОТОБРАЗИТЬ В
$2^{3r}\approx N$~АДРЕСОВ, РАЗДЕЛИВ ВТОРИЧНЫЕ КЛЮЧИ НА $r$~ГРУПП ПО ЧЕТЫРЕ
БИТА В КАЖДОЙ И ПРИМЕНИВ~(7) К КАЖДОЙ ГРУППЕ. пОЛУЧАЮЩЕЕСЯ ОТОБРАЖЕНИЕ
ОБЛАДАЕТ ТРЕБУЕМЫМ СВОЙСТВОМ: \dfn{ЗАПРОС, ОСТАВЛЯЮЩИЙ $k$ ИЗ $m$~БИТОВ
НЕСПЕЦИФИЦИРОВАННЫМИ, ЗАТРОНЕТ ПРИМЕРНО $N^{k/m}$~АДРЕСОВ}. (сМ.~УПР.~6.)

нЕКОТОРЫЕ ДРУГИЕ ОТОБРАЖЕНИЯ, НАЙДЕННЫЕ рАЙВЕСТОМ, ПРИВОДЯТСЯ В УПР.~7;
ИХ МОЖНО ИСПОЛЬЗОВАТЬ ВМЕСТЕ С~(7) ДЛЯ ПОЛУЧЕНИЯ ФУНКЦИЙ КОМБИНАТОРНОГО
ХЕШИРОВАНИЯ В СЛУЧАЕ $1\le m/n \le 2$. нА САМОМ ДЕЛЕ МОЖНО БЫЛО БЫ
ИСПОЛЬЗОВАТЬ БЛОКИ РАЗМЕРА~$b$ И ПОЛОЖИТЬ~$N \approx 2^n b$; МЫ ВЗЯЛИ
$b=1$ ДЛЯ ПРОСТОТЫ ИЗЛОЖЕНИЯ.

\section *сБАЛАНСИРОВАННЫЕ ФАЙЛОВЫЕ СИСТЕМЫ. дРУГОЙ КОМБИНАТОРНЫЙ ПОДХОД К
ЗАДАЧЕ ВЫБОРКИ ИНФОРМАЦИИ, ОСНОВАННЫЙ НА "СИСТЕМАХ СБАЛАНСИРОВАННЫХ
НЕПОЛНЫХ ГРУПП", ЯВИЛСЯ ПРЕДМЕТОМ МНОГОЧИСЛЕННЫХ ИССЛЕДОВАНИЙ. хОТЯ ОН
ОЧЕНЬ ИНТЕРЕСЕН С МАТЕМАТИЧЕСКОЙ ТОЧКИ ЗРЕНИЯ, СВОЕЙ ПРАКТИЧЕСКОЙ
ЦЕННОСТИ ЭТОТ МЕТОД, К СОЖАЛЕНИЮ, ЕЩЕ НЕ ПРОЯВИЛ. чТОБЫ ДАТЬ ЧИТАТЕЛЮ
ВОЗМОЖНОСТЬ ПОЧУВСТВОВАТЬ ИЗЯЩЕСТВО РЕЗУЛЬТАТОВ, МЫ ВСЕ ЖЕ ИЗЛОЖИМ
ЗДЕСЬ КРАТКОЕ ВВЕДЕНИЕ В ТЕОРИЮ, НЕ ТЕРЯЯ НАДЕЖДЫ, ЧТО КТО-НИБУДЬ НАЙДЕТ
ЕЙ ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ.

\emph{шТЕЙНЕРОВСКОЙ СИСТЕМОЙ ТРОЕК} НАЗЫВАЕТСЯ ТАКОЕ РАСПРЕДЕЛЕНИЕ
$v$~ОБоЕКТОВ В НЕУПОРЯДОЧЕННЫЕ ТРОЙКИ, КОГДА КАЖДАЯ ПАРА ОБоЕКТОВ
ВСТРЕЧАЕТСЯ РОВНО В ОДНОЙ ТРОЙКЕ. нАПРИМЕР, ЕСЛИ $v=7$, ИМЕЕТСЯ, ПО
СУЩЕСТВУ, ОДНА ШТЕЙНЕРОВСКАЯ СИСТЕМА ТРОЕК, А ИМЕННО
$$
\matrix{
\hbox{тРОЙКА} & \hbox{сОДЕРЖАЩИЕСЯ В НЕЙ ПАРЫ}\span \span \span\cr
\set{1,2,4} & \set{1,2}, & \set{1,4}, & \set{2,4}\cr
\set{2,3,5} & \set{2,3}, & \set{2,5}, & \set{3,6}\cr
\set{3,4,6} & \set{3,4}, & \set{3,6}, & \set{4,6}\cr
\set{4,5,0} & \set{0,4}, & \set{0,5}, & \set{4,5}\cr
\set{5,6,1} & \set{1,5}, & \set{1,6}, & \set{5,6}\cr
\set{6,0,2} & \set{0,2}, & \set{0,6}, & \set{2,6}\cr
\set{0,1,3}  & \set{0,1}, & \set{0,3}, & \set{1,8}\cr
}
$$
%%670
пОСКОЛЬКУ СУЩЕСТВУЕТ ${1\over2}v(v-1)$~ПАР ОБоЕКТОВ, А В ТРОЙКЕ---ТРИ
ПАРЫ, ОБЩЕЕ ЧИСЛО ТРОЕК РАВНО~${1\over6}v(v-1)$; ПОСКОЛЬКУ КАЖДЫЙ ОБоЕКТ
МОЖЕТ СОСТАВЛЯТЬ ПАРУ РОВНО С $v-1$ ДРУГИМИ ОБоЕКТАМИ, ОН ДОЛЖЕН
ПРИСУТСТВОВАТЬ РОВНО В ${1\over2}(v-1)$~ТРОЙКАХ. иЗ ЭТИХ СООБРАЖЕНИЙ
СЛЕДУЕТ, ЧТО СИСТЕМА шТЕЙНЕРА СУЩЕСТВУЕТ ЛИШЬ ТОГДА, КОГДА ЧИСЛА
${1\over6}v(v-1)$ И~${1\over2}(v-1)$ ЦЕЛЫЕ. зНАЧИТ,
$v$ ДОЛЖНО БЫТЬ НЕЧЕТНЫМ И ПРИ ДЕЛЕНИИ НА~3 НЕ ДАВАТЬ В ОСТАТКЕ 2, Т.~Е.
$$
v \bmod 6 =1\hbox{ ИЛИ } 3.
\eqno(10)
$$
оБРАТНО, В 1847~Г.~кИРКМАН ДОКАЗАЛ, ЧТО, ЕСЛИ $v\ge1$ И ВЫПОЛНЕНО
УСЛОВИЕ~(10), ШТЕЙНЕРОВСКАЯ СИСТЕМА ТРОЕК ДЕЙСТВИТЕЛЬНО СУЩЕСТВУЕТ. еГО
ИНТЕРЕСНАЯ КОНСТРУКЦИЯ ПРИВЕДЕНА В УПР.~10.

шТЕЙНЕРОВСКИЕ СИСТЕМЫ ТРОЕК МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ УМЕНЬШЕНИЯ ИЗБЫТОЧНОСТИ
В КОМБИНИРОВАННЫХ ИНВЕРТИРОВАННЫХ ФАЙЛАХ. рАССМОТРИМ ВНОВЬ ФАЙЛ РЕЦЕПТОВ
ПЕЧЕНИЙ (ТАБЛ.~1) И ПРЕОБРАЗУЕМ ПРАВЫЙ СТОЛБЕЦ В 31-Й~АТРИБУТ, КОТОРЫЙ
РАВЕН~1, ЕСЛИ ТРЕБУЕТСЯ СПЕЦИАЛЬНЫЙ ИНГРЕДИЕНТ, И~0 В ПРОТИВНОМ
СЛУЧАЕ. пРЕДПОЛОЖИМ, МЫ ХОТИМ ОТВЕЧАТЬ НА ВСЕ ВКЛЮЧАЮЩИЕ ЗАПРОСЫ О ПАРАХ
АТРИБУТОВ, НАПРИМЕР НА ЗАПРОС "в КАКИХ РЕЦЕПТАХ ИСПОЛЬЗУЮТСЯ И КОКОСОВЫЕ
ОРЕХИ, И ИЗЮМ?" мОЖНО БЫЛО БЫ ПОСТРОИТЬ ИНВЕРТИРОВАННЫЙ СПИСОК ДЛЯ КАЖДОГО
ИЗ $\perm{31}{2}=465$~ВОЗМОЖНЫХ ЗАПРОСОВ. оДНАКО ЭТИ СПИСКИ ЗАЙМУТ МНОГО
МЕСТА, ПОСКОЛЬКУ, НАПРИМЕР, ПЕЧЕНЬЕ С ПЕРЦЕМ БУДЕТ СОДЕРЖАТЬСЯ В
$\perm{17}{2}=136$ ИЗ НИХ, А ЗАПИСЬ, ОБЛАДАЮЩАЯ ВСЕМИ АТРИБУТАМИ,
ВОЙДЕТ В КАЖДЫЙ СПИСОК! иСПОЛЬЗОВАНИЕ СИСТЕМЫ ТРОЕК шТЕЙНЕРА НЕСКОЛЬКО
УЛУЧШАЕТ СИТУАЦИЮ. дЛЯ 31~ОБоЕКТА СУЩЕСТВУЕТ СИСТЕМА шТЕЙНЕРА ИЗ
155~ТРОЕК, ПРИЧЕМ КАЖДАЯ ПАРА ОБоЕКТОВ ВХОДИТ РОВНО В ОДНУ ТРОЙКУ. кАЖДОЙ
ТРОЙКЕ~$\set{a, b, c}$ МОЖНО СОПОСТАВИТЬ ЧЕТЫРЕ СПИСКА: ОДИН СПИСОК---ДЛЯ
ЗАПИСЕЙ, ОБЛАДАЮЩИХ АТРИБУТАМИ $a$, $b$, $\bar c$ (Т.~Е.~НЕ~$c$);
ДРУГОЙ---ДЛЯ $a$, $\bar b$, $c$; ТРЕТИЙ---ДЛЯ $\bar a$, $b$, $c$;
ЧЕТВЕРТЫЙ---ДЛЯ $a$, $b$, $c$. тАКАЯ КОНСТРУКЦИЯ ГАРАНТИРУЕТ, ЧТО НИКАКАЯ
ЗАПИСЬ НЕ ПОПАДЕТ БОЛЕЕ ЧЕМ В 155~ИНВЕРТИРОВАННЫХ СПИСКОВ, И ЭКОНОМИТ
ПРОСТРАНСТВО, ЕСЛИ ЗАПИСЬ ИМЕЕТ ТРИ АТРИБУТА, СООТВЕТСТВУЮЩИХ ТРОЙКЕ СИСТЕМЫ.

сИСТЕМА ТРОЕК ЯВЛЯЕТСЯ ЧАСТНЫМ СЛУЧАЕМ СИСТЕМ ГРУПП, СОСТОЯЩИХ ИЗ ТРЕХ
ИЛИ БОЛЕЕ ОБоЕКТОВ. нАПРИМЕР, 31~ОБоЕКТ МОЖНО ТАК РАСПРЕДЕЛИТЬ ПО
НЕУПОРЯДОЧЕННЫМ ШЕСТЕРКАМ, ЧТО КАЖДАЯ ПАРА ОБоЕКТОВ ПОПАДЕТ РОВНО В ОДНУ ШЕСТЕРКУ:
%%671
{\def\sset#1{\scriptstyle\set{#1}\hfill}
$$\matrix{
\sset{1,  5, 17, 22, 23, 25} &\sset{ 7, 11, 23, 28, 29, 0} &\sset{13, 17, 26, 3,  4,  6} &\sset{20, 24,  5, 10, 11, 13} &\sset{26, 30, 11, 16, 17, 19}\cr
\sset{2,  6, 18, 23, 24, 26} &\sset{ 8, 12, 24, 29, 30, 1} &\sset{14, 18, 30, 4,  5,  7} &\sset{21, 25,  6, 11, 12, 14} &\sset{27,  0, 12, 17, 18, 20}\cr
\sset{3,  7, 19, 24, 25, 27} &\sset{ 9, 13, 25, 30,  0, 2} &\sset{15, 19,  0, 5,  6,  8} &\sset{22, 26,  7, 12, 13, 15} &\sset{28,  1, 13, 18, 19, 21}\cr
\sset{4,  8, 20, 25, 26, 28} &\sset{10, 14, 26,  0,  1, 3} &\sset{16, 20,  1, 6,  7,  9} &\sset{23, 27,  8, 13, 14, 16} &\sset{29,  2, 14, 19, 20, 22}\cr
\sset{5,  9, 21, 26, 27, 29} &\sset{11, 15, 27,  1,  2, 4} &\sset{17, 21,  2, 7,  8, 10} &\sset{24, 28,  9, 14, 15, 17} &\sset{30,  3, 15, 20, 21, 23}\cr
\sset{6, 10, 22, 27, 28, 30} &\sset{12, 16, 28,  2,  3, 5} &\sset{18, 22,  3, 8,  9, 11} &\sset{25, 29, 10, 15, 16, 18} &\sset{ 0,  4, 16, 21, 22, 24}\cr
                             &                             &\sset{19, 23,  4, 9, 10, 12} \cr
}
$$
}
[эТА СИСТЕМА ПОЛУЧАЕТСЯ ИЗ ПЕРВОЙ ГРУППЫ ПУТЕМ СЛОЖЕНИЯ ПО МОДУЛЮ~31. дЛЯ
ПРОВЕРКИ ТОГО, ЧТО ОНА ОБЛАДАЕТ ТРЕБУЕМЫМ СВОЙСТВОМ, ЗАМЕТИМ, ЧТО
30~ЗНАЧЕНИЙ~$(a_i-a_j)\bmod 31$, $i\ne j$, РАЗЛИЧНЫ, ЕСЛИ
$(a_1, a_2, ~\ldots, a_6)=(1, 5, 17, 22, 23, 25)$. чТОБЫ НАЙТИ ШЕСТЕРКУ,
СОДЕРЖАЩУЮ ДАННУЮ ПАРУ~$(x, y)$, ВЫБЕРЕМ $i$ И~$j$ ТАК, ЧТО
$a_i-a_j\equiv x-y \pmod{31}$; ЕСЛИ $k=(x-a_i) \bmod 31$, ТО
$(a_i+k) \bmod31=x$ И~$(a_j+k)\bmod31=y$.]

сИСТЕМУ~(11) МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ ХРАНЕНИЯ ИНВЕРТИРОВАННЫХ СПИСКОВ,
ПРИЧЕМ НИ ОДНА ЗАПИСЬ НЕ ПОЯВИТСЯ БОЛЕЕ 31~РАЗА. кАЖДОЙ
ШЕСТЕРКЕ~$\set{a, b, c, d, e, f}$ СОПОСТАВЛЕНО 57~СПИСКОВ,
ПРЕДНАЗНАЧЕННЫХ ДЛЯ ЗАПИСЕЙ,
ИМЕЮЩИХ ДВА ИЛИ БОЛЕЕ АТРИБУТА $a$, $b$, $c$, $d$, $e$ ИЛИ~$f$,
Т.~Е.~ИМЕЮЩИХ АТРИБУТЫ $(a, b, \bar c, \bar d, \bar e, \bar f)$,
$(a, \bar b, c, \bar d, \bar e, f)$,~\dots,
$(a, b, c, d, e, f)$; ОТВЕТОМ НА ЛЮБОЙ ВКЛЮЧАЮЩИЙ ЗАПРОС ПО ДВУМ АТРИБУТАМ
ЯВЛЯЕТСЯ ОБоЕДИНЕНИЕ БЕЗ ПЕРЕСЕЧЕНИЙ 16~ПОДХОДЯЩИХ СПИСКОВ ПОДХОДЯЩЕЙ
ШЕСТЕРКИ. пЕЧЕНЬЕ С ПЕРЦЕМ ВОЙДЕТ В~29 ИЗ 31~ГРУППЫ ЭТОЙ СИСТЕМЫ,
ПОСКОЛЬКУ НАЗВАННОЕ БЛЮДО ИМЕЕТ ДВА ИЗ ШЕСТИ АТРИБУТОВ ВО ВСЕХ ШЕСТЕРКАХ,
 КРОМЕ $\set{19, 23, 4, 9, 10, 12}$
И~$\set{13, 17, 29, 3, 4, 6}$ (ЕСЛИ МЫ ЗАНУМЕРУЕМ СТОЛБЦЫ ЧИСЛАМИ ОТ~0 ДО~30).

аНАЛОГИЧНАЯ ИДЕЯ ПРИМЕНИМА ДЛЯ УМЕНЬШЕНИЯ ИЗБЫТОЧНОСТИ В СОСТАВНЫХ
ИНВЕРТИРОВАННЫХ СПИСКАХ, КОГДА МЫ ХОТИМ ОТВЕЧАТЬ НА БАЗОВЫЕ, А НЕ НА
ВКЛЮЧАЮЩИЕ ЗАПРОСЫ. пРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО ЗАПИСИ СОДЕРЖАТ ПЯТЬ
ВТОРИЧНЫХ КЛЮЧЕЙ $K_1$, $K_2$, $K_3$, $K_4$, $K_5$, КАЖДЫЙ ИЗ КОТОРЫХ
МОЖЕТ ПРИНИМАТЬ ОДНО ИЗ ЧЕТЫРЕХ ЗНАЧЕНИЙ~0, 1, 2 ИЛИ~3. чТОБЫ ОТВЕТИТЬ
НА ЗАПРОС О ЗАПИСЯХ, ДЛЯ КОТОРЫХ $K_i=a$ И~$K_j=b$ ПРИ ДАННЫХ $a$, $b$
И~$i\ne j$, МЫ МОГЛИ БЫ ОБРАЗОВАТЬ ИНВЕРТИРОВАННЫЕ СПИСКИ ДЛЯ ВСЕХ
160~ПОДОБНЫХ ЗАПРОСОВ; В ТАКОМ СЛУЧАЕ КАЖДАЯ ЗАПИСЬ ПРИСУТСТВОВАЛА БЫ
В ДЕСЯТИ ИНВЕРТИРОВАННЫХ СПИСКАХ. аЛЬТЕРНАТИВОЙ ЯВЛЯЕТСЯ ИСПОЛЬЗОВАНИЕ
СЛЕДУЮЩЕЙ СИСТЕМЫ УПОРЯДОЧЕННЫХ ПЯТЕРОК, ОСНОВАННОЙ НА КОМБИНАТОРНОЙ
СХЕМЕ, КОТОРАЯ НАЗЫВАЕТСЯ "ВЗАИМНО ОРТОГОНАЛЬНЫЕ ЛАТИНСКИЕ КВАДРАТЫ":
$$
\matrix{
(0, 0, 0, 0, 0) & (1, 0, 1, 2, 3) & (2, 0, 2, 3, 1) & (3, 0, 3, 1, 2) \cr
(0,1,1,1,1) & (1,1,0,3,2) & (2,1,3,2,0) & (3,1,2,0,3)\cr
(0,2,2,2,2) & (1,2,3,0,1) & (2,2,0,1,3) & (3,2,1,3,0)\cr
(0,3,3,3,3) & (1,3,2,1,0) & (2, 3,1,0,2) & (3,3,0,2,1)\cr
}
$$
еСЛИ МЫ ТЕПЕРЬ ПОСМОТРИМ НА ЛЮБЫЕ ДВЕ ИЗ ПЯТИ КОМПОНЕНТ, ТО УВИДИМ, ЧТО
ВСЕ 16~ВОЗМОЖНЫХ УПОРЯДОЧЕННЫХ ПАР ЗНАЧЕНИЙ
%%672
ВСТРЕЧАЮТСЯ В ЭТИХ ПОЗИЦИЯХ РОВНО ОДИН РАЗ. гРУППЕ ($a$, $b$, $c$, $d$,
$e$) ЭТОЙ СИСТЕМЫ МОЖНО СОПОСТАВИТЬ ЗАПИСИ, УДОВЛЕТВОРЯЮЩИЕ ПО КРАЙНЕЙ
МЕРЕ ДВУМ ИЗ УСЛОВИЙ $K_1=a$, $K_2=b$,~\dots, $K_5=e$. тАКИМ ОБРАЗОМ,
КАЖДОЙ ИЗ 16~ГРУПП БУДУТ СОПОСТАВЛЕНЫ 376 ИЗ~1024 ВОЗМОЖНЫХ ЗАПИСЕЙ,
ПОЭТОМУ СРЕДНЯЯ ИЗБЫТОЧНОСТЬ
УМЕНЬШИЛАСЬ С~ 0 ДО~$16\times 376/1024 =5{7\over8}$.

тЕОРИЯ СИСТЕМ ТАКИХ ГРУПП И ЛАТИНСКИХ КВАДРАТОВ ДЕТАЛЬНО РАЗРАБОТАНА В
"КНИГЕ Marshall Hall, Jr., Combinatorial Theory (Waltham; Mass.: Blaisdell,
 1967). нЕСМОТРЯ НА ВСЮ КРАСОТУ ЭТОГО КРУГА ИДЕЙ, В ЗАДАЧАХ ВЫБОРКИ
ИНФОРМАЦИИ ИХ УДАЛОСЬ ИСПОЛЬЗОВАТЬ ЛИШЬ ДЛЯ УМЕНЬШЕНИЯ ИЗБЫТОЧНОСТИ ПРИ
ПОСТРОЕНИИ СОСТАВНЫХ ИНВЕРТИРОВАННЫХ СПИСКОВ; дЭВИД чЖОУ [{\sl
Information and Control,\/} {\bf 15} (1969), 377--396] ЗАМЕТИЛ, ЧТО ТОГО
ЖЕ РЕЗУЛЬТАТА МОЖНО ДОСТИЧЬ И БЕЗ КОМБИНАТОРНЫХ СИСТЕМ.

\section кРАТКАЯ ИСТОРИЯ И БИБЛИОГРАФИЯ. пЕРВАЯ ОПУБЛИКОВАННАЯ СТАТЬЯ О
МЕТОДАХ ВЫБОРКИ ПО ВТОРИЧНЫМ КЛЮЧАМ НАПИСАНА л. дЖОНСОНОМ [{\sl CACM,\/}
{\bf 4} (1961), 218--222]. мНОГОСПИСОЧНУЮ СИСТЕМУ ПРИМЕРНО В ОДНО И ТО ЖЕ
ВРЕМЯ НЕЗАВИСИМО РАЗРАБОТАЛИ нОЙ пРАЙВЗ, X.~гРЭЙ, у.~лАНДАУЭР, д.~лЕФКОВИЧ
И с.~лИТВИН; СР.~С [{\sl IEEE Trans.~on Communication and Electronics,\/}
{\bf 68} (1963), 488--492]. дРУГАЯ ДОВОЛЬНО РАННЯЯ ПУБЛИКАЦИЯ,
ОКАЗАВШАЯ ВЛИЯНИЕ НА ПОСЛЕДУЮЩИЕ РАБОТЫ, ПРИНАДЛЕЖИТ д.~р.~дЭВИСУ И
э.~д.~лИНУ [{\sl CACM,\/} {\bf 8} (1965), 243--246].

в ОБШИРНОЙ ЛИТЕРАТУРЕ, ПОЯВИВШЕЙСЯ С ТЕХ ПОР ПО ЭТОМУ ВОПРОСУ, ОСНОВНОЕ
ВНИМАНИЕ УДЕЛЯЛОСЬ ВЗАИМОДЕЙСТВИЮ С ПОЛЬЗОВАТЕЛЯМИ И ЯЗЫКАМ
ПРОГРАММИРОВАНИЯ, НО ЭТИХ ТЕМ МЫВ НАШЕЙ КНИГЕ НЕ КАСАЕМСЯ. в ДОПОЛНЕНИЕ
К УЖЕ ПЕРЕЧИСЛЕННЫМ СТАТЬЯМ МОЖНО ПОРЕКОМЕНДОВАТЬ СЛЕДУЮЩИЕ
ОПУБЛИКОВАННЫЕ РАБОТЫ, ОКАЗАВШИЕ АВТОРУ НАИБОЛЬШУЮ ПОМОЩЬ
ПРИ-НАПИСАНИИ ЭТОГО ПАРАГРАФА: Jack Minker, Jerome Sable, {\sl
Ann.~Rev.~of Information Science and Technology,\/} {\sl 2} (1967),
123--160; Robert E.~Bleier, Proc.~ACM~Nat.~Conf., {\bf 22} (1967), 41--49;
Jerome A.~Feldman, Paul D.~Rovner, {\sl CACM,\/} {\bf 12} (1969),
439--449; Burton H.~Bloom, Proc.~ACM~Nat.~Conf., {\bf 24} (1969), 83--95;
H.~S.~Heaps, L.~H.~Thiel, {\sl Information Storage and Retrieval,\/} {\bf
6} (1970), 137--153;
Vincent Y.~Lum, Huei Ling, Proc.~ACM~Nat.~Conf., {\bf 26} (1971), 349--356.
 хОРОШИЙ ОБЗОР РУЧНЫХ КАРТОЧЕК СДЕЛАН В ГЛ.~5 КНИГИ бУРНА Methods of
Information Handling (New York: Wiley, 1963). "сБАЛАНСИРОВАННЫЕ ФАЙЛОВЫЕ
СИСТЕМЫ" ВПЕРВЫЕ РАЗРАБОТАЛИ аБРАХАМ, с.~гХОШ И д.~рОЙ-чОУДХУРИ В 1965~Г.;
ПОЖАЛУЙ, ЛУЧШЕЕ РЕЗЮМЕ ЭТОЙ РАБОТЫ И ПОСЛЕДУЮЩЕГО РАЗВИТИЯ МЕТОДА
ДАЛИ р.~бОЗЕ И гЭРИ кОЧ [{\sl SIAM, J.~Appl.~Math.,\/} {\bf 17} (1969), 1203--1214].

в НАСТОЯЩЕМ ПАРАГРАФЕ МЫ ОБСУДИЛИ ДОВОЛЬНО МНОГО ИНТЕРЕСНЫХ ИДЕЙ,
ПОЛЕЗНЫХ В ОЧЕНЬ РАЗНЫХ СИТУАЦИЯХ. пОСКОЛЬКУ
%% 673
МНОГИЕ ИЗ ЭТИХ МЕТОДОВ ПОЯВИЛИСЬ НЕЗАДОЛГО ДО НАПИСАНИЯ ДАННОГО
ПАРАГРАФА, ТО НОВЫЕ УСПЕХИ, ВЕРОЯТНО, НЕ ЗАСТАВЯТ СЕБЯ ЖДАТЬ.

иНТЕРЕСНО ОТМЕТИТЬ, ЧТО ЧЕЛОВЕЧЕСКИЙ МОЗГ ВЫПОЛНЯЕТ ВЫБОРКУ ПО ВТОРИЧНЫМ
КЛЮЧАМ ГОРАЗДО ЛУЧШЕ, ЧЕМ эвм; В САМОМ ДЕЛЕ, МЫ ДОВОЛЬНО ЛЕГКО РАСПОЗНАЕМ
ЛИЦА ИЛИ МЕЛОДИИ И~Т.~П.\ ПО ОТРЫВОЧНОЙ ИНФОРМАЦИИ, В ТО ВРЕМЯ КАК МАШИНЫ,
ПОЖАЛУЙ, ВООБЩЕ НЕ В СОСТОЯНИИ СДЕЛАТЬ ЭТО. и НЕТ НИЧЕГО НЕВОЗМОЖНОГО В
ТОМ, ЧТО ОДНАЖДЫ БУДЕТ ОТКРЫТ ПРИНЦИПИАЛЬНО НОВЫЙ ПОДХОД К КОНСТРУИРОВАНИЮ
МАШИН, КОТОРЫЙ РАЗ И НАВСЕГДА РЕШИТ ЗАДАЧУ ВЫБОРКИ ПО ВТОРИЧНЫМ КЛЮЧАМ,
СДЕЛАВ ТЕМ САМЫМ ВЕСЬ ЭТОТ ПАРАГРАФ НЕНУЖНЫМ.

\excercises
\rex[м27] пУСТЬ $0\le k \le {1\over2}n$. дОКАЖИТЕ, ЧТО СЛЕДУЮЩЕЕ
ПОСТРОЕНИЕ ДАЕТ
$\perm{n}{k}$~ПЕРЕСТАНОВОК ЧИСЕЛ~$\set{1, 2,~\ldots, n}$, ТАКИХ, ЧТО
КАЖДОЕ $t\hbox{-ЭЛЕМЕНТНОЕ}$ ПОДМНОЖЕСТВО МНОЖЕСТВА~$\set{1, 2,~\dots, n}$
ПРИ $t\le k$ ИЛИ~$t\ge n-k$ ВСТРЕЧАЕТСЯ ПО КРАЙНЕЙ МЕРЕ ОДИН РАЗ В
КАЧЕСТВЕ ПЕРВЫХ $t$~ЭЛЕМЕНТОВ ПЕРЕСТАНОВКИ. рАССМОТРИМ ПУТЬ НА ПЛОСКОСТИ
ИЗ ТОЧКИ~$(0, 0)$ В~$(n, r)$, ГДЕ $r\ge n-2k$, В КОТОРОМ $i\hbox{-Й}$~ШАГ
ПРОИЗВОДИТСЯ ИЗ ТОЧКИ~$(i-1, j$) В~$(i, j+1)$ ИЛИ В~$(i, j-1)$;
ПОСЛЕДНЯЯ ВОЗМОЖНОСТЬ ИМЕЕТСЯ ЛИШЬ ДЛЯ~$j\ge 1$, ПОЭТОМУ ПУТЬ НИКОГДА НЕ ОПУСКАЕТСЯ
НИЖЕ ОСИ~$x$. сУЩЕСТВУЕТ РОВНО $\perm{n}{k}$ ТАКИХ ПУТЕЙ. пЕРЕСТАНОВКА,
СООТВЕТСТВУЮЩАЯ ПОДОБНОМУ ПУТИ, СТРОИТСЯ С ИСПОЛЬЗОВАНИЕМ ТРЕХ
ПЕРВОНАЧАЛЬНО ПУСТЫХ СПИСКОВ СЛЕДУЮЩИМ ОБРАЗОМ: ЕСЛИ $i\hbox{-Й}$~ШАГ
ДЕЛАЕТСЯ ВВЕРХ, $i=1$, 2,~\dots, $n$, ТО ЧИСЛО~$i$ ПОМЕЩАЕТСЯ В
СПИСОК~$B$; ЕСЛИ ЖЕ ВНИЗ, ТО $i$~ПОМЕЩАЕТСЯ В СПИСОК~$A$, А МАКСИМАЛЬНЫЙ
НА ДАННЫЙ МОМЕНТ ЭЛЕМЕНТ СПИСКА~$B$ ИЗЫМАЕТСЯ ИЗ НЕГО И ПЕРЕНОСИТСЯ В
СПИСОК~$C$. зАТЕМ НУЖНО ВЫПИСАТЬ ДРУГ ЗА ДРУГОМ ЭЛЕМЕНТЫ СПИСКОВ~$A$, $B$
(В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ) И~$C$ (ТАКЖЕ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ). пОСТРОЕНИЕ
ПЕРЕСТАНОВКИ ЗАВЕРШЕНО.

нАПРИМЕР, ПРИ $n=4$ И~$k=2$ ПОЛУЧАЕТСЯ ШЕСТЬ ПУТЕЙ И СООТВЕТСТВУЮЩИХ ИМ
ПЕРЕСТАНОВОК
\picture{рИС. СТР. 673}
(вЕРТИКАЛЬНЫЕ ЛИНИИ РАЗДЕЛЯЮТ СПИСКИ~$A$, $B$ И~$C$. эТИ ШЕСТЬ
ПЕРЕСТАНОВОК СООТВЕТСТВУЮТ СОСТАВНЫМ АТРИБУТАМ В~(2).)

[\emph{уКАЗАНИЕ.} пРЕДСТАВЬТЕ КАЖДОЕ $t\hbox{-ЭЛЕМЕНТНОЕ}$
ПОДМНОЖЕСТВО~$S$ С ПОМОЩЬЮ ПУТИ ИЗ~$(0, 0)$ В~$ (n, n-2t)$,
$i\hbox{-Й}$~ШАГ КОТОРОГО ВЫПОЛНЯЕТСЯ ИЗ~$(i-1, j)$ В
$(i, j+1)$, ЕСЛИ $i\notin S$, И В~$(i, j-1)$, ЕСЛИ $i\in S$. пРЕОБРАЗУЙТЕ
КАЖДЫЙ ТАКОЙ ПУТЬ В ПУТЬ ОПИСАННОГО ВЫШЕ ВИДА.]

\ex[м25] (сАКТИ гХОШ.) нАЙДИТЕ МИНИМАЛЬНО ВОЗМОЖНУЮ ДЛИНУ~$l$ СПИСКА $r_1$
$r_2$~\dots $r_l$ ССЫЛОК НА ЗАПИСИ, ОБЛАДАЮЩЕГО ТЕМ СВОЙСТВОМ, ЧТО ВСЕ
ОТВЕТЫ НА ЛЮБОЙ ИЗ ВКЛЮЧАЮЩИХ ЗАПРОСОВ $* * 1$, $* 1 *$, $1* *$, $* 1 1$,
$1*1$, $11*$, $1 1 1$ ПО ТРЕМ КЛЮЧАМ С ДВУМЯ ВОЗМОЖНЫМИ ЗНАЧЕНИЯМИ
ОКАЖУТСЯ В ПОСЛЕДОВАТЕЛЬНЫХ
ЭЛЕМЕНТАХ~$r_i~\ldots r_j$.
%%674

\ex[19] рАССМОТРИМ ТАБЛ.~2. кАКИЕ ВКЛЮЧАЮЩИЕ ЗАПРОСЫ ВЫЗОВУТ
ЛОЖНОЕ ВЫПАДЕНИЕ: (a)~СТАРИННОГО САХАРНОГО ПЕЧЕНЬЯ; (b)~ОВСЯНЫХ ПАЛОЧЕК
С ФИНИКАМИ?

\ex[M30] нАЙДИТЕ ТОЧНЫЕ ФОРМУЛЫ ДЛЯ ВЕРОЯТНОСТЕЙ~(5), ПРЕДПОЛАГАЯ, ЧТО
КАЖДАЯ ЗАПИСЬ ИМЕЕТ Г РАЗЛИЧНЫХ АТРИБУТОВ, СЛУЧАЙНО ВЫБИРАЕМЫХ
ИЗ~$\perm{n}{k}$ $k\hbox{-БИТОВЫХ}$ КОДОВ В $n\hbox{-БИТОВОМ}$ ПОЛЕ, И ЧТО
ЗАПРОС ВКЛЮЧАЕТ $q$~РАЗЛИЧНЫХ, А В ОСТАЛЬНОМ СЛУЧАЙНЫХ АТРИБУТОВ. (нЕ
ПУГАЙТЕСЬ, ЕСЛИ ФОРМУЛЫ НЕ БУДУТ УПРОЩАТЬСЯ!)

\ex[40] пОЭКСПЕРИМЕНТИРУЙТЕ С РАЗЛИЧНЫМИ СПОСОБАМИ УМЕНЬШЕНИЯ
ИЗБЫТОЧНОСТИ В ТЕКСТАХ, ЕСЛИ ДЛЯ ПОИСКА ПОДЦЕПОЧЕК ИСПОЛЬЗУЕТСЯ МЕТОД
хАРРИСОНА.

\rex[м20] оБЩЕЕ ЧИСЛО $m\hbox{-БИТОВЫХ}$ ЗАПРОСОВ С $k$~СПЕЦИФИЦИРОВАННЫМИ
БИТАМИ РАВНО $s=\perm{m}{k}2^k$. еСЛИ КОМБИНАТОРНАЯ ХЕШ-ФУНКЦИЯ,
ПОДОБНАЯ~(7), ПРЕОБРАЗУЕТ ЭТИ ЗАПРОСЫ В АДРЕСА $l_1$, $l_2$,~\dots, $l_s$
СООТВЕТСТВЕННО, ТО $L(k)=(l_1+l_2+\cdots+l_s)/s$ ДАЕТ СРЕДНЕЕ ЧИСЛО
АДРЕСОВ, ПРИХОДЯЩИХСЯ НА ЗАПРОС. [нАПРИМЕР, В~(7) ИМЕЕМ $L(3)=1.75$.]

рАССМОТРИМ ТЕПЕРЬ СОСТАВНУЮ ХЕШ-ФУНКЦИЮ НАД $(m_1+m_2)\hbox{-БИТОВЫМ}$
ПОЛЕМ, ОБРАЗОВАННУЮ ОТОБРАЖЕНИЕМ ПЕРВЫХ $m_1$~БИТОВ С ПОМОЩЬЮ ОДНОЙ
ХЕШ-ФУНКЦИИ, А ОСТАВШИХСЯ $m_2$~БИТОВ---С ПОМОЩЬЮ ДРУГОЙ. пУСТЬ $L_1(k)$
И~$L_2(k)$---СООТВЕТСТВУЮЩИЕ СРЕДНИЕ КОЛИЧЕСТВА АДРЕСОВ, ПРИХОДЯЩИХСЯ НА
ЗАПРОС. нАЙДИТЕ ФОРМУЛУ, ВЫРАЖАЮЩУЮ~$L(k)$ (СРЕДНЕЕ ДЛЯ СОСТАВНОЙ ФУНКЦИИ)
ЧЕРЕЗ~$L_1$ И~$L_2$.

\ex[M24] (р.~рАЙВЕСТ.) нАЙДИТЕ ЗНАЧЕНИЯ ФУНКЦИИ~$L(k)$, ОПРЕДЕЛЕННОЙ В
ПРЕДЫДУЩЕМ УПРАЖНЕНИИ, ДЛЯ СЛЕДУЮЩИХ ФУНКЦИЙ КОМБИНАТОРНОГО ХЕШИРОВАНИЯ:
$$
{\hbox{(a) $m=3$, $n=2$}
\atop
\matrix{
0&0&*&\to&1\cr
1&*&0&\to&2\cr
*&1&1&\to&3\cr
1&0&1&\to&4\cr
0&1&0&\to&4\cr
}
}
\qquad
{\hbox{(a) $m=4$, $n=2$}
\atop
\matrix{
0&0&*&*\to&1\cr
*&1&*&0\to&2\cr
*&1&1&1\to&3\cr
1&0&1&*\to&3\cr
*&1&0&1\to&4\cr
1&0&0&*\to&4\cr
}
}
$$

\ex[м47] пРИДУМАЙТЕ НОВЫЕ ПОЛЕЗНЫЕ КЛАССЫ ФУНКЦИЙ
КОМБИНАТОРНОГО ХЕШИРОВАНИЯ, АНАЛОГИЧНЫЕ~(7).

\ex[м20] дОКАЖИТЕ, ЧТО ПРИ $v=3^n$ МНОЖЕСТВО ВСЕХ ТРОЕК ВИДА
$$
\set{ (a_1\ldots a_{k-1} 0 b_1\ldots b_{n-k})_3, (a_1\ldots
a_{k-1}1c_1\ldots c_{n-k})_3,
(a_1\ldots a_{k-1} 2 d_1\ldots d_{n-k})_3}, 1\le k\le n,
$$
ОБРАЗУЕТ ШТЕЙНЕРОВСКУЮ СИСТЕМУ ТРОЕК. пРЕДПОЛАГАЕТСЯ, ЧТО $a_i$, $b_i$,
$c_i$ И~$d_i$ РАВНЫ 0, 1 ИЛИ~2 И~$b_i+c_i+d_i\equiv 0 \pmod{3}$.

\ex[м32] (тОМАС кИРКМАН [{\sl Cambridge and Dublin Math~ Journal,\/}
{\bf 2} (1847), 191--204].) нАЗОВЕМ СИСТЕМОЙ ТРОЕК кИРКМАНА ПОРЯДКА~$v$ ТАКУЮ
ОРГАНИЗАЦИЮ $v+1$~ОБоЕКТОВ $\set{x_0, x_1,~\ldots, x_v}$ В ТРОЙКИ, ЧТО
КАЖДАЯ ПАРА~$\set{x_i, x_j}$, $i\ne j$, ВСТРЕЧАЕТСЯ РОВНО В ОДНОЙ ТРОЙКЕ;
ИСКЛЮЧЕНИЕ СОСТАВЛЯЮТ $v$~ПАР $\set{ x_i, x_{(i+1)\bmod v}}$, $0\le i<v$,
НЕ ВСТРЕЧАЮЩИХСЯ НИ В ОДНОЙ ТРОЙКЕ. нАПРИМЕР,
$$
\set{x_0, x_2, x_4}, \set{x_1, x_3, x_4}
$$
ЯВЛЯЕТСЯ СИСТЕМОЙ ТРОЕК кИРКМАНА ПОРЯДКА~4.

\item{a)}~дОКАЖИТЕ, ЧТО СИСТЕМА ТРОЕК кИРКМАНА МОЖЕТ СУЩЕСТВОВАТЬ
ТОЛЬКО ПРИ~$v\bmod 6= 0$ ИЛИ~4.
%%675
\item{b)}~дАНА ШТЕЙНЕРОВСКАЯ СИСТЕМА ТРОЕК~$S$ НАД $v$~ОБоЕКТАМИ
$\set{x_1,~\ldots, x_v}$.
дОКАЖИТЕ, ЧТО СЛЕДУЮЩЕЕ ПОСТРОЕНИЕ ПРИВОДИТ К ШТЕЙНЕРОВСКОЙ
СИСТЕМЕ ТРОЕК~$S'$ НАД $2v+1$~ОБоЕКТАМИ И КИРКМАНОВСКОЙ СИСТЕМЕ ТРОЕК~$K'$
ПОРЯДКА $2v-2$: В $S'$ ВХОДЯТ ВСЕ ТРОЙКИ ИЗ $S$ ПЛЮС
\itemitem{i)} $\set{x_i, y_j, y_k}$, ГДЕ $j+k\equiv i \pmod{v}$ И~$j<k$,
$1\le i, j, k\le v$;
\itemitem{ii)} $\set{x_i, y_j, z}$, ГДЕ $2j\equiv i \pmod{v}$, $1\le i,
j\le v$.
в СИСТЕМУ~$K'$ ВХОДЯТ ВСЕ ТРОЙКИ~$S'$, НЕ СОДЕРЖАЩИЕ $y_1$ И/ИЛИ~$y_v$.

\item{c)} дАНА КИРКМАНОВСКАЯ СИСТЕМА ТРОЕК~$K$ НАД ОБоЕКТАМИ
$\set{x_0, x_1,~\ldots, x_v}$, ГДЕ~$v=2u$. дОКАЖИТЕ, ЧТО СЛЕДУЮЩЕЕ
ПОСТРОЕНИЕ ПРИВОДИТ К ШТЕЙНЕРОВСКОЙ СИСТЕМЕ ТРОЕК~$S'$ НАД
$2v+1$~ОБоЕКТАМИ И КИРКМАНОВСКОЙ СИСТЕМЕ ТРОЕК~$K'$ ПОРЯДКА~$2v-2$: В $S'$
ВХОДЯТ ВСЕ ТРОЙКИ ИЗ $K$ ПЛЮС
\itemitem{i)}~$\set{x_i, x_{(i+1)\bmod v}, y_{i+1}}$, $ 0\le i <v$;
\itemitem{ii)}~$\set{x_i, y_j, y_k}$,.$j+k\equiv 2i+1 \pmod{v-1}$, $1\le j <k-1 \le v-2$, $1\le i \le v-2$;
\itemitem{iii)}~$\set{x_i, y_j, y_v}$, $2j\equiv 2i+1 \pmod{v-1}$, $1\le j \le v-1$, $1\le i \le v-2$;
\itemitem{iv)}~$\set{x_0, y_{2j}, y_{2j+1}}$, $\set{x_{v-1}, y_{2j-1}, y_{2j}}$, $\set{x_v, y_j, y_{v-j}}$, $1\le j <u$;
\itemitem{v)}~$\set{x_v, y_u, y_v}$.
в $K'$ ВХОДЯТ ВСЕ ТРОЙКИ ИЗ $S'$, НЕ СОДЕРЖАЩИЕ $y_1$ И/ИЛИ $y_{v-1}$.

\item{d)}~иСПОЛЬЗУЙТЕ ПРЕДЫДУЩИЕ РЕЗУЛЬТАТЫ ДЛЯ ДОКАЗАТЕЛЬСТВА ТОГО,
ЧТО КИРКМАНОВСКАЯ СИСТЕМА ТРОЕК ПОРЯДКА~$v$ СУЩЕСТВУЕТ ПРИ ЛЮБОМ $v\ge0$,
ИМЕЮЩЕМ ВИД $6k$ ИЛИ~$6k+4$, А ШТЕЙНЕРОВСКАЯ СИСТЕМА ТРОЕК НАД
$v$~ОБоЕКТАМИ СУЩЕСТВУЕТ ПРИ ЛЮБОМ $v\ge1$, ИМЕЮЩЕМ ВИД~$6k+1$ ИЛИ~$6k+3$.

\ex[м25] в ТЕКСТЕ ОПИСАНО ИСПОЛЬЗОВАНИЕ ШТЕЙНЕРОВСКОЙ СИСТЕМЫ ТРОЕК В
СВЯЗИ С ВКЛЮЧАЮЩИМИ ЗАПРОСАМИ; ЧТОБЫ ИСПОЛЬЗОВАТЬ ИХ И ДЛЯ
БАЗОВЫХ ЗАПРОСОВ, ЕСТЕСТВЕННО ВВЕСТИ СЛЕДУЮЩЕЕ ПОНЯТИЕ. \dfn{пОПОЛНЕННОЙ
СИСТЕМОЙ ТРОЕК} ПОРЯДКА~$v$ НАЗЫВАЕТСЯ ТАКАЯ ОРГАНИЗАЦИЯ $2v$~ОБоЕКТОВ
$\set{x_1,~\ldots, x_v, \bar x_1,~\ldots., \bar x_v}$ В ТРОЙКИ, ЧТО КАЖДАЯ
ПАРА ОБоЕКТОВ ВСТРЕЧАЕТСЯ РОВНО В ОДНОЙ ТРОЙКЕ; ИСКЛЮЧЕНИЕ СОСТАВЛЯЮТ ПАРЫ
ДОПОЛНИТЕЛЬНЫХ ЭЛЕМЕНТОВ~$\set{x_i, \bar x_i}$, НЕ ВХОДЯЩИЕ НИ В ОДНУ
ТРОЙКУ. нАПРИМЕР,
$$
\set{x_1, x_2, x_3},\quad, \set{x_1, \bar x_2, \bar x_3},\quad
\set{\bar x_1, x_2, \bar x_3}, \quad \set{\bar x_1, \bar x_2, x_3}
$$
ЕСТЬ ПОПОЛНЕННАЯ СИСТЕМА ТРОЕК ПОРЯДКА~3.

дОКАЖИТЕ, ЧТО ПОПОЛНЕННАЯ СИСТЕМА ТРОЕК ПОРЯДКА~$v$ СУЩЕСТВУЕТ ДЛЯ
ЛЮБОГО~$v\ge0$, НЕ ИМЕЮЩЕГО ВИДА~$3k+2$.

\ex[м23] в ПРОДОЛЖЕНИЕ УПР.~11 ПОСТРОЙТЕ ПОПОЛНЕННУЮ СИСТЕМУ
\emph{ЧЕТВЕРОК} ПОРЯДКА~7.

\ex[м25] пОСТРОЙТЕ СИСТЕМУ ЧЕТВЕРОК, СОДЕРЖАЩУЮ $v=4^n$~ЭЛЕМЕНТОВ,
 АНАЛОГИЧНУЮ СИСТЕМЕ ТРОЕК ИЗ УПР.~9.

\ex[25] оБСУДИТЕ ЗАДАЧУ УДАЛЕНИЯ УЗЛОВ ИЗ ПОЧТОВЫХ ДЕРЕВЬЕВ, ПОДОБНЫХ
ИЗОБРАЖЕННОМУ НА РИС.~45.

%%676

\bye