Tiff c lzw компрессией что это такое

Какой формат сжатия TIFF лучше, LZW или ZIP?

Какое сжатие изображений лучше, LZW или ZIP? Я использую Lightroom для экспорта изображений.

Лучше относительный термин, и, в некоторой степени, он будет варьироваться в зависимости от количества между ними в зависимости от множества факторов, включая глубину цвета, частоту дискретных цветов и т. Д. Некоторые эксперименты могут быть необходимы на этом фронте, хотя мой чтение показывает, что LZW подходит для изображений с меньшей битовой глубиной, с множеством одинаковых цветов и тонов и ZIP для случаев, когда это не так. Другими словами, если изображение состоит из 8 битов, то идет LZW, а если это 16 битов, то, как правило, используйте ZIP, но с оговоркой, что это не абсолютное правило и могут быть исключения.

В рекомендациях ЕС Succeed 2014 по метаданным и форматам данных для онлайн-доступности и долгосрочного хранения рекомендуется «Несжатое или LZW-сжатие» для мастеров TIFF (стр. 68) и обратите внимание на то, что «Если файлы активно управляются в цифровом хранилище, это возможно рассмотреть возможность использования сжатия LZW или ZIP без потерь для файлов TIFF. Сжатие JPEG не должно использоваться в формате TIFF. [. ] Большинство респондентов используют несжатые изображения (64%), если используется сжатие, то в основном используется LZW ».

Для быстрого сохранения вы хотите использовать сжатие без сжатия. Добавление сжатия может умножить время, необходимое для сохранения TIFF, в 5 раз для 16-битных файлов TIFF и в 10-15 раз для 8-битных файлов TIFF. В наши дни хранилище настолько дешево, что время сохранения файлов может быть дороже, чем затраты на добавление дополнительного хранилища, особенно для 16-разрядных файлов, в которых сжатие сокращает только 15-20% от общего размера файла.

Если вы хотите использовать сжатие, потому что для вас важно экономить место для хранения или вы выпускаете сотни файлов TIFF в день, при сохранении 8-битных файлов TIFF используйте LZW, а при сохранении 16-битных файлов TIFF используйте ZIP. В 8-битных файлах TIFF разница в размере между LZW и ZIP незначительна, но для сохранения ZIP требуется 2-3 раза больше времени. В 16-битных TIFF-файлах LZW часто создает файлы, размер которых превышает размер ZIP или несжатых TIFF-файлов, поэтому, если вы собираетесь использовать сжатие для 16-битных TIFF-файлов, пропустите LZW и используйте вместо него ZIP.

Вкратце: самое
быстрое время сохранения: без сжатия
8-битные файлы TIFF: LZW-сжатие
16-битные файлы TIFF: сжатие ZIP

Источник

Tiff c lzw компрессией что это такое

Каждый программист имеет хотя бы некоторое представление о сжатии (упаковке) данных. Такие программы, как «ARC» (System Enhancement Associates, Wayne, N.J.) и «PkZip» (PKWARE, Glendale, Wisc.) вездесущи в мире MS-DOS. «ARC», к тому же, используется в ряде других операционных систем, таких как Unix, CP/M и т.д. Пользователи CP/M долгое время использовали также «SQ» и «USQ» для сжатия и распаковки программ. Пользователи Unix имеют утилиты «COMPRESS» и «COMPACK». Однако техника сжатия данных используется этими программами только двумя способами: пересылка файлов по линиям связи и архивация. Сжатие данных имеет незаслуженную репутацию трудного для освоения, тяжелого в реализации и тем не менее существующего явления. Фактически техника, использованная в выше упомянутых программах, относительно проста и может быть реализована в виде стандартных утилит, содержащих довольно мало строк кода. В этой статье обсуждается Lempel-Ziv-Welch (LZW) сжатие, хорошая, повсеместно используемая техника.

LZW, к примеру, сжимая экранные формы, может легко «снять» 50K байт с программы, основную часть которой составляют хэлповые экраны. При использовании LZW-сжатия 500K байт программного обеспечения могут быть поставлены конечному пользователю на 360Kб дискете. Чрезмерно разбухшие файлы базы данных могут быть сжаты до десяти процентов их исходного размера.

Основы LZW

Собственно исходный Lempel/Ziv подход к сжатию данных был впервые обнародован в 1977г., а усовершенствованный (Terry Welch) вариант был опубликован в 1984г. Алгоритм на удивление прост. Если в двух словах, то LZW-сжатие заменяет строки символов некоторыми кодами. Это делается без какого-либо анализа входного текста. Вместо этого при добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, генерируемые LZW-алгоритмом, могут быть любой длины, но они должны содержать больше бит, чем единичный символ. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов. Остальные коды соответствуют обрабатываемым алгоритмом строкам.

Сжатие

СТРОКА = очередной символ из входного потока
WHILE входной поток не пуст DO
СИМВОЛ = очередной символ из входного потока
IF СТРОКА+СИМВОЛ в таблице строк THEN
СТРОКА = СТРОКА+СИМВОЛ
ELSE
вывести в выходной поток код для СТРОКА
добавить в таблицу строк СТРОКА+СИМВОЛ
СТРОКА = СИМВОЛ
END of IF
END of WHILE
вывести в выходной поток код для СТРОКА

Рис. 1 Алгоритм сжатия

Этот процесс повторяется до тех пор, пока вторая подстрока, состоящая из прочитанных символов «/» и «W», не сопоставится со строковым номером 256. В этом случае система выводит код 256 и добавляет трехсимвольную подстроку в таблицу. Этот процесс продолжается до тех пор, пока не исчерпается входной поток и все коды не будут выведены.

Входная строка : /WED/WE/WEE/WEB/WET

Рис. 2 Процесс сжатия

Выходной поток для заданной строки показан на рис. 2, также как и полученная в результате таблица строк. Как вы можете заметить, эта таблица быстро заполняется, т.к. новая строка добавляется в таблицу каждый раз, когда генерируется код. В этом явно вырожденном примере было выведено пять закодированных подстрок и семь символов. Если использовать 9-битные коды для вывода, то 19-символьная входная строка будет преобразована в 13.5-символьная выходную строку. Конечно, этот пример был выбран только для демонстрации. В действительности сжатие обычно не начинается до тех пор, пока не будет построена достаточно большая таблица, обычно после прочтения порядка 100 входных байт.

Распаковка

Алгоритму сжатия соответствует свой алгоритм распаковки. Он получает выходной поток кодов от алгоритма сжатия и использует его для точного восстановления входного потока. Одной из причин эффективности LZW-алгоритма является то, что он не нуждается в хранении таблицы строк, полученной при сжатии. Таблица может быть точно восстановлена при распаковке на основе выходного потока алгоритма сжатия. Это возможно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Это означает, что сжатые данные не обременены необходимостью тянуть за собой большую таблицу перевода.

читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОД
WHILE входной поток не пуст DO
читать НОВЫЙ_КОД
СТРОКА = перевести НОВЫЙ_КОД
вывести СТРОКУ
СИМВОЛ = первый символ СТРОКИ
добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОД
END of WHILE

Рис. 3 Алгоритм распаковки

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

Входные коды : / W E D 256 E 260 261 257 B 260 T

Рис. 4 Процесс распаковки

Выходной поток идентичен входному потоку алгоритма сжатия. Отметим, что первые 256 кодов уже определены для перевода одиночных символов, также как и в алгоритме сжатия.

Ловушка

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

Рис. 5 Некоторые проблемы

Когда распаковщик просматривает входной поток, он сначала декодирует код 300, затем выводит строку «JOEYN» и добавляет определение для, скажем, кода 399 в таблицу, хотя он уже мог там быть. Затем читает следующий входной код, 400, и обнаруживает, что его нет в таблице. Это уже проблема. К счастью, это произойдет только в том случае, если распаковщик встретит неизвестный код. Так как это фактически единственная коллизия, то можно без труда усовершенствовать алгоритм.

Модифицированный алгоритм предусматривает специальные действия для еще неопределенных кодов. В примере на рис. 6 распаковщик обнаруживает код 400, который еще не определен. Так как этот код не известен, то декодируется значение СТАРОГО_КОДА, равное 300. Затем распаковщик добавляет значение СИМВОЛА, равное «J», к строке. Результатом является правильный перевод кода 400 в строку «JOEYNJ».

читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОД
СИМВОЛ = СТАРЫЙ_КОД
WHILE входной поток не пуст DO
читать НОВЫЙ_КОД
IF NOT в таблице перевода НОВЫЙ_КОД THEN
СТРОКА = перевести СТАРЫЙ_КОД
СТРОКА = СТРОКА+СИМВОЛ
ELSE
СТРОКА = перевести НОВЫЙ_КОД
END of IF
вывести СТРОКУ
СИМВОЛ = первый символ СТРОКИ
добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОД
END of WHILE

Рис. 6 Модифицированный алгоритм распаковки

Реализация

Концепции, использованные в алгоритме сжатия, настолько просты, что весь алгоритм может быть записан в несколько строк. Но так как управление построением таблицы требует некоторых специальных действий, реализация несколько более сложна. В демонстрационной программе, приведенной ниже, использовались коды длиной 12, 13 и 14 бит. При длине кода 12 бит потенциально возможно хранить до 4096 строк в таблице. Каждый раз, когда читается новый символ, таблица строк должна просматриваться для сопоставления. Если сопоставление не найдено, новая строка должна быть добавлена в таблицу. Здесь возникают две проблемы. Во-первых, таблица строк может достаточно быстро стать очень большой. Даже если длина строк в среднем ограничивается 3 или 4 символами каждая, верхний предел длин строк может легко превысить 7 или 8 байт на код. К тому же количество памяти, необходимой для хранения строк, заранее не известно, так как оно зависит от общей длины строк.

Вторая проблема заключается в организации поиска строк. Каждый раз, когда читается новый символ, необходимо организовать поиск для новой строки вида СТРОКА+СИМВОЛ. Это означает поддержку отсортированного списка строк. В этом случае поиск для каждой строки включает число сравнений порядка log2 от общего числа строк. Использование 12-битных слов потенциально позволяет выполнять не более 12 сравнений для каждого кода.

Первая проблема может быть решена хранением строк как комбинаций код/символ. Так как каждая строка в действительности является представлением комбинации уже существующего кода и добавочного символа, можно хранить каждую строку как отдельный код плюс символ. Например в разобранном выше примере строка «/WEE» хранится как код 260 и символ «E». Это позволяет использовать для хранения только 3 байта вместо 5 (включающих дополнительный байт для конца строки). Идя назад, можно определить, что код 260 хранится как код 256 плюс добавочный символ «E». Наконец, код 256 хранится как «/» плюс «W».

Выполнение сравнения строк является немного более трудным. Новый метод хранения увеличивает время, необходимое для сравнения строк, но он не влияет на число сравнений. Эта проблема решается использованием алгоритма хэширования для хранения строк. Это означает, что код 256 не хранится в каком-либо массиве по адресу 256, а хранится в массиве по адресу, сформированному на основе самой строки. При определении места хранения данной строки можно использовать тестовую строку для генерации хэш-адреса и затем найти целевую строку однократным сравнением. Так как код для любой данной строки нельзя узнать в дальнейшем иначе как по его позиции в массиве, необходимо хранить код для данной строки совместно с данными строки. В демонстрационной программе для этого используются элементы трех массивов : code_value[i], prefix_code[i] и append_character[i].

Когда необходимо добавить новый код в таблицу, используется хэшфункция в процедуре find_match для генерации корректного i. Процедура find_match генерирует адрес и затем проверяет, не использовался ли он уже. Если это так, то find_match выполняет вторую пробу и так до тех пор, пока не найдется свободное место.

Реализация алгоритма распаковки имеет свой набор проблем. Одна из проблем алгоритма сжатия здесь исчезает. Когда выполняется сжатие, необходимо организовать поиск в таблице для данной строки. При распаковке необходимо организовать просмотр для отдельного кода. Это означает, что можно хранить префиксы кодов и добавочные символы, индексируясь по их строковому коду. Это устраняет необходимость в хэш-функции и освобождает массив, использовавшийся для хранения значений кодов.

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

Проблема появляется, когда чтение входного потока прерывается при достижении конца потока. Для этого частного случая в программе зарезервирован последний определяемый код MAX_VALUE как признак конца данных. Это не является необходимым при чтении файла, но может помочь при чтении буфера сжатых данных из памяти. Затраты на потерю одного определяемого кода весьма малы сравнительно со всем процессом.

Результаты

Достаточно трудно охарактеризовать результативность какой-либо техники сжатия данных. Степень сжатия определяется различными факторами. LZW-сжатие выделяется среди прочих, когда встречается с потоком данных, содержащим повторяющиеся строки любой структуры. По этой причине он работает весьма эффективно, когда встречает английский текст. Уровень сжатия может достигать 50% и выше. Соответственно, сжатие видеоформ и копий экранов показывает еще большие результаты.

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

Ваша реализация

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

Одной из проблем является то, что приведенная программа не адаптируется к различной длине файлов. Использование 14- или 15-битных кодов дает лучшую степень сжатия на больших файлах (это объясняется тем, что для них строятся большие таблицы строк), но хуже работает с маленькими файлами. Такие программы, как «ARC», решают эту проблему использованием кодов переменной длины. Например, когда величина next_code находится между 256 и 511, «ARC» читает и выводит 9-битные коды. Когда величина next_code становится настолько большой, что необходимы 10-битные коды, процедуры сжатия и распаковки увеличивают размер кода. Это значит, что 12- и 15-битные варианты программы работают хорошо и на маленьких файлах.

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

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

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

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

Коротко

Приведенная программа была написана и тестирована на MS-DOS машине и успешно скомпилирована и выполнена с использованием обычного компилятора «C». Она должна нормально работать на любой машине, поддерживающей 16-битный целые и 32-битные длинные целые языка «C».

Реализация компиляторов «C» для MS-DOS обычно создает сложности при использовании массивов больших, чем 64К байт, не позволяя использовать 15- или 16-битные коды в программе. На машинах с другими процессорами, таких как VAX, эти сложности преодолеваются и облегчается использование кодов большей длины.

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

Библиография

Mark R. Nelson
Перевод: Запольский С.А.

Источник

Сжатие данных LZW

Оглавление

Советы по программированию

Обзор

Если бы вы взглянули почти на любой файл данных в компьютере, просматривая символ за символом, то наверняка обратили бы внимание на множество повторяющихся элементов. LZW — это метод сжатия данных, который воспользовался этим повторением. Оригинальная версия метода была создана Лемпелем и Зивом в 1978 году (LZ78) и доработана Уэлчем в 1984 году, отсюда и аббревиатура LZW (Lempel, Ziv and Welch). Как и в любом адаптивном/динамическом методе сжатия, идея заключается в том, чтобы (1) начать с исходной модели, (2) читать данные по частям, (3) обновлять модель и кодировать данные по мере продвижения. LZW — алгоритм сжатия на основе «словаря». Это означает, что вместо сведения в таблицу количества символов и построения деревьев (как при кодировании по Хаффману), LZW кодирует данные, обращаясь к словарю. Таким образом, чтобы закодировать подстроку, в выходной файл нужно записать только одно кодовое число, соответствующее индексу этой подстроки в словаре. Хотя LZW часто рассматривается в контексте сжатия текстовых файлов, его можно использовать для любого типа файлов. Однако, как правило, он лучше всего справляется с файлами где есть повторяющиеся подстроки, например, с текстовыми файлами.

Сжатие

LZW начинает со словаря из 256 символов (в случае 8 бит) и использует их в качестве «стандартного» набора символов. Затем он считывает данные по 8 бит за раз (например, ‘t’, ‘r’ и т.д.) и кодирует их в виде числа, которое представляет собой индекс в словаре. Всякий раз, встречая новую подстроку (скажем, «tr»), он добавляет ее в словарь; каждый раз, когда ему попадается подстрока, которая ранее уже встречалась, он просто считывает новый символ и выполняет его конкатенацию с текущей строкой, чтобы получить новую подстроку. В следующий раз, когда LZW вновь обратится к подстроке, она будет закодирована с помощью одного числа. Обычно для словаря задается максимальное количество записей (скажем, 4096), чтобы процесс не исчерпал память. Таким образом, коды, занимающие место подстрок в данном примере, имеют длину 12 бит (2^12 = 4096). Это необходимо, чтобы коды были длиннее в битах, чем символы (12 против 8 бит), но поскольку вместо большого количества часто встречающихся подстрок будет использоваться только один код, в конечном итоге достигается сжатие.

Вот как это может выглядеть в псевдокоде:

Теперь предположим, что наш входной поток, который мы хотим сжать, это «banana_bandana», и при этом используется только начальный словарь:

Этапы кодирования будут выполняться следующим образом:

Вход

Текущая строка

Видели это раньше?

Кодированный

выход

Новая словарная запись/индекс

Обратите внимание, что после считывания последнего символа, «a», должна быть выведена последняя подстрока, «ana».

Распаковка

Вот как это работает. Декодер LZW сначала считывает индекс (целое число), ищет этот индекс в словаре и выводит подстроку, связанную с этим индексом. Первый символ этой подстроки конкатенируется с текущей рабочей строкой. Эта новая конкатенация добавляется в словарь (подобно тому, как подстроки были добавлены во время сжатия). Затем декодированная строка становится текущей рабочей строкой (текущий индекс, т.е. подстрока, запоминается), и процесс повторяется.

Еще раз, вот как это может выглядеть:

Есть исключение, когда алгоритм не работает; это происходит, когда код вызывает индекс, который еще не был введен (например, вызов индекса 31, когда индекс 31 в настоящее время обрабатывается и поэтому его еще нет в словаре). Пример из Sayood поможет проиллюстрировать этот момент. Предположим, у вас есть строка ababababab. и начальный словарь, состоящий только из a и b с индексами 0 и 1 соответственно. Начинается процесс кодирования:

Вход

Текущая строка

Видели это раньше?

Кодированный выход

Новая словарная запись/индекс

Кодированный вход

Преобразование словаря

Декодированный выход

Текущая строка

Новая словарная запись/индекс

Практическое задание для понимания: Расшифруйте закодированные данные для первого примера и посмотрите, сможете ли вы вернуть «banana_bandana». Помните, что вы должны начать с того же начального словаря (т.е. каждый символ находится в том же индексном слоте, что и раньше). Для облегчения работы составьте таблицу декодирования, как показано выше. Проверьте свой ответ здесь

Советы по программированию

Здесь приведены некоторые подсказки и советы, которые могут помочь при программировании LZW.

Структура данных. Программы кодирования и декодирования обращаются к словарю бесчисленное количество раз в ходе работы алгоритма. Структура данных с использованием сложности поиска 0(1) была бы очень удобна. Однако обеим программам не обязательно нужна одна и та же структура данных. Кодер ищет индексы в словаре с помощью строк (какая структура может подойти для этого?), а декодер ищет строки с помощью индексов (произвольный доступ с помощью индексов? как это звучит?)

Псевдо-EOF. В кодировании Хаффмана псевдо-EOF (End Of File) выводится в конце вывода, чтобы декодер знал, когда достигается конец закодированного вывода. Хотя LZW, как правило, не требует псевдо-eof (обычно он читает данные до тех пор, пока не сможет прочитать больше), его использование является хорошей идеей. В частности, если вы хотите расширить свою программу для сжатия нескольких файлов, вам понадобится средство для обозначения того, где заканчиваются закодированные данные одного файла и начинаются данные другого. Вероятно, самый простой способ сделать это — зарезервировать место в словаре (скажем, последний индекс) для псевдо-eof (на самом деле там ничего не хранится). Когда вы закончите кодирование, просто запишите индекс псевдо-eof. Само собой разумеется, что программа декодирования также должна зарезервировать этот индекс для сигнала псевдо-eof.

Flush Character. Это тоже необязательная функция. И снова нужно зарезервировать еще один слот в словаре. Когда программа распаковки прочитает индекс для символа flush, она вернет словарь в исходное состояние. Видите ли, когда словарь становится полным, он перестает быть динамическим и, следовательно, перестает отражать локальные характеристики. Однако, используя символ flush, вы можете следить за коэффициентом сжатия и очищать словарь всякий раз, когда этот коэффициент падает ниже определенного порога. Попробуйте поэкспериментировать с этим, и в вашем распоряжении окажется неплохая программа сжатия.

Всех желающих приглашаем на открытый урок «Сложность алгебраических алгоритмов. Часть-1 «Числа Фибоначчи»». На первом мастер-классе мы узнаем, какие бывают сложности алгоритмов, напишем функции возведения числа в целую степень и поиска чисел Фибоначчи. Сделаем это различными способами, изменяя сложность алгоритмов от экспоненциальной до логарифмической.
>> РЕГИСТРАЦИЯ

Источник