Неравномерное кодирование метод шеннон фано. Префиксный код Шеннона-Фано
Иногда возникает необходимость перенести SQL базу данных с одного SQL-сервера на другой. Обычно процесс переноса данных заключается в создании резервной копии базы данных и восстановлении ее на другом SQL-сервере. Однако, казалось бы, в такой простой операции могут возникать разного рода трудности. В данной статье мы попробуем разобраться с некоторыми из них.
1. Если база данных с таким именем уже существует
Если при переносе базы данных обнаружится, что база данных с таким именем уже существует, или при восстановлении возникает ошибка, что файл базы данных с таким именем уже существует, требуется вручную указать новое имя базы данных и/или папку, в которой будут размещаться физические файлы БД. Это можно сделать в SQL Server Managment Studio, указав при восстановлении новое имя базы данных на закладке Общие
и папку, в которой должны будут размещаться файлы БД (закладка Файлы)
2. Перенос базы данных Альта-ГТД вместе с дополнительными базами ЭД
Если требуется перенести базу данных Альта-ГТД вместе с дополнительными базами ЭД, то необходимо:
1. Создать средствами программы Альта-ГТД резервную копию базы данных вместе с дополнительными базами. Для этого необходимо выполнить Сервис - Администратор SQL - Бэкап SQL базы данных, после чего утвердительно ответить на вопрос о необходимости резервного копирования дополнительных ЭД-баз. После того, как операция по созданию резервных копий дополнительных баз будет завершена, программа выдаст информационное окно с описанием всех созданных бэкап-файлов. Эти файлы, а также бэкап-файл рабочей базы данных необходимо перенести на другой SQL-сервер.
2. Восстановить базы данных из резервных копий. Если на сервере уже имеется БД с таким названием, то ее необходимо восстановить с другим названием (см. раздел 1).
3. Если при восстановлении была переименована рабочая база данных, тогда необходимо для всех дополнительных баз выполнить скрипт:
UPDATE [Имя_Доп_Базы].. SET = "_gtd_ed@Имя_Основной_Базы"
4. Если при восстановлении была переименована одна или несколько дополнительных баз, то для каждой из них необходимо выполнить скрипт
UPDATE [Имя_Основной_Базы].. SET = "Новое_Имя_Доп_Базы" WHERE = "Старое_Имя_Доп_Базы"
Одно и тоже сообщение можно закодировать различными способами. Наиболее выгодным является такой код, при использование которого на передачу сообщений затрачивается минимальное время. Если на передачу каждого элемента символа (например, 0 или 1) тратится одно и то же время, то оптимальным будет такой код, при использование которого на передачу сообщения заданной длины будет затрачено минимальное количество элементарных символов. Коды Шеннона – Фано являются префиксными, т.е. никакое кодовое слово не является префиксом любого другого. Данное свойство позволяет однозначно декодировать любую последовательность кодовых слов
Рассмотрим принцип построения одного из первых алгоритмов сжатия, который сформулировали американские ученые Шеннон и Фано на примере букв русского алфавита. Алгоритм использует коды переменной длины, т.е. часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся – кодом большей длины .
Чтобы составить такой код, очевидно, нужно знать частоты появления букв в русском тексте. Эти частоты приведены в таблице 1 . Буквы в таблице расположены в порядке убывания частот.
Таблица 1
Частота появления букв русского алфавита
Пользуясь таблицей, можно составить наиболее экономичный код на основе соображений, связанных с количеством информации. Очевидно, код будет самым экономичным, когда каждый элементарный символ будет передавать максимальную информацию. Рассмотрим элементарный символ (т. е. изображающий его сигнал) как физическую систему с двумя возможными состояниями: 0 и 1. Информация, которую дает этот символ, равна энтропии этой системы и максимальна в случае, когда оба состояния равновероятны; в этом случае элементарный символ передает информацию 1 (двоичная единица). Поэтому основой оптимального кодирования будет требование, чтобы элементарные символы в закодированном тексте встречались в среднем одинаково часто.
Идея кодирования состоит в том, что кодируемые символы (буквы или комбинации букв) разделяются на две приблизительно равновероятные группы: для первой группы символов на первом месте комбинации ставится 0 (первый знак двоичного числа, изображающего символ); для второй группы − 1. Далее каждая группа снова делится на две приблизительно равновероятные подгруппы; для символов первой подгруппы на втором месте ставится 0; для второй подгруппы − единица и т. д.
Продемонстрируем принцип построения кода Шеннона − Фано на примере материала русского алфавита (см. табл. 1). Отсчитаем первые шесть букв (от «−» до «т»); суммируя их вероятности (частоты), получим 0,498; на все остальные буквы от «н» до «ф» придется приблизительно такая же вероятность 0,502. Первые шесть букв (от «−» до «т») будут иметь на первом месте двоичный знак 0. Остальные буквы (от «н» до «ф») будут иметь на первом месте единицу. Далее снова разделим первую группу на две приблизительно равновероятные подгруппы: от «−» до «о» и от «е» до «т»; для всех букв первой подгруппы на втором месте поставим нуль, а второй подгруппы − единицу. Процесс будем продолжать до тех пор, пока в каждом подразделении не останется ровно одна буква, которая будет закодирована определенном двоичным числом. Механизм построения показан на таблице 2, а сам код приведен в таблице 3.
Таблица 2
Механизм построения кода Шеннона – Фано на примере русского алфавита
| Двоичные знаки | |||||||||
| Буквы | 1 й | 2 й | 3 й | 4 й | 5 й | 6 й | 7 й | 8 й | 9 й |
| - | |||||||||
| о | |||||||||
| е | |||||||||
| а | |||||||||
| и | |||||||||
| т | |||||||||
| н | |||||||||
| с | |||||||||
| р | |||||||||
| в | |||||||||
| л | |||||||||
| к | |||||||||
| м | |||||||||
| д | |||||||||
| п | |||||||||
| у | |||||||||
| я | |||||||||
| ы | |||||||||
| з | |||||||||
| ъ, ь | |||||||||
| б | |||||||||
| г | |||||||||
| ч | |||||||||
| й | |||||||||
| х | |||||||||
| ж | |||||||||
| ю | |||||||||
| ш | |||||||||
| ц | |||||||||
| щ | |||||||||
| э | |||||||||
| ф |
Таблица 3
Результат кодирования букв русского алфавита кодом Шеннона - Фано
Пример 4. Запишем фразу «способ кодирования», используя код Шеннона - Фано.
Решение: Воспользуемся таблицей 3 и получим следующий результат:
(1001)с (110011)п (001)о (1001)с (001)о (111010)б (000)пробел
(10111)к (001)о (110010)д (0110)и (10100)р (001)о (10101)в
(0101)а (1000)н (0110)и (110110)я
Заметим, что здесь нет необходимости отделять друг от друга буквы специальным знаком, так как и без этого декодирование выполняется однозначно благодаря свойству префиксности: ни одна более короткая кодовая комбинация не является началом более длинной кодовой комбинации. Действительно, из таблицы 3 видно, что самыми короткими являются коды для символов «пробел» и «о». При этом не один другой более длинный код не имеет в начале последовательности 000 («пробел») и 001 («о»). То же самое можно наблюдать и для всех других двоичных последовательностей кода Шеннона – Фано, которые приведены в таблице 3.
Необходимо отметить, что любая ошибка при кодирование (случайное перепутывание знаков 0 или 1) при таком коде губительна, так как декодирование всего следующего за ошибкой текста становится невозможным.
Пример 5. Определим, является ли рассмотренный нами код оптимальным при отсутствие ошибок?
Решение: Найдем среднюю информацию, приходящуюся на один элементарный символ (0 или 1), и сравним ее с максимально возможной информацией, которая равна единице. Для этого найдем сначала среднюю информацию, содержащуюся в одной букве передаваемого текста, т. е. энтропию на одну букву (см. формулу 8):
По таблице 1 определяем среднее число элементарных символов на букву:
Таким образом, информация на один символ весьма близка к своему верхнему пределу единице, а данный код весьма близок к оптимальному.
В случае использования пятиразрядного двоичного кода информация на один символ:
Пример 6. Пусть по каналу связи получено сообщение (слово на русском языке) закодированное кодом Шеннона – Фано: 10111001110010010010100.
Необходимо декодировать данную последовательность.
Решение: Процесс декодирования основывается на свойстве префиксности кода и выполняется слева на право. Из таблицы 3 видно, что минимальная длина кода составляет три бита. Отсчитает три бита от начала принятой кодовой комбинации, получим – 101. В таблице такой код отсутствует, поэтому добавляем еще один бит, получим – 1011. Данного кода также нет в таблице, следовательно, необходимо добавить еще один бит, получим комбинацию – 10111, которой соответствует буква «к». Кодовая комбинация 10111 исключается из принятой кодовой комбинации и заменяется исходным символом (буква «к»). Процесс декодирования остальных букв принятого сообщения выполняется аналогично.
Полный процесс декодирования приведен в таблице 4. Знак «-» в таблице означает, что в таблице 3 отсутствует выбранный код.
Таблица 4
Процесс декодирования сообщения
| Принятая кодовая последовательность | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| к | ||||||||||||||||||||||
| к | о | |||||||||||||||||||||
| к | о | - | ||||||||||||||||||||
| к | о | - | ||||||||||||||||||||
| к | о | - | ||||||||||||||||||||
| к | о | д | ||||||||||||||||||||
| к | о | д | - | |||||||||||||||||||
| к | о | д | е | |||||||||||||||||||
| к | о | д | е | - | ||||||||||||||||||
| к | о | д | е | - | ||||||||||||||||||
| к | о | д | е | р |
Итак, слово, полученное в результате декодирования принятой кодовой комбинации – «кодер».
Рассмотрим алгоритм вычисления кодов Шеннона-Фано (для наглядности возьмём в качестве примера последовательность "aa bbb cccc ddddd"). Для вычисления кодов, необходимо создать таблицу уникальных символов сообщения c(i) и их вероятностей p(c(i)) , и отсортировать её в порядке невозрастания вероятности символов.
| c(i) | p(c(i)) |
| d | 5 / 17 |
| c | 4 / 17 |
| space | 3 / 17 |
| b | 3 / 17 |
| a | 2 / 17 |
Далее, таблица символов делится на две группы таким образом, чтобы каждая из групп имела приблизительно одинаковую частоту по сумме символов. Первой группе устанавливается начало кода в "0", второй в "1". Для вычисления следующих бит кодов символов, данная процедура повторяется рекурсивно для каждой группы, в которой больше одного символа. Таким образом для нашего случая получаем следующие коды символов:
Длина кода s(i) в полученной таблице равна int(-lg p(c(i))) , если сиволы удалость разделить на группы с одинаковой частотой, в противном случае, длина кода равна int(-lg p(c(i))) + 1 .
длиной в 39 бит. Учитывая, что оргинал имел длину равную 136 бит, получаем коэффициент сжатия ~28% - не так уж и плохо.
Глядя на полученную последовательность, возникает вопрос: "А как же теперь это расжать?". Мы не можем, как в случае кодирования, заменять каждые 8 бит входного потока, кодом переменной длины. При расжатии нам необходимо всё сделать наоборот - заменить код переменной длины символом длиной 8 бит. В данном случае, лучше всего будет использовать бинарное дерево, листьями которого будут являтся символы (аналог дерева Хаффмана).
Кодирование Шеннона-Фано является достаточно старым методом сжатия, и на сегодняшний день оно не представляет особого практического интереса (разве что как упражнение по курсу структур данных). В большинстве случаев, длина сжатой последовательности, по данному методу, равна длине сжатой последовательности с использованием кодирования Хаффмана. Но на некоторых последовательностях всё же формируются не оптимальные коды Шеннона-Фано, поэтому сжатие методом Хаффмана принято считать более эффективным. Для примера, рассмотрим последовательность с таким содержанием символов: "a" - 14, "b" - 7, "c" - 5, "d" - 5, "e" - 4. Метод Хаффмана сжимает её до 77 бит, а вот Шеннона-Фано до 79 бит.
|
Как же мы делили на группы? Достаточно просто:
Из-за такой неопределённости у некоторых людей возникают даже такие мысли: "... программа иногда назначает некоторым символам..." и так далее - рассуждения о длине кодов. Если вы не пишете AI, то такое понятие, как "программа иногда" что-то делает, звучит смешно. Правильно реализованный алгоритм - работает строго опеределённо.
Загрузка...
