Полное описание алгоритма сжатия

Question

Я ищу алгоритм сжатия (для соревнования по программированию), и мне нужно полное описание того, как его реализовать (все технические детали), подойдет любой алгоритм без потерь и без патента, но простота его реализации бонус:)

(хотя, возможно, и неактуально) Я планирую реализовать алгоритм на C ++ ...

Заранее спасибо.

EDIT: Я буду сжимать только текстовые файлы, никаких других типов файлов ...

Answer 1

Ну, я не могу пройти так далеко, чтобы завершить соревнование для вас, но, пожалуйста, ознакомьтесь с этой статьей на вики: Run Length Encoding . На сегодняшний день это один из самых простых способов сжатия данных, хотя и не всегда эффективный. Сжатие также зависит от конкретной области, даже среди алгоритмов без потерь вы обнаружите, что то, что вы сжимаете, определяет , как лучше его кодировать.

Answer 2

RFC 1951 описывает раздувание / раздувание, включая краткое описание алгоритма компрессора. Antaeus Feldspar's Объяснение алгоритма Deflate обеспечивает немного больше фона.

Кроме того, исходный дистрибутив zlib содержит упрощенный ссылочный инфлятор в contrib / puff / puff.c, который может быть полезен при чтении, чтобы понять, как именно расположены биты (но он не содержит дефлята, только инфляцию).

Answer 3

Хаффман хорошо, если вы сжимаете простой текст. И все комментаторы ниже уверяют меня, что радостно реализовать ;D

Answer 4

Я бы начал здесь в Википедии.

Есть из чего выбирать, но, не зная больше о том, что вы хотите, трудно помочь больше. Вы сжимаете текст, изображения, видео или просто случайные файлы? Каждый из них имеет свой собственный набор методов и задач для достижения оптимальных результатов.

Если простота реализации является единственным критерием, я бы использовал сжатие "filecopy". Гарантированная степень сжатия ровно 1: 1, а также тривиальная реализация ...

Answer 5

Мне нравится это введение в преобразование Берроуза-Уилера .

Answer 6

Простота реализации: Хаффман, как указано выше. Я считаю, что LZW больше не под патентом, но я не знаю точно. Это относительно простой алгоритм. LZ77 должен быть доступен, хотя. Наконец, преобразование Барроуза-Уилера допускает сжатие, но его реализация значительно сложнее.

Answer 7

Безопасность сейчас! Подкаст недавно выпустил эпизод, освещающий алгоритмы сжатия данных. Стив Гибсон дает довольно хорошее объяснение основам методов сжатия Хаффмана и Лемпеля-Зива. Вы можете прослушать аудиоподкаст или прочитать стенограмму Эпизод 205 .

Answer 8

Если в вашем интернет-браузере вы выберете «Вид», то должна быть опция «Уменьшить» или уменьшить текст.

Выберите один из них и ...

БАМ !

Вы только что получили больше текста на одном экране! Yay компрессия!