Цель урока: развивать внимательность, сообразительность, воспитывать интерес к предмету.
Оборудование: компьютеры, лабораторные диски, соответствующее программное обеспечение, карты с тестовым заданием.

Ход урока

1. Организационная часть.
2. Актуализация опорных знаний.
3. Изучение нового материала
4. Закрепление нового материала.
5. Домашнее задание.
6. Подведение итогов урока.

Изучение нового материала

1. Что такое архивирование. Понятие о сжатии данных.
2. Основные виды программ-архиваторов.
3. Программа-архиватор WIN-RAR.
4. Как добавлять файл в архив, а также извлекать его из архива.

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

Архивация данных - это слияние нескольких файлов или каталогов в единый файл-архив.

Сжатие данных - сокращение объема исходных файлов путем устранения избыточной информации.

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

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

Архивирование файлов. Задачи

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

3. Архивация при шифровании данных с целью уменьшения вероятности взлома криптосистемы.

Процесс записи информации в архивный файл называется - архивирование.
Извлечение файлов из архива - разархивирование.

Первые программы-архиваторы появились в середине 80-х годов. Они были ориентированы на работу в MS-DOC и поддерживали популярные архивные форматы: ARC, ICE, ARJ, ZIP и RAR и др. Существовала также группа архиваторов, которые упаковывали данные в самораспаковывающиеся архивы - файлы с расширениями. eхе,. cоm. Для сжатия всего диска были созданы резидент архиваторы. Они позволяли поднять эффективность использования дискового пространства путем создания крупных архивных файлов - «сжатий» дисков.

Значительно более удобной стала работа с архивами при появлении Windows и Windows-версий архиваторов. Из бывших архивных форматов среди пользователей Windows по-настоящему прижились ARJ, ZIP - программы которые распаковывают файлы. Большие по объему архивные файлы могут быть размещены на нескольких дискетах (томах). Такие архивы называются многотомными.

Том - это составная часть многотомного архива.

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

Помещение файлов в архив: Пуск Программы WINRAR или в виде ярлыка на Рабочем столе.

Универсальный архиватор WINRAR

Архиватор WINRAR также предназначен для архивирования файлов. Он имеет удобную графическую оболочку и поддерживает технологию Drag and Drop. Программа WINRAR позволяет работать не только с архивными файлами rar, но и с другими архивными форматами: zip, cab, arj, lzh. Запускается WINRAR любым из возможных способов, предусмотренных в Windows. Запуск программы с помощью Главного меню кнопки Пуск Программы WINRAR WINRAR или с помощью ярлыка на Рабочем столе.

Тестовый опрос по основам работы с дисками.
Домашнее задание.
Самоанализ урока.

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

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

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

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

Необратимое сжатие имеет обычно гораздо более высокую степень сжатия, чем кодирование без потерь, но допускает некоторые отклонения декодированных данных от исходных. На практике существует широкий круг практических задач, в которых соблюдение требования точного восстановления исходной информации после декомпрессии не является обязательным. Это, в частности, относится к сжатию мультимедийной информации: звука, фото- или видеоизображений. Так, например, широко применяются форматы мультимедийной информации JPEG и MPEG , в которых используется необратимое сжатие. Необратимое сжатие обычно не используется совместно с криптографическим шифрованием, так как основным требованием к криптосистеме является идентичность расшифрованных данных исходным. Однако при использовании мультимедиа-технологий данные, представленные в цифровом виде, часто подвергаются необратимой компрессии перед подачей в криптографическую систему для шифрования. После передачи информации потребителю и расшифрования мультимедиа-файлы используются в сжатом виде (то есть не восстанавливаются).

Рассмотрим подробнее некоторые из наиболее распространённых способов обратимого сжатия данных.

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

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

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

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

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

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

p(S 1)=0,2, p(S 2)=0,15, p(S 3)=0,55, p(S 4)=0,1 . Отсортируем символы по убыванию вероятности появления и представим в виде таблицы ( рис. 14.3 , а).

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

Рис. 14.3.

На втором этапе осуществляется построение кодового дерева по свернутой таблице ( рис. 14.4 , а). Дерево строится, начиная с последнего столбца таблицы.

Корень дерева образует единица , расположенная в последнем столбце. В рассматриваемом примере эта единица образуется из вероятностей 0,55 и 0,45 , изображаемых в виде двух узлов дерева, связанных с корнем. Первый из них соответствует символу S 3 и, таким образом, дальнейшее ветвление этого узла не происходит.

Второй узел, маркированный вероятностью 0,45 , соединяется с двумя узлами третьего уровня, с вероятностями 0,25 и 0,2 . Вероятность 0,2 соответствует символу S 1 , а вероятность 0,25 , в свою очередь , образуется из вероятностей 0,15 появления символа S 2 и 0,1 появления символа S 4 .

Ребра, соединяющие отдельные узлы кодового дерева, нумеруются цифрами 0 и 1 (например, левые ребра – 0 , а правые – 1 ). На третьем, заключительном этапе, строится таблица , в которой сопоставляются символы источника и соответствующие им кодовые слова кода Хаффмана. Эти кодовые слова образуются в результате считывания цифр, которыми помечены ребра, образующие путь от корня дерева к соответствующему символу. Для рассматриваемого примера код Хаффмана примет вид, показанный в таблице справа ( рис. 14.4 , б).

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

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

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

Методы Хаффмана дают достаточно высокую скорость и умеренно хорошее качество сжатия. Однако кодирование Хаффмана имеет минимальную избыточность при условии, что каждый символ кодируется в алфавите кода символа отдельной цепочкой из двух бит – {0, 1} . Основным же недостатком данного метода является зависимость степени сжатия от близости вероятностей символов к 2 в некоторой отрицательной степени, что связано с тем, что каждый символ кодируется целым числом бит .

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

Предполагаемая требуемая последовательность символов при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала = InMsg[ 2 ] ) ;

1. type
2. TRLEEncodedString = array of byte ;
3. function RLEDecode(InMsg: TRLEEncodedString) : ShortString;
4. RepeatCount: shortint ;
5. i, j: word ;
6. OutMsg: ShortString;
7. begin
8. OutMsg : = "" ;
9. i : = 0 ;
10. while i < length(InMsg) do
11. begin
12. RepeatCount : = InMsg[ i] - 128 ;
13. i : = i + 1 ;
14. if RepeatCount < 0 then
15. begin
16. RepeatCount : = abs (RepeatCount) ;
17. for j : = i to i + RepeatCount - 1 do
18. OutMsg : = OutMsg + chr (InMsg[ j] ) ;
19. i : = i + RepeatCount;
20. else
21. begin
22. for j : = 1 to RepeatCount do
23. OutMsg : = OutMsg + chr (InMsg[ i] ) ;
24. i : = i + 1 ;
25. end ;
26. end ;
27. RLEDecode : = OutMsg;
28. end ;

1. const
2. EOMsg = "|" ;
3. function BWTEncode(InMsg: ShortString) : ShortString;
4. OutMsg: ShortString;
5. LastChar: ANSIChar;
6. N, i: word ;
7. begin
8. InMsg : = InMsg + EOMsg;
9. N : = length(InMsg) ;
10. ShiftTable[ 1 ] : = InMsg;
11. for i : = 2 to N do
12. begin
13. LastChar : = InMsg[ N] ;
14. InMsg : = LastChar + copy(InMsg, 1 , N - 1 ) ;
15. ShiftTable[ i] : = InMsg;
16. end ;
17. Sort(ShiftTable) ;
18. OutMsg : = "" ;
19. for i : = 1 to N do
20. OutMsg : = OutMsg + ShiftTable[ i] [ N] ;
21. BWTEncode : = OutMsg;
22. end ;

Т.е. результатом прямого преобразования будет строка «|ННАААС». Легко заметить, что это строка гораздо лучше, чем исходная, сжимается алгоритмом RLE, т.к. в ней существуют длинные подпоследовательности повторяющихся букв.
Подобного эффекта можно добиться и с помощью других преобразований, но преимущество BWT-преобразования в том, что оно обратимо, правда, обратное преобразование сложнее прямого. Для того, чтобы восстановить исходную строку, необходимо выполнить следующие действия:
Создать пустую матрицу размером n*n, где n-количество символов в закодированном сообщении;
Заполнить самый правый пустой столбец закодированным сообщением;
Отсортировать строки таблицы в лексикографическом порядке;
Повторять шаги 2-3, пока есть пустые столбцы;
Вернуть ту строку, которая заканчивается символом конца строки.

Реализация обратного преобразования на первый взгляд не представляет сложности, и один из вариантов реализации приведён в Листинг 4.

1. const
2. EOMsg = "|" ;
3. function BWTDecode(InMsg: ShortString) : ShortString;
4. OutMsg: ShortString;
5. ShiftTable: array of ShortString;
6. N, i, j: word ;
7. begin
8. OutMsg : = "" ;
9. N : = length(InMsg) ;
10. SetLength(ShiftTable, N + 1 ) ;
11. for i : = 0 to N do
12. ShiftTable[ i] : = "" ;
13. for i : = 1 to N do
14. begin
15. for j : = 1 to N do
16. ShiftTable[ j] : = InMsg[ j] + ShiftTable[ j] ;
17. Sort(ShiftTable) ;
18. end ;
19. for i : = 1 to N do
20. if ShiftTable[ i] [ N] = EOMsg then
21. OutMsg : = ShiftTable[ i] ;
22. delete(OutMsg, N, 1 ) ;
23. BWTDecode : = OutMsg;
24. end ;

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

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

Словарное сжатие (алгоритмы LZ)

Ниже описан простейший вариант словарного алгоритма:
Инициализировать словарь всеми символами, встречающимися во входной строке;
Найти в словаре самую длинную последовательность (S), совпадающую с началом кодируемого сообщения;
Выдать код найденной последовательности и удалить её из начала кодируемого сообщения;
Если не достигнут конец сообщения, считать очередной символ и добавить Sc в словарь, перейти к шагу 2. Иначе, выход.

Например, только что инициализированный словарь для фразы «КУКУШКАКУКУШОНКУКУПИЛАКАПЮШОН» приведён в Табл. 3:

В процессе сжатия словарь будет дополняться встречающимися в сообщении последовательностями. Процесс пополнения словаря приведён в Табл. 4.

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

Для начала определим словарь как запись, хранящую не только встречавшиеся подстроки, но и количество хранящихся в словаре подстрок:

Встречавшиеся ранее подпоследовательности хранятся в массиве Words, а их кодом являются номера подпоследовательностей в этом массиве.
Также определим функции поиска в словаре и добавления в словарь:

1. const
2. MAX_DICT_LENGTH = 256 ;
3. function FindInDict(D: TDictionary; str: ShortString) : integer ;
4. r: integer ;
5. i: integer ;
6. fl: boolean ;
7. begin
8. r : = - 1 ;
9. if D. WordCount > 0 then
10. begin
11. i : = D. WordCount ;
12. fl : = false ;
13. while (not fl) and (i >= 0 ) do
14. begin
15. i : = i - 1 ;
16. fl : = D. Words [ i] = str;
17. end ;
18. end ;
19. if fl then
20. r : = i;
21. FindInDict : = r;
22. end ;
23. procedure AddToDict(var D: TDictionary; str: ShortString) ;
24. begin
25. if D. WordCount < MAX_DICT_LENGTH then
26. begin
27. D. WordCount : = D. WordCount + 1 ;
28. SetLength(D. Words , D. WordCount ) ;
29. D. Words [ D. WordCount - 1 ] : = str;
30. end ;
31. end ;

1. function LZWEncode(InMsg: ShortString) : TEncodedString;
2. OutMsg: TEncodedString;
3. tmpstr: ShortString;
4. D: TDictionary;
5. i, N: byte ;
6. begin
7. SetLength(OutMsg, length(InMsg) ) ;
8. N : = 0 ;
9. InitDict(D) ;
10. while length(InMsg) > 0 do
11. begin
12. tmpstr : = InMsg[ 1 ] ;
13. while (FindInDict(D, tmpstr) >= 0 ) and (length(InMsg) > length(tmpstr) ) do
14. tmpstr : = tmpstr + InMsg[ length(tmpstr) + 1 ] ;
15. if FindInDict(D, tmpstr) < 0 then
16. delete(tmpstr, length(tmpstr) , 1 ) ;
17. OutMsg[ N] : = FindInDict(D, tmpstr) ;
18. N : = N + 1 ;
19. delete(InMsg, 1 , length(tmpstr) ) ;
20. if length(InMsg) > 0 then
21. AddToDict(D, tmpstr + InMsg[ 1 ] ) ;
22. end ;
23. SetLength(OutMsg, N) ;
24. LZWEncode : = OutMsg;
25. end ;

Единственная проблема возможна в следующей ситуации: когда необходимо декодировать подпоследовательность, которой ещё нет в словаре. Легко убедиться, что это возможно только в случае, когда необходимо извлечь подстроку, которая должна быть добавлена на текущем шаге. А это значит, что подстрока удовлетворяет шаблону cSc, т.е. начинается и заканчивается одним и тем же символом. При этом cS – это подстрока, добавленная на предыдущем шаге. Рассмотренная ситуация – единственная, когда необходимо декодировать ещё не добавленную строку. Учитывая вышесказанное, можно предложить следующий вариант декодирования сжатой строки:

1. function LZWDecode(InMsg: TEncodedString) : ShortString;
2. D: TDictionary;
3. OutMsg, tmpstr: ShortString;
4. i: byte ;
5. begin
6. OutMsg : = "" ;
7. tmpstr : = "" ;
8. InitDict(D) ;
9. for i : = 0 to length(InMsg) - 1 do
10. begin
11. if InMsg[ i] >= D. WordCount then
12. tmpstr : = D. Words [ InMsg[ i - 1 ] ] + D. Words [ InMsg[ i - 1 ] ] [ 1 ]
13. else
14. tmpstr : = D. Words [ InMsg[ i] ] ;
15. OutMsg : = OutMsg + tmpstr;
16. if i > 0 then
17. AddToDict(D, D. Words [ InMsg[ i - 1 ] ] + tmpstr[ 1 ] ) ;
18. end ;
19. LZWDecode : = OutMsg;
20. end ;

Энтропийное кодирование

Кодирование с помощью деревьев Шеннона-Фано

Без использования кодирования сообщение будет занимать 40 бит (при условии, что каждый символ кодируется 4 битами), а с использованием алгоритма Шеннона-Фано 4*2+2+4+4+3+3+3=27 бит. Объём сообщения уменьшился на 32.5%, но ниже будет показано, что этот результат можно значительно улучшить.

Кодирование с помощью деревьев Хаффмана

Рассмотрим тот же пример, что и в случае с алгоритмом Шеннона-Фано. Дерево Хаффмана и коды, полученные для сообщения «ААААБВГДЕЖ», представлены на Рис. 2:

Легко подсчитать, что объём закодированного сообщения составит 26 бит, что меньше, чем в алгоритме Шеннона-Фано. Отдельно стоит отметить, что ввиду популярности алгоритма Хаффмана на данный момент существует множество вариантов кодирования Хаффмана, в том числе и адаптивное кодирование, которое не требует передачи частот символов.
Среди недостатков алгоритма Хаффмана значительную часть составляют проблемы, связанные со сложностью реализации. Использование для хранения частот символов вещественных переменных сопряжено с потерей точности, поэтому на практике часто используют целочисленные переменные, но, т.к. вес родительских узлов постоянно растёт, рано или поздно возникает переполнение. Т.о., несмотря на простоту алгоритма, его корректная реализация до сих пор может вызывать некоторые затруднения, особенно для больших алфавитов.

Кодирование с помощью деревьев секущих функций

Дерево строится так, чтобы каждый узел делил алфавит на максимально близкие части. На Рис. 3 показан пример дерева секущих:

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

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