для чего нужно сжатие данных

Сжатие информации

Сжатие информации

Сжатие информации, компрессия, Шаблон:Англ. data compression — алгоритмическое преобразование данных (кодирование), при котором за счет уменьшения их избыточности уменьшается их обьём.

Содержание

Принципы сжатия информации

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

Любой метод сжатия информации включает в себя два преобразования обратных друг другу:

Преобразование сжатия обеспечивает получение сжатого сообщения из исходного. Разжатие же обеспечивает получение исходного сообщения (или его приближения) из сжатого.

Все методы сжатия делятся на два основных класса

Кардинальное различие между ними в том, что сжатие без потерь обеспечивает возможность точного восстановления исходного сообщения. Сжатие с потерями же позволяет получить только некоторое приближение исходного сообщения, то есть отличающееся от исходного, но в пределах некоторых заранее определённых погрешностей. Эти погрешности должны определяться другой моделью — моделью приёмника, определяющей, какие данные и с какой точностью представленные важны для получателя, а какие допустимо выбросить.

Характеристики алгоритмов сжатия и применимость

Коэффициент сжатия

Коэффициент сжатия — основная характеристика алгоритма сжатия, выражающая основное прикладное качество. Она определяется как отношение размера несжатых данных к сжатым, то есть:

где k — коэффициент сжатия, S_o — размер несжатых данных, а S_c — размер сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм лучше. Следует отметить:

Коэффициент сжатия может быть как постоянным коэффициентом (некоторые алгоритмы сжатия звука, изображения и т. п., например А-закон, μ-закон, ADPCM), так и переменным. Во втором случае он может быть определён либо для какого либо конкретного сообщения, либо оценён по некоторым критериям:

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

Допустимость потерь

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

Однако сжатие с потерями позволяет добиться гораздо больших коэффициентов сжатия за счёт отбрасывания незначащей информации, которая плохо сжимается. Так, например алгоритм сжатия звука без потерь FLAC, позволяет в большинстве случаев сжать звук в 1,5—2,5 раза, в то время как алгоритм с потерями Vorbis, в зависимости от установленного параметра качетсва может сжать до 15 раз с сохранением приемлемого качества звучания.

Системные требования алгоритмов

Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых исполняются:

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

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

Алгоритм сжатия гораздо требовательнее к ресурсам, нежели алгоритм расжатия. Это наиболее распространённое соотношение, и оно применимо в основном в случаях, когда однократно сжатые данные будут использоваться многократно. В качетсве примера можно привести цифровые аудио и видеопроигрыватели. Алгоритмы сжатия и расжатия имеют примерно равные требования. Наиболее приемлемый вариант для линии связи, когда сжатие и расжатие происходит однократно на двух её концах. Например, это могут быть телефония. Алгоритм сжатия существенно менее требователен, чем алгоритм разжатия. Довольно экзотический случай. Может применяться в случаях, когда передатчиком является ультрапортативное устройство, где объём доступных ресурсов весьма критичен, например, космический аппарат или большая распределённая сеть датчиков, или это могут быть данные распаковка которых требуется в очень малом проценте случаев, например запись камер видеонаблюдения.

Источник

Блог Евгения Крыжановского

Я научу вас ремонтировать свой компьютер!

Процесс сжатия информации с целью уменьшения ее объема

Многих пользователей сегодня волнует процесс сжатия информации для экономии свободного пространства на жестком диске. Этот один из наиболее эффективных способов использования полезного места на накопителе.

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

Зачем сжимать информацию?

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

Когда необходимо сжатие данных?

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

1. Передача по электронной почте.

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

2. Публикация данных на интернет-сайтах и порталах.

3. Экономия свободного места на диске.

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

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

Способы сжатия информации

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

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

Сжатие с потерями информации

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

Сжатие без потери информации

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

Универсальные методы

Существуют также особые методы, при помощи которых можно сжимать информацию, хранящуюся на жестких дисках, для уменьшения ее объема. Это так называемые универсальные методы. Всего можно выделить три технологии.

1. Преобразование потока.

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

2. Статистическое сжатие.

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

3. Преобразование блока.

В процессе сжатия вся преобразовываемая информация распределяется на несколько отдельных блоков. Происходит целостное трансформирование информации.

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

Сжатие информации при копировании

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

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

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

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

Заключение

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

Запись опубликована 09.07.2015 автором katrinas11 в рубрике Моя жизнь. Отблагодари меня, поделись ссылкой с друзьями в социальных сетях:

Источник

Сжатие информации без потерь. Часть вторая

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

Итак, начнем с арифметического кодирования — на мой взгляд, одного из самых изящных (с точки зрения идеи) методов сжатия.

Введение

Как можно заметить, в случаях, когда относительные частоты не являются степенями двойки, алгоритм явно теряет в эффективности. Это легко проверить на простом примере потока из двух символов a и b с частотами 253/256 и 3/256 соответственно. В этом случае в идеале нам понадобится , то есть 24 бита. В то же время, метод Хаффмана закодирует эти символы кодами 0 и 1 соответственно, и сообщение займет 256 бит, что, конечно, меньше 256 байт исходного сообщения (напомню, мы предполагаем, что изначально каждый символ имеет размер в байт), но все же в 10 раз меньше оптимума.

Итак, перейдем к рассмотрению арифметического кодирования, которое позволит нам получить лучший результат.

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

Как и метод Хаффмана, арифметическое кодирование является методом энтропийного сжатия. Кодируемые данные представляются в виде дроби, которая подбирается так, чтобы текст можно было представить наиболее компактно. Что же это значит на самом деле?

Рассмотрим построение дроби на интервале [0,1) (такой интервал выбран для удобства подсчета), и на примере входных данных в виде слова «короб». Нашей задачей будет разбить исходный интервал на субинтервалы с длинами, равными вероятностям появления символов.

Составим таблицу вероятностей для нашего входного текста:

Здесь под «Частотой» подразумевается количество вхождений символа во входном потоке.

Будем считать, что данные величины известны как при кодировании, так и при декодировании. При кодировании первого символа последовательности (в нашем случае — «Короб»), используется весь диапазон от 0 до 1. Этот диапазон необходимо разбить на отрезки в соответствии с таблицей.
В качестве рабочего интервала берется интервал, соответствующий текущему кодируемому символу. Длина этого интервала пропорциональна частоте появления символа в потоке.
После нахождения интервала для текущего символа, этот интервал расширяется, и в свою очередь разбивается в соответствии с частотами, так же как и предыдущие (то есть, для нашего примера, на шаге 2 мы должны разбить интервал от 0.4 до 0.6 на субинтервалы так же, как сделали это на первом шаге). Процесс продолжается до тех пор, пока не будет закодирован последний символ потока.
Иными словами, i-му символу будет ставиться в соответствие интервал

где N — количество символов алфавита, p_i — вероятность i-го символа.

В нашем случае это выглядит так

Итак, мы последовательно сужали интервал для каждого символа входного потока, пока не получили на последнем символе интервал от 0.45312 до 0.4544. Именно его мы и будем использовать при кодировании.

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

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

Как же происходит декодирование? Декодирование происходит аналогичным образом (не в обратном порядке, а именно аналогичным образом).

Мы начинаем с интервала от 0 до 1, разбитого в соответствии с частотами символов. Мы проверяем, в какой из интервалов попадает наше число (0,454). Символ, соответствующий этому интервалу и будет первым символом последовательности. Далее, мы расширяем этот интервал на всю шкалу, и повторяем процедуру.

Для нашего случая процесс будет выглядеть так:

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

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

Рассмотрем предложенную в начале статьи последовательность символов a и b с вероятностями 253/256 и 3/256. Длина последнего рабочего интервала для цепочки из 256 символов будет равна

В таком случае, искомое N будет равно 24 (23 дает слишком большой интервал, а 25 не будет являться минимальным), то есть мы потратим на кодирование всего 24 бита, против 256 бит метода Хаффмана.

Преобразование Барроуза — Уилера

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

Да, это возможно. Для иллюстрации, рассмотрим преобразование Барроуза Уилера, которое превращает блок данных со сложными зависимостями в блок, структура которого легче моделируется. Еслественно, это преобразование также полностью обратимо. Авторами метода являются Девид Уилер (David Wheeler) и Майк Барроуз (Michael Burrows, если верить вики, сейчас он работает в Google).

Итак, алгоритм Барроуза-Уилера (в дальнейшем для краткости я буду называть его BTW — Burrows-Wheeler Transform) преобразовывает входной блок в более удобный для сжатия вид. Однако, как показывает практика, полученный в результате преобразования блок обычные методы сжимают не так успешно, как специально для этого разработанные, поэтому для практического применения нельзя рассматривать алгоритм BWT отдельно от соответствующих методов кодирования данных, но поскольку наша цель — изучить принцип его работы, то ничего страшного в этом нет.

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

Алгоритм преобразования

BWT является блочным алгоритмом, то есть он оперирует блоками данных, и заранее знает о составе элементов блока определенного размера. Это делает затруднительным использование BWT в тех случаях, когда необходимо посимвольное сжатие, или сжатие «на лету». В принципе, такая реализация возможна, но алгоритм получится… не очень быстрым.

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

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

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

В общем-то на этом преобразование почти закончено: все что осталось сделать — это записать последний столбец, не забыв при этом запомнить номер исходной строки. Сделав это, мы получим:

Как видим, распределение символов стало значительно лучше: теперь 4 из 5 символов «а» стоят рядом, как и оба символа «б».

Обратимость

Как я уже упоминал, преобразование полностью обратимо. Это и понятно, ведь иначе в нем не было бы никакого смысла. Так как же восстановить первоначальный вид сообщения?

Сперва нам необходимо отсортировать наши символы по порядку. Это даст нам строку «аааааббдкрр». Поскольку наша матрица циклических перестановок была отсортирована по порядку, то эта последовательность букв — ни что иное, как первый столбец нашей матрицы циклических перестановок. Кроме этого, нам известен и последний столбец (собственно, сам результат преобразования). Итак, на данном этапе мы можем восстановить матрицу до примерно такого состояния:

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

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

Для нашего примера первые четыре шага восстановления будут выглядеть так:

Затраты ресурсов при работе

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

Для обратного преобразования нам дополнительно к собственно данным необходим вектор обратного преобразования – массив чисел, размер которого равен числу символов в блоке. Таким образом, затраты памяти при линейном преобразовании растут линейно с размером блока.

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

Вектор преобразования формируется из значений номеров строк: <2,5,6,7,8,9,10,1,3,0,4>.

Теперь можно легко получить исходную строку. Возьмем элемент вектора обратного преобразования, который соответствует номеру исходной строки в матрице: T[2]=6. Иначе говоря, в качестве первого символа исходной строки необходимо взять шестой символ строки «рдакраааабб» — символ «а».
После этого мы смотрим, какой символ переместил найденный символ «а» на вторую позицию среди одинаковых с ним. Для этого мы берем номер из вектора преобразования строки, из которой был взят символ «а»: это номер 6.
Затем смотрим строку, имеющую номер 6 и выбираем оттуда последний символ – это символ «б». Продолжая эту процедуру для оставшихся символов, мы легко восстановим исходную строку.

Перемещение стопки книг

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

Рассмотрим строку «рдакраааабб», полученную нами по BWT в предыдущей части. В данном случае, наш алфавит состоит из 5 символов. Упорядочив их, получим
M=<а, б, д, к, р>.

Итак, используем на нашей строке алгоритм перемещения стопки книг. Первый символ строки («р») стоит в алфавите на 4 месте. Это число (4) мы записываем в выходной блок. Затем мы помещаем только что использованный символ на первое место, и повторяем процесс со вторым символом, затем с третьим и так далее. Процесс обработки будет выглядеть так (под «номером» я предполагаю то число, которое пойдет в выходной поток):

Результатом будет последовательность

На этом этапе не совсем понятно, какой прок от этого алгоритма. На самом деле, прок есть. Рассмотрим более абстрактную последовательность:

Для начала просто закодируем ее по методу Хаффмана. Для наглядности предположим, что расходы на хранения дерева при использовании перемещения стопки книг, и без оного совпадают.
Вероятности появления всех четырех символов в нашем случае равны ¼, то есть кодирование каждого символа требует 2 бит. Легко подсчитать, что кодированная строка займет 40 бит.
Теперь проведем изменение строки алгоритмом перемещения стопки книг. В начале алфавит имеет вид

После использования алгоритма строка будет иметь вид

В этом случае частоты появления символов сильно изменятся:

В этом случае после кодирования мы получим последовательность в 15+6+3+3=27 бит, что намного меньше чем 40 бит, которые получаются без перемещения стопки книг.

Заключение

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

Источник