Блог страдающего Лиса
Lorem ipsum hello dolor sit world amet
16 янв 2023 Пн
Про алгоритм Хаффмана
Уже не помню, когда и как я впервые услышал про этот алгоритм, но как и обычно, это было очень давно и выдумка. Обычно я сначала узнаю о чем-то, а через год, два или даже десять лет изучаю этот вопрос и реализовываю. Так же произошло и с кодом Хаффмана. Как и обычно, я сразу не смог его понять, мне показался он чересчур сложным и потому просто не стал изучать, да и всё. Впервые серьезно пытался его разобрать я после того, как однажды мы как-то зашли в магазин и купили там книгу по распродаже, она называлась что-то вроде "алгоритмы изображений", я уже реально не помню как, а книгу я эту читал очень поверхностно.
В этой книге тоже был описан алгоритм кода Хаффмана, но я его опять не понял, хоть и пытался. Но не понял. Там в этой книге, помимо Хаффмана, еще были и gif, и png, и jpg — все основные картинки в интернете. Не спорю, книга хорошая, но я не умею читать книги, просто не могу, не получается. Мне подходят различные короткие статьи с интернета, а не книги. С последних толка никакого.
Окончательно я с этим алгоритмом смог разобраться только в прошлом году. При помощи страшных мучений примитивного мозга, преодоление препятствия было выполнено, и у меня получилось даже написать алгоритм как на PHP (Pre Historic Programming, в переводе как До Историческое Программирование - ДИП), так и на Си, который является языком, на котором программируют сейчас абсолютно все и который является языком для мажоров. Ладно, я опять отступил от темы, как обычно.
Этот алгоритм Хаффмана интересен тем, что он работает только для алфавита из фиксированного количества символов, при этом необходимо, чтобы частота встречи каждого символа очень сильно различалась, чтобы каким-то образом попытаться сжать эти данные. Эффект кода Хаффмана заключается в том, чтобы сжимать более часто встречающиеся символы более короткими кодами и это факт. Этот алгоритм очень распространен, используясь везде где можно и где не можно. Да, кстати, насчет этого...
Мне пришла мысль, а что если кодировать музыку через Хаффмана? Степень сжатия, конечно, не всегда может быть, но вот как кодировать музыку? Самая первая мысль, которая у меня была, это взять все семплы, подсчитать их частотность и закодировать. Но эта мысль оказалась ошибочной, сжатия почти не было, какие-то жалкие проценты. И тут я подумал о втором варианте — кодировать не сами семплы, а разницу между ними. Вот здесь все получилось гораздо успешнее!
Для этого я написал алгоритм по-быстрому, чтобы проверить догадку. Действительно, сжатие удается до 44% примерно для аудиотрека, что чуть больше чем в 2 раза. Для очень хороших случаев сжимать получается и до 15%, но это в хороших случаях, а вообще, кодом Хаффмана более чем в 8 раз не получится сжать, потому что минимальный код — это 1 бит, который бы кодировал 8 бит.
Я не придумывал какой-то собственный формат, но мне было реально интересно, что получится и получится ли сжатие, и у меня получилось. На данный момент у меня нет реализации формата этого файла для сжатия, так что думаю, что надо будет над этим подумать, и попробовать сделать. Как обычно, через пару месяцев или через пару лет, по традиции. Кто здесь главный слоупок? Я, конечно!
В этой книге тоже был описан алгоритм кода Хаффмана, но я его опять не понял, хоть и пытался. Но не понял. Там в этой книге, помимо Хаффмана, еще были и gif, и png, и jpg — все основные картинки в интернете. Не спорю, книга хорошая, но я не умею читать книги, просто не могу, не получается. Мне подходят различные короткие статьи с интернета, а не книги. С последних толка никакого.
Окончательно я с этим алгоритмом смог разобраться только в прошлом году. При помощи страшных мучений примитивного мозга, преодоление препятствия было выполнено, и у меня получилось даже написать алгоритм как на PHP (Pre Historic Programming, в переводе как До Историческое Программирование - ДИП), так и на Си, который является языком, на котором программируют сейчас абсолютно все и который является языком для мажоров. Ладно, я опять отступил от темы, как обычно.
Этот алгоритм Хаффмана интересен тем, что он работает только для алфавита из фиксированного количества символов, при этом необходимо, чтобы частота встречи каждого символа очень сильно различалась, чтобы каким-то образом попытаться сжать эти данные. Эффект кода Хаффмана заключается в том, чтобы сжимать более часто встречающиеся символы более короткими кодами и это факт. Этот алгоритм очень распространен, используясь везде где можно и где не можно. Да, кстати, насчет этого...
Мне пришла мысль, а что если кодировать музыку через Хаффмана? Степень сжатия, конечно, не всегда может быть, но вот как кодировать музыку? Самая первая мысль, которая у меня была, это взять все семплы, подсчитать их частотность и закодировать. Но эта мысль оказалась ошибочной, сжатия почти не было, какие-то жалкие проценты. И тут я подумал о втором варианте — кодировать не сами семплы, а разницу между ними. Вот здесь все получилось гораздо успешнее!
Для этого я написал алгоритм по-быстрому, чтобы проверить догадку. Действительно, сжатие удается до 44% примерно для аудиотрека, что чуть больше чем в 2 раза. Для очень хороших случаев сжимать получается и до 15%, но это в хороших случаях, а вообще, кодом Хаффмана более чем в 8 раз не получится сжать, потому что минимальный код — это 1 бит, который бы кодировал 8 бит.
Я не придумывал какой-то собственный формат, но мне было реально интересно, что получится и получится ли сжатие, и у меня получилось. На данный момент у меня нет реализации формата этого файла для сжатия, так что думаю, что надо будет над этим подумать, и попробовать сделать. Как обычно, через пару месяцев или через пару лет, по традиции. Кто здесь главный слоупок? Я, конечно!