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 известен.
Наиболее важным фактором, определяющим скорость сжатия, является время, необходимое для сортировки вращений во входном блоке. Наиболее быстрый способ решения проблемы заключается в сортировке связанных строк по суффиксам.
Для того чтобы сжать строку 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].
Данный алгоритм может быть улучшен различными способами. Одним из самоочевидных методов является выбор символа ch на этапе 5, начиная с наименьшего общего символа в S и предшествующий наиболее общему.
А также другие работы, которые могут Вас заинтересовать | |||
68649. | Применение производных типов данных для решения прикладных задач | 92 KB | |
Написать программу выполняющую следующие действия: ввод с клавиатуры данных в массив экземпляров структур состоящий из пяти записей; поиск записей в которых средний бал студента больше 40; поиск записей в которых совпадают номера групп студентов. Написать программу выполняющую следующие действия... | |||
68650. | Использование функций для работы с массивами | 77 KB | |
Ведь элементов в массиве могут быть сотни и представляется нереальным хотя и теоретически возможным описать при передаче в функцию каждый элемент массива. Здесь необходимо вспомнить что имя массива является указателем на нулевой элемент массива. А так как элементы массива расположены непосредственно... | |||
68651. | Расчет тепловой схемы турбинной установки К-220-44 Ровенской АЭС | 4.76 MB | |
В данном дипломном проекте поверхностно рассмотрен первый и второй контур первого блока Ровенской АЭС с реактором ВВЭР-440.Приведен расчет тепловой схемы турбинной установки К-220-44 а также теплогидравлический и нейтронно-физический расчет реактора типа ВВЭР-440. | |||
68652. | РАСЧЕТ ЯДЕРНОГО РЕАКТОРА ВВЭР-1000 | 1.01 MB | |
В активной зоне реактора она нагревается до 595 0К и направляется в парогенераторы где охлаждается отдавая тепло рабочему телу второго контура. Вода первого контура при работе реактора приобретает высокую наведённую радиоактивность даже без нарушения плотности оболочек ТВЭЛов так как в воде практически... | |||
68653. | Разработка математической модели оценки платежеспособности корпоративного заемщика | 1.71 MB | |
Обзор основных моделей которые применятся в банках для анализа кредитоспособности платежеспособности потенциальных заемщиков. Контрольный пример использования математического аппарата в разработки методики анализа кредитоспособности заемщика. Перечень графических материалов... | |||
68655. | Разработка технологии создания учебного пособия и проверкаэффективность в реальном творческом проекте | 1.05 MB | |
Цель данного дипломного проекта – разработать технологию создания учебного пособия и проверить ее эффективность в реальном творческом проекте. Реализация данной цели требует содержательного и методического решения следующих задач: изучить историю и теорию Web-дизайна разработать концептуальную модель учебника... | |||
68656. | Конструкторско-технологическая часть проекта упаковки для пищевой промышленности | 2.47 MB | |
В современной жизни упаковка прочно вошла в наш быт, и сопровождает человека на всех стадиях его деятельности. По состоянию развития упаковочной индустрии стали судить об экономическом и техническом уровне той или иной страны. Наиболее развитые страны вкладывают значительные средства в эту сферу. | |||