WikiDer > Кодировщик словаря

Dictionary coder

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

Методы и приложения

Некоторые кодировщики словаря используют «статический словарь», полный набор строк которого определяется до начала кодирования и не изменяется в процессе кодирования. Этот подход чаще всего используется, когда сообщение или набор сообщений, которые должны быть закодированы, являются фиксированными и большими; например, заявление который хранит содержимое книги в ограниченном пространстве для хранения КПК обычно строит статический словарь из согласованность текста, а затем использует этот словарь для сжатия стихов. Эта схема использования Кодирование Хаффмана представление индексов в согласование было названо "Хаффворд".[1]

В родственном и более общем методе словарь строится из избыточности, извлеченной из среды данных (различных входных потоков), и этот словарь затем используется статически для сжатия дальнейшего входного потока. Например, словарь создается из старых английских текстов, а затем используется для сжатия книги.[2]

Более распространены методы, при которых словарь начинается в некотором заранее определенном состоянии, но содержимое изменяется в процессе кодирования на основе данных, которые уже были закодированы. Оба LZ77 и LZ78 алгоритмы работают по этому принципу. В LZ77 кольцевой буфер называется "скользящим окном", вмещает последний N байтов обработанных данных. Это окно служит словарем, эффективно сохраняя каждый подстрока, появившаяся в прошлом N байты как словарные статьи. Вместо единственного индекса, идентифицирующего словарную статью, необходимы два значения: длина, указывающий длину совпадающего текста, а компенсировать (также называемый расстояние), указывая, что совпадение найдено в скользящем окне, начинающемся компенсировать байтов перед текущим текстом.

LZ78 использует более явную структуру словаря; в начале процесса кодирования словарь пуст. Значение индекса, равное нулю, используется для представления конца строки, поэтому первый индекс словаря равен единице. На каждом этапе процесса кодирования, если совпадения нет, то последний совпадающий индекс (или ноль) и символ добавляются в словарь и выводятся в сжатый поток. Если есть совпадение, то рабочий индекс обновляется до соответствующего индекса, и ничего не выводится.

LZW аналогичен LZ78, но словарь инициализируется всеми возможными символами. Типичная реализация работает с 8-битными символами, поэтому «коды» словаря для шестнадцатеричного числа от 00 до шестнадцатеричного FF (десятичное 255) предопределены. Словарные статьи будут добавлены, начиная с шестнадцатеричного значения кода 100. В отличие от LZ78, если совпадение не найдено (или если конец данных), то выводится только код словаря. Это создает потенциальную проблему, поскольку выходные данные декодера отстают на один шаг от словаря. Ссылаться на LZW о том, как с этим обращаться. Усовершенствования LZW включают в себя обработку символов с размерами, отличными от 8 бит, и наличие зарезервированных кодов для сброса словаря и указания конца данных.

Рекомендации

  1. ^ Ян Х. Виттен, Алистер Моффат и Тимоти К. Белл. Управление гигабайтами. Нью-Йорк: Ван Ностранд Рейнхольд, 1994. ISBN 9780442018634.
  2. ^ Родни Дж. Смит. Система сжатия потоковой передачи с использованием динамических групп соединений, Патент США 5,748,955, дата приоритета 20 декабря 1993 г.

Смотрите также