close

Вход

Забыли?

вход по аккаунту

?

kursach koder

код для вставкиСкачать

Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
"Ивановский государственный энергетический университет им. В. И. Ленина"
Кафедра ПОКС
К У Р С О В А Я Р А Б О Т А
Кодер файлов bmp - формата. Алгоритмы RLE и BWT.
по дисциплине "Структуры и алгоритмы обработки данных"
Вариант № 1
Выполнила: студентка гр. 3-42
Бобро А. А.
Проверил: докт. техн. наук
Пантелеев Е. Р.
Иваново 2013
Содержание
1. Задание
2. Краткая теория
3. Описание алгоритмов
4. Настройки для поставленной задачи
5. Исследование эффективности алгоритмов
6. Система тестов
7. Программный код 1. Задание Написать кодер файлов bmp - формата, использующий алгоритм RLE. Использовать предварительное блочное преобразование BWT. Исследовать его эффективность (степень сжатия) на множестве файлов этого формата.
2. Краткая теория Все алгоритмы сжатия оперируют входным потоком информации, минимальной единицей которой является бит, а максимальной - несколько бит, байт или несколько байт. Целью процесса сжатия, как правило, есть получение более компактного выходного потока информационных единиц из некоторого изначально некомпактного входного потока при помощи некоторого их преобразования. Основными техническими характеристиками процессов сжатия и результатов их работы являются:
- степень сжатия или отношение объемов исходного и результирующего потоков;
- скорость сжатия - время, затрачиваемое на сжатие некоторого объема информации входного потока, до получения из него эквивалентного выходного потока;
- качество сжатия - величина, показывающая на сколько сильно упакован выходной поток, при помощи применения к нему повторного сжатия по этому же или иному алгоритму.
В данной работе будет рассматриваться алгоритм RLE, относящийся к группе алгоритмов сжатия информации без потерь, то есть тот, который гарантирует полное соответствие восстановленной информации исходной.
Для улучшений характеристик сжатия будет использован алгоритм BWT.
Если схематично изобразить последовательность преобразований, то она будет следующей:
3. Описание алгоритмов
RLE
Групповое кодирование - Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов сжатия. Сжатие в RLE происходит за счет замены цепочек одинаковых байт на пары "счетчик, значение". Лучший, средний и худший коэффициенты сжатия - 1/32, 1/2, 2/1. Несмотря на то, что кодер RLE, как правило, дает очень незначительное сжатие, он может работать очень быстро. А скорость работы декодера RLE вообще близка к скорости простого копирования блока информации.
К положительным сторонам алгоритма, можно отнести то, что он не требует дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется в различных форматах РСХ, TIFF, ВМР. т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже - с малым числом повторяющихся байтов в сериях.
Алгоритм RLE схематично может быть описан следующим образом:
Псевдокод кодера RLE:
1. Открыть входной поток для чтения.
2. Открыть входной поток для записи. 3. Читать текущий символ. 4. Длина цепочки равна 1.
5. Повторять пока не конец входного потока:
5.1 Читать новый символ
5.2 Если новый символ равен текущему, то увеличиваем длину цепочки.
Иначе:
Если длина цепочки равна 1:
а) Вывести текущий символ в выходной поток.
б) Текущий символ присвоить новый символ
Иначе (длина цепочки > 1):
а) Вывести в выходной поток код цепочки. б) Длина цепочки равна 1
в) Текущий символ присвоить новый символ.
6. Записать в выходной поток коды для остатка входного потока.
BWT - преобразование (преобразование Барроуза -Уилера)
BWT-преобразование (Burrows - Wheeler Transform) - техника для сжатия информации (в особенности текстов), основанная на преобразовании, открытом в 1983 г. и описанная в 1994 г. BWT не сжимает данные, но преобразует блок данных в формат, исключительно подходящий для компрессии.
Прежде всего, следует отметить одну из его особенностей. BWT оперирует сразу целым блоком данных. То есть, ему заранее известны сразу все элементы входного потока или, по крайней мере, достаточно большого блока. Это делает затруднительным использование алгоритма в тех областях применения, где требуется сжатие данных "на лету", символ за символом. Следует отметить, что возможна реализация сжатия данных на основе BWT, обрабатывающая данные последовательно по символам, а не по блокам. Но скоростные характеристики программ, использующих такую реализацию, будут очень далеки от совершенства.
Псевдокод прямого преобразования BWT:
1. Выделение блока во входном потоке (фрагмент фиксированной длины)
2. Выполнение циклического сдвига на блоке (формирование матрицы всех возможных циклических перестановок).
3. Сортировка строк блока по алфавиту (в порядке лексикографии).
После преобразования в выходной поток передаются:
а) Последний столбец в полученном блоке
б) Смещение исходной записи в блоке
Методы, используемые совместно с BWT: как уже было сказано, само по себе преобразование Барроуза-Уилера не сжимает. Эту работу проделывают другие методы, позволяющие толково распорядиться теми свойствами, которыми обладают преобразованные данные (увеличение вероятности появления во входном потоке цепочек не единичной длины) Среди таких методов находится метод кодирование длин повторов (RLE);
4. Настройки алгоритмов
При реализации алгоритмов возникают следующие проблемы:
1. Что использовать в качестве признака кодированных данных?
2. Размер считываемого блока данных
Проблема метода RLE заключается в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других - некодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток в начале кодированных цепочек. Такими метками могут быть, например, характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии и т.п. Таким образом, есть как минимум два выхода из этой ситуации:
1. В качестве индикатора сжатой цепочки выделить одно значение байта, а в случае коллизии с реальными данными экранировать их. Например, если использовать в "служебных" целях значение 255, то при встрече этого значения во входных данных мы вынуждены будем писать "255, 255" и после индикатора использовать максимум 254.
2. Структурировать закодированные данные, указывая количество не только для повторяемых, но и последующих далее одиночных элементов. Тогда мы будем заранее знать, где какие данные.
Первый способ в нашем случае не кажется эффективным, поэтому, в работе, прибегнем ко второму.
Итак, у нас имеется два вида последовательностей: цепочки одиночных элементов (например "4, 2, 0") и цепочки одинаковых элементов (например "0, 0, 0, 0, 0, 0"). Выделим в "служебных" байтах один бит под тип последовательности: 0 - одиночные элементы, 1 - одинаковые. Возьмём для этого, скажем, старший бит байта. В оставшихся 7 битах мы будем хранить длины последовательностей, т.е. максимальная длина кодируемой последовательности - 127 байт. Мы могли бы выделить под служебные нужды, допустим, два байта, но в нашем случае такие длинные последовательности встречаются крайне редко, поэтому проще и экономичней просто разбивать их на более короткие.
Получается, в выходной поток мы будем писать сперва длину последовательности, а далее либо одно повторяемое значение, либо цепочку неповторяемых элементов указанной длины. Следует иметь в виду, что не может быть последовательностей с нулевой длиной, поэтому мы можем увеличить максимальную длину до 128 байт, отнимая от длины единицу при кодировании и прибавляя при декодировании. Таким образом, мы можем кодировать длины от 1 до 128 вместо длин от 0 до 127.
Второе, что можно заметить - не бывает последовательностей одинаковых элементов единичной длины. Поэтому, от значения длины таких последовательностей при кодировании мы будем отнимать ещё единичку, увеличив тем самым их максимальную длину до 129 (максимальная длина цепочки одиночных элементов по-прежнему равна 128). Т.е. цепочки одинаковых элементов у нас могут иметь длину от 2 до 129.
Значит, проблемы решили путем установки в старший бит значения 0 или 1, для различия одиночных и повторяющихся последовательностей, а размер блока возьмем равным 127.
5. Исследование эффективности алгоритмов
Несмотря на то, что кодер RLE, как правило, дает очень незначительное сжатие, он может работать очень быстро. А скорость работы декодера RLE вообще близка к скорости простого копирования блока информации. Алгоритм рассчитан на деловую графику - изображения с большими областями повторяющегося цвета. Ситуация, когда файл увеличивается, для этого простого алгоритма не так уж редка. Ее можно легко получить, применяя групповое кодирование к обработанным цветным фотографиям. Для того, чтобы увеличить изображение в два раза, его надо применить к изображению, в котором значения всех пикселов больше двоичного 11000000 и подряд попарно не повторяются Как можно легко подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза в 32 раза, если для признака повторения используется 2 бита), в худшем увеличивает на 1/128. Лучший, средний и худший коэффициенты сжатия - 1/64, 1/2, 2/1. Степень сжатия сильно зависит от типа данных, например:
Тип файлаСтепень сжатия (тип коэффициента)Полностью черное изображение 64 (Лучший) Монохромное изображение2 (Средний)
Цветное изображение0,5 (Худший)
Также нужно отметить, что благодаря BWT показатели могут быть улучшены. Наиболее эффективно применение BWT-алгоритма для любых данных со стабильными контекстами. Расходы памяти в режиме максимального сжатия довольно близки у всех современных архиваторов. По расходу памяти при декодировании архиваторы на основе BWT занимают промежуточное положение.
Получаем следующие характеристики алгоритма:
Коэффициенты компрессии: Первый вариант(2бита служебные): 32, 2, 0,5. Второй вариант(1 бит служебный): 64, 3, 128/129. (Лучший, средний, худший коэффициенты)
Класс изображений: Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику.
Характерные особенности: К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он не требует дополнительной памяти при архивации и разархивации, а также быстро работает. Интересная особенность группового кодирования состоит в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.
6. Система тестов
Эффективность способа RLE зависит от структуры сжимаемого рисунка. Она тем выше, чем чаще встречаются в нем подряд одноцветные пиксели. Оценить ее в общем случае невозможно , поэтому мы ограничимся следующими примерами, отражающие характерные моменты:
1.
2.
3. 4. 1. Сжатие полностью черного рисунка 2.Монохромное(простое)
3 .Монохромное (сложное)
4.Цветное(256-цветное)
Сводная таблица полученных результатов:
Тип изображения Размер файла до сжатия (Кб)Размер файла после сжатия (Кб)Степень сжатия Полностью черное77177Монохромное (простое)62231Монохромное (сложное)62531,2Цветное (256 цветное)38790,5
Таким образом, мы получаем экспериментальное подтверждение теоритических коэффициентов сжатия. Так, полностью черное изображение имеет высокую степень сжатия, так как его структура представляет собой длинную последовательность повторяющихся одинаковых байтов. Изображение наполовину черно-белое, так же имеет высокую степень сжатия 31 близкую к теоритической (32), так как в нем присутствуют всего 2 вида различных байтов, которые хорошо упорядочены. Сложное монохромное изображение дает степень сжатия -1,2, что приемлемо, так как средний теоритический коэффициент равен 2. И наконец, цветное изображение, наоборот, ухудшает результат коэффициентом равным 0,5, что так же подтверждает теоритическую степень сжатия (из-за большого количества цветов и сложности изображения количество повторяющихся цепочек очень мало). 7.Программный код Класс Form1
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;
namespace WindowsFormsApplication3
{
public partial class Form1 : Form
{
public int getBlockSize()
{
return Convert.ToInt32(textBox1.Text.ToString());
}
public Form1()
{
InitializeComponent();
}
public byte[] bwtOut;
private void Form1_Load(object sender, EventArgs e)
{ }
private void label2_Click(object sender, EventArgs e)
{
}
private void label1_Click(object sender, EventArgs e)
{
}
private void textBox1_TextChanged(object sender, EventArgs e)
{
}
private void textBox2_TextChanged(object sender, EventArgs e)
{
}
public List<byte>codeRle(byte[] bwtOut)//АЛГОРИТМ РЛЕ
{
byte[] d = new byte[1];
d[0] = bwtOut[0];// текущий символ int l = 1;// длина цепочки =1
int notEquals = 1;//длина цепочки НЕ ОДИНАКОВЫХ символов
int i = 0;
List<byte> tempList = new List<byte>();//текущая последовательность байт (НЕ ОДИНАКОВЫХ символов)
List<byte> result = new List<byte>();//результат который возвращает алгоритм РЛЕ для записи в файл
while (i != bwtOut.Length - 1)// пока не конец потока
{
byte[] s = new byte[1];
i++;
s[0] = bwtOut[i];// читаем новый символ
if (s[0] == d[0])// если текущий равен новому
{
if (tempList.Count == 1)//tempList.Count - число элементов в списке НЕ ОДИНАКОВЫХ СИМВОЛОВ
{ result.Add((byte)(0 + 1)); result.Add(tempList[0]);
tempList.Clear();
}
if (tempList.Count > 1)
{
result.Add((byte)(0 + tempList.Count));
for (int t = 0; t < tempList.Count; t++)
{
result.Add(tempList[t]);
}
tempList.Clear();
}
l++;
d[0] = s[0];
}
if (s[0] != d[0])//если два символа не равны, то ...
{
if (l > 1)
{
result.Add((byte)(128 + l));//тип символа + его количество
result.Add(d[0]);
}
notEquals++;
tempList.Add(d[0]);//добавляем этот элемент в список НЕ ОДИНАКОВЫХ ЭЛЕМЕНТОВ
d[0] = s[0];
}
//обработка последних символов
if (i == bwtOut.Length - 1)
{
if (s[0] == d[0])// если текущий равен новому
{
if (tempList.Count == 1)
{
result.Add((byte)(0 + 1));
result.Add(tempList[0]);
tempList.Clear();
}
if (tempList.Count > 1)
{
result.Add((byte)(0 + tempList.Count));
for (int t = 0; t < tempList.Count; t++)
{
result.Add(tempList[t]);
}
tempList.Clear();
}
l++;
d[0] = s[0];
}
if (s[0] != d[0])
{
if (l > 1)
{
result.Add((byte)(128 + l));//тип символа + его количество
result.Add(d[0]);
}
notEquals++;
tempList.Add(d[0]);
d[0] = s[0];
}
} }
return result;//возвращаемый результат алгоритма РЛЕ
}
private void button2_Click(object sender, EventArgs e)
{
OpenFileDialog Open = new OpenFileDialog();
Open.ShowDialog();
string name = Open.FileName;
textBoxNameBefore.Text = name;
byte[] bwtLine = new byte[getBlockSize()];
FileStream fs = new FileStream(name, FileMode.Open);
BinaryReader imageReader = new BinaryReader(fs);
double sizeBefore = imageReader.BaseStream.Length / 1024;
textBoxSizeBefore.Text = (sizeBefore).ToString() + " Кбайт";
Byte[] arr = new Byte[imageReader.BaseStream.Length];
SaveFileDialog save = new SaveFileDialog();//создание объекта диалогового окна для сохоранения файла
save.ShowDialog();//показать диалоговое окно сохранения файла
textBoxNameAfter.Text = save.FileName;
FileStream fs1 = new FileStream(save.FileName, FileMode.OpenOrCreate);//"save.FileName" - имя файла которое пользователь вводит в диалоговом окне сохранения файла BinaryWriter write = new BinaryWriter(fs1);//открытие потока для записи байт в файл
bwtOut = new byte[getBlockSize()];
do
{
if (imageReader.BaseStream.Length - imageReader.BaseStream.Position < getBlockSize()) //если осталось меньше байт чем 1024, то считывать мы будем меньше 1024
arr = imageReader.ReadBytes(Convert.ToInt32(imageReader.BaseStream.Length - imageReader.BaseStream.Position));
else
arr = imageReader.ReadBytes(getBlockSize());//считывает 256 байта в массив arr
bwt.setinput(arr);//создаем объект типа БВТ и передаем в него массив List<byte[]> table = bwt.makeTable();//объявление списка массивов байт для таблицы БВТ
bwtLine = bwt.sort(table);//извлечение последнего столбца из отсортированной таблицы
int numberOfRow = bwt.getNumber(table);//получить номер строки в таблице БВТ для исходного слова
//textBox1.Text += numberOfRow + ", ";
write.Write((byte)numberOfRow);//запись смещения слова в блоке в выходной поток
table.Clear();//очистка таблицы БВТ для дальнейшей работы с ней
bwtOut = codeRle(bwtLine).ToArray();// (ВЫЗОВ РЛЕ) получения результата после обработки строки алгоритмом RLE
write.Write(bwtOut);//запись в выходной поток результата РЛЕ
write.Write((byte)1);//запись в выходной поток символа ESC
}
while (imageReader.BaseStream.Position < imageReader.BaseStream.Length) ; //читаем пока длина файла больше позиции чтения
////т.к. если позиция будет больше длины файла, то это будет означать что мы вышли за его пределы
float sizeAfter = (write.BaseStream.Position / 1024);
textBoxSizeAfter.Text = sizeAfter.ToString() + " Кбайт";
effectivnostSjatia.Text = ((sizeBefore/sizeAfter)).ToString()
}
private void groupBox1_Enter(object sender, EventArgs e)
{
}
private void label6_Click(object sender, EventArgs e)
{
}
private void groupBox3_Enter(object sender, EventArgs e)
{
}
}
}
Класс BWT
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace WindowsFormsApplication3
{
public sealed class ArrayComparer : IComparer<byte[]> {
public ArrayComparer() { }
int IComparer<byte[]>.Compare(byte[] x, byte[] y)
{
return Compare(x, y);
}
public static int Compare(byte[] x, byte[] y)
{
// simple cases
if (x == null) return 1;
if (y == null) return -1;
// get the 2 lengths and the minimum
int xLen = x.Length, yLen = y.Length, len = xLen < yLen ? xLen : yLen;
// loop and test
for (int i = 0; i < len; i++)
{
int result = x[i].CompareTo(y[i]);
if (result != 0) return result; // found a difference
}
if (xLen == yLen) return 0;
return xLen < yLen ? -1 : 1; // different lengths
}
}
class bwt
{
static byte[] input1;//объявление переменной для считанного из файла набора байт которому присваивается значение в "setinput"
public static void setinput(byte[] input)//после вызова "setinput" значение input1 становится равно считаному набору байт из файла
{ input1 = input;
}
public static List<byte> createWord(List<byte> temp, int i)//создание слова для таблицы, возвращает строчку { for (int j = i; j < input1.Length; j++)
{
temp.Add(input1[j]);
}
for (int n = 0; n < i; n++)
{
temp.Add(input1[n]);
}
return temp;
}
// сортировка последнего столбца по алфавиту public static byte[] sort(List<byte[]> table)
{ //lastRow - последний столбик byte[] lastRow = new byte[input1.Length];// массив символов последнего столбца
// int[] corrected = new int[input1.Length];
table.Sort(new ArrayComparer());//стандартная сортировка списка
for (int i = 0; i < input1.Length; i++)//цикл который возвращает последний столбец таблицы table
{
lastRow[i] = table[i][input1.Length - 1];// i- номер строки , input1.Length - 1 - номер последней буквы
} //сортировка таблицы по алфавиту
return lastRow;//вернем из этой функции последний столбик таблицы БВТ
}
// создание блока
public static List<byte[]> makeTable()
{
List<byte[]> table = new List<byte[]>();
List<byte> temp = new List<byte>();// текущая строка в блоке table for (int i = 0; i < input1.Length; i++)
{
temp = createWord(temp, i);//создание текущего слова со смещением в i символов table.Add(temp.ToArray());//добавление слова temp в таблицу
temp.Clear();//очистка текущего слова
}
sort(table);
return table;// возврящаем отсортированный по алфавиту блок
}
// смещение исходной строки в блоке
public static int getNumber(List<byte[]> table)
{ for (int i = 0; i < input1.Length; i++)
{
if(ArrayComparer.Compare(table[i], input1) == 0)
return i;
}
return -1;
}
}
}
3
Документ
Категория
Рефераты
Просмотров
63
Размер файла
417 Кб
Теги
kursach, kodex
1/--страниц
Пожаловаться на содержимое документа