Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана

Опубликовано: 21 Января, 2023

Текстовые файлы можно сжимать, чтобы уменьшить их размер и ускорить отправку, а распаковка файлов на устройствах сопряжена с небольшими накладными расходами. Процесс кодирования включает в себя изменение представления файла таким образом, чтобы (двоичный) сжатый вывод занимал меньше места для хранения и меньше времени для передачи, сохраняя при этом возможность воссоздать исходный файл точно из его сжатого представления. Текстовые файлы могут относиться к разным типам файлов, таким как HTML, JavaScript, CSS, .txt и т. д. Сжатие текста необходимо, поскольку несжатые данные могут занимать много места, что неудобно для хранения устройства и обмена файлами.

Как работает процесс сжатия?

Размер текстового файла можно уменьшить, сжимая его, при этом текст преобразуется в меньший формат, занимающий меньше места. Обычно он работает, находя похожие строки/символы в текстовом файле и заменяя их временным двоичным представлением, чтобы уменьшить общий размер файла. Существует два типа сжатия файлов,

Сжатие с потерями: при сжатии с потерями файл сжимается за счет безвозвратного удаления определенных элементов, особенно избыточных.
Сжатие без потерь . Сжатие без потерь может восстановить все элементы файла во время распаковки без ущерба для данных и качества.

Кодирование текста также бывает двух типов:

Кодирование фиксированной длины и
Кодирование переменной длины.

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

Как сохранить уникальность сжатого текста?

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

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

Сжатие текстового файла:

Для этой цели мы используем алгоритм кодирования Хаффмана, который является жадным алгоритмом, который назначает двоичные коды переменной длины для каждого входного символа в текстовом файле. Длина двоичного кода зависит от частоты символа в файле. Алгоритм предлагает создать двоичное дерево, в котором все уникальные символы файла хранятся в листовых узлах дерева.

Алгоритм работает, сначала определяя все уникальные символы файла и их частоты.
Затем символы и частоты добавляются в Min-кучу.
Затем он извлекает два символа минимальной частоты и добавляет их в качестве узлов в фиктивный корень.
Значение этого фиктивного корня представляет собой объединенную частоту его узлов, и этот корневой узел добавляется обратно в минимальную кучу.
Затем процедура повторяется до тех пор, пока в Min-куче не останется только один элемент.

Таким образом, можно создать дерево Хаффмана для конкретного текстового файла.

Шаги для построения дерева Хаффмана:

Входными данными алгоритма является массив символов в текстовом файле.
Вычисляется частота появления каждого символа в файле.
Создается массив структур, в котором каждый элемент включает символ вместе с его частотами. Они хранятся в приоритетной очереди (min-heap), где элементы сравниваются по их частотам.
Для построения дерева Хаффмана из минимальной кучи извлекаются два элемента с минимальной частотой.
Два узла добавляются в дерево как левый и правый потомки нового корневого узла, который содержит частоту, равную сумме двух частот. Символ с более низкой частотой добавляется к левому дочернему узлу, а символ с более высокой частотой — к правому дочернему узлу.
Затем корневой узел снова добавляется обратно в очередь приоритетов.
Повторяйте с шага 4, пока в приоритетной очереди не останется только один элемент.
Наконец, левое и правое ребра дерева пронумерованы 0 и 1 соответственно. Для каждого листового узла просматривается все дерево, и соответствующие 1 и 0 добавляются к их коду до тех пор, пока не встретится листовой узел.
Получив уникальные коды для каждого уникального символа в тексте, мы можем заменить текстовые символы их кодами. Эти коды будут храниться в побитовом виде, что займет меньше места, чем текст.

Алгоритм поясняется на примере:

Приведенное выше графическое представление ясно демонстрирует полный алгоритм кодирования Хаффмана для текста = «Десерты со стрессом».
Размер файла с этим текстом = 17*1 = 17 байт.
Размер закодированного файла = 1*S + 1*- + 2*d + 4*e + 2*r + 5*s + 2*t = 1*4 + 1*4 + 2*3 + 4*2 + 2*3 + 5*2 + 2*3 = 44 бита = 44/8 байта = 5,5 байта

Структура сжатого файла:

До сих пор мы говорили о генерации входного кода переменной длины и замене его исходными символами файла. Однако это служит только для сжатия файла. Более сложная задача — распаковать файл, расшифровав двоичные коды до их исходного значения.

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

Структура сжатого файла –

Количество уникальных символов во входном файле

Общее количество символов во входном файле

Все символы с их двоичными кодами (используются для расшифровки)

Сохранение двоичных кодов путем замены символов входного файла по одному

Распаковка сжатого файла:

Сжатый файл открывается, и извлекается количество уникальных символов и общее количество символов в файле.
Затем символы и их двоичные коды считываются из файла. Используя это, мы можем воссоздать дерево Хаффмана.
Для каждого двоичного кода:
- Левое ребро создается для 0 , а правое ребро создается для 1 .
- Наконец, формируется листовой узел, и символ сохраняется в нем.
- Это повторяется для всех символов и двоичных кодов. Таким образом, дерево Хаффмана воссоздается таким образом.
Оставшийся файл теперь считывается побитно, и просматривается соответствующий бит 0/1 в дереве. Соответствующий символ записывается в распакованный файл, как только в дереве встречается конечный узел.
Шаг 4 повторяется до тех пор, пока сжатый файл не будет прочитан полностью.

Таким образом, мы восстанавливаем все символы из нашего входного файла во вновь распакованный файл без потери данных или качества.

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

Временная сложность: O(N * logN), где N — количество уникальных символов, так как эффективная структура данных очереди с приоритетами занимает O(logN) времени на вставку, полное двоичное дерево с N листьями имеет (2*N — 1) узлов.

Реализация с использованием языка C:

Открытие входных/выходных файлов:

C

// Opening input file in read-only mode
int fd1 = open(“sample.txt”, O_RDONLY);
if (fd1 == -1) {
    perror("Open Failed For Input File:
");
    exit(1);
}
 
// Creating output file in write mode
int fd2 = open(“sample - compressed.txt”,
               O_WRONLY | O_CREAT, S_IRUSR | S_IWUSR);
if (fd2 == -1) {
    perror("Open Failed For Output File:
");
    exit(1);
}

Функция для инициализации и создания минимальной кучи:

C

// Structure for tree nodes
struct Node {
    char character;
    int freq;
    struct Node *l, *r;
};
 
// Structure for min heap
struct Min_Heap {
    int size;
    struct Node** array;
};
 
// Function to create min heap
struct Min_Heap* createAndBuildMin_Heap(char arr[],
                                        int freq[],
                                        int unique_size)
{
    int i;
 
    // Initializing heap
    struct Min_Heap* Min_Heap
        = (struct Min_Heap*)malloc(sizeof(struct Min_Heap));
    Min_Heap->size = unique_size;
    Min_Heap->array = (struct Node**)malloc(
        Min_Heap->size * sizeof(struct Node*));
 
    // Initializing the array of pointers in minheap.
    // Pointers pointing to new nodes of character
    // and their frequency
    for (i = 0; i < unique_size; ++i) {
 
        // newNode is a function
        // to initialize new node
        Min_Heap->array[i] = newNode(arr[i], freq[i]);
    }
 
    int n = Min_Heap->size - 1;
    for (i = (n - 1) / 2; i >= 0; --i) {
 
        // Standard function for Heap creation
        Heapify(Min_Heap, i);
    }
 
    return Min_Heap;
}

Функция для построения и создания дерева Хаффмана:

C

// Function to build Huffman Tree
struct Node* buildHuffmanTree(char arr[], int freq[],
                              int unique_size)
{
    struct Node *l, *r, *top;
    while (!isSizeOne(Min_Heap)) {
        l = extractMinFromMin_Heap(Min_Heap);
        r = extractMinFromMin_Heap(Min_Heap);
        top = newNode("$", l->freq + r->freq);
        top->l = l;
        top->r = r;
        insertIntoMin_Heap(Min_Heap, top);
    }
    return extractMinFromMin_Heap(Min_Heap);
}

Рекурсивная функция для печати двоичных кодов в сжатый файл:

C

// Structure to store codes in compressed file
typedef struct code {
    char k;
    int l;
    int code_arr[16];
    struct code* p;
} code;
 
// Function to print codes into file
void printCodesIntoFile(int fd2, struct Node* root,
                        int t[], int top = 0)
{
    int i;
    if (root->l) {
        t[top] = 0;
        printCodesIntoFile(fd2, root->l, t, top + 1);
    }
 
    if (root->r) {
        t[top] = 1;
        printCodesIntoFile(fd2, root->r, t, top + 1);
    }
 
    if (isLeaf(root)) {
        data = (code*)malloc(sizeof(code));
        tree = (Tree*)malloc(sizeof(Tree));
        data->p = NULL;
        data->k = root->character;
        tree->g = root->character;
        write(fd2, &tree->g, sizeof(char));
        for (i = 0; i < top; i++) {
            data->code_arr[i] = t[i];
        }
        tree->len = top;
        write(fd2, &tree->len, sizeof(int));
        tree->dec
            = convertBinaryToDecimal(data->code_arr, top);
        write(fd2, &tree->dec, sizeof(int));
        data->l = top;
        data->p = NULL;
        if (k == 0) {
            front = rear = data;
            k++;
        }
        else {
            rear->p = data;
            rear = rear->p;
        }
    }
}

Функция для сжатия файла путем замены символов их кодами Хаффмана:

C

// Function to compress file
void compressFile(int fd1, int fd2, unsigned char a)
{
    char n;
    int h = 0, i;
 
    // Codes are written into file in bit by bit format
    while (read(fd1, &n, sizeof(char)) != 0) {
        rear = front;
        while (rear->k != n && rear->p != NULL) {
            rear = rear->p;
        }
        if (rear->k == n) {
            for (i = 0; i < rear->l; i++) {
                if (h < 7) {
                    if (rear->code_arr[i] == 1) {
                        a++;
                        a = a << 1;
                        h++;
                    }
                    else if (rear->code_arr[i] == 0) {
                        a = a << 1;
                        h++;
                    }
                }
                else if (h == 7) {
                    if (rear->code_arr[i] == 1) {
                        a++;
                        h = 0;
                    }
                    else {
                        h = 0;
                    }
                    write(fd2, &a, sizeof(char));
                    a = 0;
                }
            }
        }
    }
    for (i = 0; i < 7 - h; i++) {
        a = a << 1;
    }
    write(fd2, &a, sizeof(char));
}

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

C

typedef struct Tree {
    char g;
    int len;
    int dec;
    struct Tree* f;
    struct Tree* r;
} Tree;
 
// Function to extract Huffman codes
// from a compressed file
void ExtractCodesFromFile(int fd1)
{
    read(fd1, &t->g, sizeof(char));
    read(fd1, &t->len, sizeof(int));
    read(fd1, &t->dec, sizeof(int));
}
 
// Function to rebuild the Huffman tree
void ReBuildHuffmanTree(int fd1, int size)
{
    int i = 0, j, k;
    tree = (Tree*)malloc(sizeof(Tree));
    tree_temp = tree;
    tree->f = NULL;
    tree->r = NULL;
    t = (Tree*)malloc(sizeof(Tree));
    t->f = NULL;
    t->r = NULL;
    for (k = 0; k < size; k++) {
        tree_temp = tree;
        ExtractCodesFromFile(fd1);
        int bin[MAX], bin_con[MAX];
        for (i = 0; i < MAX; i++) {
            bin[i] = bin_con[i] = 0;
        }
        convertDecimalToBinary(bin, t->dec, t->len);
        for (i = 0; i < t->len; i++) {
            bin_con[i] = bin[i];
        }
 
        for (j = 0; j < t->len; j++) {
            if (bin_con[j] == 0) {

                    
                                            Алгоритмы
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИРазница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в хэширование — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022