Алгоритм RLE

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.7. Иначе

1.7.1. Вынести Символ в Выходной поток Псевдокод декодирования:

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

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

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

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

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. Экспериментальная оценка

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

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

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

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

Form1.cs:

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 RLE

{

public partial class Form1: Form

{

string File;

string FileCode;

string FileDecode;

RLE RLE;

public Form1 ()

{

InitializeComponent ();

RLE = new RLE ();

RLE. Percent += new IntHandler (RLE_PercentChanged);

}

void RLE_PercentChanged (int t) {ProgressBar. Value = t;}

private void Packed (object sender, EventArgs e)

{

if (! RLE. IsBusy)

{

OpenDialog. FileName = ««;

OpenDialog. Filter = ««;

if (sender == null || OpenDialog. ShowDialog () == DialogResult. OK)

{

if (sender == null) OpenDialog. FileName = File;

SaveDialog. FileName = OpenDialog. FileName +". rle";

SaveDialog. Filter = «Файлы RLE|*.rle»;

SaveDialog. AddExtension = true;

SaveDialog. CreatePrompt = false;

if (SaveDialog. ShowDialog () == DialogResult. OK)

{

if (SaveDialog. FileName == OpenDialog. FileName)

{

System.IO. File. Move (OpenDialog. FileName, OpenDialog. FileName +". bak");

File = OpenDialog. FileName +". bak";

}

else

{

File = OpenDialog. FileName;

}

FileCode = SaveDialog. FileName;

RLE. Code (File, FileCode);

}

}

}

else

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

}

private void UnPacked (object sender, EventArgs e)

{

if (! RLE. IsBusy)

{

OpenDialog. FileName = ««;

OpenDialog. Filter = «Файлы RLE|*.rle|Все файлы|*.*»;

if (sender == null || OpenDialog. ShowDialog () == DialogResult. OK)

{

if (sender == null) OpenDialog. FileName = FileCode;

string rle =". rle";

bool isNorm = true;

for (int i = 0; i <� 4 && isNorm; i++)

if (OpenDialog. FileName [OpenDialog. FileName. Length — 4 + i]≠ rle[i])

isNorm = false;

if (isNorm)

SaveDialog. FileName = OpenDialog. FileName. Remove (OpenDialog. FileName. Length — 4, 4);

else

SaveDialog. FileName = OpenDialog. FileName;

SaveDialog. CreatePrompt = false;

if (SaveDialog. ShowDialog () == DialogResult. OK)

{

if (SaveDialog. FileName == OpenDialog. FileName)

{

System.IO. File. Move (OpenDialog. FileName, OpenDialog. FileName +". bak");

FileCode = OpenDialog. FileName +". bak";

}

else

{

FileCode = OpenDialog. FileName;

}

FileDecode = SaveDialog. FileName;

RLE. Decode (FileCode, FileDecode);

}

}

}

else

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

}

private void Form1_FormClosing (object sender, FormClosingEventArgs e)

{

if (RLE. IsBusy)

{

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

{

RLE. Stop (true);

e. Cancel = false;

}

else

e. Cancel = true;

}

}

private void Packed_DragDrop (object sender, DragEventArgs e)

{

string[] s = (string[]) e. Data. GetData (DataFormats. FileDrop, false);

if (s≠ null)

if (s. Length == 1)

{

File = s[0];

Packed (null, null);

}

else

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

}

private void UnPacked_DragDrop (object sender, DragEventArgs e)

{

string[] s = (string[]) e. Data. GetData (DataFormats. FileDrop, false);

if (s≠ null)

if (s. Length == 1)

{

FileCode = s[0];

UnPacked (null, null);

}

else

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

}

private void DragEnter (object sender, DragEventArgs e)

{

if (e. Data. GetDataPresent (DataFormats. FileDrop))

e. Effect = DragDropEffects. Move;

else

e. Effect = DragDropEffects. None;

}

}

}

RLE.cs:

using System;

using System. Collections. Generic;

using System. Linq;

using System. Text;

using System. IO;

using System. Windows. Forms;

using System. ComponentModel;

namespace RLE

{

delegate void IntHandler (int t);

class RLE

{

private enum Pack {Packed, Unpacked};

class Str

{

public Pack PK;

public string Input;

public string Output;

}

BackgroundWorker BW;

public event IntHandler Percent;

const byte UN = 66;

int Pred, Tek, Count;

BinaryReader Reader;

BinaryWriter Writer;

public RLE ()

{

BW = new BackgroundWorker ();

BW. DoWork += new DoWorkEventHandler (BW_DoWork);

BW. RunWorkerCompleted += new RunWorkerCompletedEventHandler (BW_RunWorkerCompleted);

BW. ProgressChanged += new ProgressChangedEventHandler (BW_ProgressChanged);

BW. WorkerReportsProgress = true;

BW. WorkerSupportsCancellation = true;

}

public void Stop (bool isForce)

{

BW. CancelAsync ();

if (Percent≠ null) Percent (0);

if (! isForce) MessageBox. Show («Отменено»);

}

void BW_ProgressChanged (object sender, ProgressChangedEventArgs e)

{

if (Percent≠ null) Percent (e. ProgressPercentage);

}

void BW_RunWorkerCompleted (object sender, RunWorkerCompletedEventArgs e)

{

if (! e. Cancelled)

{

if (Percent≠ null) Percent (100);

if (e. Result≠ null)

{

if (e. Result. GetType () == typeof (string))

MessageBox. Show ((string) e. Result);

else

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

}

else

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

}

}

void BW_DoWork (object sender, DoWorkEventArgs e)

{

string File, FileCode, FileDecode;

int Proc;

if ((e. Argument as Str).PK == Pack. Packed)

{

BW. ReportProgress (0);

Proc = 0;

File = (e. Argument as Str).Input;

FileCode = (e. Argument as Str).Output;

Reader = new BinaryReader (new FileStream (File, FileMode. Open));

Writer = new BinaryWriter (new FileStream (FileCode, FileMode. Create));

long L = 0;

Pred = -1; Tek = -1; Count = 0;

try

{

Tek = Reader. ReadByte ();

L++;

do

{

if (BW. CancellationPending)

throw new ApplicationException ();

if (Proc≠ (int) (L * 100 / AllByte))

{

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

BW. ReportProgress ((int) (L * 100 / AllByte));

}

if (Tek≠ Pred)

{

InputPred ();

Count = 1;

}

else //Tek == Pred

{

if (Count == 255)

{

InputPred ();

Count = 1;

}

else

Count++;

}

Pred = Tek;

Tek = Reader. ReadByte ();

L++;

} while (true);

}

catch (EndOfStreamException)

{

if (Tek == -1)

MessageBox. Show («Файл пуст»);

else

{

InputPred ();

Writer. Close ();

long ResLen = (new FileInfo (FileCode)).Length;

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

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

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

}

Reader. Close ();

Writer. Close ();

}

catch (ApplicationException)

{

Reader. Close ();

Writer. Close ();

System.IO. File. Delete (FileCode);

}

}

/////////////////////////////////////////////////////

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

{

BW. ReportProgress (0);

Proc = 0;

FileCode = (e. Argument as Str).Input;

FileDecode = (e. Argument as Str).Output;

Reader = new BinaryReader (new FileStream (FileCode, FileMode. Open));

Writer = new BinaryWriter (new FileStream (FileDecode, FileMode. Create));

long L = 0;

try

{

do

{

if (BW. CancellationPending)

throw new ApplicationException ();

Tek = Reader. ReadByte ();

L++;

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

if (Proc≠ (int) (L * 100 / AllByte))

{

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

BW. ReportProgress ((int) (L * 100 / AllByte));

}

if (Tek≠ UN)

{

Writer. Write ((byte) Tek);

}

else

{

Pred = Reader. ReadByte ();

Tek = Reader. ReadByte ();

L += 2;

for (Count = 0; Count <� Pred; Count++)

Writer. Write ((byte) Tek);

}

} while (true);

}

catch (EndOfStreamException)

{

Reader. Close ();

Writer. Close ();

}

catch (ApplicationException)

{

Reader. Close ();

Writer. Close ();

System.IO. File. Delete (FileDecode);

}

}

}

void InputUN ()

{

Writer. Write (UN);

Writer. Write ((byte) 1);

Writer. Write (UN);

}

vod InputPred ()

{

if (Count > 0)

{

/*if (Pred == UN)

InputUN ();

else*/

if (Count > 1)

{

if (Count == 2 && Pred≠ UN)

{

Writer. Write ((byte) Pred);

Writer. Write ((byte) Pred);

}

else

{

Writer. Write (UN);

Writer. Write ((byte) Count);

Writer. Write ((byte) Pred);

}

}

else if (Count == 1)

{

if (Pred == UN)

InputUN ();

else

Writer. Write ((byte) Pred);

}

}

}

long AllByte;

public void Code (string File, string FileCode)

{

if (! BW. IsBusy)

{

FileInfo info = new FileInfo (File);

AllByte = (long) info. Length;

BW. RunWorkerAsync (new Str {PK = Pack. Packed, Input = File, Output = FileCode});

}

else

{

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

}

}

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

public void Decode (string FileCode, string FileDecode)

{

if (! BW. IsBusy)

{

FileInfo info = new FileInfo (FileCode);

AllByte = (long) info. Length;

BW. RunWorkerAsync (new Str {PK = Pack. Unpacked, Input = FileCode, Output = FileDecode});

}

else

{

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

}

}

}

}

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

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

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