Это фактически взаимодействует с «отдыхом» декомпрессии Хаффмана.Что именно вам здесь нужно, зависит от того, намереваетесь ли вы сделать эффективное декодирование на основе таблиц или пошаговое обход дерева.Вход не может быть разделен без декодирования, потому что вы найдете длину кода только после того, как декодируете, какой символ он представляет.После декодирования нет большого смысла в разбиении, поэтому на самом деле мы получаем только декодер Хаффмана, а не разделитель битовых строк.
Для побитового блуждания по дереву все, что вам нужнонужен какой-то способ доступа к какому-либо конкретному биту (с учетом его индекса) из массива байтов.Вы также можете использовать приведенную ниже методику с размером блока 1 бит.
Для более эффективного декодирования вам необходим буфер, из которого вы можете извлечь блок битов, если ваша заранее заданная максимальная длина кода, скажем,15 бит или около того [1] .Специфика зависит от порядка, в котором ваши коды упакованы в байты, то есть от того, заполнены ли байты lsb-to-msb или msb-to-lsb, и от того, где в вашей переменной буфера вы хотите сохранить биты.Например, здесь я держу биты в буфере рядом с lsb буфера и предполагаю, что если код разделен на два байта, то он находится в lsb первого байта и в msb второго байта [2] (не тестировалось):
var rawindex = 0;
var buffer = 0;
var nbits = 0;
var done = false;
var blockmask = (1 << MAX_CODELEN) - 1;
while (!done) {
// refill buffer
while (nbits < MAX_CODELEN && rawindex < data.length) {
buffer = (buffer << 8) | data[rawindex++];
nbits += 8;
}
if (nbits < MAX_CODELEN) {
// this can happen at the end of the data
buffer <<= MAX_CODELEN - nbits;
nbits = MAX_CODELEN;
}
// get block from buffer
var block = (buffer >> (nbits - MAX_CODELEN)) & blockmask;
// decode by table lookup
var sym = table[block];
// drop only bits that really belong to the symbol
nbits -= bitlengthOf(sym);
...
// use the symbol somehow
}
Здесь показана простейшая стратегия декодирования на основе таблиц, простой поиск.Пара символ / длина может быть объектом или храниться в двух отдельных массивах Uint8Array или кодироваться в один массив Uint16Array, такого рода вещи.Создать таблицу просто, например, в псевдокоде:
# for each symbol/code do this:
bottomSize = maxCodeLen - codeLen
topBits = code << bottomSize
for bottom in inclusive_range(0, (1 << bottomSize) - 1):
table[topBits | bottom] = (symbol, codeLen)
Variants
Упаковка кодов в байты от lsb вверх изменяет поток битов.Чтобы собрать код в буфере, биты должны входить с верхней стороны буфера и уходить снизу:
// refill step
buffer |= data[rawindex++] << nbits;
nbits += 8;
...
// get block to decode
var block = buffer & blockmask;
// decode by table lookup
var sym = table[block];
// drop bits
buffer >>= getlengthOf(sym);
Таблица также изменилась, теперь заполнение находится в старших битахиндекса таблицы, распределяя записи, принадлежащие одному символу, вместо того, чтобы помещать их в непрерывный диапазон (не проверялось, показывая битовые записи таблицы с длиной 5-битного кода):
// for each symbol/code:
var paddingCount = MAX_CODELEN - codeLen;
for (var padding = 0; padding < (1 << paddingCount); padding++)
table[(padding << codelen) | code] = (symbol << 5) + codeLen;
[1]: большая максимальная длина кода делает таблицу декодирования очень большой, а MAX_CODELEN> 25 рискует переполнить буфер.Есть способы обойти это, но супер длинные символы в любом случае не очень полезны.
[2]: это не то, что делает DELFATE.