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

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

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

Задали курсовую "Реализация кодирования текста адаптивным алгоритмом Хаффмана".
Разобрался с обычным кодированием (ну вроде бы всё понятно, строим дерево, кодируем от корня до вершин, и т.д., при декодировании пользуемся табличкой)
С адаптивным же возникли проблемы. Неоднократно прочитал статью на Вики и ещё море материала РуНета, я вроде бы даже понял метод построения дерева (считываем символ, если не было, строим доп. ветку, если был, увеличиваем нужные веса вершин на 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#

for(var symbol = Escape; symbol != EndOfText; symbol = ReadCode())
{
    if(symbol == Escape)
    {
        symbol = ReadSymbol();
        RebuildTree();
    }
    result.Add(symbol);
}

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

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

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

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

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

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

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

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

@Ortaz 3 / 0 / 0 Регистрация: 02.01.2013 Сообщений: 47
	03.01.2013, 22:11 [ТС]	5
	Сообщение от x128 Декодер поступает аналогичным образом. 2 раза сказал, что не понимаю этой фразы... Я понимаю, как поступает кодер. Ему поступает символ "а" он в алфавите что-то там делает. Пусть в итоге символ "а" имеет код 0010101 1.Декодер как считывает его? Побитово? Поступила ему 0, откуда он знает чё с ней делать? 2.А если полностью считывает, ну считал он код 0010101, каким образом он узнает, что это буква "a", а не любая другая? Второй вопрос по другому. Если мы заменим в изначальном тексте все символы "а" на символ "b", которого там не было, то после построения дерева новый символ закодируется в точности так же, как и кодировался символ "a" в старом тексте. Т.е. код будет тот же. Откуда декодер, даже поняв всё что угодно, узнает, что это "b", а не "a", и не что-то левое?! Если ему поступает только сам закодированный текст (Проблема в том, что Вы Все знаете какой-то момент, который я не знаю, не понимаю и не могу понять, а Вы не можете его сформулировать или не догадываетесь, что этот момент может быть кому-то непонятен=) По этому я и попросил пример, желательно пошаговый) 0

@x128 240 / 218 / 46 Регистрация: 17.04.2010 Сообщений: 526
	03.01.2013, 23:52	6
	Сообщение от 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, соответственно по таблице мы определили, что первый символ сообщения А) Есть множество разных реализаций и оптимизаций, но общий смысл всегда похож. Надеюсь я смог объяснить. 0

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

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

@Ortaz 3 / 0 / 0 Регистрация: 02.01.2013 Сообщений: 47
	29.01.2016, 05:34 [ТС]	9
	Сообщение от f0xic Ortaz, день добрый. та же проблема. Если вы разобрались не могли бы вы пояснить как можно декодировать адаптивный алгоритм? Откуда взять алфавит? Алфавит известен и кодеру и декодеру. В общем-то в последнем сообщении от x128 хорошо алгоритм написан. Кодер: получаем символ, кодируем его, добавляем в таблицу частот (в результате чего для следующего символа кодовое дерево другое уже). Декодер: считываем биты, пока не считается какой-либо символ в соответствии с кодовым деревом, декодируем его, добавляем в таблицу частот (и опять кодовое дерево перестраивается в точности также, как перестраивалось бы при кодировании). Так как таблицы частот и кодовые дереьвя на одних и тех же этапах у кодера и декодера одинаковые, то и символы будут кодироваться/декодироваться одинаково, в соответствии друг с другом. У меня была проблема, что я не понимал, что в каждый момент времени у символа может быть разная кодировка, а не каждый раз одна и та же. 0

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

	10.02.2016, 01:19

@Ortaz 3 / 0 / 0 Регистрация: 02.01.2013 Сообщений: 47
	07.02.2016, 15:53 [ТС]	11
	Сообщение от f0xic Так вот как декодеру узнать этот размер кодируемого символа, если он не знает как кодировал кодер? Он строит в точности такое же дерево кодировки, как делает кодер. Ровно те же шаги совершает. Тольк окодеру на вход подаются символы для кодирования, после чего они добавляются в дерево, а декодеу на вход подаются закодированные символы, он их декодирует согласно текущему дерево и перестраивает дерево, добавляя декодированный символ 0

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

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

@Ortaz 3 / 0 / 0 Регистрация: 02.01.2013 Сообщений: 47
	08.02.2016, 16:43 [ТС]	14
	Сообщение от f0xic Ortaz, Или вы имеете ввиду, что считывать надо по одному биту начинать и добавлять его в дерево, а по мере роста дерева увеличивать количество бит для сравнения?) Смотри, в любой момент времени у тебя есть дерево кодировки. Допустим, (просто из головы) в какой-то момент у тебя дерево 10 = а 110 = б 111 = с. На вход подаётся 1111101110... Ты по 1 биту считываешь и по дереву движешься. Как только дойдёшь до любого листа, считай, символ считан. Теперь у тебя к счётчику считанного символа добавилась единица. Перестраиваешь дерево. Начинаешь побитово считывать новый символ. Изначально и у кодера и у декодера есть дерево, построенное на всём алфавите, при этом каждый символ входит по 0 раз (или по 1, так удобнее). После того, как закодировал 1 символ, кодер перестроил дерево, в соответствии с тем, что у закодированного символа индекс стал равен двум. Декодер будет код считывать по тому же дереву, по которому кодер кодировал. Поэтому символ считает ровно тот, который был закодирован. И точно также добавит единицу к индексу и перестроит дерево потом. 0

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

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	09.02.2016, 09:57	16
	Сообщение от f0xic нет в адаптивном методе Хаффмана дерева вначале закодированного текста, это в обычном алгоритме так Да, Вы правы. В адаптивном методе эта таблица "размазана" по тексту. Сообщение от f0xic Если считать, что один символ = 8 бит(ASCII код), то раскодировать вообще легко. Закодированные символы (коды символов) имеют разные размеры. В этом суть "сжатия на основе частот". Алфавит, используемый в тексте, который мы собираемся закодировать, должен быть известен заранее. Обычно считается, что алфавит - это все возможные байты. Сообщение от f0xic Но бывают же случаи, когда символ кодировался 1 или 2 или 3мя битами, вот тогда и вопрос встаёт, как узнать сколько бит надо считывать, чтобы в дерево заносить? Нет вначале дерева. В начале есть дерево, в котором "нулевой код". Закодированный поток может начинаться только с кодов, которые уже присутствуют в дереве. 0

@Ortaz 3 / 0 / 0 Регистрация: 02.01.2013 Сообщений: 47
	09.02.2016, 13:31 [ТС]	17
	Сообщение от f0xic Так вот как раз нет дерева, надо за один проход по поступающим данным декодировать символы. Не считая, что их размер по 8 бит. У вас есть дерево на основе алфавита. Вы неправильно понимаете суть адаптивного кодирования. Сообщение от f0xic это в обычном алгоритме так. В обычном алгоритме вообще матрица кодировки передаётся. В которой частые символы закодированы коротким кодом. А в адаптивном как раз-таки суть, что он после каждого считанного символа перестраивает дерево, уменьшая длину кода символа, который мы встретили до этого (если он по частоте кого-то обогнал после увеличения индекса). По умолчанию дерево строится на алфавите, принимая, что частота стартовая одинаковая у всех символов. Без алфавита декодировка невозможна, а зная алфавит, в чём у вас проблема построить дерево? И кодеру и декодеру один и тот же алгоритм построения дерева построит его одинаково, так что и дальше кодировка/декодировка будет однозначной. 0

@f0xic 0 / 0 / 0 Регистрация: 26.01.2016 Сообщений: 5
	10.02.2016, 00:33	18
	Ortaz, Вот возьмем к примеру закодированную последовательность 1001 1101 1111 0110. Что с ней делать дальше? Брать под одному биту и смотреть не лист ли это в дереве? Берем 1. Смотрим - ага, ее нет в дереве, значит добавляем? Вряд ли так... Сообщение от Shamil1 Алфавит, используемый в тексте, который мы собираемся закодировать, должен быть известен заранее. Обычно считается, что алфавит - это все возможные байты. А вот если не "обычно"? Как считать? Надо же алгоритм написать под все случаи, а не кода символ занимает один байт. Сообщение от Ortaz Допустим, (просто из головы) в какой-то момент у тебя дерево 10 = а 110 = б 111 = с. На вход подаётся 1111101110... Ты по 1 биту считываешь и по дереву движешься. Как только дойдёшь до любого листа, считай, символ считан. Теперь у тебя к счётчику считанного символа добавилась единица. Перестраиваешь дерево. Начинаешь побитово считывать новый символ. Изначально и у кодера и у декодера есть дерево, построенное на всём алфавите, при этом каждый символ входит по 0 раз (или по 1, так удобнее). После того, как закодировал 1 символ, кодер перестроил дерево, в соответствии с тем, что у закодированного символа индекс стал равен двум. Это всё понятно при варианте, опять же, когда есть именно буквы, то есть символы, занимающие 1 байт. А если кодер кодировал символ по 3 бита что делать? 0

@Ortaz 3 / 0 / 0 Регистрация: 02.01.2013 Сообщений: 47
	10.02.2016, 00:48 [ТС]	19
	Сообщение от 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 года назад помогло 0