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


 

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

70160. Институт наследственного правопреемства 223 KB
  Разумеется такое утверждение имеет смысл если рассматривать правопреемство традиционно то есть как переход субъективного права в широком смысле также правовой обязанности от одного лица правообладателя к другому правопреемнику в порядке производного правоприобретения в соответствующих...
70161. Инфляция: причины, последствия, опыт решения проблем 891 KB
  Независимо от состояния денежной сферы товарные цены могут возрасти вследствие изменений в динамике производительности труда, циклических и сезонных колебаний, структурных сдвигов в системе воспроизводства, монополизации рынка, государственного регулирования экономики...
70162. Виды и формы предпринимательской деятельности 251 KB
  Предпринимательство – это особый вид деятельности, особое поприще, преуспеть на котором не каждому под силу. Оно требует не только солидных экономических знаний, решительности, деловой хватки, готовности рисковать, но и способности к творчеству, неординарному мышлению.
70163. Датчиками Холла: их возможности применения в технике 935.46 KB
  Первые предложения по техническому использованию эффекта Холла были высказаны на рубеже XIX и XX вв. Реальная база для этого возникла, однако, значительно позднее, а именно со времени разработки технологии получения полупроводниковых материалов, характеризующихся значительными подвижностями носителей тока.
70164. Организация и оплата труда на предприятиях 158 KB
  Организация труда – составная часть экономики труда – это организация труда людей в процессе производства. Она способствует рациональному соединению техники и персонала, оптимизирует эффективное использование живого труда, обеспечивает сохранение здоровья работников и повышения...
70165. Анализ ценообразующих факторов 193.5 KB
  Перед всеми коммерческими и многими некоммерческими организациями встает задача назначения цены на свои товары и услуги. В условиях рыночной экономики успех любого предприятия или предпринимателя во многом зависит от того как правильно они будут устанавливать цены на свои товары и услуги.
70166. Службы управления персоналом на предприятии 245.5 KB
  Процесс формирования рыночных отношений требует изменения форм и методов хозяйствования основных звеньев экономики - предприятий. Новые общественно-экономические условия ставят производство перед необходимостью решения новых задач.
70168. Проект подстанции для ткацкого цеха №3 предприятия «ОАО ХБК Шуйские ситцы» 3.12 MB
  Производим расчет подстанции, которая получает питание от ЦРП расположенного на расстоянии 1,2 км. Подстанция питает ткацкий цех №3 предприятия «ОАО ХБК Шуйские ситцы», в котором установлено: 315 ткацких станков СТБ-1-180, освещение и вентиляция мощностью 150 кВт.