Главная / Банки и базы данных / Стандартные алгоритмы обработки данных

Стандартные алгоритмы обработки данных

ЛАБОРАТОРНАЯ РАБОТА № 9.

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

1. МЕТОДЫ СОРТИРОВКИ

Рассмотрим два метода сортировки: метод пузырьков и метод Шелла. Пусть дан список

L = [1, 5, 3, 7, 8, 6],

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

L = [1, 3, 5, 7, 8, 6]

L = [1, 3, 5, 7, 6, 8]

L = [1, 3, 5, 6, 7, 8]

В методе Шелла находят длину интервала

I = [n / 2]

Где N – число элементов списка, [x] – округленное в большую сторону значение Х. В нашем примере I = 3. Теперь проводим попарно сравнения и перестановки (при необходимости) первого элемента и четвертого, второго и пятого, третьего и шестого (т. е. двух элементов, разница между индексами которых равна 3). Для списка

L = [1, 5, 3, 7, 8, 6]

Получим новый результат

L’ = [1, 5, 3, 7, 8, 6]

Уменьшим интервал вдвое:

I = [n / 4] = 2

Сравниваем и при необходимости переставляем местами элементы первый и третий, второй и четвертый, третий и пятый, четвертый и шестой:

L’’ = [1, 5, 3, 6, 7, 8]

Снова находим новый интервал:

I = [n / 8] = 1

Теперь уже сравниваем и при необходимости меняем местами соседние элементы.

L’’’ = [1, 3, 5, 6, 7, 8]

2. МЕТОДЫ СЖАТИЯ

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

A – 0.14

B – 0.12

C – 0.18

D – 0.10

E – 0.33

F – 0.13

_________

å = 1.0

При кодировке методом Хаффмана буквы располагаются столбиком в порядке убывания частот:

E – 0.33

C – 0.18

A – 0.14

F – 0.13

B – 0.12

D – 0.10

Затем две последние буквы «объединяются» в одну, частота которой равна сумме частот объединяемых букв и список снова упорядочивается:

E – 0.33

(b, d) — 0.22

C – 0.18

A – 0.14

F – 0.13

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

(1) e – 0.33

(a, f) — 0.27

(b, d ) — 0.22

c – 0.18

(2) ((b, d), c) — 0.40

e – 0.33

(a, f) — 0.27

(3) ((b, d), c) — 0.40

(a, b, c, d, e, f)

(e, (a, f)) — 0.60

Теперь присвоим конкретные коды («0» и «1») полученным нами объединениям, начиная с последнего шага. Так, произвольно присвоим код «0» объединению ((b, d), c) и «1» – объединению (e, (a, f)). Далее в объединении ((b, d), c) произвольно присвоим код «1» объединению (b, d) и код «0» – литере с. В объединении (e, (a, f)) произвольно присвоим код «0» литере е и код «1» объединению (a, f).

Наконец, в объединении (b, d) произвольно присвоим «1» литере b и «0» — литере d, а в объединении (a, f) присвоим «1» литере а и «0» – литере f. Теперь покажем, как окончательно получить код каждой литеры. Для этого, начиная с результирующего объединения, последовательно выпишем все объединения, в которые вошла данная литера. Для буквы «а»:

(a, b, c, d, e, f) ® (e, (a, f)) ® (a, f) ® a

1 1 1

(причем под объединениями указываем присваиваемые им коды; результирующее объединение (a, b, c, d, e, f) не учитываем).

Аналогично для литеры b имеем

(a, b, c, d, e, f) ® ((b, d), c) ® (b, d) ® b

0 1 1

Для литеры с:

(a, b, c, d, e, f) ® ((b, d), c) ® c

0 0

И так далее. В итоге результирующие коды для букв:

A: 111 d: 010

B: 11 e: 010

C: 0 f: 110

Средняя длина кода вычисляется по формуле

S=SPI*SI,

где PI – частота буквы; SI – количество битов для ее кодирования. Получим в нашем случае

S=(2 * 0,33 + 3 * 0,67) = 2,67

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

(3 — 2,67) / 3 * 100% = 11%

3. МЕТОДЫ ШИФРОВАНИЯ

Целью шифрования является засекречивание передаваемой информации. Например, при необходимости засекретить базу данных следует применить к ней процедуру шифрования. Общепринято, что устойчивость шифра зависит не от используемого алгоритма, а от ключа, используемого для шифрования. Схемы шифрования могут использовать один или два ключа. Рассмотрим только случай одного ключа. Применение ключа K к данным D реализуется алгоритмом A шифрования, т. е.

Dш =A(K, D)

Где Dш — зашифрованные данные.

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

3.1. Операция перестановки

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

Пусть исходные данные разбиты на 5 блоков по 4 бита:

1000 ½ 0110 ½ 1011 ½ 0111 ½ 0100

B1 B2 B3 B4 B5

Пусть ключ K = 1834526. Ключ K также разбивается на 10 блоков, например по 2 цифры. Если ключ короткий, то он называется простым присоединением.

K’ = 18 ½ 34 ½ 52 ½ 61 ½ 83 ½ 45 ½ 26 ½ 18 ½ 34½ 52

С1 С2 С3 С4 С5 С6 С7 С8 С9 С10

Делим C1 на 5 и находим остаток. Остаток определяет номер блока, с которым меняется местами первый блок B1: 18 mod 5 = 3 ®

B3 B2 B1 B4 B5

Делим теперь C2 на 5 и находим остаток – номер блока, с которым меняется местами B2: 34 mod 5 = 4

B3 B4 B1 B2 B5

Для блока B3: 52 mod 5 = 2

B3 B1 B4 B2 B5

Для блока B4: 61 mod 5 = 1

B2 B1 B4 B3 B5

Для блока B5: 83 mod 5 = 3

B2 B1 B5 B3 B4

3.2. Операция подстановки

Вторая основная операция – подстановки – состоит в сложении по модулю 2 данных и ключа.

Для этого представим ключ в двоичном виде:

K2 = 1111110000110000011110

Запишем ключ под «перемешанными данными» и найдем результат сложения по модулю 2

0110 ½ 1000 ½ 0100 ½ 1011 ½ 0111

Å

1111 ½ 1100 ½ 0011 ½ 0000 ½ 0111

1001 ½ 0100 ½ 0111 ½ 1011 ½ 0000

Таким образом, нами получена комбинация для пересылки. Заметим, что алгоритм DES применяет подстановку и перемешивание несколько раз, используя различное разбиение на блоки.

4. ДЕШИФРОВАНИЕ ДАННЫХ

Операция дешифрования производится в обратном порядке. Сначала восстановим результат подстановки по формуле

D’ = D Å K

Т. е. складываем шифрованные данные с ключом:

1001 | 0100 | 0111 | 1011 | 0000

Å

1111 | 1100 | 0011 | 0000 | 0111

0110 | 1000 | 0100 | 1011 | 0111

Далее по значению ключа:

C1 ½ C2 ½ C3 ½ C4 ½ C5

18 ½ 34 ½ 52 ½ 61 ½ 83

Для блока 5 находим 83 mod 5 = 3.

Это значит, что блок 5 и 3 надо поменять местами. Теперь не трудно сообразить, что процесс полностью восстанавливает исходные данные, но в обратном порядке.

2. ЗАДАНИЕ НА ВЫПОЛНЕНИЕ

1) На основе средств языка FoxPro закодировать алгоритм сортировки и применить его к таблице БД.

2) Найти алгоритмическим путем частоты встречаемости букв в таблице БД.

3) Написать программу шифрования текста (Memo-поля).

3. ВОПРОСЫ

1) Суть метода пузырьков?

2) Суть метода Шелла?

3) Суть метода Хаффмана?

4) За счет чего достигается сжатие по Хаффману?

5) Суть процесса шифрования?

6) Операция подстановки/перестановки?

7) Процесс дешифрования?