Алгоритм RLE

  • Вид работы:
    Контрольная работа
  • Предмет:
    Информационное обеспечение, программирование
  • Язык:
    Русский
    ,
    Формат файла:
    MS Word
    75,18 Кб
  • Опубликовано:
    2013-05-29
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

Алгоритм RLE

1. Описание алгоритма

RLE - алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, которая содержит сам повторяющийся символ и количество его повторов.

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

Псевдокод сжатия:

1.      Пока не конец Входного потока

.1.     Читать Символ

.2.     Текущий символ равно Символ

.3.     Длина цепочки равна 1

1.4.   Пока Текущий символ равен Символ И не конец Входного потока

.4.1.  Читать Текущий символ

1.4.2. Если Текущий символ равен Символ, то

.4.2.1.         Увеличить Длину цепочки

.5.     Символ равно Текущий символ

1.6.   Если Длина цепочки больше 1, то

.6.1.  Записать в Выходной поток: Признак повторения, Длину цепочки и Символ

1.7.   Иначе

.7.1.  Вынести Символ в Выходной поток

Псевдокод декодирования:

1.      Пока не конец Входного потока

.1.     Читать Символ

.2.     Если Символ равен Признаку повторения, то

.2.1.  Развернуть цепочку в Выходной поток

.3.     Иначе

1.3.1. Вывести в Выходной поток Символ

2. Пример и описание реализации

Пример:

Символ повторения:!

Входной поток: AAAAABBBBACCCC

Выходной поток:! 5A! 4B A! 4C

В моей реализации я не кодирую символы, если длина последовательности меньше 3. Так как при последовательности: AABB; мы получим:! 2A! 2B. А это на 33% больше исходного потока. Также при обнаружении, при сжатии, во входном потоке символа обозначающий признак повторения, то он кодируется как Признак_повторенияNПризнак_повторения. Причем N будет находиться в значении от 1. Например: A! B; кодируется как: A! 1! B.

3. Анализ эффективности

Теоретическая оценка

При кодировании с помощью алгоритма RLE, длина выходного потока может оказаться больше входного, если в нём часто встречается признак повторения в последовательности меньше 3 символов, и редко встречаются другие последовательности длиной больше 3 символов.

В итоге мы можем получить следующие степени сжатия при условии что число вариантов символа равно максимальному числу повторения:

·        Максимальная степень сжатия: , где N - это число вариантов одного символа; практически возможно только в том случае, если все символы во входном потоке встречаются только в последовательности длина которой равна максимальному числу повторений.

·        Минимальная степень сжатия: , но такой вариант возможен только при наличии во входном потоке только 1 символа, который является признаком повторения, что практически не встречается

·        Средняя же оценка сильно зависит от входного потока, а именно от типа сжимаемого файла

4. Экспериментальная оценка

Для анализа эффективности были выбраны файлы различного типа и разного размера. Полученные результаты представлены в следующих таблицах:

Тип файла

Размер исходного файла (байт)

Размер сжатого файла (байт)

Степень сжатия

111.txt

2 449

2 449

100%

222.jpg

43 816

44 026

100,48%

333.docx

125 124

123 719

98,88%

444.doc

168 960

151 231

89,51%

555.bmp

747 574

34 585

4,64%

666.exe

3 941 312

3 962 809

100,55%

777.avi

733 470 870

738 582 664


Визуальная эффективность сжатия показана на следующей диаграмме:


Из полученных результатов можно сделать вывод о том, что степень сжатия зависит от типа файла. Файлы JPEG, DOCX, AVI, DOC являются уже сжатыми и поэтому практически не поддаются сжатию используя алгоритм RLE, либо вообще получаем отрицательный эффект. Файлы TEXT и EXE сильно зависят от содержания поэтому тут возможно различные варианты. А файлы BMP являются несжатыми и в большинстве случаев сжатие происходит с хорошим коэффициентом.

5. Исходный код

.cs:

using System;System. Collections. Generic;System. ComponentModel;System. Data;System. Drawing;System. Linq;System. Text;System. Windows. Forms;System.IO;RLE

{partial class Form1: Form

{File;FileCode;FileDecode;RLE;Form1 ()

{();= new RLE();. Percent += new IntHandler (RLE_PercentChanged);

}RLE_PercentChanged (int t) {ProgressBar. Value = t;}void Packed (object sender, EventArgs e)

{(! RLE. IsBusy)

{. FileName = «»;. Filter = «»;(sender == null || OpenDialog. ShowDialog() == DialogResult.OK)

{(sender == null) OpenDialog. FileName = File;. FileName = OpenDialog. FileName +».rle»;. Filter = «Файлы RLE|*.rle»;. AddExtension = true;. CreatePrompt = false;(SaveDialog. ShowDialog() == DialogResult.OK)

{(SaveDialog. FileName == OpenDialog. FileName)

{.IO. File. Move (OpenDialog. FileName, OpenDialog. FileName +».bak»);= OpenDialog. FileName +».bak»;

}

{= OpenDialog. FileName;

}= SaveDialog. FileName;. Code (File, FileCode);

}

}

}. Show («Дождитесь окончания процесса!», «Сообщение», MessageBoxButtons.OK, MessageBoxIcon. Information);

}void UnPacked (object sender, EventArgs e)

{(! RLE. IsBusy)

{. FileName = «»;. Filter = «Файлы RLE|*.rle|Все файлы|*.*»;(sender == null || OpenDialog. ShowDialog() == DialogResult.OK)

{(sender == null) OpenDialog. FileName = FileCode;rle =».rle»;isNorm = true;(int i = 0; i < 4 && isNorm; i++)(OpenDialog. FileName [OpenDialog. FileName. Length - 4 + i]!= rle[i])= false;(isNorm). FileName = OpenDialog. FileName. Remove (OpenDialog. FileName. Length - 4, 4);. FileName = OpenDialog. FileName;. CreatePrompt = false;(SaveDialog. ShowDialog() == DialogResult.OK)

{(SaveDialog. FileName == OpenDialog. FileName)

{.IO. File. Move (OpenDialog. FileName, OpenDialog. FileName +».bak»);= OpenDialog. FileName +».bak»;

}

{= OpenDialog. FileName;

}= SaveDialog. FileName;. Decode (FileCode, FileDecode);

}

}

}. Show («Дождитесь окончания процесса!»);

}void Form1_FormClosing (object sender, FormClosingEventArgs e)

{(RLE. IsBusy)

{(MessageBox. Show («Вы уверены что хотите прервать процесс?», «Выход», MessageBoxButtons. YesNo) == DialogResult. Yes)

{. Stop(true);. Cancel = false;

}. Cancel = true;

}

}void Packed_DragDrop (object sender, DragEventArgs e)

{[] s = (string[]) e. Data. GetData (DataFormats. FileDrop, false);(s!= null)(s. Length == 1)

{= s[0];(null, null);

}. Show («Копируйте по одному файлу!», «Сообщение», MessageBoxButtons.OK, MessageBoxIcon. Information);

}void UnPacked_DragDrop (object sender, DragEventArgs e)

{[] s = (string[]) e. Data. GetData (DataFormats. FileDrop, false);(s!= null)(s. Length == 1)

{= s[0];(null, null);

}. Show («Копируйте по одному файлу!», «Сообщение», MessageBoxButtons.OK, MessageBoxIcon. Information);

}void DragEnter (object sender, DragEventArgs e)

{(e. Data. GetDataPresent (DataFormats. FileDrop)). Effect = DragDropEffects. Move;. Effect = DragDropEffects. None;

}

}

}

RLE.cs:

using System;System. Collections. Generic;System. Linq;System. Text;System.IO;System. Windows. Forms;System. ComponentModel;RLE

{void IntHandler (int t);RLE

{enum Pack {Packed, Unpacked};Str

{Pack PK;string Input;string Output;

}BW;event IntHandler Percent;byte UN = 66;Pred, Tek, Count;Reader;Writer;RLE()

{= new BackgroundWorker();. DoWork += new DoWorkEventHandler (BW_DoWork);. RunWorkerCompleted += new RunWorkerCompletedEventHandler (BW_RunWorkerCompleted);. ProgressChanged += new ProgressChangedEventHandler (BW_ProgressChanged);. WorkerReportsProgress = true;. WorkerSupportsCancellation = true;

}void Stop (bool isForce)

{. CancelAsync();(Percent!= null) Percent(0);(! isForce) MessageBox. Show («Отменено»);

}BW_ProgressChanged (object sender, ProgressChangedEventArgs e)

{(Percent!= null) Percent (e. ProgressPercentage);

}BW_RunWorkerCompleted (object sender, RunWorkerCompletedEventArgs e)

{(! e. Cancelled)

{(Percent!= null) Percent(100);(e. Result!= null)

{(e. Result. GetType() == typeof(string)). Show((string) e. Result);. Show («Выполнено», «Сообщение», MessageBoxButtons.OK, MessageBoxIcon. Information);

}. Show («Выполнено», «Сообщение», MessageBoxButtons.OK, MessageBoxIcon. Information);

}

}BW_DoWork (object sender, DoWorkEventArgs e)

{. ReportProgress(0);= 0;= (e. Argument as Str).Input;= (e. Argument as Str).Output;= new BinaryReader (new FileStream (File, FileMode. Open));= new BinaryWriter (new FileStream (FileCode, FileMode. Create));L = 0;= -1; Tek = -1; Count = 0;

{= Reader. ReadByte();++;

{(BW. CancellationPending)new ApplicationException();(Proc!= (int) (L * 100 / AllByte))

{= (int) (L * 100 / AllByte);. ReportProgress((int) (L * 100 / AllByte));

}(Tek!= Pred)

{();= 1;

}//Tek == Pred

{(Count == 255)

{();= 1;

}++;

}= Tek;= Reader. ReadByte();++;

} while (true);

}(EndOfStreamException)

{(Tek == -1). Show («Файл пуст»);

{();. Close();ResLen = (new FileInfo(FileCode)).Length;. Result = «Сжатие выполнено успешно!\nРазмер Исходного файла:» + string. Format(«{0:0,0.###}», (double) AllByte / 1024.0) +

«KB\nРазмер Сжатого файла:» + string. Format(«{0:0,0.###}», (double) ResLen / 1024.0) +

«KB\nСтепень сжатия:» + string. Format(«{0:F2}», (double) ResLen / (double) AllByte * 100.0) + «%»;

}. Close();. Close();

}(ApplicationException)

{. Close();. Close();.IO. File. Delete(FileCode);

}

}

///////////////////////////////////////////////////// ((e. Argument as Str).PK == Pack. Unpacked)

{. ReportProgress(0);= 0;= (e. Argument as Str).Input;= (e. Argument as Str).Output;= new BinaryReader (new FileStream (FileCode, FileMode. Open));= new BinaryWriter (new FileStream (FileDecode, FileMode. Create));L = 0;

{

{(BW. CancellationPending)new ApplicationException();= Reader. ReadByte();++;

// Proc = (int) (L * 100 / AllByte);(Proc!= (int) (L * 100 / AllByte))

{= (int) (L * 100 / AllByte);. ReportProgress((int) (L * 100 / AllByte));

}(Tek!= UN)

{. Write((byte) Tek);

}

{= Reader. ReadByte();= Reader. ReadByte();+= 2;(Count = 0; Count < Pred; Count++). Write((byte) Tek);

}

} while (true);

}(EndOfStreamException)

{. Close();. Close();

}(ApplicationException)

{. Close();. Close();.IO. File. Delete(FileDecode);

}

}

}InputUN()

{. Write(UN);. Write((byte) 1);. Write(UN);

}InputPred()

{(Count > 0)

{

/*if (Pred == UN)();*/(Count > 1)

{(Count == 2 && Pred!= UN)

{. Write((byte) Pred);. Write((byte) Pred);

}

{. Write(UN);. Write((byte) Count);. Write((byte) Pred);

}

}if (Count == 1)

{(Pred == UN)();. Write((byte) Pred);

}

}

}AllByte;

void Code (string File, string FileCode)

{(! BW. IsBusy)

{info = new FileInfo(File);= (long) info. Length;. RunWorkerAsync (new Str {PK = Pack. Packed, Input = File, Output = FileCode});

}

{. Show («Дождитесь окончания процесса!»);

}

}

bool IsBusy {get {return BW. IsBusy;}}

void Decode (string FileCode, string FileDecode)

{(! BW. IsBusy)

{info = new FileInfo(FileCode);= (long) info. Length;. RunWorkerAsync (new Str {PK = Pack. Unpacked, Input = FileCode, Output = FileDecode});

}

{. Show («Дождитесь окончания процесса!»);

}

}

}

Список литературы

алгоритм программа сжатие файл

1.   «Структуры данных и алгоритмы сжатия информации без потерь» - Методическое пособие, Пантеллев Е.Р. - Иваново 2001 г.

2. http://ru.wikipedia.org/wiki/RLE

Похожие работы на - Алгоритм RLE

 

Не нашли материал для своей работы?
Поможем написать уникальную работу
Без плагиата!