Алгоритмы преобразования ключей

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Алгоритмы преобразования ключей

Алгоритмы преобразования ключей

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ КЛЮЧЕЙ (РАССТАНОВКА)

ГЛАВА 2. ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 ВСТАВКА ЭЛЕМЕНТА В В-ДЕРЕВО

2.2 ОБРАБОТКА ТЕКСТОВЫХ ФАЙЛОВ

ПРИЛОЖЕНИЕ К ВЫПОЛНЕННЫМ ПРОГРАММАМ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

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

1. Алгоритмы преобразования ключей (расстановка).

Хеширование - алгоритмическое преобразование ключей в адреса. В СУБД метод индексации, при котором значение ключа (идентификатора записи) служит аргументом для прямого вычисления либо локализации ассоциированной записи в файле, либо начала ее поиска.

С хешированием сталкиваются едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором (таблица символов). По словам Брайана Кернигана, это «одно из величайших изобретений информатики». Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочение по алфавиту является не чем иным, как хешированием.

2. Написать процедуру, реализующую вставку в В-дерево.

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

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

3. Разработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: подсчитать количество слов, которые содержат определённое количество согласных.

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

ГЛАВА 1. АЛГОРИТМЫ ПРЕОБРАЗОВАНИЯ КЛЮЧЕЙ

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

Термин «хеширование» (hashing) в печатных работах по программированию появился сравнительно недавно (1967 г. [1]), хотя сам механизм был известен и ранее. Глагол «hash» в английском языке означает «рубить, крошить», т. е. создавать этакий «винегрет». Для русского языка академиком А.П. Ершовым [2] был предложен достаточно удачный эквивалент -- «расстановка», созвучный с родственными понятиями комбинаторики, такими как «подстановка» и «перестановка». Однако пока он не прижился.

Как отмечает Дональд Кнут [3], идея хеширования впервые была высказана Г.П. Ланом при создании внутреннего меморандума IBM в январе 1953 г. с предложением использовать для разрешения коллизий хеш-адресов метод цепочек. В открытой печати хеширование впервые было описано Арнольдом Думи (1956), указавшим, что в качестве хеш-адреса удобно использовать остаток от деления на простое число. Подход к хешированию, отличный от метода цепочек, был предложен А.П. Ершовым (1957), который разработал и описал метод линейной открытой адресации. Среди других исследований можно отметить работы Петерсона (1957, [4]) и Морриса (1968, [5]). В первой реализовывался класс методов с открытой адресацией при работе с большими файлами, а во второй давался обширный обзор по хешированию и вводился термин «рассеянная память» (scatter storage).

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

Как известно, массив задает отображение (A) множества индексов (I) на множество элементов (E), т. е. A: I --> E. Массив позволяет по индексу быстро найти требуемый элемент. Хеширование решает в точности такую же задачу. Однако здесь уже в роли индекса выступает хеш-адрес, который определяется как значение некоей хеш-функции, применяемой к уникальному ключу. В этом смысле хеш-структуры можно рассматривать как обобщение массива.

В программировании зависимость между индексом и значением записывается в виде: A = ARRAY I OF E. В роли индексирующего типа (I) обычно выбирается конкретный диапазон значений из целочисленного типа (хотя в общем случае в их роли могут выступать так называемые скалярные типы, т. е. булев тип, перечисления, множества и др.). Ну а элементы массива в зависимости от языка программирования могут быть любыми, начиная от битов, чисел и указателей (ссылок) и заканчивая составными типами произвольной глубины.

То, что массив задает функцию отображения, в языке Ада подчеркивается даже на уровне синтаксиса. Например, при появлении в тексте программы записи вида «a(i)» трудно с ходу сказать, идет ли это обращение к i-му элементу массива «a» или же просто вызывается функция «a» с параметром «i».

Выделяют два разных вида массивов: одномерные (наиболее общий случай) и многомерные (на каждом слое адресации используется массив фиксированной структуры). Во втором случае есть и особый подвид: ступенчатые массивы (jagged arrays). Они встречаются, в частности, в языке C# в том случае, когда на каждом слое адресации используется массив переменной структуры. Иначе говоря, здесь мы имеем дело с массивом разных массивов. В других языках такая конструкция легко описывается массивом разнородных указателей (каждый указывает на массив своей структуры), что фактически определяет массив списков.

Интересно, что Н. Вирт после многих лет использования в своих языках (Паскаль, Модула-2) в качестве индексирующего типа разных скалярных типов пришел к выводу, что лаконичное решение, воплощенное в языке Си (а точнее, унаследованное в Си от языков BCPL и B), носит куда более практичный характер. И в своих новых языках Оберон и Оберон-2 он отказался от идей Паскаля и ограничился заданием размера массива (количества индексируемых элементов), т. е. определением для индексов диапазона 0...n--1, где n -- это размер массива: A = ARRAY 16 OF E. Связано это с эффективностью реализации и с активным использованием в программировании элементов модулярной арифметики. В Обероне предопределенная функция MOD («x MOD n»), как и в математике, соответствует остатку от целочисленного деления «x» на «n». Как показывает опыт, использование 0 в качестве начального индекса удобно в подавляющем большинстве задач. Механизмы хеширования опираются точно на ту же основу.

Вспомним некоторые определения из курса элементарной математики. Отображением (f: A --> B) множества A во множество B (функцией на A со значениями в B) называется правило, по которому каждому элементу множества A сопоставляется один или несколько элементов множества B. Отсюда следует, что отображения могут быть однозначными и многозначными в зависимости от того, имеет ли каждый прообраз в соответствии один или несколько образов. Однозначное отображение f: A--> B называется сюръективным (сюръекцией), если f(A) = B. Это так называемое отображение «на». Отображение (в общем случае неоднозначное) называется инъективным, если образы различных прообразов различны (отображение «в»). Cюръективное и инъективное отображение называется биекцией.

Вот теперь, пользуясь этими понятиями, попробуем разобраться в природе хеширования. Итак, одномерные и многомерные массивы -- это яркий пример сюръекции. Поэтому их можно назвать «сюръективными» массивами. Биекцию в общем случае они не задают, поскольку разным индексам (прообразам) могут соответствовать одни и те же значения (образы). Примером «биективного» массива может служить, например, соответствующим образом заполненный массив литер: ARRAY 256 OF CHAR.

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

Следовательно, в случае хеширования значения хранятся в «инъективных» массивах разной структуры.

Именно здесь проходит водораздел между разными схемами и методами хеширования. Именно отсюда и проистекают проблемы поиска оптимального баланса между пространством хранения и временем доступа.

Традиционно принято выделять две схемы хеширования:

· хеширование с цепочками (со списками);

· хеширование с открытой адресацией.

В первом случае выбирается некая хеш-функция h(k) = i, где i трактуется как индекс в таблице списков t. Поскольку нельзя гарантировать, что не встретится двух разных ключей, которым соответствует один и тот же индекс i (конфликт, коллизия), такие «однородные» ключи просто помещаются в список, начинающийся в i-ячейке хеш-таблицы t (см. рисунок).

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

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

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

A=(C-97)*L,

где А -- адрес в таблице, полученный на основе двоичного значения символа С; L -- длина элемента таблицы (для нашей задачи L=l); 97 -- десятичное смещение в кодовой таблице строчного символа «а» английского алфавита.

:prg02_07.asm - программа на ассемблере для подсчета количества слов, начинающихся с определенной строчной буквы:

Вход: ввод с клавиатуры 20 слов (длиной не более 10 символов).

Выход: вывод результата подсчета на экран.

buf_Oahstruc

len_bufdb 11 ; длина bufjn

lenjin db 0 действительная длина введенного слова (без учета Odh) bufjn db 11 dup (20h) -.буфер для ввода (с учетом Cdh) ends 1 .data

tabdb 26 dup (0) buf buf_0ah<>

db Odh.Oah,'$' ;для вывода функцией 09h (int 21h)

.code

-.вводим слова с клавиатуры

mov ex,20

lea dx.buf

movah.Oah ml: int 21h :анализируем первую букву введенного слова - вычисляем хэш-функцию: А=С*1-97

mov Ы , buf .bufjn sub Ы. 97 inc [bx] loop ml

:выводим результат подсчета на экран push ds popes

xor al ,al

lea di ,buf

mov ex.type bufjah rep stosb ; чистим буфер buf

mov ex.26 :синвол в buf.buf_1n

lea dx.buf

mcv Ы,97 m2: push bx

mov buf .bufjn.bi :опять вычисляем хэш-функцию:

А»С*1-97 и преобразуем "количество" в символьный вид

sub Ы. 97

mov al .[bx]

aam

or ax,03030h ;в ах длина в символьном виде

mov buf.len in.al --

mov buf.len_buf.ah ;теперь выводим:

mov ah, 09h

int 21h pop bx

inc Ы

loop m2

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

Перечислим области, где методы хэширования оказываются особенно эффективными.

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

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

· Разработка криптографических систем.

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

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

Пусть необходимо подсчитать количество двухсимвольных английских слов в некотором тексте. В качестве хэш-функции для вычисления адреса можно предложить функцию подсчета суммы двух символов, умноженной на длину элемента таблицы: A=(Cl+C2)*L-97, где А -- адрес в таблице, полученный на основе суммы двоичных значений символов С1 и С2; L -- длина элемента таблицы; 97 -- десятичное смещение в кодовой таблице строчного символа «а» английского алфавита. Проведем простые расчеты. Сумма двоичных значений двух символов 'а' равна 97+97=194, сумма двоичных значений двух символов 'г' равна 122+122=244. Если организовать хэш-таблицу, как в предыдущем случае, то получится, что в ней должно быть всего 50 элементов, чего явно недостаточно. Более того, для сочетаний типа ab и Ьа хэш-сумма соответствует одному числовому значению. В случае когда функция хеширования вычисляет одинаковый адрес для двух и более различных объектов, говорят, что произошла коллизия, или конфликт. Исправить положение можно введением допущений и ограничений, вплоть до замены используемой хэш-функции. Программист может либо применить один из известных алгоритмов хеширования (что, по сути, означает использование определенной хэш-функции), либо изобрести свой алгоритм, наиболее точно отображающий специфику конкретной задачи. При этом необходимо понимать, что разработка хэш-функции происходит в два этапа.

1. Выбор способа перевода ключевых слов в числовую форму.

2. Выбор алгоритма преобразования числовых значений в набор хеш-адресов.

3. Выбор способа перевода ключевых слов в числовую форму

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

· деления;

· умножения;

· извлечения битов;

· квадрата;

· сегментации;

· перехода к новому основанию;

· алгебраического кодирования;

· вычислении значения CRC (см. соответствующую главу).

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

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

Необходимо разработать программу -- фрагмент компилятора, которая собирает информацию об идентификаторах программы. Предположим, что в программе может встретиться не более М различных имен. Длину возможных имен ограничим восьмью символами. В качестве ключа используются символы идентификатора, какие и сколько -- будем уточнять для каждого из методов. Элемент таблицы состоит из 10 байт: 1 байт признаков, 1 байт для хранения длины идентификатора и 8 байт для хранения символов самого идентификатора.

Метод деления

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

А(К) = К mod M

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

· Значение М выбирается равным простому числу.

· Значение М не должно являться степенью основания, по которому производится перевод ключей в числовую форму. Так, для алфавита, состоящего из первых пяти английских букв и пробела {a,b,c,d,e,' '} (см. пример выше), основание системы равно 6. Исходя из этого число элементов таблицы М не должно быть степенью 6Р.

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

Метод умножения

Для этого метода нет ограничений на длину таблицы, свойственных методу деления. Вычисление хэш-адреса происходит в два этапа:

1. Вычисление нормализованного хэш-адреса в интервале [0..1] по формуле:

хеширование адрес алгоритм обработка текстовый

F(K) = (С*К) mod 1,

где С -- некоторая константа из интервала [0..1], К -- результат преобразования ключа в его числовое представление, mod 1 означает, что F(K) является дробной частью произведения С*К.

2. Конечный хэш-адрес А(К) вычисляется по формуле А(К) = [M*F(K)], где М -- размер хэш-таблицы, а скобки [] означают целую часть результата умножения.

Удобно рассматривать эти две формулы вместе:

А(К) = М*(С*К) mod 1.

Кнут в качестве значения С рекомендует использовать «золотое сечение» -- величину, равную ((л/5)-1)/2«0,6180339887. Значение F(K) можно формировать с помощью как команд сопроцессора, так и целочисленных команд. Команды сопроцессора вам хорошо известны и трудностей с реализацией формулы (2.4) не возникает. Интерес представляет реализация вычисления А(К) с помощью целочисленных команд. Правда, в отличие от реализации сопроцессором здесь все же Удобнее ограничиться условием, когда М является степенью 2. Тогда процесс вычисления с использованием целочисленных команд выглядит так:

Выполняем произведение С*К. Для этого величину «золотого сечения» С~0,6180339887 нужно интерпретировать как целочисленное значение,

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

Метод квадрата

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

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

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

Обработка коллизий

Для обработки коллизий используются две группы методов:

· закрытые -- в качестве резервных используются ячейки самой хэш-таблицы;

· открытые -- для хранения элементов с одинаковыми хэш-адресами используется отдельная область памяти.

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

Закрытые методы разрешения коллизий более сложные. Их основная идея -- при возникновении коллизии попытаться отыскать в хэш-таблице свободную ячейку. Процедуру поиска свободной ячейки называют пробитом, или рехешированием (вторичным хешированием). При возникновении коллизии к первоначальному хэш-адресу А(К) добавляется некоторое значение р, и вычисляется выражение (2.5). Если новый хэш-адрес А(К) опять вызывает коллизию, то (2.5) вычисляется при р2, и так далее:

А(К) = (A(K)+Pi)mod М (I = 0..М). (2.5)

push ds popes

lea si .buf.len_in

mov cl .buf .lenjn

inccx :длину тоже нужно захватить

add di .lenjd repmovsb

jmp ml displ: :выводим идентификатор, вызвавший коллизию, на экран

рехэширование

;ищем место для идентификатора, вызвавшего коллизию в таблице, путем линейного рехэширования i nc bx mov ax.bx jmp m5

Квадратичное рехеширование

Процедура квадратичного рехеширования предполагает, что процесс поиска резервных ячеек производится с использованием некоторой квадратичной функции, например такой:

Pi = а,2+Ь,+с. (2.6)

Хотя значения а, Ь, с можно задавать любыми, велика вероятность быстрого зацикливания значений р(. Поэтому в качестве рекомендации опишем один из вариантов реализации процедуры квадратичного рехеширования, позволяющий осуществить перебор всех элементов хэш-таблицы [32]. Для этого значения в формуле (2.6) положим равными: а=1,Ь = с = 0. Размер таблицы желательно задавать равным простому числу, которое определяется формулой М = 4п+3, где п -- целое число. Для вычисления значений р> используют одно из соотношений:

pi = (K+i2)modM. (2.7) Pi = [M+2K-(K+i2)modM]modM. (2.8)

где i = 1, 2, ..., (M-l)/2; К -- первоначально вычисленный хэш-адрес.

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

1. Задание I = -М.

2. Вычисление хэш-адреса К одним из методов хэширования.

3. Если ячейка свободна или ключ элемента в ней совпадает с искомым ключом, то завершение процесса поиска. Иначе, 1:=1+1.

4. Вычисление h := (h+|i|)modM.

5. Если I < М, то переход к шагу 3. Иначе (если I > М), таблица полностью заполнена.

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

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

Обобщенно можно сказать, что все перечисленные выше структуры имеют общие свойства:

· постоянство структуры данных на всем протяжении ее существования;

· память для хранения отводится сразу всем элементам структуры и все элементы находятся в смежных ячейках памяти;

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

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

Преобразование ключей

Наиболее часто встречается операция поиска записи по идентифицирующему его полю - ключу. Поэтому файл, как правило, индексируется по ключевому полю. Поиск по ключу в общем виде может рассматриваться как преобразование значения ключевого поля в адрес записи в файле (или номер записи), то есть как функция вида f(key) -> m.

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

Функция f() называется распределяющей или рассеивающей функцией. Пример одной из таких функций: берется квадрат значения ключа, из него извлекаются n значащих цифр из середины, которые и дают значение номера записи в файле:

int Place1024(key) // Функция рассеивания для файла из

unsigned key; // 1024 записей и 16 разрядного

{ // ключа

unsigned long n,n1;

int m;

n = (unsigned long)key * key;

for (m=0, n1 = n; n1 !=0; m++, n1 >>= 1); // Подсчет количества значащих

if (m < 10) return(n); // битов в n

m = (m - 10) / 2; // m - количество битов по краям

return( (n >> m) & 0x3FF);

}

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

- записи в области переполнения не связаны между собой, и для поиска в ней используется последовательный просмотр всех записей;

- в области переполнения организуются списки записей, участвующих в коллизии: то есть запись в основной области является заголовком списка записей в области переполнения, куда попадают все записи, вступающие в коллизию.

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

- первая свободная позиция, начиная от текущей;

- проверяются позиции, пропорциональные квадрату шага относительно текущей занятой, то есть m = ( f(key) + i * i ) mod n, где i - номер шага, n - размер таблицы. Такое размещение позволяет лучше "рассеивать" записи при коллизии.

Рассматриваемый метод обозначается терминами расстановка или хеширование (от hash - смешивать, перемалывать).

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

Разработать блок-схему алгоритма и составить программу обработки текстовых данных, хранящихся в произвольном файле на магнитном диске. Вид обработки данных: подсчитать количество слов, которые содержат определённое количество согласных.

1. Hellerman H. Digital Computer System Principles. McGraw-Hill, 1967.

2. Ершов А.П. Избранные труды. Новосибирск: ВО «Наука», 1994.

3. Кнут Д. Искусство программирования, т.3. М.: Вильямс, 2000.

4. Peterson W.W. Addressing for Random-Access Storage // IBM Journal of Research and Development. 1957. V.1, N2. Р.130--146.

5. Morris R. Scatter Storage Techniques // Communications of the ACM, 1968. V.11, N1. Р.38--44.

6. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Вильямс, 2000.

7. Чмора А. Современная прикладная криптография. М.: Гелиос АРВ, 2001.

8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.

9. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985.

10. Керниган Б., Пайк Р. Практика программирования. СПб.: Невский диалект, 2001.

11. Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 1995.

Размещено на Allbest.ru