Arithmetic-coding

Арифметическое кодирование / Arithmetic coding

Арифметическое кодирование — один из алгоритмов энтропийного сжатия.

В отличие от алгоритма Хаффмана, не имеет жесткого постоянного соответствия входных символов группам бит выходного потока. Это даёт алгоритму большую гибкость в представлении дробных частот встречаемости символов.

Как правило, превосходит алгоритм Хаффмана по эффективности сжатия, позволяет сжимать данные с энтропией, меньшей 1 бита на кодируемый символ, но некоторые версии имеют патентные ограничения от компании IBM. (wikipedia)

Интерфейс (visual studio 2015):

Общий принцип (алгоритм) работы:

Кодирование:

1. На вход программы поступает текст - вводится либо с клавиатуры, либо из файла.
2. Из полученного текста создается алфавит - массив символов, исключающий повторы.
3. Создается массив накапливаемых частот (размер которого равен размеру алфавита) для символов из алфавита.
4. Вызывается классовый метод кодирования, преобразующий исходный текст в последовательность 0 и 1

Раскодирование:

1. На вход поступает строка, состоящая из закодированных символов (т.е. кодовая строка из 0 и 1).
2. Вызывается классовый метод декодирования, преобразующий последовательность 0 и 1 в исходный текст

Структура класса arithmetic:

class arithmetic
{
    private:
        /* Определение половины, четверти и 3/4 */
        const int first_qtr = _high_edge / 4 + 1;
        const int half = 2 * first_qtr;
        const int third_qtr = 3 * first_qtr;
        /* Основные объекты для работы с текстом */
        string text;
        string abc;
        string encode;
        string decode;
        /* Массив частот */
        int *freq;
    protected:
        /* Режим вывода дебаг-информации */
        static bool debug_mode;
    public:
        /* Показать таблицу частот и символов */
        void show_table();
        /* Вернуть закодированную строку */
        string get_encode();
        /* Вернуть раскодированную строку */
        string get_decode();
        /* Вернуть исходный текст */
        string get_text();
        /* Поместить текст из файла в string text*/
        void get_file(string filename);
        /* Поместить текст из входной input строки в string text */
        void input_string(string input);
        /* Ввести входной текст с клавиатуры */
        void input_keyboard();
        /* Создать алфавит */
        void get_abc();
        /* Создать массив частот */
        void get_frequency();
        /* Получение индекса следующего символа */
        void get_next_symbol(int i, int *current);
        /* Записать биты */
        string write_bits(bool bit, int bits_to_foll);
        /* Вывести полученный текст в файл */
        void output_file(string filename);
        /* Метод кодирования текста */
        void encode_text();
        /* Перевод 16 бит строки в int */
        int to_int(int _pos);
        /* Перевод int в биты */
        string to_bits_16(int _value);
        /* Метод добавления бита к int числу */
        int add_bit(int value, int count_taken, bool &flag);
        /* Метод раскодирования текста */
        void decode_text();
};