91581

Алгоритм Зива-Лемпеля

Доклад

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

Кроме строки L создается индекс I исходной строки S в упорядоченном списке вращений. Существует эффективный алгоритм восстановления исходной последовательности символов S на основе строки L и индекса I. Формируем матрицу из NN элементов чьи строки представляют собой результаты циклического сдвига вращений исходной последовательности S отсортированных лексикографически. Пусть I является индексом строки S.

Русский

2015-07-21

40.2 KB

2 чел.

Алгоритм Зива-Лемпеля

Большинство алгоритмов сжатия базируется на последовательной схеме сжатия Лемпеля-Зива (Lempel-Ziv, 1977). Этот алгоритм используется, в частности, стандартной процедурой UNIX Compress. Методики со статистическим моделированием могут обеспечить лучшее сжатие, но они заметно медленнее. Но существует алгоритм, который совмещает в себе лучшие из черт названных выше. Этот алгоритм не предусматривает последовательной обработки входных данных, а обрабатывает текст поблочно. Здесь используется обратимое преобразование блока данных к виду, который позволяет эффективно сжать данные с помощью простых алгоритмов. Преобразование имеет целью сгруппировать символы так, чтобы вероятность появления последовательностей идентичных символов значительно возросла. Такой текст может быть легко сжат посредством локально-адаптивных алгоритмов в сочетании с кодировкой Хафмана и арифметической кодировкой.

Последовательность S, содержащая N символов ({S(0),… S(N-1)}), подвергается N циклическим сдвигам (вращениям), лексикографической сортировке, а последний символ при каждом вращении извлекается. Из этих символов формируется строка L, где i-ый символ является последним символом i-го вращения. Кроме строки L создается индекс I исходной строки S в упорядоченном списке вращений. Существует эффективный алгоритм восстановления исходной последовательности символов S на основе строки L и индекса I. Процедура сортировки объединяет результаты вращений с идентичными начальными символами. Предполагается, что символы в S соответствуют алфавиту, содержащему K символов.

Для пояснения работы алгоритма возьмем последовательность S= “abraca” (N=6), алфавит X = {‘a’,’b’,’c’,’r’}.

1. Формируем матрицу из N*N элементов, чьи строки представляют собой результаты циклического сдвига (вращений) исходной последовательности S, отсортированных лексикографически. По крайней мере одна из строк M содержит исходную последовательность S. Пусть I является индексом строки S. В приведенном примере индекс I=1, а матрица M имеет вид:

Номер строки

0

aabrac

1

abraca

2

acaabr

3

bracaa

4

caabra

5

racaab

2. Пусть строка L представляет собой последнюю колонку матрицы M с символами L[0],…,L[N-1] (соответствуют M[0,N-1],…,M[N-1,N-1]). Формируем строку последних символов вращений. Окончательный результат характеризуется (L,I). В данном примере L=’caraab’, I =1.

Процедура декомпрессии использует L и I. Целью этой процедуры является получение исходной последовательности из N символов (S).

1. Сначала вычисляем первую колонку матрицы M (F). Это делается путем сортировки символов строки L. Каждая колонка исходной матрицы M представляет собой перестановки исходной последовательности S. Таким образом, первая колонка F и L являются перестановками S. Так как строки в M упорядочены, размещение символов в F также упорядочено. F=’aaabcr’.

2. Рассматриваем ряды матрицы M, которые начинаются с заданного символа ch. Строки матрицы М упорядочены лексикографически, поэтому строки, начинающиеся с ch упорядочены аналогичным образом. Определим матрицу M’, которая получается из строк матрицы M путем циклического сдвига на один символ вправо. Для каждого i=0,…, N-1 и каждого j=0,…,N-1,

M’[i,j] = m[i,(j-1) mod N]

В рассмотренном примере M и M’ имеют вид:

Строка

M

M’

0

aabrac

caabra

1

abraca

aabraс

2

acaabr

racaab

3

bracaa

abraca

4

caabra

acaabr

5

racaab

bracaa

Подобно M каждая строка M’ является вращением S, и для каждой строки M существует соответствующая строка M’. M’ получена из M так, что строки M’ упорядочены лексикографически, начиная со второго символа. Таким образом, если мы рассмотрим только те строки M’, которые начинаются с заданного символа ch, они должны следовать упорядоченным образом с учетом второго символа. Следовательно, для любого заданного символа ch, строки M, которые начинаются с ch, появляются в том же порядке что и в M’, начинающиеся с ch. В нашем примере это видно на примере строк, начинающихся с ‘a’. Строки ‘aabrac’, ‘abraca’ и ‘acaabr’ имеют номера 0, 1 и 2 в M и 1, 3, 4 в M’.

Используя F и L, первые колонки M и M’ мы вычислим вектор Т, который указывает на соответствие между строками двух матриц, с учетом того, что для каждого j = 0,…,N-1 строки j M’ соответствуют строкам T[j] M.

Если L[j] является к-ым появлением ch в L, тогда T[j]=1, где F[i] является к-ым появлением ch в F. Заметьте, что Т представляет соответствие один в один между элементами F и элементами L, а F[T[j]] = L[j]. В нашем примере T равно: (4 0 5 1 2 3).

3. Теперь для каждого i = 0,…, N-1 символы L[i] и F[i] являются соответственно последними и первыми символами строки i матрицы M. Так как каждая строка является вращением S, символ L[i] является циклическим предшественником символа F[i] в S. Из Т мы имеем F[T[j]] = L[j]. Подставляя i =T[j], мы получаем символ L[T(j)], который циклически предшествует символу L[j] в S.

Индекс I указывает на строку М, где записана строка S. Таким образом, последний символ S равен L[I]. Мы используем вектор T для получения предшественников каждого символа: для каждого i = 0,…,N-1 S[N-1-i] = L[Ti[I]], где T0[x] =x, а Ti+1[x] = T[Ti[x]. Эта процедура позволяет восстановить первоначальную последовательность символов S (‘abraca’).

Последовательность Ti[I] для i =0,…,N-1 не обязательно является перестановкой чисел 0,…,N-1. Если исходная последовательность S является формой Zp для некоторой подстановки Z и для некоторого p>1, тогда последовательность Ti[I] для i = 0,…,N-1 будет также формой Z’p для некоторой субпоследовательности Z’. Таким образом, если S = ‘cancan’, Z = ‘can’ и p=2, последовательность Ti[I] для i = 0,…,N-1 будет [2,4,0,2,4,0].

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

Возьмем в качестве примера букву “t” в слове ‘the’ и предположим, что исходная последовательность содержит много таких слов. Когда список вращений упорядочен, все вращения, начинающиеся с ‘he’, будут взаимно упорядочены. Один отрезок строки L будет содержать непропорционально большое число ‘t’, перемешанных с другими символами, которые могут предшествовать ‘he’, такими как пробел, ‘s’, ‘T’ и ‘S’.

Аналогичные аргументы могут быть использованы для всех символов всех слов, таким образом, любая область строки L будет содержать большое число некоторых символов. В результате вероятность того, что символ ‘ch’ встретится в данной точке L, весьма велика, если ch встречается вблизи этой точки L, и мала в противоположном случае. Это свойство способствует эффективной работе локально адаптивных алгоритмов сжатия, где кодируется относительное положение идентичных символов. В случае применения к строке L, такой кодировщик будет выдавать малые числа, которые могут способствовать эффективной работе последующего кодирования, например, посредством алгоритма Хафмана.


 

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

37894. ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ВЯЗКОСТИ ВОЗДУХА КАПИЛЛЯРНЫМ МЕТОДОМ 2.7 MB
  Изучение внутреннего трения воздуха как одного из явлений переноса в газах. При протекании жидкости или газа в узкой прямолинейной цилиндрической трубе капилляре при малых скоростях потока течение является ламинарным т. поток газа движется отдельными слоями которые не смешиваются между собой. Для идеального газа  υТ  2.
37895. ОПРЕДЕЛЕНИЕ МОЛЯРНОЙ МАССЫ И ПЛОТНОСТИ ГАЗА МЕТОДОМ ОТКАЧКИ 140 KB
  10 ЛАБОРАТОРНАЯ РАБОТА № 124 ОПРЕДЕЛЕНИЕ МОЛЯРНОЙ МАССЫ И ПЛОТНОСТИ ГАЗА МЕТОДОМ ОТКАЧКИ 1. Цель работы Ознакомление с одним из методов определения молярной массы и плотности газа. Теоретическая часть Состояние некоторой массы газа определяется значениями трёх параметров: давлением P под которым находится газ его температурой T и объёмом V.1 представляет собой уравнение состояния данной массы газа.
37896. ОПРЕДЕЛЕНИЕ ТЕПЛОЁМКОСТИ ТВЁРДЫХ ТЕЛ 440.5 KB
  Если температура калориметра с исследуемым образцом очень медленно увеличивать от начальной T0 на ∆T то энергия электрического тока пойдет на нагревание образца калориметра: 2.18 где I и U – ток и напряжение нагревателя τ – время нагревания m0 и m – массы калориметра и исследуемого образца c0 c – удельные теплоёмкости калориметра и исследуемого образца ∆Q – потери тепла в теплоизоляцию калориметра и в окружающее пространство.18 количества теплоты расходованной на нагрев калориметра и потери теплоты в окружающее...
37897. ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ТЕПЛОПРОВОДНОСТИ ГАЗА МЕТОДОМ НАГРЕТОЙ НИТИ 268.5 KB
  12 ЛАБОРАТОРНАЯ РАБОТА № 127 ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ТЕПЛОПРОВОДНОСТИ ГАЗА МЕТОДОМ НАГРЕТОЙ НИТИ Цель работы Изучение теплопроводности в газах и определение коэффициента теплопроводности воздуха. В твердых телах распространение тепла может происходить как путем теплопроводности так и путем конвекции или того и другого способа одновременно. Основным законом теплопроводности является закон Фурье который в одномерном случае распространения тепла в одном направлении пусть вдоль оси х имеет вид:...
37898. ИЗУЧЕНИЕ ПРИНЦИПА РАБОТЫ ТУННЕЛЬНОГО ДИОДА 3.81 MB
  Если полная энергия частицы Е U0 то с классической точки зрения частица может двигаться либо в области I где х 0 либо в области III где х d. Частица полная энергия которой меньше высоты потенциального барьера U0 не может с классической точки зрения перейти барьер из области I в область III. Волновая функция в этом случае отлична от нуля и в области II даже при значениях Е U0.1 для области II...
37899. Исследование космического излучения 1.03 MB
  Изучение поглощения космического излучения в свинце9 3. Изучение углового распределения интенсивности космического излучения.12 Лабораторная работа № 88 Исследование космического излучения 1. Цель работы 1 изучение зависимости интенсивности космического излучения от толщины пройденных им свинцовых пластин; 2 проверка феноменологической формулы зависимости интенсивности космического излучения от угла наблюдения.
37900. ИЗУЧЕНИЕ ПРОБЕГА -ЧАСТИЦ В ВОЗДУХЕ 568.16 KB
  Методические указания знакомят студентов с явлением радиоактивности и с механизмами потери энергии электронов при их прохождении через вещество. Студентам предоставляется возможность эксперементально исследовать зависимость интенсивности лучей от толщины слоя воздуха и определить линейный коэффициент поглащения а также оценить верхнюю границу энергии –спектра и выявить наиболее важный механизм потерь энергии электронов при их движении в воздухе. Оценить верхнюю границу энергии –спектра и выявить наиболее важный механизм...
37901. Изучение явления внешнего фотоэффекта 70.5 KB
  Контрольные вопросы8 Список литературы8 Лабораторная работа № 93 Изучение явления внешнего фотоэффекта 1. Цель работы Снятие вольт амперной характеристики внешнего фотоэффекта изучение законов внешнего фотоэффекта определение постоянной Планка. Типичная вольт амперная характеристика фотоэффекта т. Таким образом опытным путем установлены следующие основные законы внешнего фотоэффекта: 1.
37902. Определение концентрации и подвижности носителей тока в полупроводнике методом эффекта холла 335.5 KB
  Эффект Холла 4 2. Физическая природа эффекта Холла 5 3. Контрольные вопросы 13 Список литературы 13 Лабораторная работа № 98 Определение концентрации и подвижности носителей тока в полупроводнике методом эффекта холла 1.