Новичок в программировании: Как запрограммировать собственный алгоритм сжатия данных?

Question

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

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

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

Answer 1

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

Answer 2

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

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

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

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

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

Википедия страница является хорошей отправной точкой.

Answer 3

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

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

Answer 4

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

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

Удачи!

Answer 5

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

Да.

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

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

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

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