Адаптивное кодирование Хаффмана

@Ortaz · Регистрация: 02.01.2013

Студворк — интернет-сервис помощи студентам

Задали курсовую "Реализация кодирования текста адаптивным алгоритмом Хаффмана".
Разобрался с обычным кодированием (ну вроде бы всё понятно, строим дерево, кодируем от корня до вершин, и т.д., при декодировании пользуемся табличкой)
С адаптивным же возникли проблемы. Неоднократно прочитал статью на Вики и ещё море материала РуНета, я вроде бы даже понял метод построения дерева (считываем символ, если не было, строим доп. ветку, если был, увеличиваем нужные веса вершин на 1, меняем если надо, вроде бы всё понятно.). И вот тут возникает проблема. Написав маленький пример на листочке, я понял, что не имею никакого представления, каким образом декодировать сообщение О_о
В обычном алгоритме всё было ясно, пользуемся табличкой, присылаемой перед сообщением, а здесь декодер должен каким-то невероятным образом восстановить исходное дерево? За месяц дум, я так и не пришёл хотя бы к тому, как декодер поймёт, где кончается код 1 символа и начинается другой, коды же переменной длины, сообщение может быть огромным и т.д.
Прошу помочь объяснить мне сию суть, желательно с примером кодирования небольшого сообщения, полученными кодами и декодировкой. Заранее спасибо

@Igor3D · 02.01.2013, 17:17

"decompressor is one step behind compressor"

Т.е. декодер в точности повторяет кодер, таблица не хранится, а воспроизводится. Встретив новую комбинацию кодер записывает ее напрямую + расширяет таблицу. А декодер видит ее и также добавляет. Вас видимо смущает что "более короткие комбинации являются началом более длинных", но этого не происходит.

Некоторое время размер кодированных данных больше исходных (пока таблица разрастется), потом наступает эффект сжатия. Полагается что данные как-то коррелированы, иначе ничего не выходит (напр массив random float не сжимается)

@Ortaz · 02.01.2013, 18:14 **[ТС]**

Ничего не понял..
Я видимо упустил какой-то момент адаптивного кодирования.
вот есть у нас последовательность 65000 нулей и единиц. Каким образом декодер поймёт, где кончается код 1 и начинается другой (я понимаю, что закодировано однозначно, я реализации декодирования не понимаю)
и другой момент, а как он поймёт, какому коду соответстует какой символ? Т.е даже если он поймёт, что последовательность 001 является символом, как он узнает, какой именно это символ?

@x128 · 03.01.2013, 10:33

Ortaz, смысл в том, что кодовое дерево перестраивается по мере поступления символов. Кодер и декодер делают это одинаково. В начале процесса кодирования, таблица частот содержит единицы для всех символов алфавита. При поступлении очередного символа, увеличивается вес, перестраивается дерево и кодируется этот символ. Декодер поступает аналогичным образом.

@Ortaz · 03.01.2013, 22:11 **[ТС]**

Сообщение от x128

Декодер поступает аналогичным образом.

2 раза сказал, что не понимаю этой фразы...
Я понимаю, как поступает кодер. Ему поступает символ "а" он в алфавите что-то там делает. Пусть в итоге символ "а" имеет код 0010101
1.Декодер как считывает его? Побитово? Поступила ему 0, откуда он знает чё с ней делать?

2.А если полностью считывает, ну считал он код 0010101, каким образом он узнает, что это буква "a", а не любая другая? Второй вопрос по другому. Если мы заменим в изначальном тексте все символы "а" на символ "b", которого там не было, то после построения дерева новый символ закодируется в точности так же, как и кодировался символ "a" в старом тексте. Т.е. код будет тот же. Откуда декодер, даже поняв всё что угодно, узнает, что это "b", а не "a", и не что-то левое?! Если ему поступает только сам закодированный текст

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

@x128 · 03.01.2013, 23:52

Сообщение от Ortaz

2 раза сказал, что не понимаю этой фразы...

Эта фраза имеет буквальный смысл.

Сообщение от Ortaz

Я понимаю, как поступает кодер.

Если тебя смущает конкретное определение, значит ты не понимаешь сути кодирования.

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

Предположим, что мы кодируем строку "ААБББВВВВ" с алфавитом АБВ
кодер:
1) инициализируем таблицу частот для алфавита, т.к. у нас еще нет статистики по количеству вхождения каждого символа строки, начальный вес для всех символов алфавита считаем 1, таким образом таблица частот выглядит как А=1;Б=1;В=1
2) строим кодовое дерево согласно таблице частот (А=0; Б=10; В=11)
3) кодируем очередной символ сообщения (первый символ сообщения А и текущее битовое представление 0, таким образом первый символ будет закодирован одним битом)
4) обновляем таблицу частот символом который был закодирован (А=2;Б=1;В=1)
5) повторяем с пункта 2 и так до конца сообщения
Как видно, при после каждого закодированного символа, обновляется таблица частот и соответственно пересчитывается кодовое дерево. Таким образом в битовом потоке для каждого повторяющегося символа уникальный код может отличаться.

декодер:
Для однозначного декодирования сообщения, декодер должен знать алфавит.
У декодера отличается только 3 пункт :
3) читаем битовый поток пока не декодируем первый символ по таблице построенной в пунктах 1 и 2 (первый символ у нас был закодирован 0, соответственно по таблице мы определили, что первый символ сообщения А)

Есть множество разных реализаций и оптимизаций, но общий смысл всегда похож. Надеюсь я смог объяснить.

@Ortaz · 04.01.2013, 15:08 **[ТС]**

Оо Спасибо, про то, что уникальные коды отличаются я не знал..

@f0xic · 26.01.2016, 15:12

Ortaz, день добрый. та же проблема. Если вы разобрались не могли бы вы пояснить как можно декодировать адаптивный алгоритм? Откуда взять алфавит?

@Ortaz · 29.01.2016, 05:34 **[ТС]**

Сообщение от f0xic

Ortaz, день добрый. та же проблема. Если вы разобрались не могли бы вы пояснить как можно декодировать адаптивный алгоритм? Откуда взять алфавит?

Алфавит известен и кодеру и декодеру. В общем-то в последнем сообщении от x128 хорошо алгоритм написан.
Кодер: получаем символ, кодируем его, добавляем в таблицу частот (в результате чего для следующего символа кодовое дерево другое уже).
Декодер: считываем биты, пока не считается какой-либо символ в соответствии с кодовым деревом, декодируем его, добавляем в таблицу частот (и опять кодовое дерево перестраивается в точности также, как перестраивалось бы при кодировании).
Так как таблицы частот и кодовые дереьвя на одних и тех же этапах у кодера и декодера одинаковые, то и символы будут кодироваться/декодироваться одинаково, в соответствии друг с другом.

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

@f0xic · 05.02.2016, 14:29

Ortaz, Насколько мне известно, в адаптивном методе размер кодируемого символа может быть из любого количества бит. Так вот как декодеру узнать этот размер кодируемого символа, если он не знает как кодировал кодер?

@Ortaz · 07.02.2016, 15:53 **[ТС]**

Сообщение от f0xic

Так вот как декодеру узнать этот размер кодируемого символа, если он не знает как кодировал кодер?

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

@f0xic · 08.02.2016, 15:07

Ortaz, Так вот как узнать по сколько бит считывать? Какой размер у закодированного символа? Если есть только последовательность закодированных бит. Обычно один символ равен одному байту (8 бит), но это же не всегда так. Так вот как узнать по сколько надо бит считывать, чтобы считать один символ и потом его в дерево записать?

Добавлено через 9 минут
Ortaz, Или вы имеете ввиду, что считывать надо по одному биту начинать и добавлять его в дерево, а по мере роста дерева увеличивать количество бит для сравнения?)

@Shamil1 · 08.02.2016, 16:33

f0xic,
при кодировании дерево добавляется к закодированному тексту
не существует способа восстановить дерево по закодированному тексту

@Ortaz · 08.02.2016, 16:43 **[ТС]**

Сообщение от f0xic

Ortaz, Или вы имеете ввиду, что считывать надо по одному биту начинать и добавлять его в дерево, а по мере роста дерева увеличивать количество бит для сравнения?)

Смотри, в любой момент времени у тебя есть дерево кодировки. Допустим, (просто из головы) в какой-то момент у тебя дерево 10 = а 110 = б 111 = с. На вход подаётся 1111101110... Ты по 1 биту считываешь и по дереву движешься. Как только дойдёшь до любого листа, считай, символ считан. Теперь у тебя к счётчику считанного символа добавилась единица. Перестраиваешь дерево. Начинаешь побитово считывать новый символ. Изначально и у кодера и у декодера есть дерево, построенное на всём алфавите, при этом каждый символ входит по 0 раз (или по 1, так удобнее). После того, как закодировал 1 символ, кодер перестроил дерево, в соответствии с тем, что у закодированного символа индекс стал равен двум. Декодер будет код считывать по тому же дереву, по которому кодер кодировал. Поэтому символ считает ровно тот, который был закодирован. И точно также добавит единицу к индексу и перестроит дерево потом.

@f0xic · 09.02.2016, 01:28

Shamil1, нет в адаптивном методе Хаффмана дерева вначале закодированного текста, это в обычном алгоритме так. А у меня случай, когда вообще нет дерева, нет таблицы количества символов. Есть просто набор бит, которые были закодированы именно адаптивным алгоритмом. Если считать, что один символ = 8 бит(ASCII код), то раскодировать вообще легко. Но бывают же случаи, когда символ кодировался 1 или 2 или 3мя битами, вот тогда и вопрос встаёт, как узнать сколько бит надо считывать, чтобы в дерево заносить? Нет вначале дерева.

>> Изначально и у кодера и у декодера есть дерево, построенное на всём алфавите

Так вот как раз нет дерева, надо за один проход по поступающим данным декодировать символы. Не считая, что их размер по 8 бит.

@Shamil1 · 09.02.2016, 09:57

Сообщение от f0xic

нет в адаптивном методе Хаффмана дерева вначале закодированного текста, это в обычном алгоритме так

Да, Вы правы. В адаптивном методе эта таблица "размазана" по тексту.

Сообщение от f0xic

Если считать, что один символ = 8 бит(ASCII код), то раскодировать вообще легко.

Закодированные символы (коды символов) имеют разные размеры. В этом суть "сжатия на основе частот".
Алфавит, используемый в тексте, который мы собираемся закодировать, должен быть известен заранее. Обычно считается, что алфавит - это все возможные байты.

Сообщение от f0xic

Но бывают же случаи, когда символ кодировался 1 или 2 или 3мя битами, вот тогда и вопрос встаёт, как узнать сколько бит надо считывать, чтобы в дерево заносить? Нет вначале дерева.

В начале есть дерево, в котором "нулевой код". Закодированный поток может начинаться только с кодов, которые уже присутствуют в дереве.

@Ortaz · 09.02.2016, 13:31 **[ТС]**

Сообщение от f0xic

Так вот как раз нет дерева, надо за один проход по поступающим данным декодировать символы. Не считая, что их размер по 8 бит.

У вас есть дерево на основе алфавита. Вы неправильно понимаете суть адаптивного кодирования.

Сообщение от f0xic

это в обычном алгоритме так.

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

@f0xic · 10.02.2016, 00:33

Ortaz, Вот возьмем к примеру закодированную последовательность 1001 1101 1111 0110. Что с ней делать дальше? Брать под одному биту и смотреть не лист ли это в дереве? Берем 1. Смотрим - ага, ее нет в дереве, значит добавляем? Вряд ли так...

Сообщение от Shamil1

Алфавит, используемый в тексте, который мы собираемся закодировать, должен быть известен заранее. Обычно считается, что алфавит - это все возможные байты.

А вот если не "обычно"? Как считать? Надо же алгоритм написать под все случаи, а не кода символ занимает один байт.

Сообщение от Ortaz

Допустим, (просто из головы) в какой-то момент у тебя дерево 10 = а 110 = б 111 = с. На вход подаётся 1111101110... Ты по 1 биту считываешь и по дереву движешься. Как только дойдёшь до любого листа, считай, символ считан. Теперь у тебя к счётчику считанного символа добавилась единица. Перестраиваешь дерево. Начинаешь побитово считывать новый символ. Изначально и у кодера и у декодера есть дерево, построенное на всём алфавите, при этом каждый символ входит по 0 раз (или по 1, так удобнее). После того, как закодировал 1 символ, кодер перестроил дерево, в соответствии с тем, что у закодированного символа индекс стал равен двум.

Это всё понятно при варианте, опять же, когда есть именно буквы, то есть символы, занимающие 1 байт. А если кодер кодировал символ по 3 бита что делать?

@Ortaz · 10.02.2016, 00:48 **[ТС]**

Сообщение от f0xic

Вот возьмем к примеру закодированную последовательность 1001 1101 1111 0110.

Откуда взялась эта последовательность? Её кодер передал? Распишите по пунктам, как её кодер получал.

Сообщение от f0xic

Это всё понятно при варианте, опять же, когда есть именно буквы, то есть символы, занимающие 1 байт. А если кодер кодировал символ по 3 бита что делать?

"10 = а 110 = б 111 = с. "
Вы видите у меня здесь символы, занимающие 1 байт? Я - нет.

Добавлено через 12 минут

Сообщение от x128

Для понимания процесса адаптивного кодирования, нужно четко представлять и понимать классический метод. Объяснять классический алгоритм я не буду, т.к. на эту тему есть множество статей и описаний где все разложено по полочкам и с примерами. В предыдущем ответе я описал суть, попробую повторить на пальцах...
Предположим, что мы кодируем строку "ААБББВВВВ" с алфавитом АБВ
кодер:
1) инициализируем таблицу частот для алфавита, т.к. у нас еще нет статистики по количеству вхождения каждого символа строки, начальный вес для всех символов алфавита считаем 1, таким образом таблица частот выглядит как А=1;Б=1;В=1
2) строим кодовое дерево согласно таблице частот (А=0; Б=10; В=11)
3) кодируем очередной символ сообщения (первый символ сообщения А и текущее битовое представление 0, таким образом первый символ будет закодирован одним битом)
4) обновляем таблицу частот символом который был закодирован (А=2;Б=1;В=1)
5) повторяем с пункта 2 и так до конца сообщения
Как видно, при после каждого закодированного символа, обновляется таблица частот и соответственно пересчитывается кодовое дерево. Таким образом в битовом потоке для каждого повторяющегося символа уникальный код может отличаться.
декодер:
Для однозначного декодирования сообщения, декодер должен знать алфавит.
У декодера отличается только 3 пункт :
3) читаем битовый поток пока не декодируем первый символ по таблице построенной в пунктах 1 и 2 (первый символ у нас был закодирован 0, соответственно по таблице мы определили, что первый символ сообщения А)
Есть множество разных реализаций и оптимизаций, но общий смысл всегда похож. Надеюсь я смог объяснить.

Советую сесть с листочком и ручкой и проделать то же самое для алфавита А Б В Г Д. Весь процесс кодировки слова БАВБА, например. Вы поймёте, в чём именно у вас ошибка и как работает декодер. Мне 3 года назад помогло

@Shamil1 · 10.02.2016, 01:19

Сообщение от f0xic

А вот если не "обычно"? Как считать? Надо же алгоритм написать под все случаи, а не кода символ занимает один байт.

Алгоритм выглядит примерно так:

C#
1
2
3
4
5
6
7
8
9
for(var symbol = Escape; symbol != EndOfText; symbol = ReadCode())
{
    if(symbol == Escape)
    {
        symbol = ReadSymbol();
        RebuildTree();
    }
    result.Add(symbol);
}

Функция ReadCode считывает из потока по одному биту и передвигается по дереву, пока не дойдёт до листа. Если в листе стоп-символ, то следом за ним идёт новый, не встречавшийся ранее, символ алфавита. И у нас должна быть функция ReadSymbol, которая умеет считывать из потока символ алфавита. Этот символ может быть переменной длины (как, например, юникод). А функция ReadSymbol является одним из аргументов алгоритма.

Не зная алфавита, невозможно раскодировать текст. Более того, не зная алфавита, невозможно даже просто прочитать обычный, не закодированный текст.

Кликните здесь для просмотра всего текста

Вот Вам слово, написанное алфавитом, который я только что придумал: "932847382101238775". Вы можете разбить его на отдельные символы (буквы)? Оно даже не закодировано. Как Вы себе представляете чтение сообщения без знания алфавита?

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

@Ortaz 3 / 0 / 0 Регистрация: 02.01.2013 Сообщений: 47

	Адаптивное кодирование Хаффмана 02.01.2013, 05:18. Показов 8321. Ответов 21 Метки нет (Все метки) Задали курсовую "Реализация кодирования текста адаптивным алгоритмом Хаффмана". Разобрался с обычным кодированием (ну вроде бы всё понятно, строим дерево, кодируем от корня до вершин, и т.д., при декодировании пользуемся табличкой) С адаптивным же возникли проблемы. Неоднократно прочитал статью на Вики и ещё море материала РуНета, я вроде бы даже понял метод построения дерева (считываем символ, если не было, строим доп. ветку, если был, увеличиваем нужные веса вершин на 1, меняем если надо, вроде бы всё понятно.). И вот тут возникает проблема. Написав маленький пример на листочке, я понял, что не имею никакого представления, каким образом декодировать сообщение О_о В обычном алгоритме всё было ясно, пользуемся табличкой, присылаемой перед сообщением, а здесь декодер должен каким-то невероятным образом восстановить исходное дерево? За месяц дум, я так и не пришёл хотя бы к тому, как декодер поймёт, где кончается код 1 символа и начинается другой, коды же переменной длины, сообщение может быть огромным и т.д. Прошу помочь объяснить мне сию суть, желательно с примером кодирования небольшого сообщения, полученными кодами и декодировкой. Заранее спасибо 0

@Igor3D 1969 / 825 / 115 Регистрация: 01.10.2012 Сообщений: 4,931 Записей в блоге: 2
	02.01.2013, 17:17
	"decompressor is one step behind compressor" Т.е. декодер в точности повторяет кодер, таблица не хранится, а воспроизводится. Встретив новую комбинацию кодер записывает ее напрямую + расширяет таблицу. А декодер видит ее и также добавляет. Вас видимо смущает что "более короткие комбинации являются началом более длинных", но этого не происходит. Некоторое время размер кодированных данных больше исходных (пока таблица разрастется), потом наступает эффект сжатия. Полагается что данные как-то коррелированы, иначе ничего не выходит (напр массив random float не сжимается) 0

@Ortaz 3 / 0 / 0 Регистрация: 02.01.2013 Сообщений: 47
	02.01.2013, 18:14 [ТС]
	Ничего не понял.. Я видимо упустил какой-то момент адаптивного кодирования. вот есть у нас последовательность 65000 нулей и единиц. Каким образом декодер поймёт, где кончается код 1 и начинается другой (я понимаю, что закодировано однозначно, я реализации декодирования не понимаю) и другой момент, а как он поймёт, какому коду соответстует какой символ? Т.е даже если он поймёт, что последовательность 001 является символом, как он узнает, какой именно это символ? 0

@x128 240 / 218 / 46 Регистрация: 17.04.2010 Сообщений: 526
	03.01.2013, 10:33
	Ortaz, смысл в том, что кодовое дерево перестраивается по мере поступления символов. Кодер и декодер делают это одинаково. В начале процесса кодирования, таблица частот содержит единицы для всех символов алфавита. При поступлении очередного символа, увеличивается вес, перестраивается дерево и кодируется этот символ. Декодер поступает аналогичным образом. 0

@Ortaz 3 / 0 / 0 Регистрация: 02.01.2013 Сообщений: 47
	04.01.2013, 15:08 [ТС]
	Оо Спасибо, про то, что уникальные коды отличаются я не знал.. 0

@f0xic 0 / 0 / 0 Регистрация: 26.01.2016 Сообщений: 5
	26.01.2016, 15:12
	Ortaz, день добрый. та же проблема. Если вы разобрались не могли бы вы пояснить как можно декодировать адаптивный алгоритм? Откуда взять алфавит? 0

@f0xic 0 / 0 / 0 Регистрация: 26.01.2016 Сообщений: 5
	05.02.2016, 14:29
	Ortaz, Насколько мне известно, в адаптивном методе размер кодируемого символа может быть из любого количества бит. Так вот как декодеру узнать этот размер кодируемого символа, если он не знает как кодировал кодер? 0

@f0xic 0 / 0 / 0 Регистрация: 26.01.2016 Сообщений: 5
	08.02.2016, 15:07
	Ortaz, Так вот как узнать по сколько бит считывать? Какой размер у закодированного символа? Если есть только последовательность закодированных бит. Обычно один символ равен одному байту (8 бит), но это же не всегда так. Так вот как узнать по сколько надо бит считывать, чтобы считать один символ и потом его в дерево записать? Добавлено через 9 минут Ortaz, Или вы имеете ввиду, что считывать надо по одному биту начинать и добавлять его в дерево, а по мере роста дерева увеличивать количество бит для сравнения?) 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	08.02.2016, 16:33
	f0xic, при кодировании дерево добавляется к закодированному тексту не существует способа восстановить дерево по закодированному тексту 0

@f0xic 0 / 0 / 0 Регистрация: 26.01.2016 Сообщений: 5
	09.02.2016, 01:28
	Shamil1, нет в адаптивном методе Хаффмана дерева вначале закодированного текста, это в обычном алгоритме так. А у меня случай, когда вообще нет дерева, нет таблицы количества символов. Есть просто набор бит, которые были закодированы именно адаптивным алгоритмом. Если считать, что один символ = 8 бит(ASCII код), то раскодировать вообще легко. Но бывают же случаи, когда символ кодировался 1 или 2 или 3мя битами, вот тогда и вопрос встаёт, как узнать сколько бит надо считывать, чтобы в дерево заносить? Нет вначале дерева. >> Изначально и у кодера и у декодера есть дерево, построенное на всём алфавите Так вот как раз нет дерева, надо за один проход по поступающим данным декодировать символы. Не считая, что их размер по 8 бит. 0