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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показаны 3 промежуточные версии 3 участников)
Строка 14: Строка 14:
  
 
В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [https://github.com/gtoubassi/femtozip femtozip] на разных наборах данных.
 
В таких ситуациях алгоритмы сжатия с внешним словарём оказываются существенно эффективнее потоковых алгоритмов, строящих словарь в процессе непосредственно сжатия. В проекте предлагается реализовать энтропийный алгоритм сжатия с внешним словарём и посоревноваться в скорости распаковки и степени сжатия с известным алгоритмом [https://github.com/gtoubassi/femtozip femtozip] на разных наборах данных.
 +
 +
[https://docs.google.com/presentation/d/1yOAJeue6nUhQjHui2peDh5zSQa3DCAv3WHt9qL_3G9w/edit презентация проекта]
  
 
=== Чему вы научитесь? ===
 
=== Чему вы научитесь? ===
Строка 32: Строка 34:
 
=== Критерии оценки ===
 
=== Критерии оценки ===
 
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