Функции для сжатия/распаковки данных

[Evgeniy Logunov]

В процессе освоения mql5 решил написать пару простых функций, осуществляющих сжатие/распаковку массива байт без потерь.

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

Предсказание следующего байта осуществляется исходя из частоты встречаемости различных значений после "контекста" - предыдущих нескольких бит (моя реализация предусматривает контекст фиксированной длины - 8 бит).

Класс, осуществляющий предсказание:

class CCharPredictor {
   private:
      uchar context;
      uint freq[256][256];
      uint threshold[256];
      uchar prediction[256];
   public:
      void Init() {
         context = 0;
         for (int i = 0; i < 256; i++) {
            for (int j = 0; j < 256; j++)
               freq[i][j] = 0;
            threshold[i] = 0;
            prediction[i] = 0;
         }
      };
      void Update(uchar newByte) {
         freq[context][newByte]++;
         if (freq[context][newByte] >= threshold[context]) {
            threshold[context] = freq[context][newByte];
            prediction[context] = newByte;
         }
         context = newByte;
      };
      uchar Predict() {
         return prediction[context];
      };
};

Для работы нужен всего один экземпляр класса (допустим, он уже создан в виде: "CCharPredictor model;").

Метод Init сбрасывает контекст и обнуляет таблицу частот.

Метод Predict возвращает предсказание на основе текущего контекста.

Метод Update обновляет контекст и таблицу частот.

Итак, функции для сжатия данных:

CCharPredictor model;


void Compress(const CArrayChar& srcBuffer, CArrayChar& dstBuffer) {
   uint srcLen = srcBuffer.Total();
   dstBuffer.Clear();
   if (srcLen == 0)
      return;
   dstBuffer.Add((uchar)((srcLen >> 24) & 0xff));
   dstBuffer.Add((uchar)((srcLen >> 16) & 0xff));
   dstBuffer.Add((uchar)((srcLen >> 8) & 0xff));
   dstBuffer.Add((uchar)(srcLen & 0xff));
   model.Init();
   uint code = 0;
   uint len = 0;
   uint readPos = 0;
   while (true) {
      uchar newByte;
      if (readPos < srcLen)
         newByte = srcBuffer.At(readPos);
      readPos++;
      if (readPos > srcLen) {
         if (len != 0)
            dstBuffer.Add((uchar)(code & 0xff));
         break;
      }
      if (model.Predict() != newByte) {
         code |= (0 << len);
         len++;
         code |= (newByte << len);
         len += 8;
      }
      else {
         code |= (1 << len);
         len++;
      }
      while (len >= 8) {
         dstBuffer.Add((uchar)(code & 0xff));
         code >>= 8;
         len -= 8;
      }
      model.Update(newByte);
   }
}

void Decompress(const CArrayChar& srcBuffer, CArrayChar& dstBuffer) {
   uint srcLen = srcBuffer.Total();
   dstBuffer.Clear();
   if (srcLen == 0)
      return;
   uint readPos = 0;
   uint writePos = 0;
   uint bytesCompressed = 0;
   bytesCompressed = (bytesCompressed << 8) | srcBuffer.At(readPos++);
   bytesCompressed = (bytesCompressed << 8) | srcBuffer.At(readPos++);
   bytesCompressed = (bytesCompressed << 8) | srcBuffer.At(readPos++);
   bytesCompressed = (bytesCompressed << 8) | srcBuffer.At(readPos++);
   model.Init();
   uint code = 0;
   uint len = 0;
   while (true) {
      uchar decodedByte = 0;
      if (len == 0) {
         if (readPos < srcLen)
            code = ((uint)srcBuffer.At(readPos)) & 0xff;
         readPos++;
         len = 8;
      }
      if (readPos > srcLen)
         break;
      if (writePos == bytesCompressed)
         break;
      if ((code & 1) == 0) {
         code >>= 1;
         len--;
         if (len < 8) {
            if (readPos < srcLen)
               code |= ((((uint)srcBuffer.At(readPos)) & 0xff) << len);
            readPos++;
            if (readPos > srcLen)
               break;
            len += 8;
         }
         decodedByte = (uchar)(code & 0xff);
         code >>= 8;
         len -= 8;
      }
      else {
         code >>= 1;
         len--;
         decodedByte = model.Predict();
      }
      dstBuffer.Add((uchar)(decodedByte));
      writePos++;
      model.Update(decodedByte);
   }
}

 Для использования нужно включить файл ArrayChar.mqh из стандартной библиотеки:

#include <\Arrays\ArrayChar.mqh> 

 Обе функции принимают на вход два аргумента: srcBuffer - массив входных данных, dstBuffer - массив выходных данных.

Для тестирования я сгенерировал небольшой файл при помощи следующего кода:

   int hInFile = FileOpen("infile.bin", FILE_WRITE | FILE_READ | FILE_BIN | FILE_SHARE_READ);
   if (hInFile < 0) {
      Print("Error opening file");
      return;
   }
   CArrayChar arr;
   arr.Clear();
   for (int i = 0; i < 1000; i++) {
      arr.Add('H');
      arr.Add('e');
      arr.Add('l');
      arr.Add('l');
      arr.Add('o');
      arr.Add(' ');
      arr.Add('w');
      arr.Add('o');
      arr.Add('r');
      arr.Add('l');
      arr.Add('d');
      arr.Add('!');
   }
   arr.Save(hInFile);
   FileClose(hInFile);

 Тестирование проходило следующим образом: читаем сгенерированный файл, сжимаем его, результат сжатия записываем в первый выходной файл, разжимаем сжатые данные, результат распаковки записываем во второй выходной файл. При помощи hex-редактора сравниваем входной файл и второй выходной (различий быть не должно). Код для тестирования:

   int hInFile = FileOpen("infile.bin", FILE_WRITE | FILE_READ | FILE_BIN | FILE_SHARE_READ);
   if (hInFile < 0) {
      Print("Error opening file");
      return;
   }
   CArrayChar srcBuffer;
   srcBuffer.Load(hInFile);
   FileClose(hInFile);
   
   CArrayChar compBuffer;
   Compress(srcBuffer, compBuffer);
   CArrayChar testBuffer;
   Decompress(compBuffer, testBuffer);
   
   int hOutFile1 = FileOpen("outfile1.bin", FILE_WRITE | FILE_READ | FILE_BIN | FILE_SHARE_READ);
   if (hOutFile1 < 0) {
      Print("Error opening file");
      return;
   }
   compBuffer.Save(hOutFile1);
   FileClose(hOutFile1);
   
   int hOutFile2 = FileOpen("outfile2.bin", FILE_WRITE | FILE_READ | FILE_BIN | FILE_SHARE_READ);
   if (hOutFile2 < 0) {
      Print("Error opening file");
      return;
   }
   testBuffer.Save(hOutFile2);
   FileClose(hOutFile2);

Вот и всё. Надеюсь, мой код окажется полезным.

Отзывы приветствуются :)