Алгоритм на псевдокоде. Поиск и вставка элемента с ключом x

Поиск и вставка элемента с ключом x

Пусть хеш-таблица является массивом A=(a₀, a₁, …, a_m-1), сначала заполненный нулями. Пусть x ≠0.

h:=x mod m

d:=1

DO

IF (a_h=x) элемент найден OD

IF (a_h=0) ячейка пуста, a_h:=x OD

IF (d≥m) переполнение таблицы OD

h:=h+d

IF (h≥m) h:=h-m FI

d:=d+2

OD

Заметим, что если нужен только поиск, то необходимо исключить операцию a_h:=x.

Пример построения хеш-таблицы методом квадратичных проб (m =11) для строки ВЛАДИМИР ПУТИН. Номера символов данной строки приведены в таблице.

Таблица 5 Номера символов строки

В

Л

А

Д

И

М

И

Р

П

У

Т

И

Н

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

В: h₀ =3 mod 11=3

Л: h₀ =12 mod 11=1

А: h₀ =1 mod 11=1

h₁ =1+1=2

Д: h₀ =5

И: h₀ =9

М: h₀ =13 mod 11=2

h₁ =2+1=3

h₂ =3+3=6

Р: h₀ =17 mod 11=6

h₁ =6+1=7

П: h₀ =16 mod 11=5

h₁ =5+1=6

h₂ =6+3=9

h₃ =9+5=3

h₄ =3+7=10

У: h₀ =20 mod 11=9

h₁ =9+1=10

h₂ =10+3=13 mod 11=2

h₃ =2+5=7

h₄ =7+7=14 mod 11=3

h₅ =3+9=12 mod 11=1

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

	Л	А	В		Д	М	Р		И	П

Рисунок 63 Использование квадратичных проб

15.4 Варианты заданий

1) Реализовать построение хэш-таблицы методом прямого связывания для слов заданного текста. Экспериментально определить минимально необходимый объем хэш-таблицы.

2) Реализовать процедуру поиска с использованием хэш-таблицы (метод прямого связывания). Экспериментально определить среднее число сравнений при поиске.

3) Построить хэш-таблицу методом линейных проб для слов заданного текста. Экспериментально определить минимально необходимый объем хэш-таблицы число коллизий при построении.

4) Построить хэш-таблицу методом квадратичных проб для слов заданного текста. Экспериментально определить минимально необходимый объем хэш-таблицы число коллизий при построении.

5) Экспериментально сравнить объем хэш-таблицы и число коллизий для методов линейных и квадратичных проб.

6) Реализовать процедуру поиска с использованием хэш-таблицы (метод открытой адресации). Экспериментально определить среднее число коллизий при поиске.

16. Элементы теории кодирования информации

16.1 Необходимые понятия

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

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

Рисунок 64 Модель системы передачи сигналов

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

1. Представление данных произвольной структуры (числа, текст, графика) в памяти компьютера.

2. Обеспечение помехоустойчивости при передаче данных по каналам связи.

3. Сжатие информации в базах данных.

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

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

Кодирование дискретного источника заключается в сопоставлении символов алфавита А источника символам некоторого другого алфавита В. Причем обычно символу исходного алфавита А ставится в соответствие не один, а группа символов алфавита В, называемых кодовым словом. Кодовый алфавит – множество различных символов, используемых для записи кодовых слов. Кодом называется совокупность всех кодовых слов, применяемых для представления порождаемых источником символов.

Пример. Азбука Морзе является общеизвестным кодом из символов телеграфного алфавита, в котором буквам русского языка соответствуют кодовые слова (последовательности) из «точек» и «тире».

Далее будем рассматривать двоичное кодирование, т.е. размер кодового алфавита равен 2. Конечную последовательность битов (0 и 1) назовем кодовым словом, а количество битов в этой последовательности – длиной кодового слова.

Пример. Код ASCII (американский стандартный код для обмена информацией) каждому символу ставит в однозначное соответствие кодовое слово длиной 8 бит.

Пусть даны алфавит источника А={a₁, …,a_n}, кодовый алфавит B={b₁, …,b_m}, SÍA^* – множество всевозможных сообщений в алфавите А. Тогда функция F: S®B^* – кодирование (преобразует множество сообщений в алфавит В). Если αÎS, то F(α)=β Î B^* – кодовое слово. Обратная функция F^-1 (если она существует) называется декодированием.

Задача кодирования сообщения ставится следующим образом. Требуется при заданных алфавитах А и В и множестве сообщений S найти такое кодирование F, которое обладает определенными свойствами (т.е. удовлетворяет заданным ограничениям) и оптимально в некотором смысле. Свойства, которые требуются от кодирования, могут быть различными:

1.Существование декодирования

2.Помехоустойчивость или исправление ошибок: функция декодирования обладает свойством F^-1(β)=F^-1(β¢ ), β~β¢ (эквивалентно β¢ с ошибкой)

3. Обладает заданной трудоемкостью (время, объем памяти).

Известны два класса методов кодирования дискретного источника информации: равномерное и неравномерное кодирование. Под равномерным кодированием понимается использование кодов со словами постоянной длины. Для того, чтобы декодирование равномерного кода было возможным, разным символам алфавита источника должны соответствовать разные кодовые слова. При этом длина кодового слова должна быть не меньше élog_n m ù символов, где m – размер исходного алфавита, n – размер кодового алфавита.

Пример. Для кодирования источника, порождающего 26 букв латинского алфавита, равномерным двоичным кодом, требуется построить кодовые слова длиной не меньше élog₂ 26ù =5 бит.

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

16.2 Кодирование целых чисел

Рассмотрим семейство методов, не учитывающих вероятности появления элементов. В общем случае никаких предположений о свойствах значений элементов не делается, просто каждому целому числу из определенного диапазона ставится в соответствие свое кодовое слово. Поэтому эту группу методов также называют представлением целых чисел (Representation of Integers).

Основная идея кодирования состоит в том, чтобы отдельно описывать порядок значения элемента x_i («экспоненту» E_i) и отдельно – значащие цифры значения x_i («мантиссу» М_i). Значащие цифры начинаются со старшей ненулевой цифры; порядок числа определяется позицией старшей ненулевой цифры в двоичной записи числа. Как и при десятичной записи, порядок равен числу цифр в записи числа без предшествующих незначащих нулей. Например, порядок двоичного числа 000001101 равен 4, а мантисса – 1101.

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

· Fixed + Variable (фиксированная длина экспоненты – переменная длина мантиссы)

· Variable + Variable (переменная длина экспоненты – переменная длина мантиссы)

Коды класса Fixed + Variable

В кодах класса Fixed + Variable под запись значения порядка числа отводится фиксированное количество бит, а значение порядка числа определяет, сколько бит потребуется под запись мантиссы. Для кодирования целого числа необходимо произвести с числом две операции: определение порядка числа и выделение бит мантиссы (можно хранить в памяти готовую таблицу кодовых слов). Рассмотрим процесс построения кода данного класса на примере.

Пример. Пусть R=15 – количество бит исходного числа. Отведем E= 4 бита под экспоненту (порядок), т.к. R≤2⁴. При записи мантиссы можно сэкономить 1 бит: не писать первую единицу т.к. это всегда будет только единица. Таким образом, количество бит мантиссы равно количество бит для порядка минус 1.

Таблица 6 Код класса Fixed + Variable

число	кодовое слово	длина кодового слова
	0010 0 0010 1
	0011 00 0011 01 0011 10 0011 11
…	0100 000 0100 001 0100 010 … 0100 111	..
…	0101 0000 0101 0001 …	..

Коды класса Variable + Variable

В качестве кода числа записываем сначала подряд несколько нулей (их количество равно значению порядка числа), затем единицу как признак окончания экспоненты переменной длины, затем мантиссу переменной длины (как в кодах Fixed + Variable). Рассмотрим пример построение кода этого класса.

Таблица 7 Код класса Variable + Variable

число	кодовое слово	длина кодового слова
	0 1
	00 1 0 00 1 1
	000 1 00 000 1 01 000 1 10 000 1 11
…	0000 1 000 0000 1 001 0000 1 010 …

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

Таблица 8 γ-код Элиаса

число	кодовое слово	длина кодового слова
	01 0 01 1
	00 1 00 00 1 01 00 1 10 00 1 11
…	000 1 000 000 1 001 000 1 010 …

Другим примером кода класса Variable + Variable является омега-код Элиаса (ω-код Элиаса). В нем первое значение (кодовое слово для единицы) задается отдельно. Другие кодовые слова состоят из последовательности групп длиной L₁, L₂, … L_m, начинающихся с единицы. Конец всей последовательности задается нулем. Длина первой группы – 2 бита и далее длина каждой следующей группы равна значению битов предыдущей группы плюс 1. Значение битов последней группы является итоговым значением всей последовательности групп, т.е. первые m-1 групп служат для указания длины последней группы.

Таблица 9 ω-код Элиаса

число	кодовое слово	длина кодового слова
	10 0 11 0
	10 100 0 10 101 0 10 110 0 10 111 0
..	11 1000 0 11 1001 0 … 11 1111 0	..
..	10 100 10000 0 10 100 10001 0 … 10 100 11111 0	..
	10 101 100000 0

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

Рассмотренные типы кодов могут быть эффективны в следующих случаях

1. Вероятности чисел убывают с ростом значений элементов и их распределение близко к такому: P(x) ≥ P(x+1), при любом x, т.е. маленькие числа встречаются чаще, чем большие.

2. Диапазон значений входных элементов не ограничен или неизвестен. Например, при кодировании 32-битовых чисел реально большинство чисел маленькие, но могут быть и большие.

3. При использовании в составе других схем кодирования.