Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 17

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 17)

Указатели вообще не используются, что приводит ксохранению места и ускорению поиска.Таким образом, коэффициент заполнения α = n/m не больше 1.Поиск (search): мы определенным образом просматриваемэлементы таблицы, пока не найдем искомый или не убедимся,что искомый элемент отсутствует.Просматриваются не все элементы (иначе это был быпоследовательный поиск), а только некоторые согласнозначению хеш-функции, которая в этом случае имеет двааргумента – ключ и «номер попытки»:hash: U × {0, 1, …, m – 1} → {0, 1, …, m – 1}.Функцию hash нужно выбрать такой, чтобы в последовательностипроб 〈hash(k, 0), hash(k, 1), …, hash(k, m – 1)〉 каждый номерячейки 0, 1, …, m – 1 встретился только один раз.Если при поиске мы добираемся до ячейки, содержащей NULL,можно быть уверенным, что элемент с данным ключом18отсутствует (иначе он попал бы в эту ячейку).Хеширование с открытой адресацией: программы#define m 1999struct htype {int key;int val;} *index[m];/* ключ *//* значение элемента данных *//* Поиск элемента */struct htype *search (int k) {int i = 0, j;do {j = hash (key, i);if (index[j] && index[j]->key == k)return index[j];} while (index[j] && ++i < m);return NULL;}19Хеширование с открытой адресацией: программы/* Добавление элемента */int insert (int k, int v) {int i = 0, j;do {j = hash (key, i);if (index[j] && index[j]->key == k) {index[j]->val = v;return j;}} while (index[j] && ++i < m);/* Таблица может оказаться заполненной */if (i == m)return -1; /* Или расширим index */index[j] = new ();index[j]->key = k, index[j]->val = v;return j;}20Хеширование с открытой адресацией: программы/* Внутренний поиск: вернем индекс массива */static int search_internal (int k) {int i = 0, j;do {j = hash (key, i);if (index[j] && index[j]->key == k)return j;} while (index[j] && ++i < m);return -1;}/* Внешний поиск легко реализуется через внутренний */struct htype *search (int k) {int j = search_internal (k);return j >= 0 ? index[j] : NULL;21}Хеширование с открытой адресацией: программы/* Удаление элемента */void delete (int k) {int j;j = search_internal (k);if (j < 0)return;/* Нельзя писать index[j] = NULL!Будут потеряны ключи, возможно, находящиесяза удаляемым ключом (с тем же хешем).

*/???}22Хеширование с открытой адресацией: программы#define SHADOW ((void *) (intptr_t) 1)/* Удаление элемента */void delete (int k) {int j;j = search_internal (k);if (j < 0)return;/* Нельзя писать index[j] = NULL! */free (index[j]);index[j] = SHADOW;}23Хеширование с открытой адресацией: программы#define SHADOW ((void *) (intptr_t) 1)#define ISEMPTY(el) ((!el) || (el) == SHADOW)static int search_internal (int k) {int i = 0, j;do {j = hash (key, i);if (!ISEMPTY (index[j]) && index[j]->key == k)return j;} while (index[j] && ++i < m);return -1;}24Хеширование с открытой адресацией: программы#define SHADOW ((void *) (intptr_t) 1)#define ISEMPTY(el) ((!el) || (el) == SHADOW)/* Добавление элемента */int insert (int k, int v) {int i = 0, j;do {j = hash (key, i);if (! ISEMPTY (index[j]) && index[j]->key == k) {index[j]->val = v;return j;}} while (! ISEMPTY (index[j]) && ++i < m);/* Таблица может оказаться заполненной (много вставок/удалений) */if (i == m)return -1; /* Или расширим index */index[j] = new ();index[j]->key = k, index[j]->val = v;return j;25}Хеш-функции для открытой адресацииЛинейная последовательность проб.Пусть hash′: U → {0, 1, …, m – 1} – обычная хеш-функция.Функция hash(k, i) = (hash′(k) + i) mod mопределяет линейную последовательность проб.При линейной последовательности проб начинают с ячейкиindex[h′(k)], а потом перебирают ячейки таблицы подряд:index[h′(k) + 1], index[h′(k) + 2], … (после index[m – 1] переходят кindex[0]).Cуществует лишь m различных последовательностей проб,т.к.

каждая последовательность однозначно определяетсясвоим первым элементом.26Хеш-функции для открытой адресацииСерьезный недостаток – тенденция к образованию кластеров(длинных последовательностей занятых ячеек, идущих подряд),что удлиняет поиск:Если в таблице все четные ячейки заняты, а нечетныеячейки свободны, то среднее число проб при поискеотсутствующего элемента равно 1,5.Если же те же m/2 занятых ячеек идут подряд, тосреднее число проб равно (m/2)/2 = m/4.Причины образования кластеров: если k заполненных ячеек идутподряд, то:вероятность того, что при очередной вставке в таблицубудет использована ячейка, непосредственно следующаяза ними, есть (k +1)/m ( пропорционально «толщине слоя»),вероятность использования конкретной ячейки,предшественница которой тоже свободна, всего лишь 1/m.Таким образом, хеширование с использованием линейнойпоследовательности проб далеко не равномерное.Возможное улучшение: добавляем не 1, а константу с, взаимно27простую с m (для полного обхода таблицы).Хеш-функции для открытой адресацииКвадратичная последовательность проб:hash(k, i) = (hash′(k) + c1⋅i + c2⋅i2) mod m,c1 и c2 ≠ 0 – константы.Пробы начинаются с ячейки index[h′(k)], а потом ячейкипросматриваются не подряд, а по более сложному закону.Метод работает значительно лучше, чем линейный.Чтобы при просмотре таблицы index использовались все ееячейки, значения m, c1 и c2 следует брать не произвольными, аподбирать специально.

Если обе константы равны единице:находим i ← hash′(k); полагаем j ← 0;проверяем index[i]:если она свободна, заносим в неезапись и выходим из алгоритма,если нет – полагаем j ← (j + 1) mod m,i ← (i + j) mod m и повторяем текущий шаг.28Хеш-функции для открытой адресацииДвойное хеширование – один из лучших методов открытойадресации.hash(k, i) = (h1(k) + i h2(k)) mod m,где h1(k) и h2(k) – обычные хеш-функции.Дополнительная хеш-функция h2(k) генерирует хеши, взаимнопростые с m.Если основная и дополнительная функция существеннонезависимы (т.е. вероятность совпадения их хешей обратнопропорциональна квадрату m), то скучивания не происходит,а распределение ключей по таблице близко к случайному.Оценки.

Среднее число проб для равномерного хеширования11.1−αоценивается при успешном поиске как αПри коэффициенте заполнения 50% среднее число проб дляуспешного поиска ≤ 1,387, а при 90% – ≤ 2,559.При поиске отсутствующего элемента и при добавлении новогоln1элемента оценка среднего числа проб 1 − α .29Хеширование других данныхХеширование идентификаторов в компилятореhashval_thtab_hash_string (const PTR p){const unsigned char *str = (const unsigned char *) p;hashval_t r = 0;unsigned char c;while ((c = *str++) != 0)r = r * 67 + c - 113;return r;}Хеширование ключа переменной длины: в GCC используетсяhttp://burtleburtle.net/bob/hash/evahash.html30Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 231Цифровой поискЦифровой поиск – частный случай поиска заданной подстроки(образца) в длинной строке (тексте).Примеры цифрового поиска: поиск в словаре, в библиотечномкаталоге и т.п., когда делается поиск по образцу в несколькихтекстах (названиях книг, фамилиях авторов, текстах навызванных сайтах и т.п.).Хороший пример – словарь с высечками, т.е.

словарь, в которомобеспечен быстрый доступ к некоторым страницам (например,начальным страницам списков слов, начинающихся наочередную букву алфавита). Иногда используютсямногоуровневые высечки.При цифровом поиске ключи рассматриваются какпоследовательности символов рассматриваемого алфавита(в частности, цифр или букв). Ожидаемое число сравненийпорядка О(logm N), где m - число различных букв, используемыхв словаре, N – мощность словаря. В худшем случае деревосодержит k уровней, где k – длина максимального слова.2Цифровой поискПример.

Пусть множество используемых букв (алфавит){A, B, C, D}. Мы добавим к алфавиту еще одну букву (пробел).По определению слова АА, АА , ААсовпадают.Пусть {A, AA, ABB, AC, ADBD, BCA, BCD, CBA} – словарь(множество ключей).Построим m-ичное дерево, где m = 5 = | , A, B, C, D |.Следующая небольшая хитрость позволит иногда сократитьпоиск: если в словаре есть слово а1а2а3...аk и первые i его букв(i < k) задают уникальное значение: комбинация а1...аiвстречается в словаре только один раз, то не нужно строитьдерево для j > i, так как слово можно идентифицировать попервым i буквам.Очень важное обобщение цифрового поиска: таким же образомможно обрабатывать любые ключи, не привязываясь к байту (8битам), который обычно используется для кодирования символовалфавита. Мы можем отсекать от ключа первые m бит,использовать 2m-ичное разветвление, т.е.

строить 2m-ичноедерево поиска (на двоичных деревьях для разветвления3берется один бит: m = 1).Цифровой поискПрямоугольниками изображены вершины дерева, в овалах –значения слов (ключей) и связанная с ним информация.Тем самым любая вершина дерева – массив из m элементов.Каждый элемент вершины содержит либо ссылку на другуювершину m-ичного дерева, либо на овал (ключ).4Цифровой поискИногда используют комбинации нескольких методов:цифровой поиск вначале, а затем переключение на поиск впоследовательных таблицах.Именно так мы и работаем со словарем с высечками:вначале на высечку, а затем либо последовательныйпоиск, либо дихотомический.Обычно предлагается пользоваться цифровым поиском, покаколичество различных слов не меньше некоторого k, а затемпереключаться на последовательные таблицы.Обобщения: поиск по неполным ключам, поиск по образцу.5Цифровой поиск#include <stdio.h>#include <stdlib.h>#include <string.h>#define M 5typedef enum {word, node} tag_t;struct record {char *key;int value;};struct tree {tag_t tag;union {struct record *r;struct tree *nodes[M+1];}; /* анонимное объединение */};6Цифровой поиск: поиск элементаstatic inline int ord (char c) {return c ? c - 'A' + 1 : 0;}struct record *find (struct tree *t, char *key) {int i = 0;while (t) {switch (t->tag) {case word:for (; key[i]; i++)if (key[i] != t->r->key[i])return NULL;return t->r->key[i] ? NULL : t->r;case node:t = t->nodes[ord(key[i])];if (key[i])i++;}}return NULL;}7Цифровой поиск: вставка – вспомогательные функцииstruct record *make_record (char *key, int value) {struct record *r = malloc (sizeof (struct record));r->key = strdup (key);r->value = value;return r;}struct tree *make_word (char *key, int value) {struct tree *t = malloc (sizeof (struct tree));t->tag = word;t->r = make_record (key, value);return t;}struct tree *make_node (void) {struct tree *t = calloc (1, sizeof (struct tree));t->tag = node;return t;}struct tree *make_from_record (struct record *r) {struct tree *t = malloc (sizeof (struct tree));t->tag = word;t->r = r;return t;}8Цифровой поиск: вставка элементаstruct tree *insert (struct tree *t, char *key, int value) {if (!t)return make_word (key, value);int i = 0;struct tree *root = t;/* skip all nodes */while (t->tag == node) {struct tree **p = &t->nodes[ord(key[i++])];if (!*p) {*p = make_word (key, value);return root;}t = *p;}/* all word skipped -- key exists, update value */if (i && !key[i - 1]) {t->r->value = value;return root;}9Цифровой поиск: вставка элемента/* compare the remaining part */int j = i;for (; key[i]; i++)if (key[i] != t->r->key[i])break;/* key already exists -- update value */if (!key[i] && !t->r->key[i]) {t->r->value = value;return root;}/* turn t into a node */struct record *other = t->r;t->tag = node;memset (t->nodes, 0, sizeof (t->nodes));10Цифровой поиск: вставка элемента/* make new nodes for remaining common prefix */for (; j < i; j++) {struct tree *p = make_node ();t->nodes[ord(key[j])] = p;t = p;}/* accommodate both other and new record */t->nodes[ord(other->key[i])]= make_from_record (other);t->nodes[ord(key[i])] = make_word (key, value);return root;}11Цифровой поиск: печать элементовvoid print (struct tree *t, char c) {static int level = 0;if (!t) {printf ("empty\n");return;}for (int i = 0; i < level; i++)putchar (' ');if (level)printf ("%c: ", chr (c));if (t->tag == word) {printf ("word: %s %d\n", t->r->key, t->r->value);} else {printf ("node: ");for (int i = 0; i < M + 1; i++)if (t->nodes[i])printf ("%c ", chr(i));putchar ('\n');level++;for (int i = 0; i < M + 1; i++)if (t->nodes[i])print (t->nodes[i], i);level--;}}12Самоперестраивающиеся деревья (splay trees)Двоичное дерево поиска, не содержащее дополнительныхслужебных полей в структуре данных(нет баланса, цвета и т.п.)Гарантируется не логарифмическая сложность в худшем случае,а амортизированная логарифмическая сложность:Любая последовательность из m словарных операций(поиска, вставки, удаления) над n элементами, начинаяс пустого дерева, имеет сложность O(m log n)Средняя сложность одной операции O(log n)Некоторые операции могут иметь сложность Θ(n)Не делается предположений о распределениивероятностей ключей дерева и словарных операций(т.е.

Характеристики

Список файлов лекций