Компактное сжатие малых записей для быстрого доступа (проект) — различия между версиями
Katya (обсуждение | вклад) |
|||
Строка 8: | Строка 8: | ||
|number_of_students=10 | |number_of_students=10 | ||
|categorize=yes | |categorize=yes | ||
+ | |is_archived=yes | ||
}} | }} | ||
Версия 15:47, 28 июля 2017
Ментор | Руслан Ковалёв |
Учебный семестр | Весна 2016 |
Учебный курс | 1-й курс |
Проект можно развивать на летней практике | |
Максимальное количество студентов, выбравших проект: 10 | |
Внимание! Данный проект находится в архиве и реализован не будет. |
Что это за проект?
Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных).
В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом femtozip на разных наборах данных.
Чему вы научитесь?
Вы узнаете, как устроены современные энтропийные алгоритмы сжатия и научитесь измерять и оптимизировать производительность кода на C++.
Какие начальные требования?
Владение C++
Какие будут использоваться технологии?
В качестве языка программирования мы используем C++, в качестве инструмента профилирования - perf
Темы вводных занятий
На вводных занятиях мы рассмотрим устройство различных алгоритмов сжатия без потерь, их достоинства и недостатки.
Направления развития
Алгоритм, уверенно бьющий femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения и размер словаря.
Критерии оценки
4-5: реализовано энтропийное кодирование
6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности
8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его
Ориентировочное расписание занятий
СБ 9:00-12:00