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, такой кодировщик будет выдавать малые числа, которые могут способствовать эффективной работе последующего кодирования, например, посредством алгоритма Хафмана.


 

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

10174. Смысл техники в философии Карла Маркса 41.5 KB
  Смысл техники в философии Карла Маркса О смысле техники и ее роли в человеческой истории философы много спорили. Широкое распространение получил марксистский подход который отождествлял технику с объективацией некоторых природных свойств в инструментальных целях тр
10175. Философия техники П.К. Энгельмейера 77.5 KB
  Философия техники П.К. Энгельмейера В настоящей статье обсуждаются совершенно конкретные вопросы творческой или если угодно инновационной деятельности инженера всесторонне рассмотренные в трудах во многом забытых выдающегося ученого П.К. Энгельмейера главным
10176. Карл Ясперс 262.5 KB
  Карл Ясперс. Близки к Хайдеггеру размышления известного немецкого философа одного из крупнейших экзистенциалистов Карла Ясперса 18831969. В работе Истоки истории и ее цель философ рассматривает технику как новый фактор мировой истории.[2] Он призывает к осознанию совр
10177. Техника как ставка века Жака Эллюля 38 KB
  Эллюль рассматривает ее как диалектическую противоположность библейской вере. Он утверждает, что в то время, как техника являет собой попытку людей создать в этом мире свой дом, Библия отрицает то, что человек воистину когда-либо находится у себя дома в этом мире
10178. Образ науки в философии ХХ в 41.5 KB
  Образ науки в философии ХХ в. Несциентистские образы науки. Философия науки в России. В данной лекции будут рассмотрены концепции науки в которых прослеживается линия критики науки. В первую очередь это экзистенциализм. Экзистенциалисты обосновывали
10179. Фридрих Рапп/ Техника и естествознание/ Интеллектуальные предпосылки 110.5 KB
  Фридрих Рапп Техника и естествознание Интеллектуальные предпосылки Промышленная техника и экспериментально-математическое естествознание являются результатом исторического процесса развития. Простые технические действия изготовление орудий оружия культовых ...
10180. Наука как объект теоретического исследования 46 KB
  Наука как объект теоретического исследования Проблематика науковедения и его становление. Структура современного науковедения и место в нем философии науки. Философия науки изучение которой начинается является частью обширной области исследований.
10181. Изготовление орудий труда и накопление знаний о природных веществах в каменном веке. Значение использование огня в первобытном обществе 46 KB
  Изготовление орудий труда и накопление знаний о природных веществах в каменном веке. Значение использование огня в первобытном обществе. Человек и техника появились одновременно еще в каменном веке 2 млн лет конец 4го тысячелетия до н.э.. Первыми орудиями труда сознат
10182. Техника бронзового века. Изобретение и использование плуга, колеса, паруса 35.5 KB
  Техника бронзового века. Изобретение и использование плуга колеса паруса. Следующим этапом в развитии техники стало овладение человека металлом в качестве основного сырья для производства орудий. Люди постоянно использующие огонь не могли не заметить что прокалива