Блог

Сейчас лето, и поэтому я решил взять на себя смелость написать программу сжатия данных, предпочтительно в коде C. Я неплохо разбираюсь в том, как работает сжатие для начинающих. У меня просто есть несколько вопросов:

1) Был бы c подходящим языком программирования для выполнения этой задачи?
2) Должен ли я работать в байтах с входным файлом? Или как-то на двоичном уровне?

Если бы кто-нибудь мог просто подтолкнуть меня в правильном направлении, я был бы очень признателен. Однако я хотел бы закодировать это самостоятельно, а не использовать уже существующую библиотеку сжатия или что-то в этом роде.

Вы могли бы начать с изучения кодировки Хаффмана. Многие классы информатики реализуют это как проект, поэтому он должен быть управляемым. Для кодирования по Хаффману подошел бы C, но, возможно, было бы проще сначала выполнить это на языке более высокого уровня, чтобы вы понимали концепции.На Java доступны слайды, подсказки и пример проекта для проекта уровня masters в Университете Пенсильвании (найдите «huff» на этой странице).

Чтобы ответить на ваши вопросы:

1. C подходит.
2. Это зависит от алгоритма или того, как вы думаете о `сжатии».

Мое мнение будет таким: сначала решите, хотите ли вы сделать lossless compression или a lossy compression , затем выберите алгоритм для реализации. Вот несколько советов:

Для алгоритма без потерь некоторые из них очень интуитивно понятны, такие как run-length кодирование, например, если есть 11 a секунд и 5 b секунд, вы просто кодируете их как 11a5b . Некоторые алгоритмы используют dictionary , пожалуйста, обратитесь к LZW encoding . Наконец, я рекомендую Huffman кодирование, поскольку оно очень простое и полезное для приобретения опыта в изучении алгоритма (для ваших образовательных целей).

Для сжатия с потерями, Discrete Fourier Transform (DFT) или wavelet , используется при сжатии JPEG. Это полезно для понимания сжатия мультимедиа.

Страница Википедии — хорошая отправная точка.

1. Да, C хорошо подходит для такого рода работы.

2. Будете ли вы работать с байтами или битами, будет зависеть от алгоритма, который вы решите реализовать. Например, кодирование по Хаффману изначально ориентировано на бит, в то время как многие другие алгоритмы сжатия — нет.

1. C — отличный выбор для написания программы сжатия. Впрочем, вы можете использовать и множество других языков.

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

Удачи!

1) Был бы c подходящим языком программирования для выполнения этой задачи?

ДА.

2) Должен ли я работать в байтах с входным файлом? Или как-то на двоичном уровне?

Они одинаковы, поэтому вопрос не имеет смысла.

не использовать уже существующую библиотеку сжатия

Можете ли вы использовать уже существующий алгоритм сжатия? Их десятки, и «алгоритм сжатия» — при использовании с Google — откроет много полезной информации.