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();
};