Словарь

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

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

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

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

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

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

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

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

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

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