2.5 Многоключевой поиск
В таблицах символов обычно существует взаимно однозначное соответствие между ключевым словом и связанным с ним значением. Последнее (т.е. значение) может быть абсолютным или относительным адресом некоторой переменной, участвующей в программе. Иная ситуация наблюдается в разного рода справочниках, списках заказчиков и других документах, содержащих информацию относительного характера. В них, как правило, каждый запоминаемый элемент данных (ЗЭД) снабжается несколькими ключевыми словами, или дескрипторами, причем одно и то же ключевое слово может присутствовать в произвольном количестве записей. Например, в анкетных файлах атрибут “пол” (представленный в двоичной форме), принимает одинаковые значения, по меньшей мере, в половине записей.
Для тех задач, в которых часто возникает необходимость в выборке всех элементов, отвечающих заданному ключу, наиболее подходят последовательные методы поиска. Такова, в частности, задача селективного отбора информации.
Селективный отбор информации является одной из форм обслуживания, предоставляемого современными библиотеками.
Абоненты (библиотек) описывают совокупность интересующих их предметов в виде логического выражения, содержащего набор соответствующих дескрипторов. ЭВМ одновременно обрабатывает запросы большого количества абонентов, сравнивая представленные ими данные с дескрипторами, записанными в документах. При этом могут использоваться различные функции, с помощью которых устанавливается степень сходства сравниваемых дескрипторов.
Однако задача селекции (при всей ее важности) является не слишком подходящим объектом приложения методов хеширования. Сложность их реализации связана с тем, что искомые данные обычно размещаются на МЛ (МД), поскольку это самый дешевый носитель информации. Даже если применяются МД, то и в этих случаях оказывается, что возможность одновременного поступления большого количества запросов делает последовательную обработку наиболее выгодной с точки зрения общих затрат.
Если обращение к БД происходит нерегулярно, причем запросы поступают поодиночке, то адресация по содержанию имеет явные преимущества по сравнению с последовательным поиском. В качестве примера можно указать оформление банковских операций, автоматическая коммутация сообщений в больших организациях, поиск архивных документов, управление БД в САПР, исследования в области ИИ, и т.д.
В связи с широким применением удаленных терминалов, находящихся в частном пользовании, возникает необходимость в реорганизации структуры центральных БД по принципу ассоциативной адресации. Только при этом условии обработку запросов можно будет производить в интерактивном режиме. Естественно, в ЗУ, используемых для хранения в таких БД, необходимо предусмотреть соответствующие средства адресации. В 80-е г.г. прошлого века массовая память такого типа строилась на базе МД (могут быть МОД… и др.).
Учитывая важность задач такого типа, рассмотрим основные подходы к организации поиска информации по многим ключевым словам (многоключевой поиск).
Рассмотрим некоторые стандартные методы многоключевого поиска.
2.5.1 Списки и списочные структуры
Любой упорядоченный набор ЭД можно рассматривать как список.
Если элемент списка сам по себе является списком, то такую конструкцию называют списочной структурой. Продолжая глубину вложения, можно получать все более сложные списочные структуры.
В памяти список или списочные структуры хранятся в виде отдельной записи, к которой надо предусмотреть удобный доступ.
В списке выделяется отдельный элемент (обычно – первый), именуемый заголовком, которому присваивается имя списка. Имена в ходе записи могут сортироваться – в этом случае поиск можно осуществлять при помощи стандартных методов (широко известных в литературе). Для поиска заголовков удобнее использовать методы хеширования. При этом отпадает необходимость в предварительной сортировке имен. Дополнительные элементы могут присоединяться к списку различными способами (самый простой – использование последовательно расположенных ячеек).
Примером списка, элементы которого хранятся не последовательно, а разбросаны по некоторой области памяти, является цепочка резервных ячеек – вычисленный адрес при этом играет роль заголовка списка. В ходе каждого обращения к списку последовательных адресов
- либо вычисляется при помощи пробинга;
- либо определяется при помощи указателей.
Любая совокупность элементов данных, связанных указателями, называется связанным списком.
Однонаправленный (связанный) список позволяет двигаться вдоль него только в одном направлении.
В двунаправленных списках (называемых также симметричными) каждая запись содержит два указателя (первый – со следующим ЭД, второй – с предыдущим ЭД). Это дает возможность просматривать содержимое списка в обоих направлениях.
Однонаправленный список, последний элемент которого связан указателем с его заголовком, называют циклическим или кольцевым.
Для образования списочной структуры необходимо, чтобы в некоторых ее элементах содержалось минимум по два указателя. Такие элементы называются вершинами.
Списочную структуру, которая начинает ветвиться из вершины, именуемой корнем, и в которой отсутствуют циклические цепочки элементов, будем называть деревом.
В бинарном дереве (рисунок 2.8) из каждой вершины всегда исходят по две ветви. Исключение составляют лишь последние элементы.
В общем случае списочная структура, содержащая циклические участки, представляет собой граф.
Существуют различные методы выборки информации из структур, описываемых графами. Имеются также алгоритмы, позволяющие упрощать форму графов (рассматривать их пока не будем).
Мультисписки
Структуры, в которых присутствуют ЭД, входящие в несколько списков, т.е. содержащие независимые цепочки, которые проходят через один и тот же набор элементов, называют мультисписками.
Их нельзя описывать связанными графами, т.к. общие элементы в них не являются вершинами в обычном понимании.
Каждый частный список представляет собой простую неветвящуюся цепочку, которая начинается с заголовка.
Мультисписки строятся по тому же принципу, что и таблицы хеширования. Чтобы различать отдельные цепочки, в ячейках наряду с указателями помещаются также идентификаторы заголовков соответствующих частей списков.
В структуре мультисписка имеется справочник, в котором хранятся все ключевые слова, указатели первых элементов каждого списка также числа, задающие количество элементов в списках (рисунок 2.10). Справочник может помещаться в отдельной области памяти. Ключевые слова подвергаются сортировке, либо распределяются по ячейкам таблицы путем хеширования адресов (может быть и другой вариант; рассмотрим его несколько позже).
На рисунке 2.10 записи представлены в виде небольших кружков (?). Область памяти изображена двумерной, чтобы показать, как распределены в ней цепочки элементов.
Если максимальное количество ключевых слов в записи = m, то размер ячейки памяти должен быть таким, чтобы в ней наряду с данными и управляющими битами могли поместиться m - идентификаторов и m - указателей. Последние связывают ячейку со следующими за ней ячейками во всех потенциально возможных цепочках.
Обычно мультисписковая структура формируется в процессе записи информации. Вначале устанавливается местонахождение заголовков, содержащих ключевые слова нового элемента.
Затем – прослеживаются цепочки, идущие от заголовков. В последнюю запись каждой из цепочек заносится указатель, представляющий собой адрес ячейки нового элемента. Новый элемент становится последним членом всех этих цепочек.
Наиболее распространенным методом выборки по многим ключам является комбинационный поиск, т.е. поиск по совокупности двух или более ключевых слов.
Предположим, что нам потребовалось выбрать из списка, показанного на рисунке 2.10, все записи, которые соответствуют комбинации ключей X и W. Просмотр ключей целесообразно вести вдоль более короткой цепочки (в данном случае – это по ключевому слову X). Поиск сводится к проверке – содержится в данной записи ключ W или нет. Естественно, это возможно лишь при условии, что вместе с каждым элементом данных хранятся все его ключевые слова или идентификаторы.
Отдельные списки, входящие в мультисписок, могут достигать достаточно значительного размера. С учетом того, что при добавлении к списку новых элементов приходится просматривать всю ранее сформированную цепочку, продолжительность этой операции оказывается очень большой.
Аналогичные трудности возникают и при удалении элементов. С другой стороны, в рамках принятой методики поиска невозможно сократить количество проверок.
Т.о. в данном случае единственно возможное решение состоит в ограничении длины цепочек. Необходимость в этом может быть вызвана и другими причинами, в частности, ограниченностью буферных зон в ОП.
Возьмем в качестве примера мультисписок на рисунке 2.10. Его можно разделить на фрагменты, длина каждого из которых не превышает максимальной фиксированной величины.
При этом в справочник мультисписка необходимо занести указатели всех частичных списков. Каждый новый элемент добавляется к последнему частичному списку (фрагменту), гораздо более короткому, чем соответствующая полная цепочка мультисписка обычного типа.
В так называемых блочных мультисписках предельная длина не фиксируется, однако каждая из частичных цепочек должна располагаться в пределах одного физического блока памяти – например, дорожки (ячейки, клетки и др.) – рисунок 2.12.
Достоинством подобной схемы является то, что при буферизации стандартного блока в ОП пересылаются все данные, содержащиеся в некотором частичном списке, причем по справочнику можно определить, какие блоки можно исключать из рассмотрения.
Например, если необходимо выполнить комбинационно поиск по аргументу “X и Y” в списке, показанном на рисунке 2.12, то ячейку А3 можно не проверять, т.к. в ней нет записей с ключом Y (только с ключами W и Z). Кроме того, продолжительность поиска можно сократить, выбирая для просмотра ячейки, относящиеся к наиболее коротким цепочкам – в приведенном примере – ячейки 0 и 1 в цепочке Y или ячейка 2 в цепочке X.
Блочная последовательная структура
Изображена на рисунке 2.13. Она сочетает особенности блочного мультисписка и клеточной организации. В справочник заносятся только индексы блоков, в которых имеются записи, содержащие определенные ключевые слова. В этом случае необходимо производить последовательный опрос соответствующих ячеек. Добавление и удаление ЭД в рамках такой структуры выполняется очень просто, и если одна ячейка состоит из небольшого количества записей, то поиск осуществляется достаточно быстро.
Инвертированные списки (или инвертированные файлы)
Во всех предыдущих способах многоключевого поиска ключевые слова располагаются в самой записи. В инвертированном списке адреса всех записей, связанных с данным ключевым словом, хранятся в справочнике (рисунок 2.14).
Т.о. инвертированный список является частным случаем блочной последовательной структуры, каждый блок которой состоит из одной ячейки.
При построении инвертированного списка можно воспользоваться некоторыми рассмотренными ранее методами хеширования. Например, справочник списка можно построить аналогично индексной таблице хеширования. При этом ключевые слова играют роль v (выч. адресов), а адреса записей соответствуют указателям элементов, расположенных во внешней памяти. Вариант практической реализации подобного списка рассмотрим несколько позже.
Если ключевые слова в справочнике списка рассортированы в определенном порядке, то для их поиска можно применить любой стандартный метод, а указатели разместить в следующих друг за другом ячейках памяти.
Основное достоинство инвертированного списка заключается в том, что вся информация, участвующая в процессе комбинационного поиска, занимает сравнительно немного места. Благодаря этому справочник можно хранить в ОП (по крайней мере, для файлов не очень большого размера).
Это позволяет сократить до минимума механические операции типа перемещения головок на МД, выполняя все подготовительные операции, предшествующие выборке в ЦП.
2.5.2 Использование составных ключевых слов в процедурах хеширования
Рассмотренная выше методика многоключевого поиска основана на выделении совпадающих элементов в списках, связанных с различными ключевыми словами.
Можно предложить и другой подход, рассматривая все ключи, входящие в некоторую запись, как единое составное ключевое слово. Если задается полный набор ключевых слов, то поиск можно осуществить по той же схеме, что и с одним ключевым словом. Сложнее, если часть ключей не задана.
Хеширование по всем сочетаниям ключевых слов
Наиболее простой способ организации комбинационного поиска состоит в том, что хеширование записей производится по всем возможным сочетаниям ключевых слов. Этот метод обеспечивает высокое быстродействие, но требует одновременно и самых больших затрат памяти.
Действительно, если в запись входит n ключевых слов, то существует
различных комбинаций, для каждой из которых в хеш-таблице должна храниться копия записи.
Стандартная процедура формирования хеш-адреса по составному ключу такова:
Пусть B( k1 ), B( k2 ), …, B( kk ) – битовые строки, соответствующие ключевым словам k1, k2, …,kk, причем все они получены при помощи одного и того же алгоритма хеширования и по длине совпадают с хеш-адресом. Последний (т.е. хеш-адрес) в этом случае можно определить как битовую строку B, которая вычисляется по следующей формуле:
где символ 
– операция “Исключающее ИЛИ”, т.е. операцию “+” одноименных разрядов по модулю 2.
В рассмотренном ранее методе комбинационного хеширования объем хеш-таблицы можно несколько сократить, если разделить все ключевые слова на группы по функциональному признаку.
Предположим, что x1, x2, x3 являются значениями трех различных атрибутов A1, A2, A3 соответственно (например, “национальность”, “возрастная группа” и “местожительство” граждан). Если задается одна из величин xi, то уже по ее виду можно установить, чему равно i (1, 2 или 3). Это позволяет однозначно идентифицировать каждый из компонентов составного ключевого слова, и каждому типу комбинации ключей поставить в соответствие отдельную таблицу хеширования.
В нашем примере отдельные таблицы должны быть сформированы для составных слов 
.
Обработка таких частичных хеш-таблиц значительно упрощается, т.к. цепочки резервных ячеек существенно короче, чем в общей таблице, хеширование в которой осуществляется по всем комбинациям ключевых слов.
Последовательный перебор значений ключевого слова
Хеш-таблицу можно сократить за счет увеличения количества операций поиска, выполняя хеширование лишь по тем комбинациям ключевых слов, появление которых представляется наиболее вероятным. Для сочетаний, не вошедших в это число, применяются более сложные процедуры поиска.
Возможны и другие способы. Например, способ, который состоит в том, что хеш-таблицы строятся только для некоторых, наиболее длинных, сочетаний ключевых слов. Если аргументом поиска является укороченная комбинация, в которой часть ключей не задана, то считается, что значения отсутствующих атрибутов произвольны.
В этом случае этим атрибутам поочередно присваиваются все возможные значения, и по каждому полученному таким образом сочетанию ключей производится отдельный поиск.
Если незаданные атрибуты могут принимать только несколько конкретных значений, то предложенный метод поиска оказывается достаточно эффективным.
Предположим, например, что составным атрибутом служит тройка (“пол”, А2, А3). Если хеширование записей производилось по всем элементам этой тройки, то при незаданном значении атрибута “пол” достаточно лишь дважды выполнить стандартную процедуру поиска:
- по хеш-адресу, соответствующему комбинации (мужской, А2, А3);
- по хеш-адресу, соответствующему комбинации (женский, А2, А3);
Этот метод неприменим, если отсутствующие элементы могут принимать множество значений, из-за чего количество возможных сочетаний оказывается слишком велико.
Однако эту трудность можно частично преодолеть, например, следующим образом (методом).
Сцепленные хеш-адреса
Хеш-адрес представляет собой битовую строку. Учитывая это, его можно формировать таким образом, чтобы каждый из ключей, входящих в соответствующее ключевое слово, определял свою группу битов. Полученные биты сцепляются, образуя полный хеш-адрес. Например, если каждому ключевому слову в адресе соответствует ровно 2 бита, то функция хеширования от этого ключа может принимать лишь 4 различных значения: (00, 01, 10, 11).
Следовательно, если в составном аргументе не заданы значения R ключевых слов, то поиск производится только для 4R сочетаний битов в соответствующих группах.
Можно предполагать, что сцепленные адреса распределяются по таблице менее равномерно, чем при обычном хешировании, в результате чего скорость поиска несколько снижается. Однако это окупается возможностью реализовать таким способом достаточно эффективную процедуру многоключевого поиска.