Сжатие строк ASCII в C

Ответ 1

ZLib всегда к вашим услугам - у него очень мало накладных расходов для случаев, когда строка содержит несжимаемые данные, она относительно быстро, бесплатно и могут быть легко интегрированы в программы на C и С++.

Ответ 2

Большинство алгоритмов сжатия не очень хорошо работают с короткими строками. Вот несколько алгоритмов сжатия, которые предназначены для сжатия коротких английских текстовых строк. Хотя они могут обрабатывать любой произвольный байт в строке открытого текста, такие байты часто делают "сжатые" данные длиннее, чем открытый текст. Поэтому неплохо было бы, чтобы компрессор сохранил "несжимаемые" данные без изменений и установил флаг "буквальный" для таких данных (как предложил Стив Джессоп).

• "base 40 encoding": максимальное сжатие 3: 2
• "Стандартный код Zork для обмена информацией" (ZSCII): максимальное сжатие 3: 2
• сжатие байтовой пары: максимальное сжатие 2: 1
• статическая таблица Хаффмана, распределенная между всеми строками (как было предложено cygil).
  • идеально, сформированный из точных частот символов всех ваших фактических данных.
  • Varicode: максимальное сжатие 2: 1
• сжатие PalmDoc (сжатие байт-пары + простой вариант LZ77).

Ответ 3

Я не уверен, что подходы сжатия zlib или LZW будут хорошо работать в случае индивидуального сжатия коротких строк менее 250 байт. Как правило, требуется создание довольно значимого словаря, прежде чем заметны преимущества сжатия.

Возможно, простое кодирование Хаффмана с фиксированным деревом кодирования или одно разделяемое между всеми экземплярами строк? Кроме того, вы видели кодировку ZSCII, используемую для сжатия коротких строк на микрокомпьютерах с ограниченным объемом памяти в 80-х годах?

текст ссылки

Ответ 4

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

Например, вы можете обнаружить, что под 20 символами сжатая строка на самом деле больше и, следовательно, только сжимает более длинные строки.

Ответ 5

Зачем использовать длину 4 байта, когда строки имеют длину 10-250 байт, используйте длину в 1 байт, которая сохранит вам 3 байта на одну строку.

Является ли текст текстовым только то, что 0-9 A-z или некоторый поднабор? если так перекодировать его, чтобы использовать это подмножество и сохранить несколько бит на символ.

Теперь просмотрите http://gnosis.cx/publish/programming/compression_primer.html в разделе кодирования Хаффмана и разделе lempel-zev.

Это должно заставить вас начать.

Ответ 6

При использовании нескольких строк, подобных этому, можно избежать накладных расходов указателя для каждой строки (4 или 8 байтов каждый), объединив их вместе с \0 (1 байт) и используя функцию поиска.

#include <stdio.h>

static const char strings[]="hello\0world\0test";

char * nthstring(const char *s, unsigned n){
    while(n--)
        while(*s++)
        ;
    return s;
}
int main(void) {
    printf("%s\n",nthstring(strings,1));
    return 0;
}

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

#include <stdio.h>
/* each "string" is prefixed with its octal length */
static const char lenstrings[]="\05hello\05world\04test";

char * ithstring(const char *s, unsigned n){
    while(n--){
        s+=*s+1;
    }
    return s;
}
int main(void) {
    char *s=ithstring(lenstrings,1);
    /* use the length because we don't have terminating \0 */
    printf ("%.*s",(unsigned char)*s,s+1);
    //write(1,s+1,(unsigned char)*s); //POSIX variation via <unistd.h>
    return 0;
}

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

Примечание. Чтобы получить максимальное сжатие из стандартных компрессоров, вы, скорее всего, захотите изменить поле длины своих заголовков на unsigned char (или unsigned short, если длина строк превышает 256, но не 65536 байт), поскольку большая часть они будут пытаться поддерживать сжатие больших файлов (это может сэкономить 3-7 байт на строку)