Просмотр кода страницы Компактное сжатие малых записей для быстрого доступа (проект)

{{Карточка_проекта
|name=Компактное сжатие малых записей для быстрого доступа
|mentor=Руслан Ковалёв
|mentor_login={{URLENCODE:Rkovalev|WIKI}}
|semester=Весна 2016
|course=1
|summer=on
|number_of_students=10
|categorize=yes
}}

=== Что это за проект? ===
Довольно часто возникает ситуация, когда имеется относительно большое число (например, миллиард) относительно небольших записей (например, длиной в сотню байт и меньше), доступ к которым осуществляется произвольным образом и имеет существенные требования по производительности (мы можем представить себе таблицу в высоко нагруженной базе данных). 

В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [https://github.com/gtoubassi/femtozip femtozip] на разных наборах данных.

[https://docs.google.com/presentation/d/1yOAJeue6nUhQjHui2peDh5zSQa3DCAv3WHt9qL_3G9w/edit презентация проекта]

=== Чему вы научитесь? ===
Вы узнаете, как устроены современные энтропийные алгоритмы сжатия и научитесь измерять и оптимизировать производительность кода на C++.

=== Какие начальные требования? ===
Владение C++

=== Какие будут использоваться технологии? ===
В качестве языка программирования мы используем C++, в качестве инструмента профилирования - perf

=== Темы вводных занятий ===
На вводных занятиях мы рассмотрим устройство различных алгоритмов сжатия без потерь, их достоинства и недостатки.

=== Направления развития ===
Алгоритм, уверенно бьющий femtozip, ценен сам по себе. Можно оптимизировать скорость распаковки и запаковки, степень сжатия, скорость построения и размер словаря.

=== Критерии оценки ===
4-5: реализовано энтропийное кодирование

6-7: в энтропийном кодировании учитываются каким-либо образом условные вероятности

8-10: алгоритм сравним с femtozip по скорости и степени сжатия или опережает его

=== Ориентировочное расписание занятий ===
СБ 9:00-12:00