91609

Локально адаптивный алгоритм сжатия

Доклад

Информатика, кибернетика и программирование

Сначала кодируется каждый символ L с использованием локально адаптивного алгоритма для каждого из символов индивидуально. Применяем алгоритм Хафмана или другой аналогичный алгоритм сжатия к элементам R рассматривая каждый элемент в качестве объекта для сжатия. Результатом работы алгоритма будет LI.

Русский

2015-07-21

36.53 KB

0 чел.

Локально адаптивный алгоритм сжатия

Этот алгоритм используется для кодирования (L,I), где L строка длиной N, а I – индекс. Это кодирование содержит в себе несколько этапов.

1. Сначала кодируется каждый символ L с использованием локально адаптивного алгоритма для каждого из символов индивидуально. Определяется вектор целых чисел R[0],…,R[N-1], который представляет собой коды для символов L[0],…,L[N-1]. Инициализируется список символов Y, который содержит в себе каждый символ из алфавита Х только один раз. Для каждого i = 0,…,N-1 устанавливается R[i] равным числу символов, предшествующих символу L[i] из списка Y. Взяв Y = [‘a’,’b’,’c’,’r’] в качестве исходного и L = ‘caraab’, вычисляем вектор R: (2 1 3 1 0 3).

2. Применяем алгоритм Хафмана или другой аналогичный алгоритм сжатия к элементам R, рассматривая каждый элемент в качестве объекта для сжатия. В результате получается код OUT и индекс I.

Рассмотрим процедуру декодирования полученного сжатого текста (OUT,I).

Здесь на основе (OUT,I) необходимо вычислить (L,I). Предполагается, что список Y известен.

  1. Сначала вычисляется вектор R, содержащий N чисел: (2 1 3 1 0 3).
  2. Далее вычисляется строка L, содержащая N символов, что дает значения R[0],…,R[N-1]. Если необходимо, инициализируется список Y, содержащий символы алфавита X (как и при процедуре кодирования). Для каждого i = 0,…,N-1 последовательно устанавливается значение L[i], равное символу в положении R[i] из списка Y (нумеруется, начиная с 0), затем символ сдвигается к началу Y. Результирующая строка L представляет собой последнюю колонку матрицы M. Результатом работы алгоритма будет (L,I). Взяв Y = [‘a’,’b’,’c’,’r’] вычисляем строку L = ‘caraab’.

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

Для того чтобы сжать строку S, сначала сформируем строку S’, которая является объединением S c EOF, новым символом, который не встречается в S. После этого используется стандартный алгоритм к строке S’. Так как EOF отличается от прочих символов в S, суффиксы S’ сортируются в том же порядке, как и вращения S’. Это может быть сделано путем построения дерева суффиксов, которое может быть затем обойдено в лексикографическом порядке для сортировки суффиксов. Для этой цели может быть использован алгоритм формирования дерева суффиксов Мак-Крейгта. Его быстродействие составляет 40% от наиболее быстрой методики в случае работы с текстами. Алгоритм работы с деревом суффиксов требует более четырех слов на каждый исходный символ. Манбер и Майерс предложили простой алгоритм сортировки суффиксов строки. Этот алгоритм требует только двух слов на каждый входной символ. Алгоритм работает сначала с первыми i символами суффикса а за тем, используя положения суффиксов в сортируемом массиве, производит сортировку для первых 2i символов. К сожалению этот алгоритм работает заметно медленнее.

В книге [M.Burrows and D.J.Wheeler. A block-sorting Lossless Data Compression Algorithm. Digital Systems Research Center. SRC report 124. May 10, 1994.] предложен несколько лучший алгоритм сортировки суффиксов. В этом алгоритме сортируются суффиксы строки S, которая содержит N символов S[0,…,N-1].

  1. Пусть k число символов, соответствующих машинному слову. Образуем строку S’ из S путем добавления k символов EOF в строку S. Предполагается, что EOF не встречается в строке S.
  2. Инициализируем массив W из N слов W[0,…,N-1] так, что W[i] содержат символы S’[i,…,i+k-1] упорядоченные таким образом, что целочисленное сравнение слов согласуется с лексикографическим сравнением для k-символьных строк. Упаковка символов в слова имеет два преимущества: это позволяет для двух префиксов сравнить сразу k байт и отбросить многие случаи, описанные ниже.
  3. Инициализируется массив V из N целых чисел. Если элемент V содержит j, он представляет собой суффикс S’, чей первый символ равен S’[j]. Когда выполнение алгоритма завершено, суффикс V[i] будет i-ым суффиксом в лексикографическом порядке.
  4. Инициализируем целочисленный массив V так, что для каждого i = 0,…,N-1 : V[i]=i.
  5. Сортируем элементы V, используя первые два символа каждого суффикса в качестве ключа сортировки. Далее для каждого символа ch из алфавита выполняем шаги 6 и 7. Когда эти итерации завершены, V представляет собой отсортированные суффиксы S и работа алгоритма завершается.
  6. Для каждого символа ch’ в алфавите выполняем сортировку элементов V, начинающихся с ch, за которым следует ch’. В процессе выполнения сортировки сравниваем элементы V путем сопоставления суффиксов, которые они представляют при индексировании массива W. На каждом шаге рекурсии следует отслеживать число символов, которые оказались равными в группе, чтобы не сравнивать их снова. Все суффиксы, начинающиеся с ch, отсортированы в рамках V.
  7. Для каждого элемента V[i], соответствующего суффиксу, начинающемуся с ch (то есть, для которого S[V[i]] = ch), установить W[V[i]] значение с ch в старших битах и i в младших битах. Новое значение W[V[i]] сортируется в те же позиции, что и старые значения.

Данный алгоритм может быть улучшен различными способами. Одним из самоочевидных методов является выбор символа ch на этапе 5, начиная с наименьшего общего символа в S и предшествующий наиболее общему.


 

А также другие работы, которые могут Вас заинтересовать

43206. АНДРЕЙ БИТОВ, ЗАХАР ПРИЛЕПИН, МИХАИЛ ЕЛИЗАРОВ: ХУДОЖЕСТВЕННЫЕ (ЛИТЕРАТУРНЫЕ) ПАРАЛЛЕЛИ 450.5 KB
  Объект нашей дипломной работы – литературный экстремизм всех трёх авторов, находящий выражение как в индивидуальных авторских стилях, так и во взаимодействии поэтических и прозаических элементов, так и в определённой философской системе, выстраиваемой в ходе повествования.
43207. Привод шаровой мельницы 2.03 MB
  Выбираем асинхронный электродвигатель закрытый обдуваемый единой серии АИР мощностью = 15 кВт и синхронной частотой вращения = 3000 об/мин
43208. Проектування привіду до стрічкового конвейєра за схемою та графіком навантаження 1.35 MB
  Закриті зубчасті передачі при коловій швидкості змащуються зануренням їх в мастило, а також за рахунок масляного туману, який утворюється за рахунок великої колової швидкості. Контактне напруження при швидкості дорівнює 475 МПа. За цими даними вибираємо необхідну в’язкість мастила і вибираємо мастило: індустріальне леговане, для зубчастих передач ИРП-150. одноступінчатого редуктора.
43209. Определение основных параметров бульдозера ДЗ-171 на базе трактора Т-170 957.5 KB
  Бульдозеры как навесное оборудование на тракторы, тягачи и другие базовые машины широко распространены, что объясняется простотой их конструкции, высокой производительностью, возможностью их использования в самых разнообразных грунтовых и климатических условиях и относитнльно низкой стоимостью выполненных работ. Применяются они в дорожном, железнодорожном, горнорудном, мелиоративном и ирригационном строительстве. Для большинства современных гусеничных бульдозеров экономически выгодная дальность дальность перемещений в настоящее время не превышает 60-80м, колесных 100-150м.
43210. Проектирование станочного приспособления 1.5 MB
  На основании этой комплексной детали будем разрабатывать и проектировать станочное приспособление. Технические характеристики для САТ630 Наибольший диаметр обрабатываемого изделия мм: над станиной 720 над суппортом 560 Расстояние между центрами мм 1 000 1 500 2 500 Максимальное перемещение суппорта мм: по оси Х 400 по оси Z 1 100 1 600 2 600 по оси Y 55 65 Максимальный вес обрабатываемой детали кг: в патроне 300 в центрах 800 Диаметр отверстия в шпинделе мм 102 166 Пределы частот вращения...
43211. Разработка автоматизированной системы анализа финансового состояния предприятия в условиях неопределенности 1.47 MB
  Основной целью проведения анализа финансового состояния организаций является получение объективной оценки их платежеспособности, финансовой устойчивости, деловой и инвестиционной активности, эффективности деятельности. Для проведения анализа финансового состояния используются следующие группы показателей, характеризующих различные аспекты деятельности организации...
43212. Деталь типа тело вращения – вал-шестерня 2.4 MB
  Изделие – редуктор зубчатый цилиндрический двухступенчатый предназначен для увеличения передаваемого крутящего момента и может быть использован во многих механизмах – лебёдка, станция приводная транспортёров, станция натяжная и др.
43213. Автоматизация листовых штамповочных работ 5.59 MB
  Расчет зависимости частоты вращения ротора серводвигателя от шага подачи ленты валковой подачи от числа ходов ползуна пресса и от фазового угла подачи ленты в зону штампа 3 Экономическая часть 3. При полной автоматизации работы коэффициент использования числа ходов пресса достигает 100 хотя абсолютное число используемых ходов за рабочую смену несколько ниже предельно возможного изза потерь времени на перестановку штампов заправку ленты и т. Работа комплекса начинается с того что рулон ленты устанавливается...
43214. Электропривод цепного транспортера 1.73 MB
  Вращающий момент с вала электродвигателя передается через упругую муфту с вогнутым профилем торообразной оболочки на быстроходный вал двухступенчатого цилиндрического редуктора. ВЫБОР ЭЛЕКТРОДВИГАТЕЛЯ Основными исходными данными для выбора электродвигателя являются мощность на выходном валу привода и частота вращения его вала между которыми существует связь: где: мощность на выходном валу привода кВт; окружная сила тяговое усилие кН; скорость ленты м с; Требуемая мощность электродвигателя где: требуемая мощность...