Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Топ:
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Дисциплины:
2023-01-02 | 27 |
5.00
из
|
Заказать работу |
|
|
Преобразование Шиндлера (список Шиндлера)
Следует отметить еще одно преобразование, основанное на сортировке блока данных - преобразование Шиндлера (ST) [5]. Отличие от BWT заключается в том, что строки матрицы перестановок упорядочиваются не по всей длине, а только по указанному количеству первых символов. Число таких символов называется порядком преобразования Шиндлера. В случае, если эти символы одинаковы у двух или более строк, они упорядочиваются в соответствии с номером позиции, в которой эти строки встречаются в исходной последовательности.
Distance Coding (кодирование расстояний).
Стоит упоминания метод, который все чаще используется как альтернатива MTF. По крайней мере, на большинстве файлов архиваторы, его использующие, имеют преимущество по сравнению с работающими в традиционной манере. Пока описание этого метода нигде официально не опубликовано, подробно он разобран в статье В. Юкина “Преобразования Барроуза-Уилера или алгоритм сжатия без потерь при помощи сортировки блока данных” (см. www. compression. ru). Используют его всего три архиватора - DC, YBS и SBC.
Рассмотрим кодирование строки "рдакраааабб" из прошлого примера. Первый шаг заключается в том, чтобы определить первое вхождение каждого символа. Для этого к началу строки мы по очереди приписываем все символы алфавита (при декодировании мы можем проделать тоже самое). А также воспользуемся символом конца строки, означающим окончание кодирования определенного символа. Обозначим его как '%'. Получается "абдкррдакраааабб%".
Находим число - расстояние от первого символа этой последовательности, 'а' до следующего такого же. Оно равно 6 - это число других символов между ними. Но нам заранее известно, что после 'а' идут символы 'б','д','к' и 'р'. А поскольку наша задача выяснить номер позиции, в которой потенциально может оказаться символ 'а' при декодировании, эти символы мы можем не считать. Таким образом, получаем число 2.
|
Аналогично кодируем еще несколько символов по очереди, подсчитывая число точек, символизирующих незанятые позиции, в строке известных символов.
а б д к р | рдакраааабб | |
а б д к р | .. а........ | 2 |
а б д к р | .. а...... б. | 28 |
а б | . да...... б. | 281- |
а б | . дак..... б. | 281-1- |
а б | рдак..... б. | 281-1-0 |
а б | рдак. а... б. | 281-1-01 |
а | рдак. а... бб | 281-1-014- |
а | рдакра... бб | 281-1-014-0- |
рдакраааабб | 281-1-014-0-000- |
Run Length Encoding (RLE).
Как видно из названия, суть этого кодирования - в замене части последовательности одинаковых символов на число, показывающее количество замененных символов.
Например, мы можем включать RLE в случае, когда количество одинаковых символов превышает 4. Тогда строка "abbbbbbbbccddddd" будет записана в виде "abbbb4ccddddl".
RLE может пригодиться тогда, когда в данных есть длинные повторы одинаковых символов. Такие повторы могут возникнуть в двух случаях - в исходных данных и после преобразования Барроуза-Уилера. В первом случае, особенно если повторов особенно много, RLE нам может заметно помочь ускорить сортировку матрицы перестановок ценой небольшого ухудшения сжатия. Аналогично, тот же эффект может иметь применение RLE и во втором случае. Правда, как было показано в предыдущем параграфе, использование DC делает RLE ненужным.
1-2 coding (OTC).
Альтернатива метода Хаффмена на третьем этапе. Это один из широко используемых способов кодирования длинных повторов. Обычно он применяется после MTF. Этот метод нашел свое применение в Bzip2, Imp.
Как известно, после MTF-преобразования мы получаем последовательность, в которой при удачном раскладе присутствует большое количество нулей, соответствующих нулевому рангу MTF.
Если кодировать каждый код MTF-0, то во-первых, это накладно по времени и, во-вторых, может заметно ухудшить сжатие из-за погрешностей статистического кодера.
|
Элегантный выход был найден в отведении под MTF-0 не одного, а двух символов (назовем их zl и z2). Таким образом, у нас в MTF-алфавите получилось не 256, а 257 символов. Эти zl и z2 можно использовать для кодирования числа идущих подряд MTF-0:
1 - zl
2 - z2
3 - zlzl
4 - zlz2
5 - z2zl
6 - z2z2
7 - zlzlzl
8 - zlzlz2
9 - zlz2zl
10 - zlz2z2
11 - z2zlzl
Как вы помните, наша строка "абракадабра" после двух преобразований выглядела как {4,3,2,4,3,2,0,0,0,4,0}. Подвергнем ее еще одному - и получим {4,3,2,4,3,2,zl,zl,4,zl}.
Структурная модель.
Было замечено, что данные, полученные после преобразования Барроуза-Уилера, состоят из так называемых "хороших фрагментов" (которые соответствуют часто встречаемым сочетаниям символов), разделенных "плохими фрагментами". Одна из главных задач при сжатии заключается в своевременном обнаружении границ фрагментов. То есть, в быстрой адаптации к смене фрагмента одного типа другим.
Еще одно наблюдение связано со статистикой MTF-рангов, полученных на типичных данных. Как уже упоминалось, для большинства текстов количество нулей превышает половину всех значений. Количество остальных рангов в среднем убывает по мере увеличения ранга и, соответственно, увеличивается погрешность при появлении конкретного значения и сглаживается разница между соседними рангами. Кроме того, появление нескольких больших рангов подряд в файле, подвергнутом BWT и MTF, может служить признаком "плохого фрагмента".
Одна из довольно эффективных моделей, призванных воспользоваться этой информацией, была описана Петером Фенвиком. Все MTF-ранги были поделены на группы:
MTF-ранги | Номер группы |
0 | 0 |
1 | 1 |
2-3 | 2 |
4-7 | 3 |
8-15 | 4 |
16-31 | 5 |
32-63 | 6 |
64-255 | 7 |
При обработке очередного ранга первым делом кодируется номер группы, а затем, в случае необходимости - номер ранга внутри группы.
Описанная модель получила довольно широкое распространение и используется в ряде современных архиваторах.
|
|
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!