Адские тиски правосудия

Косякин Антон

Xakep, номер #066, стр. 066-112-4

Теперь переходим к сути – к воплощению самого алгоритма сжатия, а затем - распаковке сжатых данных.

Процесс кодирования достаточно прост: пока не пуст входной поток, читаем СИМВОЛ и проверяем, есть ли в словаре СТРОКА (префикс) + СИМВОЛ (изначально префикс пуст). Если нет - добавляем эту комбинацию в словарь, в выходной файл записываем код для СТРОКА, СТРОКА = СИМВОЛ; повторяем цикл. Если же СТРОКА+СИМВОЛ в словаре присутствуют - СТРОКА=СТРОКА+СИМВОЛ, повторяем цикл. По завершению цикла (когда входной файл кончился) записываем в выходной файл код для СТРОКА. Для лучшего понимания рассмотрим небольшой пример: пусть нам нужно закодировать строку "zed_ze". Напомню, что под номерами 0-255 у нас в словаре уже имеются все 256 ASCII-символов. Итак. Изначально СТРОКА=пусто. Читаем "z": СИМВОЛ=z. В словаре уже имеется буква "z", поэтому СТРОКА=z. Читаем "e". "ze" в словаре нет, запоминаем под номером 256, "z" выводим в результат, СТРОКА=e. Считали "d": "ed" в словаре нет, запомнили с кодом 257, "e" в результат, СТРОКА=d. "_": "d_" в словаре нет, запомнили с кодом 258, "d" в результат, СТРОКА=_. И так далее. По завершению цикла в выходном файле получим - "zed_<256>". На С этот цикл тоже кодируется довольно просто: предположим, что dict[] - наш массив, в котором храним словарь. Каждый элемент массива - запись, имеющая поле int pref (СТРОКА), int byte (СИМВОЛ). Итак, получаем:

Код паковки

pref = -1; // СТРОКА = пусто

ch = fgetc(input); // читаем СИМВОЛ

while ( ch != EOF) {

tmp = find_dict(pref, ch); // ищем в dict[] нужную комбинацию

if (tmp != -1) { // если нашли

pref = tmp;

else {

add_dict(pref, ch); // добавляем в словарь

fwrite(&pref, sizeof(pref), 1, output); // выводим в результат

pref = ch;

};

ch = fgetc(input);

};

С кодированием, вроде бы, разобрались. Осталось дело за раскодированием. В принципе, здесь все аналогично. Одной из причин эффективности описываемого алгоритма является то, что нам не нужно хранить полученный при сжатии словарь - он может быть точно восстановлен при распаковке на основе выходного потока алгоритма сжатия. Это возможно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде, чем он поместит этот код в выходной файл. Это и означает, что сжатые данные не обременены необходимостью тянуть за собой большую таблицу перевода. А вот и сам алгоритм: из входного потока читаем СТАРЫЙ_КОД, выводим его в файл. Далее пока входной поток не пуст, читаем НОВЫЙ_КОД. СТРОКА = расшифровать НОВЫЙ_КОД (пройтись по словарю и по его данным на основании кода построить строку). Далее выводим в результат СТРОКА. СИМВОЛ = первый символ СТРОКА, добавляем СТАРЫЙ_КОД+СИМВОЛ в словарь, СТАРЫЙ_КОД = НОВЫЙ_КОД. И продолжаем цикл. Говоря проще - из входного потока (пока он не закончится) читаем символ. Если его код меньше 256, то повторяем, совершаем над ним процедуру кодирования. Если же код больше или равен 256, то, проходясь по словарю, генерируем строку и выводим ее в результат. А затем с каждым символом строки совершаем процедуру кодирования.