Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Словарь

1. Почему невыгодно включение длинных фраз в словарь и-графов?

2. Каковы недостатки и преимущества динамического составления словаря и-графов?

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

4. Почему при организации LIPT для записи индекса фраз удобно исполь­зовать только те символы, которые входят в словарь букв?

5. В каких случаях при специальном кодировании символов конца строки выгоднее указывать длину строки не через ...

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

В общем случае, словарные ...

До этого момента считалось, что словарем LZW служит массив из строк переменной длины. Чтобы понять, почему специальное дерево будет являться лучшей структурой для словаря, следует напомнить работу кодера. Он считывает символы и добавляет их в строку I до тех пор, пока I находится в словаре. В некоторый момент строка 1х в словаре не обнаруживается, и тогда строка 1х помещается в словарь. Значит, при добавлении новых строк в словарь поступает всего один новый символ х. Это предложение можно перефразировать еще так: для каждой словарной строки в словаре найдется «родительская» строка, ...

Метод LZ78 (иногда его называют LZ2, см. [Ziv 78]) не использует буфер поиск, упреждающий буфер и скользящее окно. Вместо этого имеется словарь встретившихся ранее строк. В начале этот словарь пуст (или почти пуст), и размер этого словаря ограничен только объемом доступной памяти. На выход кодера поступает последовательность меток, состоящих из двух полей. Первое поле -это указатель на строку в словаре, а второе - код символа. Метка не содержит длины строки, поскольку строка берется из словаря. Каждая метка соответствует последовательности во входном файле, и эта последовательность ...

Эта версия LZ77 была разработана Сторером (Storer) и Сжимански (Szymanski) в 1982 [Storer 82]. Базовый алгоритм был улучшен по трем направлениям: (1) упреждающий буфер сохранялся в циклической очереди, (2) буфер поиска (словарь) хранился в виде дерева двоичного поиска и (3) метки имели два поля, а не три.

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

Основная идея этого метода (его еще часто называют методом LZ1, см. [Ziv 77]) состоит в использовании ранее прочитанной части входного файла в качестве словаря. Кодер создает окно для входного файла и двигает его справа налево в виде строки символов, требующих сжатие. Таким образом, метод основан на скользящем окне. Окно разбивается на две части. Часть слева называется буфером поиска. Она будет служить текущим словарем, и в ней всегда содержатся символы, которые недавно поступили и были закодированы. Правая часть окна называется упреждающим буфером, содержащим ...

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

Можно сказать, что мы пытаемся преобразовать исходную последова­тельность путем ее представления в таком алфавите, что его "буквы" явля­ются фразами словаря, ...