Алгоритмы сжатия данных
Мне было интересно, если у кого-нибудь есть список алгоритмов сжатия данных. Я практически ничего не знаю о сжатии данных, и я надеялся узнать больше о различных алгоритмах и посмотреть, какие из них являются самыми новыми и которые еще не разработаны для многих ASIC.
Я надеюсь реализовать ASIC сжатия данных, которая не зависит от типа поступающих данных (аудио, видео, изображения и т.
Если мой вопрос слишком открыт, пожалуйста, дайте мне знать, и я пересмотрю. Спасибо
Решение
Существует множество алгоритмов сжатия. Здесь вам нужен алгоритм сжатия без потерь. Алгоритм сжатия без потерь сжимает данные так, что их можно распаковать, чтобы получить именно то, что было задано до сжатия. Противоположным был бы алгоритм сжатия с потерями. Сжатие с потерями может удалить данные из файла. Изображения PNG используют сжатие без потерь, в то время как изображения JPEG могут и часто используют сжатие с потерями.
Некоторые из наиболее широко известных алгоритмов сжатия включают в себя:
ZIP-архивы используют комбинацию кодирования Хаффмана и LZ77, чтобы обеспечить быстрое время сжатия и распаковки а также достаточно хорошие коэффициенты сжатия.
LZ77 — это в значительной степени обобщенная форма RLE, и она часто дает гораздо лучшие результаты.
Хаффман позволяет большинству повторяющихся байтов представлять наименьшее количество битов.
Представьте себе текстовый файл, который выглядел так:
aaaaaaaabbbbbcccdd
Типичная реализация Хаффмана приведет к следующей карте:
Bits Character
0 a
10 b
110 c
1110 d
Таким образом, файл будет сжат до этого:
00000000 10101010 10110110 11011101 11000000
^^^^^
Padding bits required
18 байтов уменьшаются до 5. Конечно, таблица должна быть включена в файл. Этот алгоритм лучше работает с большим количеством данных: P
Алекс Аллен имеет хорошая статья на алгоритм сжатия Хаффмана в случае, если Wiki не достаточно.
Не стесняйтесь спрашивать дополнительную информацию. Эта тема чертовски широка.
Другие решения
Вокруг очень много алгоритмов сжатия данных. Если вы ищете что-то энциклопедическое, я рекомендую Справочник по сжатию данных Salomon и др., который является настолько полным, насколько вы, вероятно, получите (и также имеет хорошие разделы о принципах и практике сжатия данных).
Мое предположение заключается в том, что сжатие на основе ASIC обычно реализуется для конкретного приложения или в качестве специализированного элемента SoC, а не в качестве отдельного чипа сжатия. Я также сомневаюсь, что поиск «новейшего и наилучшего» формата сжатия — это путь, которым я бы хотел воспользоваться — я бы ожидал, что стандартизация, зрелость и пригодность для конкретной цели будут более важными.
Вот некоторые алгоритмы без потерь (могут отлично восстановить исходные данные, используя эти):
- Код Хаффмана
- LZ78 (и вариация LZW)
- LZ77
- Арифметическое кодирование
- Sequitur
- прогноз с частичным совпадением (промилле)
Многие из известных форматов, таких как png или gif, используют варианты или комбинации этих форматов.
С другой стороны, существуют алгоритмы с потерями (точность компромисса для сжатия ваших данных, но часто работает довольно хорошо). Современные методы с потерями объединяют идеи, среди прочего, дифференциальное кодирование, квантование и DCT.
Чтобы узнать больше о сжатии данных, я рекомендую https://www.elsevier.com/books/introduction-to-data-compression/sayood/978-0-12-809474-7. Это очень доступный вводный текст. 3-е издание там в формате PDF онлайн.
Моя бумага Обзор архитектурных подходов к сжатию данных в системах кэш-памяти и основной памяти (Permalink Вот) рассматривает множество алгоритмов сжатия, а также методы их использования в современных процессорах. В нем рассматриваются алгоритмы и методы сжатия как исследовательского, так и коммерческого уровня, поэтому вы можете найти такой, который еще не был реализован в ASIC.
Алгоритм LZW или Lempel Ziv — отличный алгоритм без потерь. Псевдокод здесь: http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html