Алгоритм 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.txt2 4492 449100%222.jpg43 81644 026100,48%333.docx125 124123 71998,88%444.doc168 960151 23189,51%555.bmp747 57434 5854,64%666.exe3 941 3123 962 809100,55%777.avi733 470 870738 582 664100,7%

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

Из полученных результатов можно сделать вывод о том, что степень сжатия зависит от типа файла. Файлы 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)

{File, FileCode, FileDecode;Proc;((e. Argument as Str).PK == Pack. Packed)

{. 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

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

Больше работ по теме: