Достаточно часто в школе или университете преподаватели задают своим ученикам задание, связанное с написанием простого архиватора на том или ином языке программирования. Давайте рассмотрим данную задачу на примере языка C#…
Вообще создание архиватора — задача не из простых. Если говорить точнее, то вся сложность заключается в нахождении алгоритма, позволяющего эффективно сжимать данные.
Давайте рассмотрим самый простой и известный алгоритм сжатия данных.
Пусть дан файл со следующим содержимым (байты):
15 12 00 00 00 00 00 00 00 00 00 00 00 00 44 44
44 55 77 44 AF 00 00 11 11 12 45 45 00 00 00 00
01 02 03 04 05 01 02 03 04 05 06 01 02 03 04 05
Как мы видим в содержимом файла есть много повторов. А значит первое что должно прийти в голову — «нужно как-то избавиться от них». Решение данной проблемы вполне легко себе представить, ведь можно например, заменить все повторяющиеся подряд байты всего двумя. Первый будет указывать на число повторов, второй на повторяющийся байт.
Например было: 00 00 00 00 00 00 00 00
Стало: 08 00
Однако тут стоит помнить, что максимальное значение байта (FF или 255). Значит мы можем сокращать цепочки максимум из 255 одинаковых байтов. На самом деле можно сократить цепочку в 256 байтов, для этого нужно начинать нумерацию с нуля, однако я не буду этого делать (дальше станет ясно почему).
Так же стоит помнить о том, что файл нужно разархивировать, а значит нужен способ декодирования. Чтобы была возможность однозначно восставовить файл придется использовать данный метод и к неповторяющимся байтам. А это уже может повлечь за собой рост размера архива, так как один байт исходного файла заменяется двумя байтами в архиве.
В итоге для нашего исходного файла имеем:
01 15 01 12 0С 00 03 44 01 55 01 77 01 44 01 AF
02 00 02 11 01 12 02 45 04 00 01 01 01 02 01 03
01 04 01 05 01 01 01 02 01 03 01 04 01 05 01 06
01 01 01 02 01 03 01 04 01 05
Как видим файл не уменьшился, а стал больше. Поэтому нужно вводить еще одно правило архивации. Не трудно заметить, что структура архива такова, что его можно считывать парами байт. При этом каждый четный байт не будет нулевым, так как он отвечает за количество повторяющихся символов и как минимум будет равен единице. Введем следующее правило: если четный байт равен нулю, то далее идет байт-число неповторяющихся байт, за ним идут непосредсвенно эти байты.
Например было: 01 02 03 04 AA AB AC AE
Стало: 00 08 01 02 03 04 AA AB AC AE
Очевидно что такая конструкция не приводит к уменьшению числа байт, однако это увеличение крайне мало, по сравнению с первым методом. Приходится чем то жертвовать…
Теперь применим оба правила к нашему файлу. Имеем:
00 02 15 12 0С 00 03 44 00 04 55 77 44 AF 02 00
02 11 00 01 12 02 45 04 00 00 10 01 02 03 04 05
01 02 03 04 05 06 01 02 03 04 05
Вот теперь наш файл стал меньше, чучуть, но меньше. Если подумать, то можно еще усовершенствовать данный алгоритм, например анализирую группу байт на повтор. Но этого мы делать не будет.
Сейчас же мы рассмотрим реализацию описанного метода на языке программирования C#.
Архивация файла
public static void Zip(string FileRes, string FileDest)
{
FileStream fs = null; //исходный файл
FileStream rs = null; //архив
try
{
if (File.Exists(FileDest))
File.Delete(FileDest);
string Format = FileRes.Substring(FileRes.LastIndexOf('.') + 1); //получаем формат файла
fs = new FileStream(FileRes, FileMode.Open, FileAccess.Read, FileShare.ReadWrite);
rs = new FileStream(FileDest, FileMode.CreateNew);
//сначала сохраним формат исходного файла
rs.WriteByte((byte)Format.Length);
for (int i = 0; i < Format.Length; ++i)
rs.WriteByte((byte)Format[i]);
List<byte> Bt = new List<byte>();
List<byte> nBt = new List<byte>();
while (fs.Position < fs.Length)
{
byte B = (byte)fs.ReadByte();
if (Bt.Count == 0)
Bt.Add(B);
else if (Bt[Bt.Count - 1] != B)
{
//неповторяющиеся байты
Bt.Add(B);
if (Bt.Count == 255)
{
rs.WriteByte((byte)0);
rs.WriteByte((byte)255);
rs.Write(Bt.ToArray(), 0, 255);
Bt.Clear();
}
}
else
{
//повтор
if (Bt.Count != 1)
{
//в буфере могут быть неповторяющиеся байты
//их нужно сохранить
rs.WriteByte((byte)0);
rs.WriteByte((byte)(Bt.Count - 1));
rs.Write(Bt.ToArray(), 0, Bt.Count - 1);
Bt.RemoveRange(0, Bt.Count - 1);
}
Bt.Add(B);
while ((B = (byte)fs.ReadByte()) == Bt[0])
{
//пока идут повторы сохраняем их в буфер
Bt.Add(B);
if (Bt.Count == 255)
{
rs.WriteByte((byte)255);
rs.WriteByte(Bt[0]);
Bt.Clear();
break;
}
}
if (Bt.Count > 0)
{
//если в буфере что-то есть, сохраняем это
rs.WriteByte((byte)Bt.Count);
rs.WriteByte(Bt[0]);
Bt.Clear();
Bt.Add(B);
}
}
}
if (Bt.Count > 0)
{
//после просмотра файла у нас может быть буфер с неповторяющимися байтами
rs.WriteByte((byte)0);
rs.WriteByte((byte)Bt.Count);
rs.Write(Bt.ToArray(), 0, Bt.Count);
}
}
catch (Exception ex)
{
MessageBox.Show(ex.Message);
}
finally
{
if (fs != null) fs.Close();
if (rs != null) rs.Close();
}
}
Распаковка файла
public static void UnZip(string FileRes, string FolderDest)
{
if (!File.Exists(FileRes)) return;
FileStream fs = null;
FileStream rs = null;
try
{
if (FolderDest[FolderDest.Length - 1] != '\\') FolderDest += '\\';
string FileName = FileRes.Split('\\')[FileRes.Split('\\').Length - 1];
string Name = FolderDest + FileName.Substring(0, FileName.LastIndexOf('.'));
string Format = ".";
fs = new FileStream(FileRes, FileMode.Open, FileAccess.Read, FileShare.ReadWrite);
int FormatLen = fs.ReadByte();
for (int i = 0; i < FormatLen; ++i)
Format += (char)fs.ReadByte();
if (File.Exists(Name + Format))
File.Delete(Name + Format);
rs = new FileStream(Name + Format, FileMode.CreateNew);
while (fs.Position < fs.Length)
{
int Bt = fs.ReadByte();
if (Bt == 0) //различные байты
{
Bt = fs.ReadByte();
for (int j = 0; j < Bt; ++j)
{
byte b = (byte)fs.ReadByte();
rs.WriteByte(b);
}
}
else //повторы
{
int Value = fs.ReadByte();
for (int j = 0; j < Bt; ++j)
rs.WriteByte((byte)Value);
}
}
}
catch (Exception ex)
{
MessageBox.Show(ex.Message);
}
finally
{
if (fs != null) fs.Close();
if (rs != null) rs.Close();
}
}
