Методы рандомизации

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

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

Наиболее часто используемый при прямом хранении и поиске данных метод состоит в том, что устанавливается определенное отношение между ключом и его адресом. Известны численные алгоритмы, с помощью которых по заданному ключу можно определить местоположение данных в памяти [8—121. Так, в разд. 5.4 обсуждался простейший алгоритм хеширования, состоящий в том, что числовой ключ делится на простое число, ближайшее к числу доступных адресов, и остаток от деления берется в качестве адреса. Был также рассмотрен и простой метод обработки синонимов, т. е. данных, для которых был вычислен один и тот же адрес; синонимы размещались в очередных свободных ячейках памяти.

Другой метод состоит в том, что выбирается только некая часть ключа и из нее либо непосредственно, либо с помощью некоторого алгоритма вырабатывается адрес. Этот метод в разд. 5.4.7 иллюстрировался примером, где символические имена (ключи в терминологии данной главы) состояли из буквы и цифры, а адрес считался равным числовой части имени.

Для того чтобы добиться эффективного поиска данных, необходимо минимизировать количество синонимов. Поэтому важно выбирать из ключей те части, которые позволяют (посредством выбранного алгоритма) получить наиболее равномерное распределение адресов и, таким образом, уменьшить количество синонимов. Для этого определяются частотные характеристики разрядов или битов в
различных участках ключей, нe из них, в которых возможные значения распределяются наиболее равномерно, выбираются для выработки адреса. Например, если необходимо хранить не более 10 000 статей и номер статьи, используемый в качестве ключа поиска, состоит из 6 десятичных разрядов, причем почти все из ключей начинаются с цифры 1 или 2 и заканчиваются 0 или 1, в то время как значения других разрядов появляются случайно приблизительно с одной и той же частотой, то для выработки адреса следует использовать только четыре средние разряда номера статьи, и их значение можно считать непосредственно равным адресу.

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

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

Например, рассмотрим случай формирования четырехразрядных адресов из 10-разрядных ключей. Анализ этих ключей показывает, что значения первых двух разрядов ключей распределяются неравномерно, и поэтому они не используются при. вычислении адреса. Тогда путем тривиального сложения или умножения можно получить из значения ключа 1023461210 следующие адреса:
Другой вариант метода умножения сводится к возведению значения ключа в квадрат и выделению разрядов в середине результата. Основанием для выбора этих разрядов из квадрата ключа является то, что все разряды ключа принимают участие в формировании этой части произведения. Поэтому любые систематические отклонения, вероятно, окажутся здесь значительно сглаженными.

Другой простой метод вычисления адреса — это преобразование в другую систему счисления. В этом случае число, представленное ключом, переводится в другую систему счисления, и коэффициент или коэффициенты (mod 10) рассматриваются как десятичное число, определяющее адрес.


Организация данных и структуры данных Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора	Методы рандомизации К сожалению, на практике очень редко случается так, что значения ключей плотно заполняют некий числовой интервал. Часто ключи представляются не в виде цифровых, а в виде алфавитных или алфавитно-цифровых последовательностей символов. Большинству пользователей удобно, чтобы ключ непосредственно передавал информацию о связанных с ним данных. (Например, первые символы телефонных номеров указывают основной географический район абонента.) Поскольку данные, как правило, не являются равномерно распределенными, то ключи покрывают значительно больший интервал, чем требует их количество, так что остается достаточно места для максимально возможного количества элементов внутри одной подгруппы. Иногда оказывается возможным добавить к исходному ключу в качестве суффикса адрес данных на диске и рассматривать этот многополевой ключ как целое. Однако для больших фирм и организаций, а также при обработке больших объемов данных такой подход не рекомендуется. Он приводит к слишком жесткой системе. Любая реорганизация в хранении данных влечет изменение ключей, что не будет восприниматься доброжелательно большинством пользователей. Наиболее часто используемый при прямом хранении и поиске данных метод состоит в том, что устанавливается определенное отношение между ключом и его адресом. Известны численные алгоритмы, с помощью которых по заданному ключу можно определить местоположение данных в памяти [8—121. Так, в разд. 5.4 обсуждался простейший алгоритм хеширования, состоящий в том, что числовой ключ делится на простое число, ближайшее к числу доступных адресов, и остаток от деления берется в качестве адреса. Был также рассмотрен и простой метод обработки синонимов, т. е. данных, для которых был вычислен один и тот же адрес; синонимы размещались в очередных свободных ячейках памяти. Другой метод состоит в том, что выбирается только некая часть ключа и из нее либо непосредственно, либо с помощью некоторого алгоритма вырабатывается адрес. Этот метод в разд. 5.4.7 иллюстрировался примером, где символические имена (ключи в терминологии данной главы) состояли из буквы и цифры, а адрес считался равным числовой части имени. Для того чтобы добиться эффективного поиска данных, необходимо минимизировать количество синонимов. Поэтому важно выбирать из ключей те части, которые позволяют (посредством выбранного алгоритма) получить наиболее равномерное распределение адресов и, таким образом, уменьшить количество синонимов. Для этого определяются частотные характеристики разрядов или битов в различных участках ключей, нe из них, в которых возможные значения распределяются наиболее равномерно, выбираются для выработки адреса. Например, если необходимо хранить не более 10 000 статей и номер статьи, используемый в качестве ключа поиска, состоит из 6 десятичных разрядов, причем почти все из ключей начинаются с цифры 1 или 2 и заканчиваются 0 или 1, в то время как значения других разрядов появляются случайно приблизительно с одной и той же частотой, то для выработки адреса следует использовать только четыре средние разряда номера статьи, и их значение можно считать непосредственно равным адресу. Используя двоичные представления алфавитных или алфавитно-цифровых ключей, эти ключи можно обрабатывать такими же численными алгоритмами. Так, общее правило для нечисловых ключей заключается в том, что зонная часть (или по крайней мере первые два одинаковых бита) каждого символа опускается и только вторая половина байта используется процедурой вычисления адреса. В остальном принципиальных различий между обработкой числовых и нечисловых ключей нет. Поэтому в последующих примерах мы ограничимся только числовыми ключами. Более или менее равномерно распределенные адреса можно получить сложением или умножением, так же как и делением на простое число. В этих случаях, ключ или его выделенные части разделяются на группы, которые затем складываются или умножаются. Например, рассмотрим случай формирования четырехразрядных адресов из 10-разрядных ключей. Анализ этих ключей показывает, что значения первых двух разрядов ключей распределяются неравномерно, и поэтому они не используются при. вычислении адреса. Тогда путем тривиального сложения или умножения можно получить из значения ключа 1023461210 следующие адреса: Другой вариант метода умножения сводится к возведению значения ключа в квадрат и выделению разрядов в середине результата. Основанием для выбора этих разрядов из квадрата ключа является то, что все разряды ключа принимают участие в формировании этой части произведения. Поэтому любые систематические отклонения, вероятно, окажутся здесь значительно сглаженными. Другой простой метод вычисления адреса — это преобразование в другую систему счисления. В этом случае число, представленное ключом, переводится в другую систему счисления, и коэффициент или коэффициенты (mod 10) рассматриваются как десятичное число, определяющее адрес.