Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
1. Информация и энтропия. Информация – функция события. – функция вероятности события. Свойства I(A). I(A)=-logP(A).Энтропия ДСВ ξ как матожидание ДСВ I(ξ=x). «Ипподромный» пример. Свойства энтропии: минимум, максимум, энтропия случайного вектора. Кодирование исходов ξ числами или словами. Избыточность. Теоремы Шеннона об оптимальном кодировании и о доле типичных последовательностей (без д-ва). Задача о сжатии данных: дано слово w, нужно найти низкоэнтропийную ДСВ, для которой w является типичным результатом серии испытаний и экономно закодировать результаты опытов.
2. Источник информации. Марковская модель источника. Состояния. ДСВ для генерации символов и ДСВ для перехода. Энтропия марковского источника. Вычисление стационарного распределения. Простая модель МИ: конечный автомат, переходящий по сгенерированным символам. Антисловарное сжатие. Пример с антисловарем {00,111,01010}.
3. Префиксное кодирование. Префиксный код: однопроходное декодирование. Бинарные ПК и бинарные деревья. Коды Шеннона-Фано. Коды Хаффмана. Неравенство Крафта-Макмиллана. Задача мат. программирования. Оптимальность кода Хаффмана в классе префиксных кодов. Метод Хаффмана сжатия текстов. Особенности реализации статического МХ: сортировка деревьев за константное время, кодирование дерева (1бит на узел). Погрешность относительно шенноновского оптимума. Свойство братьев. Динамический МХ: симметричность кодирования-декодирования, возможность адаптации (масштабирование счетчиков). Особенности реализации: узел ART, быстрая перестройка дерева (перестановка поддеревьев для сохранения свойства братьев), оценка времени работы.
4. Арифметическое кодирование. Представление сообщения вероятности p отрезком длины p. Выбор кратчайшего числа на отрезке, оптимальность по Шеннону. Целочисленная реализация АК: скользящее окно и нормализация интервала. Расширение узкого интервала (вдвое от середины), хранение и передача отложенных битов. Динамический вариант: сбор статистики, хранение таблиц частот в упорядоченном виде.
5. Словарные алгоритмы. Разбиение Лемпеля-Зива. Методы LZ77: DEFLATE, особенности реализации. Методы LZ78 с явным хранением словаря на примере метода LZW: кодирование символа и обновление словаря; симметричность кодирования/декодирования; особая ситуация при декодировании, ее обработка. Построение разбиения Лемпеля-Зива при помощи суффиксного массива (оффлайн) и суффиксного дерева (онлайн).
6. Статистическое кодирование. Контексты (левые и правые). Глубина контекста. Контекстная модель, ее порядок. Модель источника как дерево контекстных моделей. Взвешивание моделей. Неявное взвешивание. Метод PPM. Символы ухода. Метод исключений (маскировка счетчиков при кодировании). Использование АК. Обновление КМ. Исключения при обновлении. Пример: ACGAGACGGCCCG(T). Оценка вероятности ухода. Априорные методы A, B, C, D, XC. Адаптивные методы: средняя частота ухода из похожих контекстов. Метод Шкарина разбиения на однотипные контексты (с учетом трех типов контекстов). Выбор порядка модели для кодирования символа. Наследование информации при добавлении нового счетчика в КМ. Масштабирование счетчика последнего символа при кодировании.
7. Преобразование Барроуза-Уилера (BWT) и связанные с ним алгоритмы сжатия. Прямое BWT. Сведение к задаче о сортировке суффиксов. Структура BWT-образа: замена контекстных закономерностей на локальную однородность. Обратное преобразование за линейное время: стабильная сортировка. Алгоритм MTF («стопка книг») и его модификации. Распределение частот символов после MTF. Алгоритм ZLE. Схема BWT+MTF+ZLE+ARI. Выбор порядка на алфавите. Алгоритм кодирования расстояний (DC). Эффективные алгоритмы для сортировки суффиксов. Линейный «китайский» алгоритм: два типа позиций, сведение к сортировке «локальных экстремумов», сортировка локальных экстремумов как рекурсивная сортировка более короткой строки.
8. Сжатие бинарных и числовых данных. Черно-белые изображения: использование двумерной структуры. Стандарт CCITT group 4: три режима, кодирование длин в горизонтальном режиме. Бинарное BWT и дожимание результатов CCITT 4. Представление массивов чисел: коды Элиаса, коды Фибоначчи.
Некоторые полезные источники:
1. Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. М: Диалог-МИФИ, 2003.
2. M. Crochemore, T. Lecroq. Text data compression algorithms. In: Atallah M. J. Ed., Algorithms and theory of computation handbook. Ch. 12. CRC Press, 1999.
3. В. В.Семенюк. Экономное кодирование дискретной информации. СПб: СПбГУ ИТМО, 2001.
4. Стандарт CCITT group 4. International telecommunication union, 1988.
5. M. Maniscalco, S. Puglisi, Faster lightweight suffix array construction, Proceedings of the 17th Australasian Workshop on Combinatorial Algorithms (AWOCA'06), 2006. pp.16-29.
6. K. M. Likhomanov, A. M. Shur, Two combinatorial criteria for BWT images. Proc. 6th Symposium on Computer Science in Russia. 2011. pp.385-396. [Lecture Notes in Computer Science Vol. 6651].
7. Ge Nong, Sen Zhang, Wai Hong Chan, Two Efficient Algorithms for Linear Time Suffix Array Construction. IEEE puters 60(10): 1471-1484 (2011)
8. S. Deorowicz, Second step algorithms in the Burrows–Wheeler compression algorithm. Software: Practice and Experience 32: 99–111 (2002)
9. C. E. Shannon, A Mathematical Theory of Communication. Reprinted with corrections from: The Bell System Technical Journal, Vol. 27, pp. 379–423, 623–656, July, October, 1948.
10. T. Gagie, G. Manzini, Move-to-Front, Distance Coding, and Inversion Frequencies revisited. Theoretical Computer Science 411 (2010) 2925-2944.
11. J. Kärkkäinen, D. Kempa, S. J. Puglisi, Linear Time Lempel-Ziv Factorization: Simple, Fast, Small. binatorial Pattern Matching 2013. pp.189-200. [Lect. Notes in Computer Science Vol.7922].
Основные порталы (построено редакторами)