Словарь-кодер

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

Методы и приложения [ править ]

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

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

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

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

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

Ссылки [ править ]

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

См. также [ править ]

[1] Ян Х. Виттен, Алистер Моффат и Тимоти К. Белл. Управление гигабайтами . Нью-Йорк: Ван Ностранд Рейнхольд, 1994. ISBN 9780442018634 .

[2] Родни Дж. Смит. Система сжатия потоковой передачи с использованием групп динамических соединений , патент США № 5,748,955, дата приоритета 20 декабря 1993 г.

[1]

[2]