842 (алгоритм сжатия)
-
Алгоритм сжатия 842
- 842 — это алгоритм сжатия данных, основанный на методе Лемпеля-Зива с ограниченной длиной словаря.
- Обеспечивает от 80 до 90% сжатия данных, сравнимого с LZ77, с высокой пропускной способностью и меньшим использованием памяти.
- Подходит для сжатия виртуальной памяти, баз данных, особенно ориентированных на столбцы, и потокового ввода-вывода.
-
Принцип работы алгоритма
- Работает с блоками по 8 байт и подфрагментами по 8, 4 и 2 байта.
- Использует хэш каждой фразы для поиска в хэш-таблице с смещениями в буфере скользящего окна.
- Совпадения могут быть заменены смещениями, что приводит к смеси совпадающих данных и новых данных.
-
Реализации алгоритма
- IBM добавила аппаратные ускорители для 842 в процессоры POWER7+ и POWER9/Power10.
- В Linux драйвер устройства для 842 был добавлен в 2011 году, но в последнее время возможна программная реализация.
- Исследователи реализовали 842 на графических процессорах, что в 30 раз быстрее, чем программная реализация.
- Библиотека с открытым исходным кодом предоставляет реализацию 842 для CUDA и OpenCL.
- Реализация на ПЛИС показала в 13 раз большую пропускную способность по сравнению с программной реализацией.
Полный текст статьи: