Методы ускорения доступа к данным

 

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

Эти же методы необходимы при организации доступа к ин­формации по нескольким ключевым атрибутам одновременно.

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

Адресная функция

Расстановка записей происходит в соответствии с так на­зываемой адресной функцией (другие общеупотребительные ее названия - "рандомизирующая функция" или"хэш-функция" от hashing – рассеянная память от глагола to hash – крошить рубить и делать из этого месиво).

Идея хеширования состоит в использовании некоторой частичной информации, полученной из ключа. В качестве основы поиска. Вычисляется хеш-адрес F(p) и используется для проведения поиска.

Рассмотрим знаменитый пример «парадокс дня рождения». Который обсуждался математиками в 30-е годы. Например, в компании из 23 человек более всего вероятно совпадение дней рождения у двух человек, чем то что у всех дни рождения окажутся различеиные. Иными словами, если выбрать случайную функции, отображающую 23 ключа в таблицу размером 365, вероятность, что никакие два ключа не будут отображены в одно и тоже место таблицы, составляет 0,4927, т.е. менее половины. Этот пример предупреждает нас, что вероятно найдутся различныеключи Pi ¹ Pj при которых F(pi)=F(pj). Такое событие именуется коллизией. Для разрешения коллизий разработаны некоторые подходы.

Поэтому для использования хеширования программист должен решить две практических задачи – выбрать хеш-функцию f(p) и способ разрешения коллизий.

Адресной функцией или хеш функциенй называется зависимость

i= f(p),

где i— номер (адрес) записи;

р - значение ключевого атрибута в записи.

К функции f предъявляются следующие требования:

• она должна быть задана аналитически и вычисляться до­статочно быстро;

•ключевые атрибуты, подчиняющиеся произвольному рас­пределению, функция должна переработать в равномер­но распределенные номера записей; это условие обычно соблюдается приближенно;

• число записей-синонимов или коллизий должно составлять 10-20% от общего числа записей.

Построение хеш-функции.

Предположим, что хеш-функция имеет не более М различных значений, причем для всех ключей Р

0 <=F(p) < М. (1)

Известно достаточно много адресных функций, хорошо соответствующих этим требованиям. Простейшая адресная функция имеет вид:

i=р-а, где а - константа.

Пусть известны минимальное значение ключевого атрибута в массиве р' и максимальное значение р ". Тогда а = р' - 1. Необходимый участок памяти для данных оценивается в р" - р' +1 запись. Записи-синонимы связываются в цепочки с помощью адресов связи, они занимают дополнительную (ре­зервную) память.

Пример размещения записей с ключами 13,11,14,11,15,18, 14,16 согласно адресной функции i = р - а показан на рис. 6.1

		Æ		Æ	Æ		Æ

 

 

Рис. 6.1. Организация записей в соответствии с адресной функцией i = р - а

При доступе к записи с ключом q вычисляется i= f(q) и про­изводится обращение к i-й записи. При необходимости с по­мощью адресов связи извлекаются все синонимы.

Недостаток адресной функции вида i = р - а - большой объем неиспользуемой памяти, если р "- р 'много больше, чем количество записей М.

В реальном файле ключи часто избыточны, а потому нужно иметь это ввиду при поиске хеш-функции, чтобы не допустить создания кластеров из близких ключей с целью уменьшения количества коллизий (cинонимов).

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

Рассмотрим, например, десятизначные ключи на десятичном компьютере. Положить, М = 1000 в качестве f(p) используем три цифры, выбранные около средины двадцати-значного произведения Р х Р. Этот метод должен давать довольно равномерное распределение значений между 000 и 999 с низкой вероятностью коллизий; однако эксперименты с реальными данными показывают, что такой метод “середины квадратов" неплох при условии, что ключи не имеют большого количества нулей слева или справа.

Многочисленные тесты показали хорошую работу двух основных типов хеш функций, один из которых основан на делении, а другой — на умножении.

Метод деления весьма прост; мы просто используем остаток от деления на М

i= ОСТ (р/m). (2)

Здесь m - целое число; ОСТ - остаток от деления р на m.

Вычисление i производится с помощью специального оператора, например i = p mod m. (язык Паскаль)

Значение m принимается равным простому числу, которое непосредственно больше либо непосредственно меньше числа записей М.

В этом случае очевидно, что, при четном М значение F {p) будет чет­ным при четном p и нечетным — при нечетном, что приведет к значительному смещению данных во многих файлах. Еще хуже обстоят дела, если М представля­ет собой степень основания счисления компьютера, поскольку при этом p mod М представляет собой несколько цифр числа p, расположенных справа, и не зависит от остальных цифр. Точно так же можно показать, что М не должно быть кратно трем поскольку при буквенных ключах два из них, отличающиеся только перестановкой букв, могут давать числовые значения с разностью, кратной 3 (это происходит, поскольку 2²ⁿ mod 3 = 1 и 10ⁿ mod 3 =1). В целом, следует избегать значений М, делящих r^k ± а, где k и а — небольшие числа, а г — "основание системы счисления" набора используемых алфавитно-цифровых символов (обычно r = 64, 256 или 100), так как остаток от деления по модулю на такие значения М зачастую представляет простую суперпозицию цифр ключа. Приведенные рассуждения при­водят к мысли, что лучше всего использовать в качестве М простое число, такое, что r^k ¹ ±а (по модулю М) при небольших k и а. В большинстве случаев подобный выбор вполне удовлетворителен.

Рассмотрим работу данной функции на примере. Как уже говорилось, значение m принимается равным простому числу.

Выделяются 2 зоны памяти - основная и резервная. Основ­ная зона содержит m записей. Резервная зона предназначена для размещения записей синонимов.

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

Например, для массива ключей со значениями 17, 9, 4, 14, 25, 21, 20, 11 необходимо выбрать m=7, поскольку М=8 (возможно также m=19). Содержимое основной и резервной зон иллюстриру­етрисунок. Резервная зона заполняется последовательно. При по­иске значения, например р=11, вычисляется i = ОСТ(11/7)=4, и да­лее последовательно сравниваются 4 и 11, 25 и 11 и т.д. В рассмат­риваемом примере число записей-синонимов составляет 3/8.

Мультипликативная схема хеширования также просто реализуется, однако сло­жнее описывается, поскольку мы работаем с дробями, а не с целыми числами. Пусть w размер машинного слова[6]. Целое число А можно рассматривать как дробь A/w, если представить, что разделяющая точка (точка, разделяющая целую и дробную части числа в различных системах счисления, например десятич-1ая точка) расположена слева от числа. Метод состоит в выборе некоторой целой кнстанты А, взаимно простой с w, после чего можно положить

F(p) = [M((A/p)mod 1) ]. (3)

В этом случае обычно на двоичном компьютере в качестве М используется степень двойки, так что F(p) состоит из старших битов правой половины произведения A*Р

Вычисленное значение F(p) помещается в регистр А. На многих компьютерах умножение выполняется значи­тельно быстрее деления.

По сути, предложенный метод представляет собой обобщение метода (2), по­скольку можно, например, в качестве А использовать приближение w/M; умно­жение на обратную величину зачастую происходит быстрее деления. Технология (3) практически совпадает с методом середины квадрата, но с одним важным отличием: в дальнейшем мы увидим, что умножение на подходящую константу имеет много полезных свойств.

Одна из привлекательных черт мультипликативной схемы заключается в от­сутствии потери информации в (3); мы в состоянии восстановить значение p по содержимому регистра по окончании работы (3). Дело в том, что А и w взаимно просты и при помощи алгоритма Евклида можно найти константу А', такую, что АА' mod w = 1; отсюда следует, что p = (A'(A.pmod w)) mod w. Другими словами, если обозначить через F(p) содержимое регистра Х непосредственно перед выполнением командой сдвига, то для

Р₁¹Р₂ повлечет h(Р₁) ¹ h(Р₂) (4)

Конечно, h(p) принимает значения в диапазоне от 0 до w-1, поэтому ее нельзя счи­тать сколь-нибудь хорошей хеш-функцией. Однако она может быть весьма полезной в качестве рассеивающей функции (scrambling function), т. е. функции, удовлетворя­ющей (4) и обычно рандомизирующей ключи. Такая функция может эффективно использоваться и в связи с алгоритмами поиска по дереву (если порядок ключей не имеет значения), поскольку она предотвращает возможность построения вырожденного дерева в случае поступления ключей в порядке возра­стания. Рассеивающая функция может быть применена и для цифрового поиска по дереву

Другое аспект мультипликативного хеш-метода в том, что он хоршо работает с неслучайными файлами. Например, часто множества ключей представляют собой арифметические прогрессии, когда в файле содержатся ключи {Р, Р+d, Р+2d,..., Р+td}. Например, рассмотрим имена типа {PART1, PART2, PART3} или {TYPEA, TYPEB, TYPEC}. Мультипликативный хеш-метод преоб­разует арифметическую прогрессию в приближенно арифметическую прогрессию

f{K), f{K + d), f(K + 2d),... различных хеш-значений, уменьшая число коллизий. По сравнению со случайной ситуацией. Метод деления обладает тем же свойством.

На рис. 37 проиллюстрировано мультипликативное хеширование в частном случае. Предположим, что A/w приближенно равно золотому сечению f ^-1 = (Ö5- l)/2»0.6180339887; при этом последовательность значений

f(P), f(P + 1), f(P +2),... ведет себя точно так же, как последовательность хеш-значений f(0), f(l), f(2),..., так что естественным становится следующий эксперимент: на отрезке [0..1] последовательно отмечаем точки {f^-1},{2f^-2}, {3f^-3},.... где {х} означает дробную часть числа х (т.е. х - ½х ½или ж mod 1) Как показано на рис.37, эти точки достаточно хорошо отделены одна от другой каждая вновь добавляемая точка попадает в один из наибольших оставшихся интервалов и делит его в соответствии с золотым сечением!

Это замечательное свойство золотого сечения в действительности является част ным случаем более общей теоремы, предложенной Хьюго Штейнгаузом (Hugo Stein haus) и впервые доказанной Верой Туран Шош (Vera Turan Sos)

Теорема S. Пусть q — произвольное иррациональное число. При размещена точек {q }, {2 q },..., {пq } на отрезке [0..1] длины n + 1 образовавшихся отрезков имеют не более трех различных значений. Кроме того, очередная точка {(п+1) q } попадет в один из наибольших уже полученных отрезков.

Таким образом, точки {q }, {2 q },..., {пq } расположены между 0 и 1 достаточно равномерно. Если q - рациональное число, то теорема остается верна (при подходящей интерпретации отрезков нулевой длины, которые образуются при n, большем или равном знаменателю q). Доказательство теоремы S[7]

Рассмотренная теория подводит нас к хешированию Фибоначчи, при котором в качестве А берется ближайшее к f^-1w целое число, взаимно простое с w. Например, если компьютер десятичный можно воспользоваться множеством

(7)

Он хорошо рассеивает алфавитные ключи типа LIST1, LIST2, LIST3. Но при изменения ключей в четвертой позиции - например, SUMl_, SUM2_,SUM3_ - получим, что рассеяние происходит так же, как если бы теорема S использовалась с q = {100А/w} =.80339887 вместо q =. 6180339887 = A/w. В результате данное рассеяние оказывается несколько хуже, чем при q=f^-1, хотя и остается достаточно хорошим. Однако в случае изменения во второй позиции ключа –Al___ A2___, A3___ - эффективное значение q равно 0.9887, что, пожалуй, слишкс близко к 1.

Поэтому можно былобы работать с множителем

вместо множителя (7); такой множитель будет хорошо разделять последовательности ключей, отличающиеся в любой позиции. К сожалению, подобный выбор приводит к новой проблеме, аналогичной возникающей при делении на r^k±1.•. ключи типа XY и YX попадут при хешировании в одно и то же место! Для обхода возникающией ситуации воспользуемся теоремыой S. Для коротких последовательностей ключей важны лишь несколько первых частичных отношений представлений q виде цепной дроби. Маленькие частичные отношения соответствуют "хорошим” свойствам распределения. Поэтому можно показать, что наилучшие значения q лежат в интервалах

Значение А можно составить так, что каждый из его байтов будет находиться в "хорошем" интервале и будет не слишком близок к значениям других байтов (или их дополнениям), например

Такой множитель может быть смело рекомендован к использованию. (Изложенн в этом разделе идеи по мультипликативному хешированию в основном принадлемжат - В. Флойду (R. W. Floyd).)

Хорошая хеш-функция должна удовлетворять двум требованиям.

a) Ее вычисление должно выполняться очень быстро.

b) Она должна минимизировать количество коллизий.

Свойство (а) зависит от особенностей компьютера, а свойство (b) — от особенностей данных. Если бы все ключи были действительно случайными, можно было бы использовать несколько битов из них и с их помощью получить хеш-функцю; однако на практике для удовлетворения (b) требуется функция,зависящая от всех битов ключа.