Компактное сжатие малых записей для быстрого доступа (проект) — различия между версиями
Rkovalev (обсуждение | вклад) (Новая страница, с помощью формы Новый_проект) |
|||
| (не показано 11 промежуточных версии 3 участников) | |||
| Строка 11: | Строка 11: | ||
=== Что это за проект? === | === Что это за проект? === | ||
| − | Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности ( | + | Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных). |
| − | В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать | + | В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [https://github.com/gtoubassi/femtozip femtozip] на разных наборах данных. |
| + | |||
| + | [https://docs.google.com/presentation/d/1yOAJeue6nUhQjHui2peDh5zSQa3DCAv3WHt9qL_3G9w/edit презентация проекта] | ||
=== Чему вы научитесь? === | === Чему вы научитесь? === | ||
| − | Вы узнаете, как устроены современные алгоритмы сжатия и | + | Вы узнаете, как устроены современные энтропийные алгоритмы сжатия и научитесь измерять и оптимизировать производительность кода на C++. |
=== Какие начальные требования? === | === Какие начальные требования? === | ||
| Строка 22: | Строка 24: | ||
=== Какие будут использоваться технологии? === | === Какие будут использоваться технологии? === | ||
| − | + | В качестве языка программирования мы используем C++, в качестве инструмента профилирования - perf | |
=== Темы вводных занятий === | === Темы вводных занятий === | ||
| − | На вводных занятиях мы рассмотрим устройство | + | На вводных занятиях мы рассмотрим устройство различных алгоритмов сжатия без потерь, их достоинства и недостатки. |
=== Направления развития === | === Направления развития === | ||
| − | Алгоритм, | + | Алгоритм, уверенно бьющий femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения и размер словаря. |
=== Критерии оценки === | === Критерии оценки === | ||
4-5: реализовано энтропийное кодирование | 4-5: реализовано энтропийное кодирование | ||
| + | |||
6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности | 6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности | ||
| + | |||
8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его | 8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его | ||
=== Ориентировочное расписание занятий === | === Ориентировочное расписание занятий === | ||
СБ 9:00-12:00 | СБ 9:00-12:00 | ||
Текущая версия на 16:13, 28 июля 2017
| Ментор | Руслан Ковалёв |
| Учебный семестр | Весна 2016 |
| Учебный курс | 1-й курс |
| Проект можно развивать на летней практике | |
| Максимальное количество студентов, выбравших проект: 10 | |
Что это за проект?
Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных).
В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом femtozip на разных наборах данных.
Чему вы научитесь?
Вы узнаете, как устроены современные энтропийные алгоритмы сжатия и научитесь измерять и оптимизировать производительность кода на C++.
Какие начальные требования?
Владение C++
Какие будут использоваться технологии?
В качестве языка программирования мы используем C++, в качестве инструмента профилирования - perf
Темы вводных занятий
На вводных занятиях мы рассмотрим устройство различных алгоритмов сжатия без потерь, их достоинства и недостатки.
Направления развития
Алгоритм, уверенно бьющий femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения и размер словаря.
Критерии оценки
4-5: реализовано энтропийное кодирование
6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности
8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его
Ориентировочное расписание занятий
СБ 9:00-12:00
