Ответ 1

Я вижу несколько вариантов уплотнения массива.

1. Отдельные 8-битные и 1-битные массивы

Вы можете разделить свой массив на 2 части: сначала хранится 8 младших бит исходного массива, а второй - "1", если значение не соответствует 8 бит или "0" в противном случае. Это займет 9 бит на каждое значение (такое же пространство, как и при ночном скрещивании, но немного проще). Чтобы прочитать значение из этих двух массивов, сделайте следующее:

int8_t array8[37*73] = {...};
uint16_t array1[(37*73+15)/16] = {...};
size_t offset = 37 * x + y;
int16_t item = static_cast<int16_t>(array8[offset]); // sign extend
int16_t overflow = ((array1[offset/16] >> (offset%16)) & 0x0001) << 7;
item ^= overflow;

2. Приближение

Если вы можете аппроксимировать свой массив некоторой эффективно вычисленной функцией (например, полином или экспонентой), вы можете сохранить в массиве только разницу между вашим значением и приближением. Для этого может потребоваться только 8 бит на значение или даже меньше.

3. Дельта-кодирование

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

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

  Original array: 0 0 1 1 2 2 2 2 2 3 3 3 4 4 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7
     Short array: 0         2         3         5         6         6
Difference array:   0 1 1 2   0 0 0 1   0 1 1 2   0 0 0 1   0 0 0 0   0 1 1 1

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

  Original array: 0 0 1 1 2 2 2 2 2 3 3 3 4 4 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7
     Short array: 0         2         3         5         6         6
     Delta array:   0 1 0 1   0 0 0 1   0 1 0 1   0 0 0 1   0 0 0 0   0 1 0 0

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

Инициализация

Для опции №2 может использоваться препроцессор. Для других опций препроцессор возможен, но может быть не очень удобен (препроцессор не очень хорош для обработки списков длинных значений). Некоторая комбинация препроцессора и вариационных шаблонов может быть лучше. Или может быть проще использовать некоторую текстовую обработку script.

Обновление

Посмотрев на фактические данные, я могу рассказать некоторые подробности. Вариант № 2 (Приближение) не очень удобен для ваших данных. Вариант №1 выглядит лучше. Или вы можете использовать подход Mark Ransom или ночной скрепер. Это не имеет значения, какой из них - во всех случаях вы сохраняете 7 бит из 16.

Вариант № 3 (Дельта-кодирование) позволяет сэкономить гораздо больше места. Его нельзя использовать напрямую, потому что в некоторых ячейках данные массива резко меняются. Но, насколько я знаю, эти большие изменения происходят не чаще одного раза для каждой строки. Который может быть реализован одним дополнительным столбцом с полным значением данных и одним специальным значением в массиве дельта.

Я заметил, что (игнорируя эти резкие изменения) разница между соседними значениями не более +/- 32. Для этого требуется 6 бит для каждого значения дельта. Это означает 6,6 бит на каждое значение. 58% сжатия. Около 2400 байт. (Не так много, но немного лучше, чем 2464K в ваших комментариях).

Средняя часть массива намного более гладкая. Для его кодирования вам потребуется всего 5 бит на каждое значение. Это может сэкономить 300..400 байт больше. Наверное, неплохо разбить этот массив на несколько частей и по-разному закодировать каждую часть.

Ответ 2

Как отметил ночной трекер, ваши значения будут вписываться в 9 бит. Там более простой способ сохранить эти значения. Поместите абсолютные значения в массив байтов и поместите знаковые биты в отдельный массив упакованных бит.

int8_t my_array[37][73] = {{**DATA ABSOLUTE VALUES HERE**}};
int8_t my_signs[37][10] = {{**SIGN BITS HERE**}};
int16_t my_value = my_array[i][j];
if (my_signs[i][j/8] & (1 << j%8))
    my_value = -my_value;

Это сокращение на 44% в исходном размере таблицы без особых усилий.

Ответ 3

Я знаю по опыту, что визуализация вещей может помочь найти хорошее решение проблемы. Поскольку не совсем ясно, что ваши данные фактически представляют (и поэтому мы ничего не знаем/очень мало о проблемной области), мы не можем придумать "лучшее" решение (если оно существует вообще). Поэтому я взял на себя смелость и визуализировал данные; как говорится: картина стоит 1000 слов: -)

Мне жаль, что у меня нет решения (пока) лучше, чем те, которые уже были опубликованы, но я думал, что сюжет может помочь кому-то (или мне самому) придумать лучшее решение.

Ответ 4

Вам нужен диапазон + -179. Это означает, что с 360 значениями вы будете урегулированы. В 9 бит можно выразить 360 уникальных значений. Это пример 9-битной целочисленной таблицы поиска:

// size is ceil(37 * 73 * 9 / 16)
uint16_t my_array[1520];

int16_t get_lookup_item(int x, int y) {
    // calculate bitoffset
    size_t bitoffset = (37 * x + y) * 9;

    // calculate difference with 16 bit array offset
    size_t diff = bitoffset % 16;

    uint16_t item;

    // our item doesn't overlap a 16 bit boundary
    if (diff < (16 - 9)) {
        item = my_array[bitoffset / 16]; // get item
        item >>= diff;
        item &= (1 << 9) - 1;

    // our item does overlap a 16 bit boundary
    } else {
        item = my_array[bitoffset / 16];
        item >>= diff;
        item &= (1 << (16 - diff)) - 1;
        item += my_array[bitoffset / 16 + 1] & ((1 << (9 - 16 + diff)) - 1);
    }

    // we now have the unsigned item, substract 179 to bring in the correct range
    return item - 179;
}

Ответ 5

Здесь другой подход, совершенно отличный от моего первого, поэтому он является отдельным ответом.

Если количество значений, которые не соответствуют 8 битам, составляет менее 1/8 от общего числа, вы можете выделить весь лишний байт для каждого и все же завершить с меньшим результатом по сравнению с сохранением другого 1-битного массива.

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

Для этой реализации я придерживался очень простой кодировки. Сначала я сделал дельту, предложенную Евгением Клуевым, начиная с каждой строки; ваши данные необычайно поддаются этому подходу. Каждый байт затем кодируется с помощью следующих правил:

• Абсолютное значение >= 97 задается ведущим байтом 97. Это значение было получено, попробовав разные пороговые значения и выбрав тот, который сгенерировал наименьший результат. За этим следует значение меньше 97.
• Длина выполнения проверяется только на значения от -96 до 96. Длины от 3 до 32 кодируются как от 98 до 127, а длины пробега между 33 и 64 кодируются как -97... -128.
• Наконец, значения между -96 и 96 выводятся как есть.

В результате получается кодированный массив из 2014 байт, плюс еще один из 36 байтов для индексации в начале каждой строки для общего количества 2050 байт.

Полную реализацию можно найти в http://ideone.com/SNdRI. Результат идентичен таблице, помещенной в вопросе.

Ответ 6

Как и другие, вы можете сэкономить много места, сохранив абсолютное значение каждой записи в массиве из 8-битных целых чисел и знаковый бит в отдельном массиве бит-бит. Решение Mark Ransom прост и даст хорошую производительность и уменьшит размер с 5,402 байт до 3,071 байт, сохранив 43,1%.

Если вы действительно пытаетесь сжать все последние бит пространства, вы можете сделать еще немного лучше, используя характеристики этого набора данных. В частности, обратите внимание, что значения в основном положительны и что существует несколько прогонов значений с одним и тем же знаком. Вместо отслеживания знака для каждого значения в массиве "my_signs" вы могли отслеживать только прогоны отрицательных значений в качестве начального индекса (два байта для диапазона [0..2701]) и длину выполнения (один байт, так как самый длинный пробег составляет 36 записей). Для этого набора данных, который уменьшает размер таблицы знаков с 370 байт до 168 байтов. Общее хранилище составляет 2,869 байт, экономия 46,8% по сравнению с оригиналом (на 2,533 байт меньше).

Здесь код, реализующий эту стратегию:

uint8_t my_array[37][73] = {{ /* ABSOLUTE VALUES OF ORIGINAL ARRAY HERE */ }};

// Sign bits for the values in my_array.  The data is arranged in groups of
// three bytes.  The first two give the starting index of a run of negative
// values.  The third gives the length of the run.  To determine if a given
// value should be negated, compute it index as (row * 73) + col, then scan this
// table to see if that index appears in any of the runs.  If it does, the value
// should be negated.

uint8_t my_signs[168]    = {
    0x00, 0x1f, 0x14, 0x00, 0x68, 0x15, 0x00, 0xb1, 0x16, 0x00, 0xfa, 0x18, 
    0x01, 0x42, 0x1a, 0x01, 0x8b, 0x1e, 0x01, 0xd2, 0x23, 0x02, 0x1a, 0x24, 
    0x02, 0x62, 0x24, 0x02, 0xaa, 0x25, 0x02, 0xf2, 0x25, 0x03, 0x3a, 0x25, 
    0x03, 0x83, 0x25, 0x03, 0xcb, 0x25, 0x04, 0x14, 0x24, 0x04, 0x5c, 0x24, 
    0x04, 0xa5, 0x23, 0x04, 0xee, 0x14, 0x05, 0x05, 0x0c, 0x05, 0x36, 0x14, 
    0x05, 0x50, 0x0a, 0x05, 0x7f, 0x13, 0x05, 0x9a, 0x09, 0x05, 0xc8, 0x12, 
    0x05, 0xe4, 0x07, 0x06, 0x10, 0x12, 0x06, 0x2f, 0x05, 0x06, 0x38, 0x05, 
    0x06, 0x59, 0x12, 0x06, 0x7f, 0x08, 0x06, 0xa2, 0x11, 0x06, 0xc7, 0x0b, 
    0x06, 0xeb, 0x11, 0x07, 0x10, 0x0c, 0x07, 0x34, 0x11, 0x07, 0x59, 0x0d, 
    0x07, 0x7c, 0x12, 0x07, 0xa2, 0x0d, 0x07, 0xc5, 0x12, 0x07, 0xeb, 0x0e, 
    0x08, 0x0e, 0x13, 0x08, 0x34, 0x0e, 0x08, 0x57, 0x13, 0x08, 0x7e, 0x0e, 
    0x08, 0x9f, 0x14, 0x08, 0xc7, 0x0e, 0x08, 0xe8, 0x14, 0x09, 0x10, 0x0e, 
    0x09, 0x30, 0x16, 0x09, 0x5a, 0x0d, 0x09, 0x78, 0x17, 0x09, 0xa4, 0x0c, 
    0x09, 0xc0, 0x18, 0x09, 0xef, 0x09, 0x0a, 0x04, 0x1d, 0x0a, 0x57, 0x14
};

int getSign(int row, int col)
{
    int want = (row * 73) + col;
    for (int i = 0 ; i < 168 ; i += 3) {
        int16_t start = (my_signs[i] << 8) | my_signs[i + 1];
        if (start > want) {
            // Not going to find it, so may as well stop now.

            break;
        }

        int runlength = my_signs[i + 2];
        if (want < start + runlength) {
            // Found this index in the signs array, so this entry is negative.

            return -1;
        }
    }
    return 1;
}

int16_t getValue(int row, int col)
{
    return getSign(row, col) * my_values[row][col];
}

На самом деле вы могли бы сделать еще немного лучше, ценой более сложного кода, узнав, что для кодированной версии таблицы знаков для длины строки вам действительно нужно всего 12 бит для начального индекса и 6 бит для длины выполнения, для всего 18 бит (по сравнению с 24, которые использует простая реализация выше). Это сократило бы размер еще 42 байта до 2,827, что на 47,6% меньше по сравнению с оригиналом (на 2,575 байт меньше).

Ответ 7

Исследование фактического массива показывает, что данные очень гладкие и могут быть значительно уплотнены. Простые методы не дают значительного сокращения пространства после кодирования 16-битных значений в 9 бит. Это связано с тем, что в разных местах массива различаются различные характеристики данных. Разделение массива на несколько частей и кодирование их по-разному может уменьшить размер массива дальше, но это сложнее и увеличивает размер кода.

Подход, описанный здесь, позволяет кодировать блоки данных переменной длины, обеспечивая относительно быстрый доступ к исходным значениям (но медленнее, чем простые методы). Для скорости скорости значительно увеличивается степень сжатия.

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

Также существует одно базовое значение для всех дельтах в блоке. Это позволяет кодировать линейно изменяющиеся данные (что довольно часто для реального массива) только с базовым значением, снова проводя нулевое пространство для значений дельта. И немного уменьшает среднюю битовую глубину для других случаев.

Сжатые данные сохраняются в массиве битовых потоков, к которым обращается считыватель битового потока. Чтобы обеспечить быстрый доступ к началу каждого потока битов, используется таблица индексов (всего лишь массив из 37 16-разрядных индексов).

Каждый поток бит начинается с количества блоков в потоке (5 бит), затем следует индекс блоков и, наконец, блоков данных. Индекс блоков дает возможность пропускать ненужные блоки данных во время поиска. Индекс содержит: количество элементов в блоке (4 бита позволяют кодировать от 9 до 24 значений дельта плюс начальное значение), размер базового значения для всех дельт (1 бит для размеров 4 или 6) и размер дельта (2 бита для размеров 0..3 - если размер базы равен 4 или для размеров 2..5 - если размер базы равен 6). Эти конкретные битовые глубины, вероятно, близки к оптимальным значениям, но могут быть изменены для обмена некоторой скоростью для некоторого пространства или для адаптации алгоритма к различным массивам данных.

Блок данных содержит начальное значение (9 бит), базовое значение для дельта (4 или 6 бит) и значения дельта (0..3 или 2..5 бит для каждого).

Вот функция, извлекающая исходные значения из сжатых данных:

int get(size_t row, unsigned col)
{
  BitstreamReader bsr(indexTable[row]);
  unsigned blocks = bsr.getUI(5);

  unsigned block = 0;
  unsigned start = 0;
  unsigned nextStart = 0;
  unsigned offset = 0;
  unsigned nextOffset = 0;
  unsigned blockSize = 0;
  unsigned baseSize = 0;
  unsigned deltaSize = 0;
  while (col >= nextStart) // 3 iterations on average
  {
    start = nextStart;
    offset = nextOffset;
    ++block;
    blockSize = bsr.getUI(4) + 9;
    nextStart += blockSize;
    baseSize = bsr.getUI(1)*2 + 4;
    deltaSize = bsr.getUI(2) + baseSize - 4;
    nextOffset += deltaSize * blockSize + baseSize + 9;
  }
  -- block;

  bsr.skip((blocks - block) * 7 + offset);
  int value = bsr.getI(9);
  int base = bsr.getI(baseSize);

  while(col-- > start) // 12 iterations on average
  {
    int delta = base + bsr.getUI(deltaSize);
    value += delta;
  }

  return value;
}

Вот реализация для считывателя битового потока:

  class BitstreamReader
  {
  public:
    BitstreamReader(size_t start): word_(start), bit_(0) {}

    void skip(unsigned offset)
    {
      word_ += offset / 16 + ((bit_ + offset >= 16)? 1: 0);
      bit_ = (bit_ + offset) % 16;
    }

    unsigned getUI(unsigned size)
    {
      unsigned old = bit_;
      unsigned result = dataTable[word_] >> bit_;
      result &= ((1 << size) - 1);
      bit_ += size;

      if (bit_ >= 16)
      {
        ++word_;
        bit_ -= 16;

        if (bit_ > 0)
        {
          result += (dataTable[word_] & ((1 << bit_) - 1)) << (16 - old);
        }
      }

      return result;
    }

    int getI(unsigned size)
    {
      int result = static_cast<int>(getUI(size));
      return result | -(result & (1 << (size - 1)));
    }

  private:
    size_t word_;
    unsigned bit_;
  };

Я вычислил некоторую оценку результирующего размера данных. (Я не отправляю код, который позволил мне сделать это из-за очень низкого качества кода). Результат - 1250 байт. Это может быть больше, чем лучшие программы сжатия. Но значительно ниже, чем любые простые методы.

Обновление

1250 байт не является пределом. Этот алгоритм может быть улучшен, чтобы сжать данные сложнее и работать быстрее.

Я заметил, что количество блоков (5 бит) может быть перемещено из битового потока в неиспользуемые биты таблицы индексов строк. Это экономит около 30 байт.

И чтобы сэкономить 20 байт, вы можете хранить потоки битов в байтах вместо uint16, это экономит место на битах заполнения.

Итак, у нас около 1200 байт. Что не является точным. Размер может быть немного недооценен, потому что я не принимал во внимание, что не каждая битовая глубина может быть закодирована в индексе строки. Также этот размер может быть завышен, поскольку единственная эвристика, принятая для кодировщика, вычисляла глубину бита для первых 9 значений и ограничивала размер блока только в том случае, если эту битовую глубину нужно увеличить более чем на 2 бита. Конечно, кодер может быть умнее этого.

Скорость декодирования также может быть увеличена. Если мы переместим 9-й бит из исходных значений в индексы строк, каждый элемент индекса будет ровно 8 бит. Это позволяет запускать потоки битов с набором байтов, каждый из которых может быть декодирован с помощью более быстрых методов, чем обычные абитуриенты битового потока. Остальные 8 бит исходного значения могут быть перемещены в место сразу после индекса строки для той же цели. Или, альтернативно, они могут быть включены в каждую запись индекса, так что индекс состоит из 16-битных значений. После этих изменений битовые потоки содержат только поля данных переменной длины.

Ответ 8

1049 байт

Я заметил, что большинство прогонов линейны. Вот почему я решил кодировать не дельта-значение, а дельта-дельта. Подумайте об этом как о второй производной. Это заставляет меня хранить значения -1, 0 и 1 большую часть времени с некоторыми заметными исключениями.

Во-вторых, я делаю данные 1-мерным. Преобразование его в 2 разряда легко, но наличие его в 1 измерении позволяет сжатию охватывать несколько строк.

Сжатые данные организованы в куски различного размера. Каждый фрагмент начинается с заголовка:

• 9 бит - абсолютное значение, значение input[x]
• 7 бит - разница, значение input[x+1]-input[x]
• 7 бит - разница, значение input[x+2]-input[x+1]
• 9 бит - длина следующих данных второй производной
• 2 бита каждый - массив второй производной

Прогоны вторых производных в этом примере на удивление длинны, хотя могут сохраняться только значения -2, -1, 0 и 1.

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

• C (GCC). Нет конструкций С++.
• Представленный массив ввода
• Функция визуализации для печати содержимого массива
• Функция сжатия (в случае, если ваш вход немного меняется)
• Функция Getter - выбор элемента из массива
• В основной функции: я сжимаю, распаковываю и выполняю проверку

Удачи!

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef int16_t Arr[37][73];
typedef int16_t ArrFlat[37*73];
typedef int16_t* ArrPtr;

Arr input = { {150,145,140,135,130,125,120,115,110,105,100,95,90,85,80,75,70,65,60,55,50,45,40,35,30,25,20,15,10,5,0,-4,-9,-14,-19,-24,-29,-34,-39,-44,-49,-54,-59,-64,-69,-74,-79,-84,-89,-94,-99,104,109,114,119,124,129,134,139,144,149,154,159,164,169,174,179,175,170,165,160,155,150}, \
{143,137,131,126,120,115,110,105,100,95,90,85,80,75,71,66,62,57,53,48,44,39,35,31,27,22,18,14,9,5,1,-3,-7,-11,-16,-20,-25,-29,-34,-38,-43,-47,-52,-57,-61,-66,-71,-76,-81,-86,-91,-96,101,107,112,117,123,128,134,140,146,151,157,163,169,175,178,172,166,160,154,148,143}, \
{130,124,118,112,107,101,96,92,87,82,78,74,70,65,61,57,54,50,46,42,38,34,31,27,23,19,16,12,8,4,1,-2,-6,-10,-14,-18,-22,-26,-30,-34,-38,-43,-47,-51,-56,-61,-65,-70,-75,-79,-84,-89,-94,100,105,111,116,122,128,135,141,148,155,162,170,177,174,166,159,151,144,137,130}, \
{111,104,99,94,89,85,81,77,73,70,66,63,60,56,53,50,46,43,40,36,33,30,26,23,20,16,13,10,6,3,0,-3,-6,-9,-13,-16,-20,-24,-28,-32,-36,-40,-44,-48,-52,-57,-61,-65,-70,-74,-79,-84,-88,-93,-98,103,109,115,121,128,135,143,152,162,172,176,165,154,144,134,125,118,111}, \
{85,81,77,74,71,68,65,63,60,58,56,53,51,49,46,43,41,38,35,32,29,26,23,19,16,13,10,7,4,1,-1,-3,-6,-9,-13,-16,-19,-23,-26,-30,-34,-38,-42,-46,-50,-54,-58,-62,-66,-70,-74,-78,-83,-87,-91,-95,100,105,110,117,124,133,144,159,178,160,141,125,112,103,96,90,85}, \
{62,60,58,57,55,54,52,51,50,48,47,46,44,42,41,39,36,34,31,28,25,22,19,16,13,10,7,4,2,0,-3,-5,-8,-10,-13,-16,-19,-22,-26,-29,-33,-37,-41,-45,-49,-53,-56,-60,-64,-67,-70,-74,-77,-80,-83,-86,-89,-91,-94,-97,101,105,111,130,109,84,77,74,71,68,66,64,62}, \
{46,46,45,44,44,43,42,42,41,41,40,39,38,37,36,35,33,31,28,26,23,20,16,13,10,7,4,1,-1,-3,-5,-7,-9,-12,-14,-16,-19,-22,-26,-29,-33,-36,-40,-44,-48,-51,-55,-58,-61,-64,-66,-68,-71,-72,-74,-74,-75,-74,-72,-68,-61,-48,-25,2,22,33,40,43,45,46,47,46,46}, \
{36,36,36,36,36,35,35,35,35,34,34,34,34,33,32,31,30,28,26,23,20,17,14,10,6,3,0,-2,-4,-7,-9,-10,-12,-14,-15,-17,-20,-23,-26,-29,-32,-36,-40,-43,-47,-50,-53,-56,-58,-60,-62,-63,-64,-64,-63,-62,-59,-55,-49,-41,-30,-17,-4,6,15,22,27,31,33,34,35,36,36}, \
{30,30,30,30,30,30,30,29,29,29,29,29,29,29,29,28,27,26,24,21,18,15,11,7,3,0,-3,-6,-9,-11,-12,-14,-15,-16,-17,-19,-21,-23,-26,-29,-32,-35,-39,-42,-45,-48,-51,-53,-55,-56,-57,-57,-56,-55,-53,-49,-44,-38,-31,-23,-14,-6,0,7,13,17,21,24,26,27,29,29,30}, \
{25,25,26,26,26,25,25,25,25,25,25,25,25,26,25,25,24,23,21,19,16,12,8,4,0,-3,-7,-10,-13,-15,-16,-17,-18,-19,-20,-21,-22,-23,-25,-28,-31,-34,-37,-40,-43,-46,-48,-49,-50,-51,-51,-50,-48,-45,-42,-37,-32,-26,-19,-13,-7,-1,3,7,11,14,17,19,21,23,24,25,25}, \
{21,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,21,20,18,16,13,9,5,1,-3,-7,-11,-14,-17,-18,-20,-21,-21,-22,-22,-22,-23,-23,-25,-27,-29,-32,-35,-37,-40,-42,-44,-45,-45,-45,-44,-42,-40,-36,-32,-27,-22,-17,-12,-7,-3,0,3,7,9,12,14,16,18,19,20,21,21}, \
{18,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,18,17,16,14,10,7,2,-1,-6,-10,-14,-17,-19,-21,-22,-23,-24,-24,-24,-24,-23,-23,-23,-24,-26,-28,-30,-33,-35,-37,-38,-39,-39,-38,-36,-34,-31,-28,-24,-19,-15,-10,-6,-3,0,1,4,6,8,10,12,14,15,16,17,18,18}, \
{16,16,17,17,17,17,17,17,17,17,17,16,16,16,16,16,16,15,13,11,8,4,0,-4,-9,-13,-16,-19,-21,-23,-24,-25,-25,-25,-25,-24,-23,-21,-20,-20,-21,-22,-24,-26,-28,-30,-31,-32,-31,-30,-29,-27,-24,-21,-17,-13,-9,-6,-3,-1,0,2,4,5,7,9,10,12,13,14,15,16,16}, \
{14,14,14,15,15,15,15,15,15,15,14,14,14,14,14,14,13,12,11,9,5,2,-2,-6,-11,-15,-18,-21,-23,-24,-25,-25,-25,-25,-24,-22,-21,-18,-16,-15,-15,-15,-17,-19,-21,-22,-24,-24,-24,-23,-22,-20,-18,-15,-12,-9,-5,-3,-1,0,1,2,4,5,6,8,9,10,11,12,13,14,14}, \
{12,13,13,13,13,13,13,13,13,13,13,13,12,12,12,12,11,10,9,6,3,0,-4,-8,-12,-16,-19,-21,-23,-24,-24,-24,-24,-23,-22,-20,-17,-15,-12,-10,-9,-9,-10,-12,-13,-15,-17,-17,-18,-17,-16,-15,-13,-11,-8,-5,-3,-1,0,1,1,2,3,4,6,7,8,9,10,11,12,12,12}, \
{11,11,11,11,11,12,12,12,12,12,11,11,11,11,11,10,10,9,7,5,2,-1,-5,-9,-13,-17,-20,-22,-23,-23,-23,-23,-22,-20,-18,-16,-14,-11,-9,-6,-5,-4,-5,-6,-8,-9,-11,-12,-12,-12,-12,-11,-9,-8,-6,-3,-1,0,0,1,1,2,3,4,5,6,7,8,9,10,11,11,11}, \
{10,10,10,10,10,10,10,10,10,10,10,10,10,10,9,9,9,7,6,3,0,-3,-6,-10,-14,-17,-20,-21,-22,-22,-22,-21,-19,-17,-15,-13,-10,-8,-6,-4,-2,-2,-2,-2,-4,-5,-7,-8,-8,-9,-8,-8,-7,-5,-4,-2,0,0,1,1,1,2,2,3,4,5,6,7,8,9,10,10,10}, \
{9,9,9,9,9,9,9,10,10,9,9,9,9,9,9,8,8,6,5,2,0,-4,-7,-11,-15,-17,-19,-21,-21,-21,-20,-18,-16,-14,-12,-10,-8,-6,-4,-2,-1,0,0,0,-1,-2,-4,-5,-5,-6,-6,-5,-5,-4,-3,-1,0,0,1,1,1,1,2,3,3,5,6,7,8,8,9,9,9}, \
{9,9,9,9,9,9,9,9,9,9,9,9,8,8,8,8,7,5,4,1,-1,-5,-8,-12,-15,-17,-19,-20,-20,-19,-18,-16,-14,-11,-9,-7,-5,-4,-2,-1,0,0,1,1,0,0,-2,-3,-3,-4,-4,-4,-3,-3,-2,-1,0,0,0,0,0,1,1,2,3,4,5,6,7,8,8,9,9}, \
{9,9,9,8,8,8,9,9,9,9,9,8,8,8,8,7,6,5,3,0,-2,-5,-9,-12,-15,-17,-18,-19,-19,-18,-16,-14,-12,-9,-7,-5,-4,-2,-1,0,0,1,1,1,1,0,0,-1,-2,-2,-3,-3,-2,-2,-1,-1,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,8,9}, \
{8,8,8,8,8,8,9,9,9,9,9,9,8,8,8,7,6,4,2,0,-3,-6,-9,-12,-15,-17,-18,-18,-17,-16,-14,-12,-10,-8,-6,-4,-2,-1,0,0,1,2,2,2,2,1,0,0,-1,-1,-1,-2,-2,-1,-1,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,8}, \
{8,8,8,8,9,9,9,9,9,9,9,9,9,8,8,7,5,3,1,-1,-4,-7,-10,-13,-15,-16,-17,-17,-16,-15,-13,-11,-9,-6,-5,-3,-2,0,0,0,1,2,2,2,2,1,1,0,0,0,-1,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,-1,0,0,1,3,4,5,7,7,8}, \
{8,8,9,9,9,9,10,10,10,10,10,10,10,9,8,7,5,3,0,-2,-5,-8,-11,-13,-15,-16,-16,-16,-15,-13,-12,-10,-8,-6,-4,-2,-1,0,0,1,2,2,3,3,2,2,1,0,0,0,0,0,0,0,0,0,0,-1,-1,-2,-2,-2,-2,-2,-1,0,0,1,3,4,6,7,8}, \
{7,8,9,9,9,10,10,11,11,11,11,11,10,10,9,7,5,3,0,-2,-6,-9,-11,-13,-15,-16,-16,-15,-14,-13,-11,-9,-7,-5,-3,-2,0,0,1,1,2,3,3,3,3,2,2,1,1,0,0,0,0,0,0,0,-1,-1,-2,-3,-3,-4,-4,-4,-3,-2,-1,0,1,3,5,6,7}, \
{6,8,9,9,10,11,11,12,12,12,12,12,11,11,9,7,5,2,0,-3,-7,-10,-12,-14,-15,-16,-15,-15,-13,-12,-10,-8,-7,-5,-3,-1,0,0,1,2,2,3,3,4,3,3,3,2,2,1,1,1,0,0,0,0,-1,-2,-3,-4,-4,-5,-5,-5,-5,-4,-2,-1,0,2,3,5,6}, \
{6,7,8,10,11,12,12,13,13,14,14,13,13,11,10,8,5,2,0,-4,-8,-11,-13,-15,-16,-16,-16,-15,-13,-12,-10,-8,-6,-5,-3,-1,0,0,1,2,3,3,4,4,4,4,4,3,3,3,2,2,1,1,0,0,-1,-2,-3,-5,-6,-7,-7,-7,-6,-5,-4,-3,-1,0,2,4,6}, \
{5,7,8,10,11,12,13,14,15,15,15,14,14,12,11,8,5,2,-1,-5,-9,-12,-14,-16,-17,-17,-16,-15,-14,-12,-11,-9,-7,-5,-3,-1,0,0,1,2,3,4,4,5,5,5,5,5,5,4,4,3,3,2,1,0,-1,-2,-4,-6,-7,-8,-8,-8,-8,-7,-6,-4,-2,0,1,3,5}, \
{4,6,8,10,12,13,14,15,16,16,16,16,15,13,11,9,5,2,-2,-6,-10,-13,-16,-17,-18,-18,-17,-16,-15,-13,-11,-9,-7,-5,-4,-2,0,0,1,3,3,4,5,6,6,7,7,7,7,7,6,5,4,3,2,0,-1,-3,-5,-7,-8,-9,-10,-10,-10,-9,-7,-5,-4,-1,0,2,4}, \
{4,6,8,10,12,14,15,16,17,18,18,17,16,15,12,9,5,1,-3,-8,-12,-15,-18,-19,-20,-20,-19,-18,-16,-15,-13,-11,-8,-6,-4,-2,-1,0,1,3,4,5,6,7,8,9,9,9,9,9,9,8,7,5,3,1,-1,-3,-6,-8,-10,-11,-12,-12,-11,-10,-9,-7,-5,-2,0,1,4}, \
{4,6,8,11,13,15,16,18,19,19,19,19,18,16,13,10,5,0,-5,-10,-15,-18,-21,-22,-23,-22,-22,-20,-18,-17,-14,-12,-10,-8,-5,-3,-1,0,1,3,5,6,8,9,10,11,12,12,13,12,12,11,9,7,5,2,0,-3,-6,-9,-11,-12,-13,-13,-12,-11,-10,-8,-6,-3,-1,1,4}, \
{3,6,9,11,14,16,17,19,20,21,21,21,19,17,14,10,4,-1,-8,-14,-19,-22,-25,-26,-26,-26,-25,-23,-21,-19,-17,-14,-12,-9,-7,-4,-2,0,1,3,5,7,9,11,13,14,15,16,16,16,16,15,13,10,7,4,0,-3,-7,-10,-12,-14,-15,-14,-14,-12,-11,-9,-6,-4,-1,1,3}, \
{4,6,9,12,14,17,19,21,22,23,23,23,21,19,15,9,2,-5,-13,-20,-25,-28,-30,-31,-31,-30,-29,-27,-25,-22,-20,-17,-14,-11,-9,-6,-3,0,1,4,6,9,11,13,15,17,19,20,21,21,21,20,18,15,11,6,2,-2,-7,-11,-13,-15,-16,-16,-15,-13,-11,-9,-7,-4,-1,1,4}, \
{4,7,10,13,15,18,20,22,24,25,25,25,23,20,15,7,-2,-12,-22,-29,-34,-37,-38,-38,-37,-36,-34,-31,-29,-26,-23,-20,-17,-13,-10,-7,-4,-1,2,5,8,11,13,16,18,21,23,24,26,26,26,26,24,21,17,12,5,0,-6,-10,-14,-16,-16,-16,-15,-14,-12,-10,-7,-4,-1,1,4}, \
{4,7,10,13,16,19,22,24,26,27,27,26,24,19,11,-1,-15,-28,-37,-43,-46,-47,-47,-45,-44,-41,-39,-36,-32,-29,-26,-22,-19,-15,-11,-8,-4,-1,2,5,9,12,15,19,22,24,27,29,31,33,33,33,32,30,26,21,14,6,0,-6,-11,-14,-15,-16,-15,-14,-12,-9,-7,-4,-1,1,4}, \
{6,9,12,15,18,21,23,25,27,28,27,24,17,4,-14,-34,-49,-56,-60,-60,-60,-58,-56,-53,-50,-47,-43,-40,-36,-32,-28,-25,-21,-17,-13,-9,-5,-1,2,6,10,14,17,21,24,28,31,34,37,39,41,42,43,43,41,38,33,25,17,8,0,-4,-8,-10,-10,-10,-8,-7,-4,-2,0,3,6}, \
{22,24,26,28,30,32,33,31,23,-18,-81,-96,-99,-98,-95,-93,-89,-86,-82,-78,-74,-70,-66,-62,-57,-53,-49,-44,-40,-36,-32,-27,-23,-19,-14,-10,-6,-1,2,6,10,15,19,23,27,31,35,38,42,45,49,52,55,57,60,61,63,63,62,61,57,53,47,40,33,28,23,21,19,19,19,20,22}, \
{168,173,178,176,171,166,161,156,151,146,141,136,131,126,121,116,111,106,101,-96,-91,-86,-81,-76,-71,-66,-61,-56,-51,-46,-41,-36,-31,-26,-21,-16,-11,-6,-1,3,8,13,18,23,28,33,38,43,48,53,58,63,68,73,78,83,88,93,98,103,108,113,118,123,128,133,138,143,148,153,158,163,168} };

void visual(Arr arr) {
  int row;
  int col;
  for (row=0; row<37; ++row) {
    for (col=0; col<73; ++col)
      printf("%3d",arr[row][col]);
    printf("\n");
  }
}

void visualFlat(ArrFlat arr) {
  int cell;
  for (cell=0; cell<37*73; ++cell) {
    printf("%3d",arr[cell]);
  }
  printf("\n");
}

typedef struct {
  int16_t absolute:9;
  int16_t adiff:7;
  int16_t diff:7;
  unsigned short diff2_length:9;
} __attribute__((packed)) Header;

typedef union {
  struct {
  int16_t diff2_a:2;
  int16_t diff2_b:2;
  int16_t diff2_c:2;
  int16_t diff2_d:2;
  } __attribute__((packed));
  unsigned char all;
} Chunk;

int16_t chunkGet(Chunk k, int16_t offset) {
  switch (offset) {
    case 0 : return k.diff2_a;
    case 1 : return k.diff2_b;
    case 2 : return k.diff2_c;
    case 3 : return k.diff2_d;
  }
}

void chunkSet(Chunk *k, int16_t offset, int16_t value) {
  switch (offset) {
    case 0 : k->diff2_a=value; break;
    case 1 : k->diff2_b=value; break;
    case 2 : k->diff2_c=value; break;
    case 3 : k->diff2_d=value; break;
    default: printf("Invalid offset %hd\n", offset);
  }
}

unsigned char data[1049];

void compress (ArrFlat src) {
  Chunk diffData;
  int16_t headerIdx=0;
  int16_t diffIdx;
  int16_t currentDiffValue;
  int16_t length=-3;
  int16_t shift=0;
  Header h;
  int16_t position=0;
  while (position<37*73) {
    if (length==-3) { //encode the absolute value
      h.absolute=currentDiffValue=src[position];
      ++position;
      ++length;
      continue;
    }
    if (length==-2) { //encode the first diff value
      h.adiff=currentDiffValue=src[position]-src[position-1];
      if (currentDiffValue<-64 || currentDiffValue>+63)
        printf("\nDIFF TOO BIG\n");
      ++position;
      ++length;
      continue;
    }
    if (length==-1) { //encode the second diff value
      h.diff=currentDiffValue=src[position]-src[position-1];
      if (currentDiffValue<-64 || currentDiffValue>+63)
        printf("\nDIFF TOO BIG\n");
      ++position;
      ++length;
      diffData.all=0;
      diffIdx=headerIdx+sizeof(Header);
      shift=0;
      continue;
    }
    //compute the diff2
    int16_t diff=src[position]-src[position-1];
    int16_t diff2=diff-currentDiffValue;
    if (diff2>1 || diff2<-2) { //big change - restart with header
      if (length>511)
        printf("\nLENGTH TOO LONG\n");
      if (shift!=0) { //store partial byte
        data[diffIdx]=diffData.all;
        diffData.all=0;
        ++diffIdx;
      }
      h.diff2_length=length;
      memcpy(data+headerIdx,&h,sizeof(Header));
      headerIdx=diffIdx;
      length=-3;
      continue;
    }
    chunkSet(&diffData,shift,diff2);
    shift+=1;
    currentDiffValue=diff;
    ++position;
    ++length;
    if (shift==4) {
      data[diffIdx]=diffData.all;
      diffData.all=0;
      ++diffIdx;
      shift=0;
    }
  }
  if (shift!=0) { //finalize
    data[diffIdx]=diffData.all;
    ++diffIdx;
  }
  h.diff2_length=length;
  memcpy(data+headerIdx,&h,sizeof(Header));
  headerIdx=diffIdx;
  printf("Ending byte=%hd\n",headerIdx);
}

int16_t get(int row, int col) {
  int idx=row*73+col;
  int dataIdx=0;
  int pos=0;
  int16_t absolute;
  int16_t diff;
  Header h;
  while (1) {
    memcpy(&h, data+dataIdx, sizeof(Header));
    if (idx==pos) return h.absolute;
    absolute=h.absolute+h.adiff;
    if (idx==pos+1) return absolute;
    diff=h.diff;
    absolute+=diff;
    if (idx==pos+2) return absolute;
    dataIdx+=sizeof(Header);
    pos+=3;
    if (pos+h.diff2_length <= idx) {
      pos+=h.diff2_length;
      dataIdx+=(h.diff2_length+3)/4;
    } else break;
  }
  int shift=4;
  Chunk diffData;
  while (pos<=idx) {
    if (shift==4) {
      diffData.all=data[dataIdx];
      ++dataIdx;
      shift=0;
    }
    diff+=chunkGet(diffData,shift);
    absolute+=diff;
    ++shift;
    ++pos;
  }
  return absolute;
}

int main() {
  printf("Input:\n");
  visual(input);
  int row;
  int col;
  ArrPtr flatInput=(ArrPtr)input;
  printf("sizeof(Header)=%lu\n",sizeof(Header));
  printf("sizeof(Chunk)=%lu\n",sizeof(Chunk));
  compress(flatInput);
  ArrFlat re;
  for (row=0; row<37; ++row)
    for (col=0; col<73; ++col) {
      int cell=row*73+col;
      re[cell]=get(row,col);
      if (re[cell]!=flatInput[cell])
        printf("ERROR DETECTED IN CELL %d\n",cell);
    }
  visual(re);
  return 0;
}

Версия Visual Studio (скомпилирована с VS 2010)

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

typedef int16_t Arr[37][73];
typedef int16_t ArrFlat[37*73];
typedef int16_t* ArrPtr;

Arr input = { [... your array as above ...] };

void visual(Arr arr) {
    int row;
    int col;
    for (row=0; row<37; ++row) {
        for (col=0; col<73; ++col)
            printf("%3d",arr[row][col]);
        printf("\n");
    }
}

void visualFlat(ArrFlat arr) {
    int cell;
    for (cell=0; cell<37*73; ++cell) {
        printf("%3d",arr[cell]);
    }
    printf("\n");
}

#pragma pack(1)
typedef struct {
    int16_t absolute:9;
    int16_t adiff:7;
    int16_t diff:7;
    unsigned short diff2_length:9;
} Header;

#pragma pack(1)
typedef union {
    struct {
        char diff2_a:2;
        char diff2_b:2;
        char diff2_c:2;
        char diff2_d:2;
    };
    unsigned char all;
} Chunk;

int16_t chunkGet(Chunk k, int16_t offset) {
    switch (offset) {
    case 0 : return k.diff2_a;
    case 1 : return k.diff2_b;
    case 2 : return k.diff2_c;
    case 3 : return k.diff2_d;
    }
}

void chunkSet(Chunk *k, int16_t offset, int16_t value) {
    switch (offset) {
    case 0 : k->diff2_a=value; break;
    case 1 : k->diff2_b=value; break;
    case 2 : k->diff2_c=value; break;
    case 3 : k->diff2_d=value; break;
    default: printf("Invalid offset %hd\n", offset);
    }
}

unsigned char data[1049];

void compress (ArrFlat src) {
    Chunk diffData;
    int16_t headerIdx=0;
    int16_t diffIdx;
    int16_t currentDiffValue;
    int16_t length=-3;
    int16_t shift=0;
    int16_t diff;
    int16_t diff2;
    Header h;
    int16_t position=0;
    while (position<37*73) {
        if (length==-3) { //encode the absolute value
            h.absolute=currentDiffValue=src[position];
            ++position;
            ++length;
            continue;
        }
        if (length==-2) { //encode the first diff value
            h.adiff=currentDiffValue=src[position]-src[position-1];
            if (currentDiffValue<-64 || currentDiffValue>+63)
                printf("\nDIFF TOO BIG\n");
            ++position;
            ++length;
            continue;
        }
        if (length==-1) { //encode the second diff value
            h.diff=currentDiffValue=src[position]-src[position-1];
            if (currentDiffValue<-64 || currentDiffValue>+63)
                printf("\nDIFF TOO BIG\n");
            ++position;
            ++length;
            diffData.all=0;
            diffIdx=headerIdx+sizeof(Header);
            shift=0;
            continue;
        }
        //compute the diff2
        diff=src[position]-src[position-1];
        diff2=diff-currentDiffValue;
        if (diff2>1 || diff2<-2) { //big change - restart with header
            if (length>511)
                printf("\nLENGTH TOO LONG\n");
            if (shift!=0) { //store partial byte
                data[diffIdx]=diffData.all;
                diffData.all=0;
                ++diffIdx;
            }
            h.diff2_length=length;
            memcpy(data+headerIdx,&h,sizeof(Header));
            headerIdx=diffIdx;
            length=-3;
            continue;
        }
        chunkSet(&diffData,shift,diff2);
        shift+=1;
        currentDiffValue=diff;
        ++position;
        ++length;
        if (shift==4) {
            data[diffIdx]=diffData.all;
            diffData.all=0;
            ++diffIdx;
            shift=0;
        }
    }
    if (shift!=0) { //finalize
        data[diffIdx]=diffData.all;
        ++diffIdx;
    }
    h.diff2_length=length;
    memcpy(data+headerIdx,&h,sizeof(Header));
    headerIdx=diffIdx;
    printf("Ending byte=%hd\n",headerIdx);
}

int16_t get(int row, int col) {
    int idx=row*73+col;
    int dataIdx=0;
    int pos=0;
    int16_t absolute;
    int16_t diff;
    int shift;
    Header h;
    Chunk diffData;
    while (1) {
        memcpy(&h, data+dataIdx, sizeof(Header));
        if (idx==pos) return h.absolute;
        absolute=h.absolute+h.adiff;
        if (idx==pos+1) return absolute;
        diff=h.diff;
        absolute+=diff;
        if (idx==pos+2) return absolute;
        dataIdx+=sizeof(Header);
        pos+=3;
        if (pos+h.diff2_length <= idx) {
            pos+=h.diff2_length;
            dataIdx+=(h.diff2_length+3)/4;
        } else break;
    }
    shift=4;

    while (pos<=idx) {
        if (shift==4) {
            diffData.all=data[dataIdx];
            ++dataIdx;
            shift=0;
        }
        diff+=chunkGet(diffData,shift);
        absolute+=diff;
        ++shift;
        ++pos;
    }
    return absolute;
}

int main() {
    int row;
    int col;
    ArrPtr flatInput=(ArrPtr)input;
    ArrFlat re;

    printf("Input:\n");
    visual(input);
    printf("sizeof(Header)=%lu\n",sizeof(Header));
    printf("sizeof(Chunk)=%lu\n",sizeof(Chunk));
    compress(flatInput);

    for (row=0; row<37; ++row)
        for (col=0; col<73; ++col) {
            int cell=row*73+col;
            re[cell]=get(row,col);
            if (re[cell]!=flatInput[cell])
                printf("ERROR DETECTED IN CELL %d\n",cell);
        }
        visual(re);
        return 0;
}

Ответ 9

Есть еще одна возможность:

• Имейте два массива: один основной и один переполнение.
• Каждый элемент основного массива содержит 7 бит фактических данных + бит "статус".
• Если бит состояния reset, значение вписывается в остальные 7 бит.
• Если бит состояния установлен, часть значения все еще находится в этих 7 битах, но остальные бит содержатся в массиве переполнения.
• индекс в массиве переполнения найден путем подсчета всех предыдущих элементов в основном массиве, у которых установлен бит состояния.

Это имеет следующие преимущества:

• Очень быстрый поиск значений, которые вписываются в 7 бит.
• Может обрабатывать значения неограниченного диапазона (либо с использованием подходящих элементов в массиве переполнения, либо путем повторения алгоритма и укладки другого массива переполнения и т.д.).
• С другой стороны, если вы знаете, что значения всегда будут вписываться в 9 бит, используйте 2-битные элементы в массиве переполнения, чтобы сэкономить дополнительное пространство (требуется некоторое свертывание бит, но это может быть сделано).
• Для некоторых распределений данных он может использовать меньше места, чем просто использовать 9-битные элементы (либо в одном массиве, либо в 8-битном массиве + 1-битный массив) - когда большинство значений вписывается в 7 бит.
• Довольно просто реализовать, поэтому размер кода не будет экономить на съёмках для данных.

Недостатки:

• Медленный поиск значений, которые не вписываются в 7 бит. Доступ к такому значению требует линейного перемещения всех элементов, оставшихся от него в основном массиве (и проверки их битов состояния), чтобы определить индекс в массиве переполнения.
• Для некоторых других распределений данных он может использовать больше пространства, чем 9-битный подход - когда есть много значений, которые не вписываются в 7 бит.
• Не так просто, как 8-битный массив + 1-битный подход к массиву, поэтому, хотя он еще не очень большой, код будет несколько больше.

Ответ 10

726 байт

Этот алгоритм кодирует разницу между фактическим значением и значением, полученным путем линейной экстраполяции из предыдущих значений. Другими словами, он использует серию Тейлора первого порядка или, как называется CygnusX1, delta-of-delta.

После этого экстраполяционного кодирования большинство значений находятся в диапазоне [-1.. 1]. Это хорошая причина использовать Арифметическое кодирование или Диапазон кодирования, Я реализовал арифметический кодер Arturo San Emeterio Campos. Также доступен алгоритм для Range coder того же автора.

Малые значения в диапазоне [-2.. 2] сжимаются арифметическим кодером, а большие значения упаковываются в 4-битные куски.

Существует также несколько оптимизаций, которые используются для более компактного его компоновки:

• все значения сжимаются до одного непрерывного потока
• последний столбец вообще не закодирован, так как он равен первому
• при первом кодировании столбца история обновляется лишь частично, чтобы улучшить результаты для второго столбца.
• несколько случаев, когда значения перескакивают от -100 до 100, обрабатываются по-разному.

Этот алгоритм работает медленно, он использует до 8000 32-разрядных целочисленных делений и множество бит-манипуляций для извлечения одного значения. Но он упаковывает данные в массив размером 726 байтов, а размер кода не очень большой.

Скорость может быть оптимизирована (до ~ 2800 32-разрядных целых делений), если таблица частот правильно масштабирована. Кроме того, использование кодирования диапазона вместо арифметического кодирования может дать некоторое улучшение скорости. Пространство может быть оптимизировано, если данные арифметического кодера и полубайты упакованы в массивы байтов вместо массивов uint16 (2 байта), и если до двух начальных нулевых байтов сглаживаются с концом некоторой другой структуры данных (1..2 байт). При использовании второго порядка порядок Тейлора не получил никакого пространства, но, возможно, другие методы экстраполяции дадут некоторое улучшение.

Полную реализацию можно найти здесь: encoder, декодер и проверить. Протестировано на GCC.

Ответ 11

Не забудьте проверить размер скомпилированного кода, если важна сумма кода + размер данных. Вот пример, который использует стандартную 8-битную кодировку для данных (50% усиления) и оптимизирует размер кода.

Мы будем хранить 8-битные значения для каждой строки:

    unsigned char *row_data = compressed_data[row*73];
    int value = row_data[column];

Для первых строк разбить их на две. Первое значение будет закодировано напрямую. Следующая часть будет использовать отрицательную дельта от первого значения. Вторая часть будет кодироваться как положительная дельта от 100.

    if (row <= 4) {
        char break = break_point[row];
        if (column >= break) return 100 + value;
        if (column == 0) return value;
        return row_data[0] - value;
    }

Break_point будет позицией 104, 101, 100, 103, 110 в первых пяти строках. Я не проверял, может ли он быть вычислен, а не сохранен. Возможно ли это 51 + строка?

После 5-й строки значения становятся более плавными, мы можем просто сохранить их в 8-битном двоичном дополнении. Исключение составляет последняя строка.

    if (row != 36) return (signed char) value;

Последняя строка может быть закодирована таким образом без каких-либо данных (что экономит 73 байта):

    value = 168+5*column;
    if (value <= 178) return value;
    value = 359 - x; /* 359 = 176 + 183 */
    if (value >= 101) return value;
    value = -x;
    if (value > 0) x--;
    return value;

Для этого потребуется около 2640 байт, но было бы очень быстро и компактно для доступа.

Первая строка может быть закодирована аналогично последней (с приращением на -5, сменой знака на -104 и 359-x "флип" на этапе 184), экономя 70 байтов данных с некоторой стоимостью в размере кода.

Ответ 12

Если дублирующиеся являются смежными, и у вас есть дополнительный процессор, вы можете использовать кодировку длины прогона.

Набор данных, к сожалению, выглядит слишком плотным для DFA... но вы можете полностью заставить работать. Это потребует предварительной обработки и будет очень быстрым. Сборка может превышать набор данных 4K, поэтому это может быть не вариант.

Предполагая, что ваши 16-битные значения нечасты, хеш может работать для дополнительных больших записей (см.: google sparsehash)... там 1 бит + накладные расходы для каждого объекта.

Вы также можете использовать 9-битные значения и вручную управлять границами байтов памяти, что является одним и тем же накладным расходами, как отдельный бит-массив... может быть больше.