Http 2.0 и кодирование хаффманом (Huffman encoding/decoding)

Пытаюсь сделать кодирование/декодирование для Http2.0 с помощью алгоритма хаффмана, в обычной версии этого алгоритма, нужно прочитать входные данные, посмотреть частоту использования каждого символа, построить соответствие символа частоте, отсортировать по частоте, взять две самые маленькие частоты, соединить их в дерево в корне будет сумма этих частот, в левой ветви будет первый символ, в правой второй, потом взять следующие по мере возрастания две, соединить в дерево, далее эти два дерева соединить в одно и тд, пока не построим 1 больше дерево, таким образом далее если мы ходим закодировать какой-либо символ, мы ищем его в дереве, и строим его код побитово, используя путь по дереву к данному символу, левая ветвь - 0, правая ветвь 1.
Но вот в Http2.0 как я понял используется заранее составленная таблица:
https://http2.github.io/http2-... ffman.code

Я сначала подумал что надо просто по этой таблице сверять символы и выписывать результирующие значения, то есть например:

'w' (119) |1111000 78 [ 7]

Я думал что если я хочу закодировать букву w, я просто выписываю 1111000 в результирующий символ. Однако когда я посмотрел на примеры:

8c | Literal value (len = 12)
| Huffman encoded:
f1e3 c2e5 f23a 6ba0 ab90 f4ff | .....:k.....
| Decoded:
| www.example.com
| -> :authority:
| www.example.com

В данном случае www.example.com кодируется как hex: f1e3 c2e5 f23a 6ba0 ab90 f4ff, и как видно тут несоответствует результат таблице. Первые три w в данном случае должно кодироваться в 1 байт f1, а по каким правилам оно собственно получается? Ну и остальные символы которые встречаются 1 раз тоже не соотвествуют таблице, например 'x' должен кодироваться как 7 бит 1111001 ( 0x79 )

0

Хаффман рассматривает битовый поток, не зря там возле каждого символа длина в битах:

0

Да я тупанул, надо было считать биты ещё же. Тогда всё сходится, кроме последних символов, я накидал кодировщик, в итоге для строки

www.example.com получаю

f1e3 c2e5 f23a 6ba0 ab90 f480

В оригинале

f1e3 c2e5 f23a 6ba0 ab90 f4ff

Пробовал ещё строку из примера 'no-cache'

a8eb 1064 9ca0 у меня

в оригинале a8eb 1064 9cbf

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

Собственно ещё такой вопрос, а каким образом это всё дело можно раскодировать? По идее где-то в пакетах хтпп 2.0 должна быть таблица для декодировки? Потому что я не совсем понимаю как вот это можно раскодировать зная только длинну исходного текста f1e3 c2e5 f23a 6ba0 ab90 f4ff, ну вот допустим я на стороне сервера читаю первый байт, 0xf1 ( *11110001‬) , я же не могу быть увереным точно что там закодировано w, а если например там закодирован первый кусок какого-нибудь другого символа? Или сервер просто читает побитово и как только находит первое совпадение декодирует букву?

0

Код Хаффмана - префиксный, поэтому для декодирования строится дерево.
Идём от корня, на каждом нуле налево, на каждой единице направо.
Дошли до листа - символ найден, выводим и начинаем от корня

0

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

0

Что мешает построить дерево по кодам?

0