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 и предшествующий наиболее общему.


 

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

46389. Изучение схемотехники усилителей электрических сигналов с использованием биполярных и полевых транзисторов 268.5 KB
  Для всех схем включения транзистора снять АЧХ. АЧХ на биполярном транзисторе при включении его с общим эмиттером. Ширина полосы пропускания = 1 kHz – 400 kHz АЧХ на биполярном транзисторе при включении его с общим коллектором. АЧХ на биполярном транзисторе при включении его с общим эмиттером c включенным конденсатором С2.
46390. ЖИТТЄВИЙ ЦИКЛ КЛІТИН. МІТОЗ 875 KB
  Виготовлення тимчасових препаратів корінців проростків пофарбованих ацетокарміном Визначення рівня мітотичної активності мерістематичної тканини Мета: Навчитися фіксувати і фарбувати хромосоми в клітинах рослинних мерістематичних тканин що активно діляться розрізняти фази мітозу в клітинах корінців проростків різних сільськогосподарських культур та розраховувати мітотичний індекс; Матеріали обладнання та реактиви: 1 корінці 5ти денних проростків різних сільськогосподарських культур фіксовані протягом 24 годин через кожні...
46391. Розробка функціональної схеми МПС 179.5 KB
  Розробити функціональну схему МПС яка забезпечує виконання наступних функцій: Роздільне керування записом та читанням пам’яті і ЗП за допомогою сигналів МЕMR MEMW I OR i I OW; Ввід вивід даних у послідовному форматі по 3м каналам; 3 Обробку запитів на переривання від 5ти джерел; Керування клавіатурою; Прямий доступ до пам’яті від 3ти джерел; Обмін даними у паралельному форматі між ЗП та МПС по 6ти каналам у режимі синхронний ввід вивід. Загальний опис МПС Дана МПС не має у своєму складі системного контролера отже...
46392. Магнетизм, електромагнітні коливання і хвилі. Оптика, теорія відносності. Елемен- ти атомної фізики, квантової механіки і фізики твердого тіла. Фізика ядра та елементарних часток 7.63 MB
  Він побудований у відповідності з робочою програмою цієї частини курсу дотриманням вимог загальноприйнятих найменувань і позначення фізичних величин та одиниць їх вимірювання у системі SI; нумерація формул і малюнків проведена в межах кожного розділу. Цей момент дорівнює нулю в рівноважному положенні контура а в деякому положенні він – максимальний.1 де І – сила струму в контурі S – його площа – одиничний вектор нормалі до площини контура напрямок якого визначається за правилом свердлика. Відношення максимального обертового моменту до...
46393. Сутність, складові та засади організації місцевих фінансів 443 KB
  Сутність складові та засади організації місцевих фінансів Сучасне поняття місцеві фінанси ґрунтується на ідейнотеоретичних засадах що формувалися протягом досить тривалого часу: 1. Він представляв собою збірник місцевих законів що вміщував норми державного земельного кримінального проце суального та спадкового права. розвиток поглядів на сутність місцевих фінансів їх склад та принципи організації проходив від представлення їх як: 1. Фінансового господарства...
46394. Розрахунок теплової схеми і устаткування блоку 300 МВт 1.23 MB
  Розрахунок процесу розширення пари в турбіні. Розрахунок термодинамічних параметрів підігрівників живильної та сітьової води. Тепловий розрахунок теплофікаційної установки. Визначення витрат пари на підігрівники живильної води. Тепловий розрахунок трубопроводу живильного насосу.
46395. ПОЛІТИЧНА ЕКОНОМІЯ 821.5 KB
  У ньому комплексно розкриті загальні закономірності розвитку економічних систем їх рушійні сили і суперечності показана роль продуктивних сил і економічних відносин у процесі розвитку суспільного виробництва. Головною метою вивчення дисципліни є формування системи знань про економічні відносини як суспільну форму виробництва проблеми ефективного використання обмежених виробничих ресурсів і шляхи забезпечення суспільних потреб у різних соціальноекономічних системах формування у студентів наукового світогляду сучасного економічного...
46396. Проблема промислової безпеки. Дії населення в очагах хімічної поразки 86 KB
  Проблема промислової безпеки значно загострилась з появою крупномасштабных хімічних виробництв в першій половині нашого сторіччя. Основу хімічної промисловості склали виробництва безперервного циклу, продуктивність яких не має, по суті, природних обмежень. Постійне зростання продуктивності зумовлене значними економічними перевагами великих настанов