Вопросы оптимального кодирования, Хаффман и компания :) Опции

[СЛАУ]

Не, ну я так не играю. (IMG:style_emoticons/default/rolleyes.gif) Равномерное кодирование совершенно не оптимально... (IMG:style_emoticons/default/skonfuzen.gif) Ну хотя бы Хаффмана посимвольно что ли применили... (IMG:style_emoticons/default/rolleyes.gif)

Хаффмана не знаю. (IMG:style_emoticons/default/skonfuzen.gif)

[Ninat]

Хаффмана не знаю. (IMG:style_emoticons/default/skonfuzen.gif)

Это же известный актер-комик! (IMG:style_emoticons/default/smile.gif)

[СЛАУ]

Почитала Википедию. Почему код Хаффмана префиксный, я пока не поняла, но ладно. А "мысль" по Хаффману вроде бы состоит как минимум из 17 битов. Это если в таком большом тексте, что битами, потраченными на таблицу частот, можно пренебречь.

[Elena]

Почитала Википедию. Почему код Хаффмана префиксный, я пока не поняла, но ладно. А "мысль" по Хаффману вроде бы состоит как минимум из 17 битов. Это если в таком большом тексте, что битами, потраченными на таблицу частот, можно пренебречь.

Чё-т 17 как-то явно маловато. У меня вот тут по таблице 32 вроде получилось (IMG:style_emoticons/default/rolleyes.gif)

А префиксные от слова префикс, т.е. приставка (IMG:style_emoticons/default/wink.gif) Ни одно кодовое слово не является префиксом (т.е. началом) другого. Благодаря этому возможно однозначное декодирование. Потому и префиксные. (IMG:style_emoticons/default/smile.gif)

[СЛАУ]

Чё-т 17 как-то явно маловато. У меня вот тут по таблице 32 вроде получилось (IMG:style_emoticons/default/rolleyes.gif)

Ни нашим, ни вашим. 13.
Допустим, в тексте 5 000 знаков, причём каждая из букв "м", "ы", "с", "л", "ь" повторяется по 1 000 раз, а все остальные символы, что буквы, что пробелы, что знаки препинания и тэ пэ не встречаются в тексте ни разу. (Редкая ситуация, но не невозможная). Тогда имеем такое дерево и такой результат (см. рисунок). ("а-я" - это у меня обозначение для упомянутых "всех остальных букв, пробелов, знаков препинания и тэ пэ").



Это на основании вот этого.

Сообщение отредактировал СЛАУ - 23.05.2012, 6:37

[Elena]

Ни нашим, ни вашим. 13.
Допустим, в тексте 5 000 знаков, причём каждая из букв "м", "ы", "с", "л", "ь" повторяется по 1 000 раз, а все остальные символы, что буквы, что пробелы, что знаки препинания и тэ пэ не встречаются в тексте ни разу. (Редкая ситуация, но не невозможная). Тогда имеем такое дерево и такой результат (см. рисунок). (а-я - это у меня обозначение для упомянутых "всех остальных букв, пробелов, знаков препинания и тэ пэ").

[attachment=26009:IMG_0689.jpg]

Это на основании вот этого.

В случае с по 1000 на 5000 мы имеем дело не с Хаффманом, а с равномерным кодированием. Хаффман здесь вообще никакого смысла не имеет.

P.S. Я брала коды из честного кодирования Хаффманом русского алфавита. У меня даже собственноручно сделанная табличка есть. (IMG:style_emoticons/default/skonfuzen.gif) Правда дома. Поэтому сейчас я воспользовалась табличкой из И-нета.

[СЛАУ]

В случае с по 1000 на 5000 мы имеем дело не с Хаффманом, а с равномерным кодированием. Хаффман здесь вообще никакого смысла не имеет.

Имеет, если описанное мной необычное сообщение передаётся по линии при помощи автоматов, умеющих работать ТОЛЬКО с кодом Хаффмана. Если нет других способов передать сообщение. При исследовании кода должны учитываться всевозможные сообщения, в том числе и такое.

P.S. Я брала коды из честного кодирования Хаффманом русского алфавита. У меня даже собственноручно сделанная табличка есть. (IMG:style_emoticons/default/skonfuzen.gif) Правда дома. Поэтому сейчас я воспользовалась табличкой из И-нета.

Я, кажется, поняла. Вы, наверное, говорите о кодировании по единой таблице частот для всех сообщений, написанных на русском языке. А я-то говорила про описанное в Википедии. Там для любого сообщения составляется СВОЯ, именно этого сообщения таблица частот. При таком подходе слово "мысль" в разных сообщениях будет состоять из разного количества бит. Минимум - из 13 бит.

Сообщение отредактировал СЛАУ - 22.05.2012, 17:27

[Elena]

Я, кажется, поняла. Вы, наверное, говорите о кодировании по единой таблице частот для всех сообщений, написанных на русском языке. А я-то говорила про описанное в Википедии. Там для любого сообщения составляется СВОЯ, именно этого сообщения таблица частот. При таком подходе слово "мысль" в разных сообщениях будет состоять из разного количества бит. Минимум - из 13 бит.

С минимумом не согласна, у меня по Вашим частотам 12 бит получилось. (IMG:style_emoticons/default/tongue.gif) А Вы, судя по всему, вместо Хаффмана, Шеннона-Фано использовали, который, кстати, в отличие от Хаффмана, является субоптимальным. Ну а что касается своей, то у меня студенты уже несколько лет подряд строят "свои" частотные таблицы для реальных текстов. (IMG:style_emoticons/default/skonfuzen.gif) И все они получаются весьма похожими. (IMG:style_emoticons/default/smile.gif) Ну а что касается передачи такой экзотики, как слово мысль 1000 раз подряд в разных комбинациях, то связисты застрелили бы за такое нерациональное использование канала связи. (IMG:style_emoticons/default/rolleyes.gif)

[СЛАУ]

А префиксные от слова префикс, т.е. приставка (IMG:style_emoticons/default/wink.gif) Ни одно кодовое слово не является префиксом (т.е. началом) другого. Благодаря этому возможно однозначное декодирование. Потому и префиксные. (IMG:style_emoticons/default/smile.gif)

М-м! Поняла! Только что. Спасибо.

[СЛАУ]

С минимумом не согласна, у меня по Вашим частотам 12 бит получилось. (IMG:style_emoticons/default/tongue.gif)

Это странно. Потому что я себя проверяла. Я применила алгоритм из статьи Википедии "Код Хаффмана", как я его поняла, к примеру из той же статьи (а15, б7, в6, г6, д5) и у меня получился совершенно тот же результат, что и в этой статье (а0, б100, в101, г110, д111).
Ну да бог с ним.

Сообщение отредактировал СЛАУ - 22.05.2012, 14:24

[СЛАУ]

А Вы, судя по всему, вместо Хаффмана, Шеннона-Фано использовали, который, кстати, в отличие от Хаффмана, является субоптимальным.

Прочитала в Википедии про алгоритм Шеннона-Фано. Нет, я его не использовала. Я его даже не знала. При построении дерева я шла от листочков дерева к его корню, а не наоборот.
Воля ваша, а я осталась при мнении, что Вы где-то обсчитались.

Сейчас придёт Нинат и за этот флуд ВСЕМ достанется.

Сообщение отредактировал СЛАУ - 23.05.2012, 6:38

[Elena]

Русскоязычная википедия, увы, авторитетным источником не является. Будет время, позже подробнее напишу, как я кодировала символы.

Сейчас придёт Нинат и за этот флуд ВСЕМ достанется.

За флуд здесь достаться может только от меня (как модератора раздела и админа форума) и супермодеров (IMG:style_emoticons/default/skonfuzen.gif)

Это странно. Потому что я себя проверяла. Я применила алгоритм из статьи Википедии "Код Хаффмана", как я его поняла, к примеру из той же статьи (а15, б7, в6, г6, д5) и у меня получился совершенно тот же результат, что и в этой статье (а0, б100, в101, г110, д111).
Ну да бог с ним.

P.S. У Вас не могло получиться то же самое, что в примере в вики, т.к. там символы а-д не равновероятны.

[СЛАУ]

Будет время, позже подробнее напишу, как я кодировала символы.

Это было бы замечательно. Заранее спасибо.

[ycheff]

Почему код Хаффмана префиксный, я пока не поняла, но ладно.

Префиксный - значит многократно пофиксенный.

[Elena]

Это было бы замечательно. Заранее спасибо.

Вот:



На каждом шаге объединяются самые маловероятные веточки. У вершин в скобках приписаны частоты, чтобы было нагляднее.

[СЛАУ]

Вот:


На каждом шаге объединяются самые маловероятные веточки. У вершин в скобках приписаны частоты, чтобы было нагляднее.

Спасибо! Вы правы - 12. Я совсем уже - с кем стала спорить)

А алгоритм в Википедии описан правильно, и я его поняла правильно: я тоже объединяла самые маловероятные веточки. А я уж была в полной растерянности: думаю, неужели в Википедии под названием одного кода описали другой код. Это была бы умопомрачительно странная ситуация, учитывая, что статья написана хорошо.

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

Я сейчас читаю раздел "Адаптивное сжатие" во всё той же статье Википедии. Я уже почти поняла, как кодировать сообщение за один проход, то есть не подсчитывая заранее количество символов в сообщении. И я так поняла Википедию, что если сообщение закодировано вот этим алгоритмом Хаффмана, адаптированным, то таблицу частот передавать не надо, всё и так может быть раскодировано (или я её не так поняла). Но вот метод раскодирования адаптированного алгоритма Хаффмана там не описан. Что печалит. (Или я несу чушь, и раскодирование в классическом и адаптированном варианте одинаково).

И ещё я пока не поняла, на каком основании можно утверждать, что код Хаффмана - оптимальный.

Но это я так, к слову. Всё, я больше не флужу. Я думаю, может, этот нечаянный разговор - в раздел "Математика", отдельной темой? В назидание потомкам. :-)

Сообщение отредактировал СЛАУ - 24.05.2012, 2:08

[Elena]

И ещё я пока не поняла, на каком основании можно утверждать, что код Хаффмана - оптимальный.

Доказательство есть, например, у Шоломова (Л.А. Шоломов, Основы теории дискретных логических и вычислительных устройств, под ред. С.В. Емельянова, М.: Наука, 1980), начало на с. 375. Можно легко найти в сети (если скан разворотами, то в ридере со стр. 188).

Но это я так, к слову. Всё, я больше не флужу. Я думаю, может, этот нечаянный разговор - в раздел "Математика", отдельной темой? В назидание потомкам. :-)

Это можно, но не сегодня. Если скажете, что конкретно переносить, буду премного благодарна. (IMG:style_emoticons/default/smile.gif)

[СЛАУ]

Доказательство есть, например, у Шоломова (Л.А. Шоломов, Основы теории дискретных логических и вычислительных устройств, под ред. С.В. Емельянова, М.: Наука, 1980), начало на с. 375. Можно легко найти в сети (если скан разворотами, то в ридере со стр. 188).

Спасибо!

Это можно, но не сегодня. Если скажете, что конкретно переносить, буду премного благодарна. (IMG:style_emoticons/default/smile.gif)

Посты №№
2599, 2601-2611, 2618-2621, 2623.

Сообщение отредактировал СЛАУ - 24.05.2012, 19:08

[Cerberuser]

И ещё я пока не поняла, на каком основании можно утверждать, что код Хаффмана - оптимальный.

А можно ли вообще хоть какой-то код, генерирующий для каждого символа последовательности бит, считать оптимальным? Насколько я помню, в большинстве нетривиальных случаев минимальный объём каждого элемента вполне может быть не целым... Близок к оптимальности - да, но можно ли говорить об оптимальности?

[Elena]

Посты №№
2599, 2601-2611, 2618-2621, 2623.

Уффф, вроде всё перенесла (IMG:style_emoticons/default/smile.gif)

А можно ли вообще хоть какой-то код, генерирующий для каждого символа последовательности бит, считать оптимальным? Насколько я помню, в большинстве нетривиальных случаев минимальный объём каждого элемента вполне может быть не целым... Близок к оптимальности - да, но можно ли говорить об оптимальности?

Оптимальный = наилучший. Доказательство, что код Хаффмана является оптимальным для посимвольного кодирования, есть в литературе. Например, в упомянутой выше.

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

А что понимается под минимальным объемом каждого элемента?

[Cerberuser]

Оптимальный = наилучший. Доказательство, что код Хаффмана является оптимальным для посимвольного кодирования, есть в литературе. Например, в упомянутой выше.

Вопрос снят, ответ понят (IMG:style_emoticons/default/smile.gif)