Словарные кодировщики: принципы и алгоритмы сжатия данных.

Введение

Кодер словаря, также иногда называемый кодером замещения, представляет собой класс алгоритмов сжатия данных без потерь, которые работают, осуществляя поиск совпадений между текстом, подлежащим сжатию, и набором строк, содержащихся в структуре данных (называемой «словарь»), поддерживаемой кодировщиком. Когда кодировщик находит такое совпадение, он заменяет его ссылкой на позицию этой строки в структуре данных.

Методы и применения

Некоторые кодировщики словарей используют "статический словарь", полный набор строк которого определяется до начала кодирования и не изменяется в процессе кодирования. Этот подход наиболее часто применяется, когда сообщение или набор сообщений, подлежащих кодированию, фиксированы и велики; например, приложение, хранящее содержимое книги в ограниченном объеме памяти КПК, обычно создает статический словарь на основе конкорданса текста, а затем использует этот словарь для сжатия отрывков. Эта схема использования кодирования Хаффмана для представления индексов в конкордансе получила название "Хаффворд". В смежном и более общем методе словарь строится на основе избыточности, извлеченной из среды данных (различных входных потоков), который затем статически используется для сжатия дополнительного входного потока. Например, словарь строится на основе старых английских текстов, а затем используется для сжатия книги. Более распространены методы, при которых словарь начинается в некотором предопределенном состоянии, но его содержимое изменяется в процессе кодирования на основе уже закодированных данных. Алгоритмы LZ77 и LZ78 работают по этому принципу. В LZ77 круговой буфер, называемый "скользящим окном", хранит последние N байтов обработанных данных. Это окно служит словарем, эффективно сохраняя каждую подстроку, которая встречалась в предыдущих N байтах, в качестве элементов словаря. Вместо одного индекса, идентифицирующего элемент словаря, требуются два значения: длина, указывающая длину совпавшего текста, и смещение (также называемое расстоянием), указывающее, что совпадение найдено в скользящем окне, начиная со смещения байтов до текущего текста. LZ78 использует более явную структуру словаря; в начале процесса кодирования словарь пуст. Значение индекса ноль используется для обозначения конца строки, поэтому первый индекс словаря равен единице. На каждом шаге процесса кодирования, если совпадение не найдено, последний совпадающий индекс (или ноль) и символ добавляются в словарь и выводятся в сжатый поток. Если совпадение найдено, рабочий индекс обновляется до совпадающего индекса, и ничего не выводится. LZW аналогичен LZ78, но словарь инициализируется всеми возможными символами. Типичная реализация работает с 8-битными символами, поэтому словарные "коды" для hex 00 до hex FF (десятичное 255) предопределены. Элементы словаря будут добавляться, начиная с кода hex 100. В отличие от LZ78, если совпадение не найдено (или достигнут конец данных), выводится только код словаря. Это создает потенциальную проблему, поскольку выход декодера на один шаг отстает от словаря. Обратитесь к описанию LZW, чтобы узнать, как это обрабатывается. Улучшения LZW включают поддержку размеров символов, отличных от 8 бит, и наличие зарезервированных кодов для сброса словаря и указания конца данных.

Some dictionary coders use a 'static dictionary', one whose full set of strings is determined before coding begins and does not change during the coding process. This approach is most often used when the message or set of messages to be encoded is fixed and large; for instance, an application that stores the contents of a book in the limited storage space of a PDA generally builds a static dictionary from a concordance of the text and then uses that dictionary to compress the verses. This scheme of using Huffman coding to represent indices into a concordance has been called "Huffword". In a related and more general method, a dictionary is built from redundancy extracted from a data environment (various input streams) which dictionary is then used statically to compress a further input stream. For example, a dictionary is built from old English texts then is used to compress a book. More common are methods where the dictionary starts in some predetermined state but the contents change during the encoding process, based on the data that has already been encoded. Both the LZ77 and LZ78 algorithms work on this principle. In LZ77, a circular buffer called the "sliding window" holds the last N bytes of data processed. This window serves as the dictionary, effectively storing every substring that has appeared in the past N bytes as dictionary entries. Instead of a single index identifying a dictionary entry, two values are needed: the length, indicating the length of the matched text, and the offset (also called the distance), indicating that the match is found in the sliding window starting offset bytes before the current text. LZ78 uses a more explicit dictionary structure; at the beginning of the encoding process, the dictionary is empty. An index value of zero is used to represent the end of a string, so the first index of the dictionary is one. At each step of the encoding process, if there is no match, then the last matching index (or zero) and character are both added to the dictionary and output to the compressed stream. If there is a match, then the working index is updated to the matching index, and nothing is output. LZW is similar to LZ78, but, the dictionary is initialized to all possible symbols. The typical implementation works with 8 bit symbols, so the dictionary "codes" for hex 00 to hex FF (decimal 255) are pre defined. Dictionary entries would be added starting with code value hex 100. Unlike LZ78, if a match is not found (or if the end of data), then only the dictionary code is output. This creates a potential issue since the decoder output is one step behind the dictionary. Refer to LZW for how this is handled. Enhancements to LZW include handing symbol sizes other than 8 bits and having reserved codes to reset the dictionary and to indicate end of data.