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


 

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

9484. Наркотические анальгетики 28.96 KB
  Наркотические анальгетики Продолжение Обзор препаратов в сравнении с Морфином. Кодеин (Метилморфин) Внутрь: БД 50% (биодоступность) - хорошая, у морфина всего 24%. Анальгезирующее действие, по сравнении. С морфином, меньше в 6-10 раз. А противо...
9485. Ненаркотические анальгетики. Психотропные средства 29.31 KB
  Ненаркотические анальгетики Производное анальгина - парацетамол - считается самым безопасным анальгетиком Нет противовоспалительного действия, т.к. ингибирует ЦОГ-3 в ЦНС, в периферических тканях синтез простогландинов не нарушается....
9486. Транквилизаторы. Психостимуляторы и антидепрессанты 28.76 KB
  Транквилизаторы Механизм действия: Анатомический субстрат - лимбическая система, гипоталамус, РФ ствола мозга, таламические ядра ГАМК-ергическое торможение - бензодизепиновые рецепторы рецепторы ГАМК ГАМК - реали...
9487. Антидепрессанты. Антигистаминные средства 43.56 KB
  Антидепрессанты Ниаламид - ингибитор МАО Производное гидразида изоникотиновой кислоты – ГИНК Устраняет боль при стенокардии, НТН (невралгия тройничного нерва) Эффект - через 7-14 дней психостимулирующее дейст...
9488. Бронхолитики. Отхаркивающие средства 30.26 KB
  Бронхолитики СБО (синдром бронхиальной обструкции): Аллергические заболевания (астматический бронхит, БА) ХОБЛ Инфекционно-воспалительные заболевания (бронхит, пневмония, ОРВИ) Пороки развития бронхолегочной системы ...
9489. Средства, влияющие на ЖКТ 32.65 KB
  Средства, влияющие на ЖКТ Группы препаратов: Рвотные и противорвотные Средства, влияющие на аппетит Желчегонные, гепатопротекторы Слабительные Средства, влияющие на секрецию желез желудка Средства заместительной т...
9490. Средства, влияющие на свертывание крови и фибринолиз 30.11 KB
  Средства, влияющие на свертывание крови и фибринолиз Препараты, препятствующие свертыванию крови, при тромбозах: антиагриганты, антикоагулянты, фибринолитики. Вторая группа средств, способствующая свертыванию, это гемостатики, коагулянты, ингибиторы...
9491. Сердечные гликозиды 29.2 KB
  Сердечные гликозиды Кардиотоники - средства, увеличивающие сократительную способность миокарда. Негликозидной структуры - короткодействующие, только при острых состояниях: Адреналина гидрохлорид (г/х) Добутамин (мимети...
9492. Антиаритмические средства 26.8 KB
  Антиаритмические средства Противоаритмические средства при передозировке СГ (сердечные гликозиды): Дифенин Лидокаин (экстрасистолы) Атропин (АВ блок) Причины аритмий: Поражение сердца (90%) - ИБС, пороки, миокардит, инф...