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