Обсуждение статьи SadKo "Кодирование Хаффмана"

Тема в разделе "WASM.ARTICLES", создана пользователем SadKo, 20 авг 2017.

  1. SadKo

    SadKo Владимир Садовников

    Публикаций:
    1
    Регистрация:
    4 июн 2007
    Сообщения:
    1.123
    Адрес:
    г. Санкт-Петербург
    статья в разделе "Публикации"
     

    Вложения:

    • 00.gif
      00.gif
      Размер файла:
      1,6 КБ
      Просмотров:
      226
    • 01.gif
      01.gif
      Размер файла:
      3 КБ
      Просмотров:
      223
    • 00.png
      00.png
      Размер файла:
      60,2 КБ
      Просмотров:
      115
    • 01.png
      01.png
      Размер файла:
      31,2 КБ
      Просмотров:
      113
    • 02.gif
      02.gif
      Размер файла:
      766 байт
      Просмотров:
      120
    • 03.gif
      03.gif
      Размер файла:
      733 байт
      Просмотров:
      114
    • 04.gif
      04.gif
      Размер файла:
      8 КБ
      Просмотров:
      115
    • 05.gif
      05.gif
      Размер файла:
      1,2 КБ
      Просмотров:
      119
    • 06.gif
      06.gif
      Размер файла:
      1,7 КБ
      Просмотров:
      65
    • 07.gif
      07.gif
      Размер файла:
      8 КБ
      Просмотров:
      57
    • descriptor.gif
      descriptor.gif
      Размер файла:
      2,7 КБ
      Просмотров:
      120
    • selector.gif
      selector.gif
      Размер файла:
      954 байт
      Просмотров:
      113
    yashechka нравится это.
  2. yashechka

    yashechka Ростовский фанат Нарвахи Команда форума

    Публикаций:
    31
    Регистрация:
    2 янв 2012
    Сообщения:
    1.174
    Адрес:
    Россия, Ростов-на-Дону
    Ого, какой ты краусаучик, завтра прочитаю обязательно. Это нужно перенести в статьи!!!
    Призываю всех написать по одной статье как Садко!!!:drinks:
     
  3. SadKo

    SadKo Владимир Садовников

    Публикаций:
    1
    Регистрация:
    4 июн 2007
    Сообщения:
    1.123
    Адрес:
    г. Санкт-Петербург
    На самом деле, это давнишние статьи, Mikl___ запросил разрешения на публикацию их здесь.
    Вообще, я планирую цикл статей по SIMD написать, но чуть позже.
     
    yashechka нравится это.
  4. yashechka

    yashechka Ростовский фанат Нарвахи Команда форума

    Публикаций:
    31
    Регистрация:
    2 янв 2012
    Сообщения:
    1.174
    Адрес:
    Россия, Ростов-на-Дону
    Все правильно, так и надо:yes:
    Наш ресурс должен стать самым посещаемым, а чтобы он был таким нужен годный контент.
     
  5. Мановар

    Мановар Active Member

    Публикаций:
    0
    Регистрация:
    2 дек 2016
    Сообщения:
    104
    Жду с нетерпением. Инфа есть, но как то вся разбросана, не систематизирована. Думаю будет очень актуально.
     
  6. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    370
    > Здесь должно быть какое-нибудь заумное высказывание
    Размышления. Трансформатор Хаффмана
    http://www.proza.ru/2017/06/14/138
     
  7. Мановар

    Мановар Active Member

    Публикаций:
    0
    Регистрация:
    2 дек 2016
    Сообщения:
    104
    Это надо оформить как ежегодные членские взносы. А кто не будет писать отключим от сайта.
    Шутка, шуткой, а предложение хорошее. Ведь каждый где то, в чем то, что то да сможет интересное или полезное написать. Получится может и не много, но в нескольких разных областях, что для контента не плохо. Поддерживаю.
    yashechka, но в таких статьях, на мой взгляд, не должно быть посторонних от тематики, тем. Все обсуждения должны быть конкретно только по теме, без всякого отступления и лирики. Так что кое что из выше написанного предлагаю или в отдельную тему, или вообще убрать. А то люди будут про кодирование Хоффмана читать, а тут наши философские рассуждения о сайте.
     
    Коцит, Mikl___ и yashechka нравится это.
  8. sniper

    sniper Member

    Публикаций:
    0
    Регистрация:
    10 мар 2017
    Сообщения:
    44
    Не факт, уважаемый, не факт.
    То есть Вы считаете, что среднестатистический пользователь ветки WASM.BEGINNERS сможет написать интересную статью?
     
  9. Мановар

    Мановар Active Member

    Публикаций:
    0
    Регистрация:
    2 дек 2016
    Сообщения:
    104
    Там еще есть слово - полезное.
     
    Mikl___ нравится это.
  10. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    0
    Регистрация:
    11 июн 2004
    Сообщения:
    2.792
    Адрес:
    Russia
    Мановар, ок, предлагаю вам начать с себя. А то на словах все Львы ТОлстые....
     
    sniper нравится это.
  11. Мановар

    Мановар Active Member

    Публикаций:
    0
    Регистрация:
    2 дек 2016
    Сообщения:
    104
    При чем тут Лев Николаевич? Я по моему себя с ним не сравнивал, да и вообще ни с кем. yashechka, предложил, я поддержал. Может и написал чего нибудь, да только не знаю чего надо, опыта то у меня по сравнению с другими пользователями почти никакого.
     
    Mikl___ нравится это.
  12. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    0
    Регистрация:
    11 июн 2004
    Сообщения:
    2.792
    Адрес:
    Russia
    Об этом и речь, что перед тем, как задвигать предложения, наподобие этого:
    нужно прикинуть, как вы почувствуете себя, на месте тех, кто не будет писать. Яшечка предлагал совсем другое.
    А Лев Николаевич хоть и не причем, но фраза очень даже в тему.
     
  13. Мановар

    Мановар Active Member

    Публикаций:
    0
    Регистрация:
    2 дек 2016
    Сообщения:
    104
    TermoSINteZ, у Вас что, с чувством юмора туго или его вообще нет?
    Можете отключить.
    Я прекрасно понял что он предлагал, поэтому и написал что поддерживаю. Вы сообщения в теме читаете?
     
    Mikl___ нравится это.
  14. TermoSINteZ

    TermoSINteZ Синоби даоса Команда форума

    Публикаций:
    0
    Регистрация:
    11 июн 2004
    Сообщения:
    2.792
    Адрес:
    Russia
    Ну если вы поддерживаете его, так возьмите и напишите.
     
  15. Mikl___

    Mikl___ Супермодератор Команда форума

    Публикаций:
    6
    Регистрация:
    25 июн 2008
    Сообщения:
    2.491
    Мановар,
    предложение хорошее. В конце концов не боги горшки обжигают. Но если, по какой-то причине, нельзя написать статью самостоятельно, то можно выкладывать ссылки на статьи других авторов, контент которых попадает под низкоуровневое программирование или будет интересен другим. Сайт необходимо наполнять статьями, идеями и т.д.
     
  16. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    370
    Решил добавить в двух словах основные тезисы


    Трансформатор Хаффмана - теоретическая часть

    Алгоритм компрессии данных Давида Хаффмана ("Трансформатор Хаффмана") описан в сотнях (если не тысячах) статей, но я не знаю ни одной, где это было бы сделано правильно :-)

    Во-первых, алгоритм Хаффмана связывают исключительно с текстом. Между тем, текст - один из вариантов представления фрактала (для простоты не будем различать истинные - бесконечные фракталы и конечные предфракталы). То, что текст - фрактальный объект следует, например, из его эквивалентного представления другим классическим фрактальным объектом - деревом.

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

    Во-вторых, при описании алгоритма Хаффмана умалчивается, что вторая фаза алгоритма является инверсией построенного на первом шаге дерева максимальной высоты.

    Это затемняет тот факт, что с инверсией дерева связано понятие инварианта трансформации - в терминологии Клода Шеннона "количество информации" в сообщении.

    Два экстремальных (двойственных) варианта полностью сбалансированного дерева - это симметричное дерево минимальной высоты, обычно, называемое просто "сбалансированным деревом", высота которого есть (двоичный) логарифм от числа терминальных узлов ("дерево Хартли") и дерево максимальной высоты ("дерево Фибоначчи").

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

    Энтропия Шеннона описывает "насыпную" (фрактальную) плотность текста, который можно "утрамбовать" до энтропийного предела. В результате "сжатия" сообщения (термин неверный, но общепринятый) его размер уменьшается, при этом энтропия на символ текста растет, и, в результате, "количество информации" остается неизменным. Таким образом, на плоскости параметров (размер сообщения, энтропия на символ) сжатие текста отвечает гиперболическому повороту (лоренц-сжатие) и преобразования текста могут быть описаны в терминах, используемых в теории относительности.
     
  17. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    1.744
    Как по мне, это простое и понятное описание кодирования Хаффмана и нет никакой необходимости дополнять его какой-то выдуманной фрактальной шизотерикой :)
     
  18. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    370
    Это "качественное" описание, не отражающее инвариантность преобразования. Оно верно, но недостаточно для понимания того, почему преобразование Хаффмана биективно (исходный и сжатый код есть два эквивалентных представления того же самого объекта в различных кодовых системах (системах отсчета)).
     
  19. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    1.744
    gazlan,
    Все там достаточно. Исходное сообщение переписывается другим алфавитом (наименее избыточным), созданным специально для этого сообщения.
     
  20. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    370
    На самом деле, понятие Инверсии очень упрощает понимание. Это ключик ко многим проблемам. В теории графов понятие двойственности хорошо разработано. И бывает, что решение двойственной задачи проще, чем исходной. Тогда решают двойственную задачу, а потом просто инвертируют решение. Скажем, минимуму в двойственной задаче будет соответствовать максимум в исходной итд.

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

    В этом можно легко убедиться, посмотрев таблицы частот символов до сжатия архиватором и после.

    Например, таблицы частотностей для текста этой заметки - хорошо заметно выравнивание частот. Для файлов большого размера результат будет еще лучше.

    huffman.txt.png huffman.7z.png