2021-01-23 20:08:19
99% всех алгоритмов сжатия сводятся к тому, чтобы заменить повторяющуюся последовательность символов, ссылкой или индексом в словаре (LZ и LZW), и энтропийному кодированию того, что получилось (как правило, Huffman или AC/ANS). С кодированием интереснее. В конце сороковых годов, семьдесят лет уже этим алгоритмам, после того как св. Шеннон, отец теории информации, сформулировал основы, Шеннон и Фано попытались придумать оптимальный код. Получился субоптимальный, и Роберт Фано предложил своим студентам альтернативу - или сдавать экзамен или найти оптимальный код. О том, что он сам вместе с Шенноном такой код не нашли он им конечно не сказал.
Все сводится к тому, что для того, чтобы представить символ, который встречается в тексте с вероятностью P, потребуется ceil(-log2(P)) бит. Не бином Ньютона. Вероятность выпадения "орла" или "решки" 1/2, -log2(1/2) = 1 бит на каждый бросок монеты. Или орел или решка. Шеннон считал количество бит напрямую, вот прямо по формуле. Фано отсортировал символы в порядке убывания вероятности, затем список режется пополам (по "весу", не по количеству) и левая часть становится левой веткой дерева, а правая - правой. Потом процесс повторяется и все левые ветки - ноль, а правые - один. Проходим из корня дереву к листу, записывая "сено-солома" - получаем код. Не идеальный, но не хуже, чем +1 бит на символ.
С экзаменом на носу, Хаффман уже собрался выкинуть все свои черновики и приступить к зубрежке, и только тогда его осенило, что если начать строить дерево не сверху вниз, а снизу вверх, то получится оптимальный код (с целым количеством битов). Так вот к чему это я. То что я понаходил на гитхабе - или лютая дичь написанная безмозглой школотой, или уже взрослые продукты, которые настолько оптимизированы, что в них уже не видно, как работает алгоритм. При этом люди смотрят на всё это, и копируют, не глядя, самые распространенные и криво портированные с доисторических компьютеров решения (привет, многострадальный Йошизаки и Окумура).
А всё просто на самом деле. Проще некуда.
1.9K viewsedited 17:08