Адаптивная модель, пpи угpозе пpевышения общей суммой накопленных частот значение max_frequency, уменьшает все счетчики. Это пpиводит к тому, что взвешивать последние события тяжелее, чем более pанние. Т.о. показатели имеют тенденцию пpослеживать изменения во входной последовательности, котоpые могут быть очень полезными.
Заключение
Данные хранятся в форме, которая обеспечивает их наиболее тривиальное использование, скажем: обычные книжные тексты, ASCII коды текстовых редакторов, двоичные коды данных ЭВМ, отдельные отсчеты сигналов в системах сбора данных и т.д. Тем не менее, такое наиболее простое в использовании представление данных спрашивает вдвое - втрое, а иногда и в сотни раз больше места для их сохранения и полосу частот для их передачи, чем на самом деле нужно. Потому сжатие данных – это одно из наиболее злободневных направлений современной радиотехники.
Таким образом, цель сжатия данных - обеспечить компактное представление данных, производимых источником, для их более экономного сохранения и передачи по каналам связи.
В данной курсовой работе также были рассмотрены вопросы архивации данных различными методами: сжатие без потерь и с потерями данных.
В практической части был реализован алгоритм арифметического кодирования и создана программа «Архиватор» со всеми необходимыми функциями.
Для реализации использовался язык C# и визуальная среда программирования Microsoft Visual Studio. В результате программное обеспечение очень компактно, интуитивно понятно и эффективно в работе.
Список литературы:
1. Нечта И.В. Введение в информатику [Электронный ресурс]: учебно-методическое пособие/ И.В. Нечта— Электрон. текстовые данные.— Новосибирск: Сибирский государственный университет телекоммуникаций и информатики, 2016.
2.Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — Диалог-МИФИ, 2009.
3.Алгоритмы архивации данных http://www.getinfo.ru/article473.html
4.Т.О. Сундукова, Г. В. Ваныкина Структуры и алгоритмы компьютерной обработки данных http://www.iprbookshop.ru/57384.html?replacement=1
5.Метод Xаффмана и родственные методы http://www.compression.ru/arctest/descript/huffmans.htm
6.Д. Сэломон. Сжатие данных, изображения и звука. — М.: Техно-сфера, 2010.
7.Работа со сжатыми данными https://studfiles.net/preview/4299290/page:2/
8.Семенов Ю.А. Сжатие данных с использованием преобразования Барроуза-Вилера https://knowledge.allbest.ru/programming/d-2c0a65625a2bd69b4c43a89421316c27.html
9.Сжатие с потерями https://spravochnick.ru/informatika/kodirovanie_informacii/szhatie_informacii_s_poteryami/
Приложение 1 . Программный код
// Количество бит для кода
const int bits_in_register = 16;
// Максимально возможное значение кода
const int top_value = (int)(((long)1 << bits_in_register) - 1);
// Диапазоны
const int first_qtr = (top_value / 4 + 1);
const int half = (2 * first_qtr);
const int third_qtr = (3 * first_qtr);
// Количество символов алфавита
const int no_of_chars = 256;
// Специальный символ Конец файла
const int eof_symbol = (no_of_chars + 1);
// Всего символов в модели
const int no_of_symbols = (no_of_chars + 1);
// Порог частоты для масштабирования
const int max_frequency = 16383;
// Таблицы перекодировки
public int[] index_to_char = new int[no_of_symbols];
public int[] char_to_index = new int[no_of_chars];
// Таблицы частот
public int[] cum_freq = new int[no_of_symbols + 1];
public int[] freq = new int[no_of_symbols + 1];
// Регистры границ и кода
public static long low, high;
public static long value;
// Поддержка побитовых операций с файлами
public static long bits_to_follow;
// Буфер
public static int buffer;
// Количество бит в буфере
public static int bits_to_go;
// Количество бит после конца файла
public static int garbage_bits;
// Указатель на входной файл
FileStream datain;
// Указатель на выходной файл
FileStream dataout;
//--------------------------------------------------------------
// Инициализация адаптивной модели
public void start_model ()
{
int i;
// Установки таблиц перекодировки
for ( i = 0; i < no_of_chars; i++)
{
char_to_index [i] = i + 1;
index_to_char [i + 1] = i;
}
// Установка счетчиков накопленных частот
for ( i = 0; i <= no_of_symbols; i++)
{
freq [i] = 1;
cum_freq[i] = no_of_symbols - i;
}
freq [0] = 0;
}
//------------------------------------------------------------
// Обновление модели очередным символом
void update_model(int symbol)
{
// Новый индекс
int i;
int ch_i, ch_symbol;
int cum;
// Проверка на переполнение счетчика частоты
if (cum_freq[0] == max_frequency)
{
cum = 0;
/* Масштабирование частот при переполнении (если счетчики частот достигли своего максимума, то делим на пополам) */
for (i = no_of_symbols; i >= 0; i--)
{
freq[i] = (freq[i] + 1) / 2;
cum_freq[i] = cum;
cum += freq[i];
}
}
/* Обновление перекодировочных таблиц в случае перемещения символа */
for (i = symbol; freq[i] == freq[i - 1]; i--) ;
if (i < symbol)
{
ch_i = index_to_char[i];
ch_symbol = index_to_char[symbol];
index_to_char[i] = ch_symbol;
index_to_char[symbol] = ch_i;
char_to_index[ch_i] = symbol;
char_to_index[ch_symbol] = i;
}
// Увеличить значение счетчика частоты для символа
freq[i] += 1;
// Обновление значений в таблицах частот
while (i > 0)
{
i -= 1;
cum_freq[i] += 1;
}
}
//------------------------------------------------------------
// Инициализация побитового ввода
void start_inputing_bits ()
{
bits_to_go = 0;
garbage_bits = 0;
}
//------------------------------------------------------------
// Ввод очередного бита сжатой информации
int input_bit ()
{
int t;
// Чтение байта если буфер пуст
if (bits_to_go == 0)
{
buffer = datain.ReadByte();
if (buffer == -1)
{
/* Помещение битов после конца файла, с проверкой небольшого их количества */
garbage_bits += 1;
if (garbage_bits > bits_in_register - 2)
{
Application.Exit();
}
eof = buffer;
}
bits_to_go = 8;
}
// Выдача очередного бита с правого конца
t = buffer & 1;
buffer >>= 1;
bits_to_go -= 1;
return t;
}
//------------------------------------------------------------
// Инициализация побитового вывода
public void start_outputing_bits ()
{
buffer = 0;
bits_to_go = 8;
}
//------------------------------------------------------------
// Вывод очередного бита сжатой информации
public void output_bit(int bit)
{
// Бит - в начало буфеpа
buffer >>= 1;
if (bit == 1)
buffer |= 0x80;
bits_to_go -= 1;
// Вывод полного буфера
if (bits_to_go == 0)
{
dataout.WriteByte((byte)buffer);
bits_to_go = 8;
}
}
//------------------------------------------------------------
// Очистка буфера побитового вывода
public void done_outputing_bits ()
{
dataout.WriteByte((byte)(buffer >> bits_to_go));
}
//------------------------------------------------------------
// Вывод указанного бита и отложенных ранее
public void output_bit_plus_follow(int bit)
{
output_bit(bit);
while (bits_to_follow > 0)
{
output_bit(
bit + 2);
bits_to_follow--;
}
}
//------------------------------------------------------------
// Инициализация регистров границ и кода перед началом сжатия
public void start_encoding()
{
// Полный кодовый интервал
low = 0L;
high = top_value;
bits_to_follow = 0L;
}
//------------------------------------------------------------
// Очистка побитового вывода
public void done_encoding ()
{
/* Вывод двух бит, определяющих четверть, лежащую в текущем интервале */
bits_to_follow++;
if (low < first_qtr)
output_bit_plus_follow (0);
else
output_bit_plus_follow (1);
}
//------------------------------------------------------------
/* Инициализация регистров перед декодированием.
Загрузка начала сжатого сообщения*/
void start_decoding ()
{
int i;
int a;
value = 0L;
// Воод бит для заполнения значения кода
for (i = 1; i <= bits_in_register; i++)
{
a = input_bit();
value = 2 * value + a;
}
// Текущий интервал равен исходному
low = 0L;
high = top_value;
}
//------------------------------------------------------------
// Кодирование очередного символа
public void encode_symbol(int symbol)
{
// Ширина текущего кодового интервала
long range;
range = (long)(high - low) + 1;
// Пересчет значений границ
high = low + (range*cum_freq[symbol - 1]) / cum_freq[0] - 1;
low = low + (range*cum_freq[symbol]) / cum_freq[0];
// Вывод битов
for ( ; ; )
{
// Если в нижней половине
if (high < half)
output_bit_plus_follow(0);
// Если в верхней половине
else if (low >= half)
{
output_bit_plus_follow(1);
low -= half;
high -= half;
}
/* Если текущий интервал содержит середину, то вывод еще одного обратного бита позже */
else if (low >= first_qtr && high < third_qtr)
{
bits_to_follow += 1;
low -= first_qtr;
high -= first_qtr;
}
else
break;
// Расширить текущий рабочий кодовый интервал
low = 2 * low;
high = 2 * high + 1;
}
}
//------------------------------------------------------------
// Декодирование очередного символа
int decode_symbol ()
{
// Ширина интервала
long range;
// Накопленная частота
int cum;
// Декодируемый символ
int symbol;
int a;
// Определение текущего масштаба частот
range = (long) (high - low) + 1;
// Hахождение значения накопленной частоты для value
cum=(int)((((long)(value-low)+1)*cum_freq[0]-1)/ range);
// Поиск соответствующего символа в таблице частот
for (symbol = 1; cum_freq [symbol] > cum; symbol++);
// Пересчет границ
high = low + (range*cum_freq[symbol - 1]) / cum_freq[0] - 1;
low = low + (range * cum_freq [symbol]) / cum_freq [0];
// Удаление очередного символа из входного потока
for (;;)
{
// Расширение нижней половины
if (high < half)
{
}
// Расширение верхней половины
else if (low >= half)
{
value -= half;
low -= half;
high -= half;
}
// Расширение середины
else if (low >= first_qtr && high < third_qtr)
{
value -= first_qtr;
low -= first_qtr;
high -= first_qtr;
}
else
break;
// Увеличение масштаба интервала
low = 2 * low;
high = 2 * high + 1;
// Добавить новый бит
a = input_bit();
value = 2 * value + a;
}
return symbol;
}
//--------------------------------------------------------------
// Собственно адаптивное арифметическое кодирование
public void encode(string infile, string outfile)
{
int ch, symbol;
try
{
dataout = new FileStream(outfile, FileMode.Create);
}
catch (IOException exc)
{
return;
}
try
{
datain = new FileStream(infile, FileMode.Open);
}
catch (FileNotFoundException exc)
{
return;
}
start_model();
start_outputing_bits();
start_encoding();
// Цикл обработки символов
for ( ; ; )
{
try
{
// Чтение исходного символа
ch = datain.ReadByte();
}
catch (Exception exc)
{
return;
}
// Выход при достижении конца файла
if (ch == -1)
break;
// Найти рабочий символ
symbol = char_to_index[ch];
// Закодировать символ
encode_symbol(symbol);
// Обновить модель
update_model(symbol);
}
// Закодировать символ конца файла
encode_symbol(eof_symbol);
// Завершение кодирования
done_encoding();
done_outputing_bits();
dataout.Close();
datain.Close();
}
//------------------------------------------------------------
// Собственно адаптивное арифметическое декодирование
void decode(string infile, string outfile)
{
int ch, symbol;
try
{
dataout = new FileStream(outfile, FileMode.Create);
}
catch (IOException exc)
{
return;
}
try
{
datain = new FileStream(infile, FileMode.Open);
}
catch (FileNotFoundException exc)
{
return;
}
start_model ();
start_inputing_bits ();
start_decoding ();
// Цикл обработки сиволов
for (;;)
{
// Получаем индекс символа
symbol = decode_symbol ();
if (symbol == eof_symbol)
break;
// Получаем декодированный символ
ch = index_to_char [symbol];
// Записываем в выходной файл
dataout.WriteByte((byte)ch);
// Обновляем модель
update_model (symbol);
}
dataout.Close();
datain.Close();
}
Приложение 2. Интерфейс программы
Примечание. Для работы программы необходим Microsoft .NET Framework 2.0.
Список литературы:
1. Нечта И.В. Введение в информатику [Электронный ресурс]: учебно-методическое пособие/ И.В. Нечта— Электрон. текстовые данные.— Новосибирск: Сибирский государственный университет телекоммуникаций и информатики, 2016.
2.Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — Диалог-МИФИ, 2009.
3.Алгоритмы архивации данных http://www.getinfo.ru/article473.html
4.Т.О. Сундукова, Г. В. Ваныкина Структуры и алгоритмы компьютерной обработки данных http://www.iprbookshop.ru/57384.html?replacement=1
5.Метод Xаффмана и родственные методы http://www.compression.ru/arctest/descript/huffmans.htm
6.Д. Сэломон. Сжатие данных, изображения и звука. — М.: Техно-сфера, 2010.
7.Работа со сжатыми данными https://studfiles.net/preview/4299290/page:2/
8.Семенов Ю.А. Сжатие данных с использованием преобразования Барроуза-Вилера https://knowledge.allbest.ru/programming/d-2c0a65625a2bd69b4c43a89421316c27.html
9.Сжатие с потерями https://spravochnick.ru/informatika/kodirovanie_informacii/szhatie_informacii_s_poteryami/ |
Скачать 340.59 Kb.