Сортировка

Алгоритм сортировки разделением множеств

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

Сортировка, используемая в BWT

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

Основные требования к сортировке заключаются в том, что она ...

Способы сжатия преобразованных с помощью BWT данных

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

Рассмотрим фрагмент данных, типичный для текста, преобразованного посредством BWT. Для примера взят файл bookl из набора "Calgary Corpus" (рис. 5.19).

eteksehendeynkrtdserttnregenskngsgsedeneyswmessrne xgynystslgyegsgstssrhmsstetehselxtptneessthndesddy htksthwtpfdttegedmmhysyresprssneenselgetdemsetse,t reehsetrtteseeeeeesssdeedmnlendeedgtdgttdsgtteeysy tddentnrxsltshtghnteeernsdpwlttensedehsteeswekheee ...