Основные способы обработки большого количества текстовой информации (стр. 2 из 6)

Если элементы списка упорядочены по ключу, индекс обычно содержит не ссылки на каждый элемент, а ссылки на блоки элементов, внутри которых можно выполнить поиск или сканирование.

Хранение ссылок на блоки элементов, а не на отдельные элементы в значительной степени уменьшает размер индекса. Причем даже в этом случае индекс часто оказывается слишком большим для поиска и поэтому используется индекс индекса. В больших списках может быть больше двух уровней индекса.

Для ускорения поиска сегменты нижнего уровня индекса могут находиться среди данных, на которые они указывают. Например, в файле на диске обычно имеется на каждом цилиндре индекс дорожек, содержащий ссылки на записи, хранящиеся на этом цилиндре.

Индексно-последовательные файлы представляют собой наиболее распространенную форму адресации файлов.

1.5. Индексно-произвольная организация

Произвольный (непоследовательный) список можно индексировать точно так же, как и последовательный список. Однако при этом требуется значительно больший по размерам индекс, так как он должен содержать по одному элементу для каждого элемента списка, а не для блока элемента. Более того, в нем должны содержаться полные абсолютные (или относительные) адреса, в то время как в индексе последовательного списка адреса могут содержаться в усеченном виде, так как старшие знаки последовательных адресов будут совпадать.

По сравнению с произвольным доступом индексно-последовательный список более экономичен как с точки зрения размера индекса, так и с точки зрения времени, необходимого для поиска в нем. Произвольные списки в основном используются для обеспечения возможности адресации элементов списка с несколькими ключами. Если список упорядочен по одному ключу, то он не упорядочен по другому ключу. Для каждого типа ключей может существовать свой индекс: для упорядоченных ключей индексы будут более длинными, так как должны будут содержать по одному данному для каждого элемента. Ключ, который чаще всего используется при адресации списка, обычно служит для его упорядочения, поскольку наиболее быстрый доступ возможен в том случае, когда применяется короткий последовательный индекс.

Аналогия с картотекой библиотеки скорее соответствует индексно-последовательному доступу, чем произвольному. В картотеке используются два ключа - название книги и фамилия автора, и, как правило, ни тот, ни другой ключ не применяются при упорядочивании книг на полках, следовательно, оба индекса должны содержать по элементу для каждой книги. Книги упорядочиваются по номеру в каталоге. После того как пользователь нашел номер интересующей его книги в каталоге, он отыскивает книгу на рядах полок. В каждом ряду обычно указаны начальный и конечный номера книг в нем. Пользователь сравнивает номер, который он получил из каталога (индекса), с номерами, указанными в рядах. Найдя нужный ряд, он ищет полку, на которой стоит книга. Аналогично ЭВМ выполняет поиск в файлах, начиная, например, с главного индекса, далее просматривая индекс цилиндров, а затем индекс дорожек.

В картотеке библиотеки не указывается физическое местоположение книги на полках. Вместо этого в ней содержится номер в каталоге, который может рассматриваться как символический адрес. Символический адрес указывается потому, что книги переставляются, и, если бы использовался физический адрес, это потребовало бы частой корректировки картотеки библиотеки. По той же причине в индексно-произвольных списках часто используются символические, а не абсолютные адреса. При добавлении новых или удалении старых элементов изменяется местоположение остальных элементов. Если имеется несколько ключей, то индекс вторичного ключа может содержать в качестве выхода первичный ключ записи. При определении же местоположения элемента по его первичному ключу можно использовать какой-нибудь другой способ адресации. По этому методу поиск осуществляется медленнее, чем поиск, при котором физический адрес элемента определяется по индексу. В списках, в которых положение элементов часто изменяется, символическая адресация может оказаться предпочтительнее.

Другой причиной для непоследовательного размещения элементов могут служить частые изменения списка. Интенсивное включение новых и удаление старых элементов в последовательно упорядоченном списке связано с большими трудностями и значительным расходом машинного времени. Если бы книги хранились на полках библиотеки в алфавитном порядке, то обеспечение такого порядка занимало бы излишне много времени, так как каждый раз при добавлении новой книги требовалось бы передвигать много книг.

1.6. Адресация с помощью ключа, эквивалентного адресу

Известно много методов преобразования ключа непосредственно в адрес в файле. В тех случаях, когда такое преобразование возможно, оно обеспечивает самую быструю адресацию; при этом нет необходимости организовывать поиск внутри файла или выполнять операции с индексами.

Наиболее простое решение задачи адресации - указывать во входном сообщении относительный машинный адрес запрашиваемой записи. В некоторых ранних банковских системах номера счетов видоизменялись так, чтобы новый номер или его часть являлись бы адресом элемента для данного счета в списке. Таким образом, адрес был равен ключу или определялся по нему простым способом.

Во многих приложениях такой прямой подход невозможен. Номера изделий на заводе не могут изменяться только ради удобства использования ЭВМ, поскольку для работников фирмы они имеют в запросе определенный смысл.

Иногда во входном сообщении используется внутренний машинный код; при этом не требуется, чтобы он был равен номеру клиента или номеру изделия. Например, адрес записи счета в файле может печататься в банковской расчетной книжке клиента сберкассы и указываться далее в запросе с терминала.

Такие схемы называются прямой адресацией, хотя обычно этот термин используется в более широком смысле для обозначения любого алгоритма, преобразующего ключ непосредственно в машинный адрес.

1.7. Алгоритм преобразования ключа в адрес

Способ преобразования ключа в адрес дает почти ту же скорость поиска, что и способ, в котором используется ключ, эквивалентный адресу. В некоторых приложениях адрес может быть вычислен на основе идентификаторов объекта, таких как адрес улицы и номер дома или номер рейса и его дата. Для таких приложений рассматриваемый метод адресации является наиболее простым и быстрым. Чаще всего данный способ применяется в диалоговых системах, где критичным является время поиска в списке, и называется хешированием, перемешиванием или рандомизацией.

К недостаткам данного способа относится малое заполнение списка: в списке остаются свободные участки, поскольку ключи преобразуются не в непрерывное множество адресов.

При этом методе вся область памяти для размещения списка делится на участки – бакеты размером несколько десятков элементов списка. Сам алгоритм хеширования по первичному ключу определяет, в отличие от других методов, не адрес одного элемента списка, а адрес бакета, содержащего целую группу элементов. При размещении элемента в списке каждый новый элемент добавляется в конец уже имеющихся в бакете элементов; при поиске - после определения адреса бакета поиск нужного элемента выполняется методом последовательного сканирования.

Алгоритм хеширования выполняется в три этапа:

1) первый этап выполняется только для нечисловых значений ключей и заключается в замене их числовыми значениями. Для этого составляется таблица соответствия символов алфавита, в котором записываются значения ключей, с цифрами от 1 до 9. Затем каждый символ нечислового значения ключа заменяется своим цифровым эквивалентом. Например, если нечисловые значения ключей определены на русском алфавите, такая таблица будет иметь вид:

а 1 и 9 р 8 ш 7

б 2 й 1 с 9 щ 8

в 3 к 2 т 1 э 9

г 4 л 3 у 2 ю 1

д 5 м 4 ф 3 я 2

е 6 н 5 х 4 ь 3

ж 7 о 6 ц 5 ъ 4

з 8 п 7 ч 6 ы 5

Очевидно, разным символам присваивается один цифровой код, что ведет к потере информации.

Тогда, например, для ключа со значением КОМПЬЮТЕР цифровой эквивалент имеет вид 264731168.

2) формируется относительный адрес элемента списка. Для этого числовое значение адреса приводится к порядку, равному порядку адресов памяти, где размещен список. Например, список размещен на диске в кластерах с номерами от 10 до 999, т.е. в адресах с порядком, равным 3. Тогда для ключа, полученного на предыдущем этапе, надо выполнить такое преобразование, чтобы из девятизначного числа превратить его в трехзначное. Подобные преобразования выполняются разными способами. Рассмотрим некоторые из них:

- возведение в квадрат. Числовое значение ключа возводится в квадрат и в полученном числе по центру выбирается нужное количество цифр. Для нашего случая 264731168² = 70082591310644200, центральными цифрами являются 131. Таким образом, относительный адрес для ключа КОМПЬЮТЕР равен 131,

- метод складывания (не путать со сложением). Числовое значение ключа делится на три части: средняя часть (размещается по центру) имеет количество цифр, равное порядку адресов памяти, где размещен список; оставшиеся правая и левая части «заворачиваются» к средней и совпавшие цифры складываются до образования цифр. Например, для ключа 264731168 этот способ дает следующий результат:

264 731 168

левая средняя правая