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