0 / 0 / 0
Регистрация: 15.06.2017
Сообщений: 3
1

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

15.06.2017, 02:12. Показов 586. Ответов 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

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.06.2017, 02:12
Ответы с готовыми решениями:

XML decoding & encoding
На проекте на тест-сервеhах данные в XML прописаны в таком виде: &#u044B; Подскажите что за...

RLE encoding / decoding в delphi
уважаемые форумчани у кого нибудь есть исходник алгоритма RLE кодирующий и декодирующий текста

Http-протокол без chanked encoding
Задача - написать на C++ лексический анализатор http-протокола без chunked encoding. Нужно, чтобы...

Чем отличается Encoding.Unicode от Encoding.UTF16
я вот что то не пойму чем отличается Encoding.Unicode от Encoding.UTF16? и почему в браузерах...

5
Фрилансер
3685 / 2055 / 566
Регистрация: 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
Фрилансер
3685 / 2055 / 566
Регистрация: 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
Фрилансер
3685 / 2055 / 566
Регистрация: 31.05.2009
Сообщений: 6,683
16.06.2017, 19:04 6
Что мешает построить дерево по кодам?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.06.2017, 19:04

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Почему реализация ГОСТ 89 работает с Encoding.UTF8 и не работает с Encoding.ASCII?
Класс GOSTCrypto //S-блок protected byte S_Block = { new byte {...

Huffman
Я почти всё сделал...строится бин. дерево... Остался вывод в файл! Как из совокупности нулей и...

Decoding str is not supported
class Person(): def __init__(self): self.data_person = def...

с Хаффманом, код рабочий, но мне пишут что точка входа не определена, хоть я и создал файл в проекте
#include <iostream> #include <vector> #include <map> #include <list> #include <fstream> using...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.