Краткий обзор понятий. 2 Алгоритмы сжатия текстов/файлов неизвестного формата

СОДЕРЖАНИЕ

ВВЕДЕНИЕ
1. Компрессия (сжатие) данных, техника и типы.

1.1 Краткий обзор понятий.

1.2 Алгоритмы сжатия текстов/файлов неизвестного формата.

1.3 Сжатие данных с потерями.

1.3.1 Типы сжатия с потерями.

1.3.2 Примеры сжатия данных с потерями.

1.4 Сжатие данных без потерь.

1.4.1 Техника сжатия без потерь.

1.4.2 Методы сжатия без потерь.

2.1 Алгоритм Зива-Лемпеля (LZ*).

2.1.1 Принцип скользящего окна.

2.1.2 Механизм кодирования совпадений.

2.1.3 Недостатки алгоритма.

2.1.4 LZ78.

2.2 Алгоритм Лемпеля — Зива — Велча (LZW).

2.2.1 Алгоритм.

2.2.2 Применение.

2.2.3 Пример.

2.2.4 Кодирование.

2.2.5 Декодирование.

2.2.6 Патенты.

2.2.7 Unisys, GIF и PNG.

2.3 Локально адаптивный алгоритм сжатия.

2.4 Сжатие данных с использованием преобразования Барроуза-Вилера.

2.5 Метод Шеннона-Фано.

2.6 Статический алгоритм Хаффмана.

3.1 Алгоритм фрактального сжатия.

3.2 Сжатие с использованием вейвлет.

3.3 JPEG.

СПИСОК ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

Сжатие информации является одним из самых интересных и динамически развивающихся направлений современной науки - теории информации. Вопросы сжатия данных достаточно остро стоят в различных областях науки и техники, везде, где требуется хранение и передача информации. Во-первых, это связано со все еще достаточно высокой стоимостью носителей информации (магнитные и оптические диски, ПЗУ, ОЗУ и т.д.), во-вторых, с необходимостью передачи больших потоков информации по перегруженным линиям связи (радио- и оптическая связь, телефония, сети). Кроме того, сжатие данных неразрывно связано с криптографией и защитой информации от случайного и преднамеренного воздействия. Естественно, универсального алгоритма сжатия данных не существует и для каждой конкретной задачи имеется свой наиболее эффективный метод. Более того, применение нерационально выбранного алгоритма может привести к противоположному результату увеличения потока информации. Иными словами, всегда можно найти такой набор данных, для которого выбранный способ сжатия окажется неэффективным.

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

В данной работе рассматриваются существующие на сегодняшний день методы компрессии данных.

1. 
   Компрессия (сжатие) данных.
   

Сжатие бывает без потерь (когда возможно восстановление исходных данных без искажений) или с потерями (восстановление возможно с незначительными искажениями). Сжатие без потерь используется при обработке компьютерных программ и данных. Сжатие с потерями обычно применяется для сокращения объёма звуковой, фото- и видеоинформации, оно значительно эффективнее сжатия без потерь.

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

2. 
   Алгоритмы сжатия текстов/файлов неизвестного формата.
   

Имеется 2 основных подхода к сжатию файлов неизвестного формата.

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

Для каждой последовательности в каждый момент времени собирается статистика её встречаемости в файле. На её основе вычисляется вероятность значений для очередного символа. После этого можно применять арифметическое кодирование или кодирование Хаффмана для замены часто встречающихся последовательностей на более короткие, а редко встречающихся — на более длинные.

2. 
   Сжатие данных с потерями.
   

Сжатие данных с потерями — это метод сжатия данных, когда распакованный файл отличается от оригинального, но «достаточно близок» для того, чтобы быть полезным каким-то образом. Этот тип компрессии часто используется в Интернете, особенно в потоковой передаче данных и телефонии. Эти методы часто называются кодеками в этом контексте. Альтернативой является сжатие без потерь.

1. 
   Типы сжатия с потерями.
   

Существуют две основных схемы сжатия с потерями:

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

1. 
   Компрессия изображений:
   

● Метод главных компонент

● Фрактальное сжатие

● JPEG

● Вэйвлетная компрессия

● JPEG 2000

● DjVu

2. 
   Компрессия видео:
   

● Flash (также поддерживает движущиеся изображения JPEG)

● H.261

● H.263

● H.264/MPEG-4 AVC

● MNG (поддерживает движущиеся изображения JPEG)

● Motion JPEG

● MPEG-1 Part 2

● MPEG-2 Part 2

● MPEG-4 Part 2

● Ogg Theora (отличается отсутствием патентных ограничений)

● Sorenson video codec

● VC-1 — попытка Microsoft выпустить открытую спецификацию для формата WMV

3. 
   Компрессия звука:
   

● MP3 — Определён спецификацией MPEG-1

● Ogg Vorbis (отличается отсутствием патентных ограничений и более высоким качеством^[1])

● AAC, AAC+ — существует в нескольких вариантах, определённых спецификациями MPEG-2 и MPEG-4, используется, например, в Apple Computer

● eAAC+ — формат, предлагаемый Sony, как альтернатива AAC и AAC+

● Musepack

● WMA — собственность Microsoft

● ADPCM

● ATRAC

● Dolby AC-3

● DTS

● MP2

● VQF

4. 
   Речь
   

● CELP

● G.711

● G.726

● HILN

● Speex (отличается отсутствием патентных ограничений)

2. 
   Сжатие данных без потерь.
   

Сжатие без потерь (англ. Lossless data compression) — метод сжатия информации, при использовании которого закодированная информация может быть восстановлена с точностью до бита. При этом оригинальные данные полностью восстанавливаются из сжатого состояния. Этот тип сжатия диаметрально отличается от сжатия данных с потерями. Для каждого из типов цифровой информации, как правило, существуют свои алгоритмы сжатия без потерь.

Сжатие данных без потерь используется во многих приложениях. Например, оно используется в популярном файловом формате ZIP и Unix-утилите Gzip. Оно также используется как компонент в сжатии с потерями.

Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример — исполняемые файлы и исходный код. Некоторые графические файловые форматы, такие как PNG или GIF, используют только сжатие без потерь; тогда как другие (TIFF, MNG) могут использовать сжатие как с потерями, так и без.

1. 
   Техника сжатия без потерь.
   

Методы сжатия без потерь могут быть распределены по типу данных, для которых они были созданы. Три основных типа данных для алгоритма сжатия данных это текст, изображения и звук. В принципе, любой многоцелевой алгоритм сжатия данных без потерь (многоцелевой означает, что он может обрабатывать любой тип бинарных данных) может использоваться для любого типа данных, но большинство из них неэффективны для каждого основного типа. Звуковые данные, например, не могут быть хорошо сжаты алгоритмом сжатия текста.

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

Статистические модели алгоритмов для текста (или текстовых бинарных данных, таких как исполняемые файлы) включают:

● Преобразование Барроуза — Уилера (блочно-сортирующая пре-обработка, которая делает сжатие более эффективным)

● LZ77 и LZ78 (используется DEFLATE)

● LZW

Алгоритмы кодирования через генерирование битовых последовательностей:

● Алгоритм Хаффмана (также используется DEFLATE)

● Арифметическое кодирование

2. 
   Методы сжатия без потерь.
   

1. 
   Многоцелевые:
   

● Кодирование длин серий — простая схема, дающая хорошее сжатие данных, которые содержат много повторяющихся значений

● LZW — используется в gif и во многих других

● Deflate — используется в gzip, усовершенствованной версии zip и как часть процесса сжатия PNG

● Audio Lossless Coding — также известен как MPEG-4 ALS

● Direct Stream Transfer — DST

● Dolby TrueHD

● DTS-HD Master Audio

● Free Lossless Audio Codec — FLAC

● Meridian Lossless Packing — MLP

● Monkey's Audio — Monkey’s Audio APE

● OptimFROG

● RealPlayer — RealAudio Lossless

● Shorten — SHN

● TTA — True Audio Lossless

● WavPack — WavPack lossless

● WMA Lossless — Windows Media Lossless

3. 
   Сжатие графики:
   

● ABO — Adaptive Binary Optimization

● GIF — (без потерь, но содержащий очень небольшое число цветов)

● JBIG2 — (с потерями или без Ч/Б изображений)

● JPEG-LS — (стандарт сжатия без потерь/почти без потерь)

● JPEG 2000 — (включает сжатие без потерь; также, испытан Sunil Kumar, профессором университета штата Сан-Диего)

● PGF — Progressive Graphics File (сжатие с/без потерь)

● PNG — Portable Network Graphics

● Qbit Lossless Codec — фокусируется на intra-frame («одна картинка») сжатии без потерь

● TIFF

● WMPhoto — (включая метод сжатия без потерь)

4. 
   Сжатие видео:
   

● Animation codec

● CamStudio Video Codec

● CorePNG

● FFV1

● H.264/MPEG-4 AVC

● Huffyuv

● Lagarith

● LCL

● MSU Lossless Video Codec

● Qbit Lossless Codec

● SheerVideo

● TSCC — TechSmith Screen Capture Codec
Примеры алгоритмов:
● Семейство алгоритмов Лемпеля-Зива

● RLE (Run-length encoding — Кодирование длин серий)

● звук — FLAC (Free Lossless Audio Codec), Monkey’s Audio (APE), TTA (True Audio), TTE, LA (LosslessAudio), RealAudio Lossless, WavPack и др.

● изображения — BMP, GIF, PNG

видео — Huffyuv.

2. 
   Методы сжатия (компрессии данных).
   

Целью архивации файлов является экономия места на жестком или гибком магнитном диске. Существует большое число программ-архиваторов, имеются и специальные системные программные средства типа Stacker или Doublespace и т.д., решающие эту проблему.

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

Сжатие информации без потерь осуществляется статистическим кодированием или на основе предварительно созданного словаря. Статистические алгоритмы (напр., схема кодирования Хафмана) присваивают каждому входному символу определенный код. При этом наиболее часто используемому символу присваивается наиболее короткий код, а наиболее редкому - более длинный. Таблицы кодирования создаются заранее и имеют ограниченный размер. Этот алгоритм обеспечивает наибольшее быстродействие и наименьшие задержки. Для получения высоких коэффициентов сжатия статистический метод требует больших объемов памяти.

Альтернативой статистическому алгоритму является схема сжатия, основанная на динамически изменяемом словаре (напр., алгоритмы Лембеля-Зива). Данный метод предполагает замену потока символов кодами, записанными в памяти в виде словаря (таблица перекодировки). Соотношение между символами и кодами меняется вместе с изменением данных. Таблицы кодирования периодически меняются, что делает метод более гибким. Размер небольших словарей лежит в пределах 2-32 килобайт, но более высоких коэффициентов сжатия можно достичь при заметно больших словарях до 400 килобайт.

Реализация алгоритма возможна в двух режимах: непрерывном и пакетном. Первый использует для создания и поддержки словаря непрерывный поток символов. При этом возможен многопротокольный режим (например, TCP/IP и DECnet). Словари сжатия и декомпрессии должны изменяться синхронно, а канал должен быть достаточно надежен (напр., X.25 или PPP), что гарантирует отсутствие искажения словаря при повреждении или потере пакета. При искажении одного из словарей оба ликвидируются и должны быть созданы вновь.

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

При передаче пакетов иногда применяется сжатие заголовков, например, алгоритм Ван Якобсона (RFC-1144). Этот алгоритм используется при скоростях передачи менее 64 Kбит/с. При этом достижимо повышение пропускной способности на 50% для скорости передачи 4800 бит/с. Сжатие заголовков зависит от типа протокола. При передаче больших пакетов на сверх высоких скоростях по региональным сетям используются специальные канальные алгоритмы, независящие от рабочих протоколов. Канальные методы сжатия информации не могут использоваться для сетей, базирующихся на пакетной технологии, SMDS (Switched Multi-megabit Data Service), ATM, X.25 и Frame Relay. Канальные методы сжатия дают хорошие результаты при соединении по схеме точка-точка, а при использовании маршрутизаторов возникают проблемы - ведь нужно выполнять процедуры сжатия/декомпрессии в каждом маршрутизаторе, что заметно увеличивает суммарное время доставки информации. Возникает и проблема совместимости маршрутизаторов, которая может быть устранена процедурой идентификации при у становлении виртуального канала.

Иногда для сжатия информации используют аппаратные средства. Такие устройства должны располагаться как со стороны передатчика, так и со стороны приемника. Как правило, они дают хорошие коэффициенты сжатия и приемлемые задержки, но они применимы лишь при соединениях точка-точка. Такие устройства могут быть внешними или встроенными, появились и специальные интегральные схемы, решающие задачи сжатия/декомпрессии. На практике задача может решаться как аппаратно, так и программно, возможны и комбинированные решения.

Если при работе с пакетами заголовки оставлять неизмененными, а сжимать только информационные поля, ограничение на использование стандартных маршрутизаторов может быть снято. Пакеты будут доставляться конечному адресату, и только там будет выполняться процедура декомпрессии. Такая схема сжатия данных приемлема для сетей X.25, SMDS, Frame Relay и ATM. Маршрутизаторы корпорации CISCO поддерживают практически все режимы сжатия/декомпрессии информации, перечисленные выше.

Сжатие информации является актуальной задачей, как при ее хранении, так и при пересылке. Сначала рассмотрим вариант алгоритма Зива-Лемпеля.

2.1 Алгоритм Зива-Лемпеля (LZ*).
В 1977 году Абрахам Лемпель и Якоб Зив предложили алгоритм сжатия данных, названный позднее LZ77. Этот алгоритм используется в программах архивирования текстов compress , lha , pkzip и arj . Можно сказать, что алгоритмы семейства LZ* представляют собой более сложное обобщение простого и интуитивного способа сжатия данных, используемого в RLE. Для понимания данного алгоритма необходимо разобраться с двумя его составляющими: принципом скользящего окна и механизмом кодирования совпадений.
2.1.1 Принцип скользящего окна.
Метод кодирования согласно принципу скользящего окна учитывает уже ранее встречавшуюся информацию, то есть информацию, которая уже известна для кодировщика и декодировщика (второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на ее первое вхождение).

Благодаря этому принципу алгоритмы LZ* иногда называются методами сжатия с использованием скользящего окна. Скользящее окно можно представить в виде буфера (или более сложной динамической структуры данных), который организован так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ. Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне». Размер скользящего окна может динамически изменяться и составлять 2 КБ, 4 КБ или 32 КБ. Следует также отметить, что размер окна кодировщика может быть менее или равен размеру окна декодировщика, но не наоборот.

Приведенное выше сравнение процесса кодирования с «программированием» может натолкнуть на преждевременный вывод о том, что алгоритм LZ77 относится к методам контекстного моделирования. Поэтому следует отметить, что алгоритм LZ77 принято классифицировать как метод словарного сжатия данных, когда вместо понятия «скользящего окна» используется термин «динамического словаря».
2.1.2 Механизм кодирования совпадений.
Перед тем, как перейти к рассмотрению механизма кодирования, уточним понятие совпадения (от англ. match). Рассмотрим последовательность из N элементов. Если все элементы последовательности уникальны, то такая последовательность не будет содержать ни одного повторяющегося элемента, или, иначе говоря, в последовательности не найдется хотя бы двух равных друг другу или совпадающих элементов.

В стандартном алгоритме LZ77 совпадения кодируются парой:

● длина совпадения (match length)

● смещение (offset) (или дистанция (distance))

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

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

Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними. Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары длина-смещение. Такая кодируемая пара будет представлять собой многократное (определяемое значением смещения) повторение последовательности (определяемой значением длины) символов, что представляет собой более общую форму RLE.
2.1.3 Недостатки алгоритма.
● невозможность кодирования подстрок, отстоящих друг от друга на расстоянии, большем длины словаря

● длина подстроки, которую можно закодировать, ограничена размером буфера

Алгори́тм Ле́мпеля — Зи́ва — Ве́лча (Lempel-Ziv-Welch, LZW) — это универсальный алгоритм сжатия данных без потерь, созданный Абрахамом Лемпелем (Abraham Lempel), Якобом Зивом (Jacob Ziv) и Терри Велчем (Terry Welch). Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм разработан так, чтобы его можно было быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных.

Акроним «LZW» указывает на фамилии изобретателей алгоритма: Лемпель, Зив и Велч, но многие утверждают, что, поскольку патент принадлежал Зиву, то метод должен называться алгоритмом Зива — Лемпеля — Велча.

Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов — это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.

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

1. 
   Алгоритм.
   

1. 
   Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы w первым символом сообщения.
   
2. 
   Считать очередной символ K из кодируемого сообщения.
   
3. 
   Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для w, иначе Конец
   

2. 
   Применение.
   

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

Алгоритм был реализован в программе compress, которая стала более-менее стандартной утилитой Unix-систем приблизительно в 1986 году. Несколько других популярных утилит-архиваторов также используют этот метод или близкие к нему.

В 1987 году алгоритм стал частью стандарта на формат изображений GIF. Он также может (опционально) использоваться в формате TIFF.

В настоящее время, реализация алгоритма содержится в программе Adobe Acrobat.

3. 
   Пример.
   

Данный пример показывает алгоритм LZW в действии, показывая состояние выходных данных и словаря на каждой стадии, как при кодировании, так и при раскодировании сообщения. С тем чтобы сделать изложение проще, мы ограничимся простым алфавитом — только заглавные буквы, без знаков препинания и пробелов. Сообщение, которое нужно сжать, выглядит следующим образом:

A = 00001

B = 00010

C = 00011

.

.

.

(на выходе)

O 15 = 01111 28: TO

B 2 = 00010 29: OB

E 5 = 00101 30: BE

O 15 = 01111 31: EO

R 18 = 010010 32: OR

N 14 = 001110 33: RN

O 15 = 001111 34: NO

T 20 = 010100 35: OT

TO 28 = 011100 36: TT

BE 30 = 011110 37: TOB

OR 32 = 100000 38: BEO

TOB 37 = 100101 39: ORT

EO 31 = 011111 40: TOBE

RN 33 = 100001 41: EOR

OT 35 = 100011 42: RNO

# 0 = 000000 43: OT#
Общая длина = 5*5 + 12*6 = 97 бит.
Таким образом, используя LZW мы сократили сообщение на 28 бит из 125 — это почти 22%. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно.
2.2.5 Декодирование.
Теперь представим что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей.
Данные: На выходе: Новая запись:

Полная: Частичная:

10100 = 20 T 28: T?

01111 = 15 O 28: TO 29: O?

00010 = 2 B 29: OB 30: B?

00101 = 5 E 30: BE 31: E?

01111 = 15 O 31: EO 32: O?

010010 = 18 R 32: OR 33: R?

001110 = 14 N 33: RN 34: N?

001111 = 15 O 34: NO 35: O?

010100 = 20 T 35: OT 36: T?

011100 = 28 TO 36: TT 37: TO?

011110 = 30 BE 37: TOB 38: BE? следующего слова словаря

100000 = 32 OR 38: BEO 39: OR?

100101 = 37 TOB 39: ORT 40: TOB?

011111 = 31 EO 40: TOBE 41: EO?

100001 = 33 RN 41: EOR 42: RN?

100011 = 35 OT 42: RNO 43: OT?

000000 = 0 #
Единственная небольшая трудность может возникнуть, если новое слово словаря пересылается немедленно. В приведённом выше примере декодирования, когда декодер встречает первый символ, T, он знает, что слово 28 начинается с T, но чем оно заканчивается? Проиллюстрируем проблему следующим примером.

Мы декодируем сообщение ABABA:

Полная: Частичная:

.

.

.

101111 = 47 AB?
На первый взгляд, для декодера это неразрешимая ситуация. Мы знаем наперёд, что словом 47 должно быть ABA, но как декодер узнает об этом? Заметим, что слово 47 состоит из слова 29 плюс символ идущий следующим. Таким образом, слово 47 заканчивается на «символ идущий следующим». Но, поскольку это слово посылается немедленно, то оно должно начинаться с «символа идущего следующим», и поэтому оно заканчивается тем же символом что и начинается, в данном случае — A. Этот трюк позволяет декодеру определить, что слово 47 это ABA.

В общем случае, такая ситуация появляется, когда кодируется последовательность вида cScSc, где c — это один символ, а S — строка, причём слово cS уже есть в словаре.