- •§ 8. Диафантовы множества.
- •Теорема Лагранжа.
- •8.1. Разрешимость в натуральных числах.
- •Определение.
- •Определение.
- •Теорема 8.1.
- •Теорема 8.2.
- •Необходимость.
- •Достаточность.
- •8.2. Нумерация кортежей.
- •Канторова нумерация.
- •Геделево кодирование.
- •Определение.
- •Теорема 8.3.
- •Теорема 8.4.
- •Определение.
- •0.2. Машина с неограниченными регистрами (мнр) [Ктл, c.16]
- •0.3. Равнодоступные адресные машины (рам) [Ахо, с.22]
- •Типы операндов.
- •Команды.
- •0.4. Интерпретация программы как функции.
- •0.6. Вычислительная сложность рам-программ.
- •Определение.
- •Определение.
- •Определение.
- •Логарифмический критерий.
- •0.7. Модификации рам.
- •0.8. Неветвящиеся программы и равномерный весовой критерий.
- •Определение.
- •0.9. Неветвящиеся программы и логарифмический весовой критерий.
- •0.10. Ветвления.
- •0.11. Операции с двоичными векторами фиксированной длины. Определение.
- •Определение.
- •0.12. Машина Тьюринга (k-ленточная).
- •Определение.
- •Определение.
- •0.13. Связь мт и рам.
- •Теорема 0.1.
- •Утверждение 1.
- •Утверждение 2.
- •§ 1. Структуры данных. Определение.
- •1) Вставка.
- •2) Удаление.
- •1.1. Очередь и стек. Определение.
- •Определение.
- •1.2. Множества. Представление множеств.
- •1) Применение списков.
- •3) Представление в виде массивов.
- •4) Представление в виде графа.
- •Определение.
- •Определение.
- •§ 2. “Разделяй и властвуй”.
- •Теорема 2.1
- •§ 3. Динамическое программирование
- •Алгоритм 3.1.
- •§ 4. Редактирующее расстояние
- •Алгоритм 4.1.
- •Алгоритм 4.2.
- •§ 5. Порядковые статистики Определение.
- •Алгоритм 5.1
- •Теорема 5.2.
- •§ 6. Вхождение образца
- •Определение.
- •Алгоритм 6.1a.
- •Алгоритм 6.1б. Вычисление функции отказов.
- •Теорема 6.2.
- •Алгоритм 6.1.Б вычисляет f за o(n) шагов.
- •Конец пока
- •Алгоритм lz
- •Дельта – алгоритм
- •Арифметическое кодирование
Конец пока
б) Декодирование
Инициализируем словарь,
Устанавливаем позицию на начало архива.
Пока не весь архив распакован, прчесть из архива очередное число pi ; найти строку
S, лежащую на позиции p в словаре. Записать S в конец распакованного текста.
Прочесть из архива следующее за p число a и отыскать в словаре строку u,
находящуюся на месте q. Записать в словаре s и [1] (s+ i-ый символ u).
Продвинуть текущую позицию на символ q.
Конец пока.
Заметим, что упаковщик сразу заносит расширенную строку в словарь, но при распаковке сразу этого сделать нельзя. Необходимо прочесть следующую строку. Поэтому для обеспечения одинаковой последовательности манипуляций со словарем расширенную строку для начала помещают во вспомогательный буфер, а в словарь заносят только на следующей ветке цикла.
Алгоритм lz
Алгоритм LZ (с плавающим словарем) использует в качестве словаря кольцевой буфер, в котором хранятся последние M байт кодируемого текста (от текущей позиции).
Данные в упакованном тексте делятся на две категории:
1) ссылки на словарь < размер, расстоояние >
2) неупорядоченные данные < размер, данные >
Каждой паре предметов префиксный бит определяет ее тип.
Данные – последовательность байтов, длина которых указана в поле “ размер” заголовка.
Последовательность неупакованных данных посылается только в том случае, когда кодируемая последовательность символов не встречается в словаре или встречается длиной 1 или 2.
В некоторых вариантах LZ-алгоритма в этом случае вместо пары < размер, данные >
передается только один символ (без кодирования, но с нулевым префиксным битом), и процесс
возобновляется со следующим символом.
Алгоритм LZW- удобнее.
Оба алгоритма можно оптимизировать.
-
в LZ поле “размер” и “расстояние” можно кодировать по Хаффману.
-
в LZW – ввести операции удаления из словаря, а также поддерживать словарь с различной длиной индекса. Можно отказаться от “жадной ” одношаговой стратегии и перейти к 2х – 3х
шаговой.
Построение словаря на предварительном проходе может дать улучшение на 5-15%, а может и ухудшить алгоритм.
Дельта – алгоритм
Метод дельта-кодирования – кодирования с предсказанием – обычно используется для кодирования графических файлов (формат bmp или tga). Поскольку изображение является довольно гладким, выгодно вместо значений RGB хранить закодированные по Хаффману границы соответствующих полей.
В этом случае кодируются разницы между пикселами.
Арифметическое кодирование
Этот метод позволяет отказаться от кодирования каждого символа целым числом бит.
В результате можно более эффектно использовать знание таблицы частот встречаемых символов. Это позволяет увеличить коэффициент компрессии на 5-15% по сравнению с алгоритмом Хаффмана за счет некоторого увеличения сложности вычислений.
Метод адаптивного арифметического кодирования позволяет избавиться от дополнительного статистического прохода при компрессии и от передачи таблицы частот.