0 / 0 / 0
Регистрация: 15.06.2017
Сообщений: 3
|
|
1 | |
Http 2.0 и кодирование хаффманом (Huffman encoding/decoding)15.06.2017, 02:12. Показов 759. Ответов 5
Метки нет (Все метки)
Пытаюсь сделать кодирование/декодирование для 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
|
15.06.2017, 02:12 | |
Ответы с готовыми решениями:
5
XML decoding & encoding RLE encoding / decoding в delphi Http-протокол без chanked encoding Чем отличается Encoding.Unicode от Encoding.UTF16 |
Фрилансер
3705 / 2077 / 567
Регистрация: 31.05.2009
Сообщений: 6,683
|
|
15.06.2017, 03:57 | 2 |
Хаффман рассматривает битовый поток, не зря там возле каждого символа длина в битах:
Код
f 1 e 3 c 2 e 5 ... 1111 0001 1110 0011 1100 0010 1110 0101 ... 1111000 1111000 1111000 010111 00101 w w w . e
0
|
0 / 0 / 0
Регистрация: 15.06.2017
Сообщений: 3
|
|
15.06.2017, 06:38 [ТС] | 3 |
Да я тупанул, надо было считать биты ещё же. Тогда всё сходится, кроме последних символов, я накидал кодировщик, в итоге для строки
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
|
Фрилансер
3705 / 2077 / 567
Регистрация: 31.05.2009
Сообщений: 6,683
|
|
15.06.2017, 11:35 | 4 |
Код Хаффмана - префиксный, поэтому для декодирования строится дерево.
Идём от корня, на каждом нуле налево, на каждой единице направо. Дошли до листа - символ найден, выводим и начинаем от корня
0
|
0 / 0 / 0
Регистрация: 15.06.2017
Сообщений: 3
|
|
15.06.2017, 23:19 [ТС] | 5 |
Да это в обычном варианте, но ведь тут у нас нету данных для построения дерева. Есть только эта табличка, в которой просто соответствия без весов. Походу придётся декодить тупо сверяясь с таблицей
0
|
Фрилансер
3705 / 2077 / 567
Регистрация: 31.05.2009
Сообщений: 6,683
|
|
16.06.2017, 19:04 | 6 |
Что мешает построить дерево по кодам?
0
|
16.06.2017, 19:04 | |
16.06.2017, 19:04 | |
Помогаю со студенческими работами здесь
6
Почему реализация ГОСТ 89 работает с Encoding.UTF8 и не работает с Encoding.ASCII? Huffman Decoding str is not supported с Хаффманом, код рабочий, но мне пишут что точка входа не определена, хоть я и создал файл в проекте Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |