Ого, какой ты краусаучик, завтра прочитаю обязательно. Это нужно перенести в статьи!!! Призываю всех написать по одной статье как Садко!!!
На самом деле, это давнишние статьи, Mikl___ запросил разрешения на публикацию их здесь. Вообще, я планирую цикл статей по SIMD написать, но чуть позже.
Все правильно, так и надо Наш ресурс должен стать самым посещаемым, а чтобы он был таким нужен годный контент.
Жду с нетерпением. Инфа есть, но как то вся разбросана, не систематизирована. Думаю будет очень актуально.
> Здесь должно быть какое-нибудь заумное высказывание Размышления. Трансформатор Хаффмана http://www.proza.ru/2017/06/14/138
Это надо оформить как ежегодные членские взносы. А кто не будет писать отключим от сайта. Шутка, шуткой, а предложение хорошее. Ведь каждый где то, в чем то, что то да сможет интересное или полезное написать. Получится может и не много, но в нескольких разных областях, что для контента не плохо. Поддерживаю. yashechka, но в таких статьях, на мой взгляд, не должно быть посторонних от тематики, тем. Все обсуждения должны быть конкретно только по теме, без всякого отступления и лирики. Так что кое что из выше написанного предлагаю или в отдельную тему, или вообще убрать. А то люди будут про кодирование Хоффмана читать, а тут наши философские рассуждения о сайте.
Не факт, уважаемый, не факт. То есть Вы считаете, что среднестатистический пользователь ветки WASM.BEGINNERS сможет написать интересную статью?
При чем тут Лев Николаевич? Я по моему себя с ним не сравнивал, да и вообще ни с кем. yashechka, предложил, я поддержал. Может и написал чего нибудь, да только не знаю чего надо, опыта то у меня по сравнению с другими пользователями почти никакого.
Об этом и речь, что перед тем, как задвигать предложения, наподобие этого: нужно прикинуть, как вы почувствуете себя, на месте тех, кто не будет писать. Яшечка предлагал совсем другое. А Лев Николаевич хоть и не причем, но фраза очень даже в тему.
TermoSINteZ, у Вас что, с чувством юмора туго или его вообще нет? Можете отключить. Я прекрасно понял что он предлагал, поэтому и написал что поддерживаю. Вы сообщения в теме читаете?
Мановар, предложение хорошее. В конце концов не боги горшки обжигают. Но если, по какой-то причине, нельзя написать статью самостоятельно, то можно выкладывать ссылки на статьи других авторов, контент которых попадает под низкоуровневое программирование или будет интересен другим. Сайт необходимо наполнять статьями, идеями и т.д.
Решил добавить в двух словах основные тезисы Трансформатор Хаффмана - теоретическая часть Алгоритм компрессии данных Давида Хаффмана ("Трансформатор Хаффмана") описан в сотнях (если не тысячах) статей, но я не знаю ни одной, где это было бы сделано правильно Во-первых, алгоритм Хаффмана связывают исключительно с текстом. Между тем, текст - один из вариантов представления фрактала (для простоты не будем различать истинные - бесконечные фракталы и конечные предфракталы). То, что текст - фрактальный объект следует, например, из его эквивалентного представления другим классическим фрактальным объектом - деревом. Трансформация Хаффмана применима к произвольному фрактальному объекту. Такой объект может быть отображен на другой (в том числе, двойственный) фрактальный объект с иным правилом разбиения. Выбор минимального набора элементов (например, минимального числа разновесов при взвешивании) отвечает оптимальной стратегии разбиения и эквивалентен алгоритму Хаффмана. Во-вторых, при описании алгоритма Хаффмана умалчивается, что вторая фаза алгоритма является инверсией построенного на первом шаге дерева максимальной высоты. Это затемняет тот факт, что с инверсией дерева связано понятие инварианта трансформации - в терминологии Клода Шеннона "количество информации" в сообщении. Два экстремальных (двойственных) варианта полностью сбалансированного дерева - это симметричное дерево минимальной высоты, обычно, называемое просто "сбалансированным деревом", высота которого есть (двоичный) логарифм от числа терминальных узлов ("дерево Хартли") и дерево максимальной высоты ("дерево Фибоначчи"). Инверсия Хаффмана заключается в сопоставлении каждому терминальному узлу построенного в первой фазе алгоритма дерева максимальной высоты (в пределе - дерева Фибоначчи) инцидентной к нему ветви. При этом каждому терминальному узлу ставится в соответствие код этой ветви таким образом, что узел с наибольшим весом (самый частый символ) получает наиболее короткий код. В результате, код этого узла имеет наименьшую долю в полном кодовом пространстве и, наоборот, код с наименьшим весом (самый редкий символ) получает наибольшую долю. В результате такого выравнивания происходит симметрирование кодового дерева и, в пределе, инверсии дерева Фибоначчи соответствует двойственное ему дерево Хартли. Энтропия Шеннона описывает "насыпную" (фрактальную) плотность текста, который можно "утрамбовать" до энтропийного предела. В результате "сжатия" сообщения (термин неверный, но общепринятый) его размер уменьшается, при этом энтропия на символ текста растет, и, в результате, "количество информации" остается неизменным. Таким образом, на плоскости параметров (размер сообщения, энтропия на символ) сжатие текста отвечает гиперболическому повороту (лоренц-сжатие) и преобразования текста могут быть описаны в терминах, используемых в теории относительности.
Как по мне, это простое и понятное описание кодирования Хаффмана и нет никакой необходимости дополнять его какой-то выдуманной фрактальной шизотерикой
Это "качественное" описание, не отражающее инвариантность преобразования. Оно верно, но недостаточно для понимания того, почему преобразование Хаффмана биективно (исходный и сжатый код есть два эквивалентных представления того же самого объекта в различных кодовых системах (системах отсчета)).
gazlan, Все там достаточно. Исходное сообщение переписывается другим алфавитом (наименее избыточным), созданным специально для этого сообщения.
На самом деле, понятие Инверсии очень упрощает понимание. Это ключик ко многим проблемам. В теории графов понятие двойственности хорошо разработано. И бывает, что решение двойственной задачи проще, чем исходной. Тогда решают двойственную задачу, а потом просто инвертируют решение. Скажем, минимуму в двойственной задаче будет соответствовать максимум в исходной итд. Применительно к компрессии, зная, что исходный код соответствует минимуму дисперсии размеров кодов, можно без вычислений сказать, что сжатый код будет соответствовать минимуму дисперсии кратностей символов. В этом можно легко убедиться, посмотрев таблицы частот символов до сжатия архиватором и после. Например, таблицы частотностей для текста этой заметки - хорошо заметно выравнивание частот. Для файлов большого размера результат будет еще лучше.
