Часто я замечаю, что меня увлекает какой-то программный продукт или алгоритм, и я настолько увлекся, что думаю про себя: "Я это сделаю!" И каждый раз думаю: не может быть, чтобы это было так сложно построить... А потом понимаю, что это так, и вижу, как все мои надежды и мечты рушатся. 😭 Хорошо, небольшое преувеличение для дополнительной драмы. Но в большинстве случаев я обнаружил, что когда я начинаю такое приключение, мне трудно найти хорошие исходники, особенно на Javascript, которые я могу понять. Помня об этом, я решил написать этот пост в надежде, что кто-то еще, кто также интересуется этими эзотерическими темами, может найти его полезным.
Когда я пытался понять, как читать файл JPEG в Javascript, был сегмент под названием DHT: определение таблицы Хаффмана. Не зная, что такое Хаффман, я, конечно, профессионально погуглил. Это оказался алгоритм сжатия текста. Например, кодировка Хаффмана также используется в алгоритме дефляции, который, в свою очередь, используется в наиболее знакомом алгоритме Gzip. Очевидно, первое, о чем я подумал, это то, что я должен построить это на Javascript. Я имею в виду, как трудно это может быть правильно? 🤓
Итак, для всех, кто заинтересован, нижеследующее представляет собой исследование того, как реализовать кодирование Хаффмана в Javascript с нуля. В конце этого поста мы, надеюсь, создали рабочую библиотеку, способную кодировать и декодировать текст с кодированием Хаффмана. 🥹
К вашему сведению, я не ставлю точку с запятой, когда в этом нет необходимости. Эй, где разговор о сжатии текста, зачем тратить лишнее пространство. 🧐
Попутно мы также коснемся темы работы с двоичными данными в Javascript, потому что она понадобится нам при реализации кодирования Хаффмана.
Итак, первый вопрос: что такое кодирование Хаффмана?
Кодирование Хаффмана — это метод сжатия текста без потерь.
Что это значит? Это означает, что при кодировании Хаффмана исходный текст может храниться с меньшим количеством битов, по крайней мере, большую часть времени, без потери информации.
Если предположить, что мы работаем с текстом, в котором символы хранятся как 8 бит, 1 байт, то общее количество битов, необходимых для хранения текста из n символов, составляет n * 8 бит.
Так, например, если мы хотим сохранить текст: абракадабра длиной 11 символов, нам нужно 88 бит или 11 байт. Так как же мы можем хранить ту же информацию в меньшем количестве битов?
Как следует из названия, один из способов сделать это — использовать кодирование Хаффмана. Результатом кодирования Хаффмана является кодовая таблица переменной длины. Эта кодовая таблица сопоставляет символы с кодом, генерируемым в процессе кодирования. В среднем эти коды будут меньше 8 бит, необходимых для хранения фактического символа.
Так как же работает кодирование Хаффмана?
Создание таблицы частых контактов
Сначала мы начнем с создания таблицы частых контактов. Это таблица символов, основанная на возникновении. Затем эта таблица упорядочивается на основе частоты от самой высокой до самой низкой.
Если мы возьмем наш предыдущий текст: абракадабра, наша таблица частот будет выглядеть так:
a: 5 b: 2 r: 2 c: 1 d: 1
Создание дерева Хаффмана
Следующий шаг — преобразовать его в то, что называется деревом Хаффмана.
Начнем с того, что возьмем персонажей с наименьшей частотой. В нашем случае это c и d и преобразовать их в промежуточный узел, который представляет собой сумму обеих частот, и два листовых узла с соответствующими символами и частотами.
dc:2
d:1 c:1
Затем мы перемещаем этот новый промежуточный узел обратно в список на основе частоты узла. В нашем случае этот новый узел будет вставлен после r. Итак, наш новый список будет выглядеть так:
a: 5 b: 2 r: 2 dc: 2 -> Which is the node we just created.
Затем мы повторяем этот процесс, пока не останемся с одним узлом в нашем списке. Результирующий список будет выглядеть так:
rdcba: 11
И наше дерево Хаффмана выглядит так:
rdcba:11
rdc:4 ba:7
r:2 dc:2 b:2 a:5
d:1 c:1
Обратите внимание, что частота корневого узла представляет собой сумму всех символов.
Построение кодовой таблицы
Теперь из этого бинарного дерева мы можем построить нашу кодовую таблицу. Итак, как мы это сделаем? Что ж, мы идем вниз по дереву, и каждый раз, когда мы идем вправо, мы опускаемся вниз на 1, а когда мы идем влево, мы опускаемся вниз на 0, пока не достигнем конечного узла.
Для символа a мы сначала идем влево, а затем вправо, поэтому мы опускаем 01.
Если мы сделаем это для каждого символа в дереве, мы получим следующие коды:
a: 11
b: 10
r: 00
c: 011
d: 010
Сжатие данных
Чтобы сжать данные, вместо того, чтобы сохранять символ как есть, мы сохраняем код, связанный с символом, в приведенной выше таблице кодирования. В нашем примере абракадабра мы получим следующую кодировку:
11 10 00 11 011 11 010 11 10 00 11
Но мы не можем хранить только эти сжатые данные, потому что тогда у нас нет возможности их распаковать. Вам всегда нужно определенное «представление» о данных, то есть вам нужно знать, как их интерпретировать. Поэтому, чтобы распаковать эти данные, нам нужно сохранить нашу таблицу кодирования вместе со сжатыми данными. Поскольку нам нужно хранить эти дополнительные данные, особенно для более коротких текстов, мы фактически расширим наши данные, а не сократим их.
Обратите внимание, что выбор 1 = справа и 0 = слева произволен. Вы также можете использовать 0 для правого и 1 для левого. Также обратите внимание, что вы можете поменять местами второй и третий узлы и получить разные коды, но с одинаковым размером кода для одних и тех же символов. Таким образом, вы можете создать более одного дерева из одних и тех же входных данных. Конечный результат не имеет значения, потому что мы добавляем таблицу кодирования вместе со сжатыми данными.
Распаковка данных
Чтобы распаковать данные, мы можем просто найти последовательность битов в таблице кодирования, чтобы узнать, какой символ использовать.
Теперь давайте реализуем это на Javascript
Вы можете ввести или клонировать репозиторий отсюда: https://github.com/vincentcorbee/Huffman.
К вашему сведению, эта реализация основана на предположении, что каждый символ в исходном тексте может быть прочитан как 8-битное целое число без знака. Так что если вы чувствуете приключения, вы можете использовать многобайтовые символы. Кроме того, я стараюсь быть как можно более описательным в именах функций и переменных, поэтому, надеюсь, сам код может быть в значительной степени понятным.
Итак, начнем печатать. Сначала мы создаем новый каталог с именем huffman и инициализируем новый проект. Мы собираемся сделать это без каких-либо зависимостей. Но поскольку мы собираемся использовать Typescript, мы собираемся установить typescript и ts-node и types/nodes в зависимости от разработчиков.
touch huffman && cd huffman npm init -y npm i -D ts-node typescript @types/node npx tsc --init mkdir src && mkdir src/lib && mkdir src/modules && mkdir src/samples touch src/lib/index.ts && touch src/modules/index.ts && touch src/index.ts && touch src/types.ts
В index.ts добавьте следующее.
export * from './encode' export * from './decode'
В lib/index.ts добавьте следующее.
export * from './create-frequentie-table' export * from './create-huffman-tree' export * from './create-encoding-table' export * from './encode-data' export * from './to-array-buffer' export * from './get-bit-count'
И в modules/index.ts добавить.
export * from './binary-reader' export * from './binary-writer'
Весь вышеперечисленный функционал мы создадим в соответствующее время.
В нашей папке src создайте новый файл с именем encode.ts. В этом файле мы собираемся создать функцию, которая принимает строку и выводит буфер массива с нашими сжатыми данными вместе с таблицей кодирования.
import { createFrequentieTable, createHuffmanTree, createEncodingTable, encodeData, toArrayBuffer } from './lib'
export const encode = (input: string) => {
const frequentieTable = createFrequentieTable(input)
const huffmanTree = createHuffmanTree(frequentieTable)
const encodingTable = createEncodingTable(frequentieTable, huffmanTree)
const encodedData = encodeData(encodingTable)(input)
return toArrayBuffer(encodedData, encodingTable)
}
Внутри нашей функции encode мы сначала создаем таблицу частот. Затем мы используем эту функцию для создания нашего дерева Хаффмана. Используя таблицу частот и дерево Хаффмана, мы строим нашу таблицу кодирования. Затем мы можем продолжить и закодировать наши исходные данные. Последнее, что мы делаем, это объединяем наши закодированные данные и таблицу кодирования в буфер массива и возвращаем его.
Итак, первый шаг — создать нашу таблицу часто задаваемых вопросов. В нашей папке lib мы создаем новый файл с именем create-frequentie-tabel.ts.
import { FrequentieTable } from '../types'
export const createFrequentieTable = (input: string) => {
const frequentieTabel: FrequentieTable = {}
for (let i = 0, l = input.length; i < l; i++) {
const char = input.charAt(i)
if (frequentieTabel[char] !== undefined) {
frequentieTabel[char] ++
} else {
frequentieTabel[char] = 1
}
}
return frequentieTabel
}
В types.ts мы добавляем импортированный ранее тип.
export type FrequentieTable = Record<string, number>
В этой функции мы сначала создаем пустую таблицу. Затем мы перебираем каждый символ, и когда он находится в таблице, мы увеличиваем его значение, а если его нет в нашей таблице, мы добавляем его и устанавливаем его значение равным единице. Как только весь ввод обработан, мы возвращаем нашу таблицу.
Далее дерево Хаффмана. В нашей папке lib создайте файл с именем create-huffman-tree.ts.
import { FrequentieTable, HuffmanTree, IntermediaryNode, Node } from '../types'
const getNewIndex = (entries: Node[], count: number) => {
let index = entries.length - 1
while(index > 0) {
if (count <= entries[index][1]) return index
index--
}
return 0
}
const getSortedEntries = (frequentieTable: FrequentieTable): Node[] =>
Object.entries(frequentieTable).sort((a, b) => b[1] - a[1])
export const createHuffmanTree = (frequentieTable: FrequentieTable): HuffmanTree => {
const entries = getSortedEntries(frequentieTable)
while(entries.length > 1) {
const left = entries.pop() as Node
const right = entries.pop() as Node
const [charLeft, countLeft] = left
const [charRight, countRight] = right
const newCount = countLeft + countRight
const newIndex = getNewIndex(entries, newCount)
const intermediaryNode: IntermediaryNode = [`${charLeft}${charRight}`, newCount, [left, right]]
entries.splice(newIndex, 0, intermediaryNode)
}
return entries as HuffmanTree
}
Так что эта функция нуждается в дополнительных пояснениях. Поскольку мы создали нашу таблицу частот как простую хэш-карту, она не сортируется по частотам. Итак, сначала мы собираемся преобразовать его в отсортированный массив на основе частоты от наибольшей до наименьшей в форме:
[[строка, число]]
Затем мы проходим по нашему списку, и на каждой итерации мы создаем новый промежуточный узел и помещаем его обратно в список с правильным индексом на основе новой частоты нового узла. Промежуточный узел, который мы создаем, представляет собой тройку в виде [символы, частота, [левый узел, правый узел]].
Мы продолжаем этот процесс, пока не получим один узел, корень нашего дерева Хаффмана. Когда цикл завершается, мы возвращаем дерево Хаффмана.
Нам также нужно добавить несколько новых типов в types.ts.
// After previous types export type IntermediaryNode = [string, number, [Node, Node]] export type LeafNode = [string, number] export type Node = IntermediaryNode | LeafNode export type HuffmanTree = [IntermediaryNode]
Нет, мы создали функцию для нашего дерева Хаффмана, пришло время написать функцию, которая строит таблицу кодирования. В нашей папке lib создайте новый файл с именем create-encoding-table.ts.
import { EncodingTable, HuffmanTree, Node, Encoding, FrequentieTable } from '../types'
const traverseHuffmanTree = (node: Node, char: string, encoding: Encoding = []): Encoding => {
/* We don't need the count, so will only be using the characters and children */
const [characters, _count, children] = node
if (char === characters) return encoding
if (children) {
const [left, right] = children
/* If left node matches go left and add 0 to the encoding */
if (left[0].includes(char)) return traverseHuffmanTree(left, char, [...encoding, 0])
/* If right node matches go right and add 1 to the encoding */
if (right[0].includes(char)) return traverseHuffmanTree(right, char, [...encoding, 1])
}
throw Error(`No match found for: ${char}`)
}
const getCharacterEncoding = (huffmanTree: HuffmanTree) => (char: string) => {
const [rootNode] = huffmanTree
return traverseHuffmanTree(rootNode, char)
}
export const createEncodingTable = (frequentieTable: FrequentieTable, huffmanTree: HuffmanTree): EncodingTable =>
Object.keys(frequentieTable).reduce((table, char) => {
table[char] = getCharacterEncoding(huffmanTree)(char)
return table
}, {} as EncodingTable)
В этой функции мы собираемся сопоставить нашу таблицу частот и для каждого символа в таблице мы собираемся получить наш новый код символа из нашего дерева Хаффмана. Этот код будет массивом из 1 и 0. Для этого нам нужно пройти по дереву Хаффмана и найти соответствующий конечный узел.
Поэтому для каждого символа в таблице мы вызываем getCharacterEncoding с нашим деревом Хаффмана и символом, для которого мы хотим получить код. Затем эта функция вызывает traverseHuffmanTree с корневым узлом и персонажем.
В traverseHuffmanTree первое, что мы делаем, — проверяем, соответствует ли символ символу в узле. Если он совпадает, мы нашли соответствующий конечный узел и возвращаем кодировку, успех. 🥳 Обратите внимание, что на данный момент нас не волнует количество.
Если у нас нет совпадения, но есть дочерние элементы, то есть это промежуточный узел, и мы проверяем, содержат ли символы левого или правого узла тот символ, для которого мы хотим получить код.
Если левый совпадает, мы проходим по левому узлу и добавляем 0 к кодировке. И если правильное совпадение, мы проходим по правому узлу и добавляем 1 к кодировке.
Если у нас нет совпадения и ни один из дочерних элементов не включает символ, мы выдаем ошибку, потому что наш персонаж не существует в нашем дереве Хаффмана, и мы разрыдаемся. 😭
В types.ts добавьте следующие типы.
// After previous types export type Encoding = number[] export type EncodingTable = Record<string, Encoding>
Итак, на данный момент у нас есть все, что нам нужно, чтобы начать кодировать наши данные. Мы создали нашу таблицу частот, затем использовали ее для построения нашего дерева Хаффмана и, наконец, создали нашу таблицу кодирования.
В нашей папке lib мы создадим файл с именем encode-data.ts.
import { EncodedData, EncodingTable } from '../types'
export const encodeData = (encodingTable: EncodingTable) => (input: string): EncodedData =>
input
.split('')
.flatMap(char => encodingTable[char])
Также в types.ts добавьте следующее.
// After previous types export type EncodedData = number[]
Функция encodeData принимает таблицу кодирования и возвращает функцию, которая принимает строку, наш ввод. Затем мы разделяем эту строку на отдельные символы и для каждого символа выбираем наш соответствующий код, который представляет собой массив из 1 и 0. Мы используем flatMap, потому что возвращаем один массив из 1 и 0.
Теперь последнее, что нам нужно сделать, это взять наши закодированные данные и нашу таблицу кодирования и соединить их вместе. Мы собираемся хранить весь наш вывод в ArrayBuffer.
Мы собираемся создать два модуля, чтобы упростить работу с нашими двоичными данными. Один - читатель, а другой - писатель, который исходит из читателя. Сначала мы создадим двоичный считыватель. В модулях создайте файл с именем binary-reader.ts.
import { getBitCount } from "../lib"
export class BinaryReader {
protected chunk: number
protected pos: number
protected bitPos: number
protected bitCount: number
view: DataView
constructor(arrayBuffer: ArrayBuffer) {
this.view = new DataView(arrayBuffer)
this.pos = 0
this.bitPos = -1
this.chunk = 0
this.bitCount = 0
}
protected getData(type = 'Uint8') {
if (this.view.byteLength > this.pos) {
this.bitPos = -1
// @ts-ignore
return this.view[`get${type}`](this.pos++)
}
throw new RangeError()
}
get buffer () {
return this.view.buffer
}
getBytePosition() {
return this.pos
}
seek(pos: number) {
const oldPos = this.pos
this.pos = pos
return oldPos
}
peak(index = this.pos + 1) {
if (this.view.byteLength > index && index > -1) {
return this.view.getUint8(index)
}
return null
}
peakBit() {
const chunk = this.chunk
const pos = this.pos
const bitPos = this.bitPos
const bitCount = this.bitCount
const bit = this.getBit()
this.bitPos = bitPos
this.chunk = chunk
this.pos = pos
this.bitCount = bitCount
return bit
}
getPadSize() {
if (this.chunk === null) {
return 0
} else {
const bitCount = getBitCount(this.chunk)
return 8 - bitCount
}
}
getBitPos() {
return getBitCount(this.chunk) - 1 + this.getPadSize()
}
getBit() {
if (this.bitPos === -1) {
this.chunk = this.getData()
this.bitPos = this.getBitPos()
this.bitCount = getBitCount(this.chunk)
}
if (this.chunk === null) return null
const bitCount = this.bitCount
const bit = this.bitPos >= bitCount ? 0 : (this.chunk >> this.bitPos) & 1
this.bitPos--
return bit
}
getUint32() {
return (
(this.getData() << 24) |
(this.getData() << 16) |
(this.getData() << 8) |
this.getData()
)
}
getUint16() {
return (this.getData() << 8) | this.getData()
}
getUint8() {
return this.getData()
}
}
Конструктор BinaryReader принимает в качестве входных данных ArrayBuffer. Что такое ArrayBuffer? Это массив фиксированной длины, содержащий необработанные байты. Вы ничего не можете с этим поделать. Это просто контейнер. Чтобы читать двоичные данные, вам нужно определенное окно в ваши данные. Чтобы понять, зачем вам это нужно, рассмотрим следующее. Допустим, у вас есть следующая последовательность байтов:
011000010110001001100011
Откуда ты знаешь, что это значит? Это все зависит от контекста, без него не знаешь, что читать. Допустим, приведенные выше данные являются частью текста, в котором используется кодировка ASCII. Тогда мы знаем, как это интерпретировать. Мы можем прочитать его как три блока 8-битных целых чисел без знака:
01100001|01100010|01100011
Три блока будут преобразованы в 97 98 99, которые представляют символы a b c.
Но если контекст диктует, что мы должны читать их как 8-битное целое число без знака и 16-битное целое число без знака, мы читаем последовательность как два блока:
01100001|0110001001100011
Затем два блока преобразуются в 97 и 25187. Значение этих двух чисел зависит от программного обеспечения, в котором они используются. Этот контекст также является тем, что мы будем предоставлять для того, как читать и интерпретировать наши данные.
В Javascript вы используете различные массивы, чтобы получить окно в буфер массива, например. Uint8Array для 8-битных целых чисел без знака, Uint16Array для 16-битных целых чисел без знака и т. д. Вместо использования различных типов массивов наш двоичный считыватель будет использовать DataView. Это удобный класс для чтения и записи различных типов чисел. Кроме того, DataView также обрабатывает порядок следования байтов, то есть порядок следования байтов.
Наш класс предоставляет методы для чтения байтов как uint8, uint16 и uint32. Также мы добавили возможность чтения отдельных битов. Каждый из этих методов внутренне вызывает getData с соответствующим числовым типом. Эта функция, в свою очередь, вызывает соответствующую функцию в нашем представлении данных с правильным смещением, а затем обновляет внутреннюю позицию.
Причина, по которой мы сохраняем внутреннюю позицию, заключается в том, что мы можем непрерывно считывать данные без необходимости вручную указывать смещение относительно того, где наше представление должно искать в нашем ArrayBuffer.
Обратите внимание, что вместо использования dataView.getUint32 и dataView.getUint16 мы смещаем наш результат от getData на n битов. > и добавить следующий результат, если он есть. Причина, по которой мы это делаем, заключается в том, что мы можем повторно использовать getData и позволить этой функции обновлять нашу позицию для количества прочитанных нами байтов.
Наряду с этими методами чтения мы также можем использовать пиковые биты и пиковые байты или перейти к определенному смещению.
Теперь о нашем писателе. В модулях создайте файл с именем binary-writer.ts.
import { BinaryReader } from './binary-reader'
export class BinaryWriter extends BinaryReader {
constructor(length: number) {
super(new ArrayBuffer(length))
}
private setData(data: number, type = 'Uint8') {
let advance = 0
switch(type) {
case 'Uint16':
advance = 2
break;
case 'Uint32':
advance = 4
break;
default:
advance = 1
}
if (this.view.byteLength > this.pos) {
this.bitPos = -1
// @ts-ignore
this.view[`set${type}`](this.pos, data)
this.pos += advance
return this
}
return this
}
setUint32(data: number) {
return this.setData(data, 'Uint32')
}
setUint16(data: number) {
return this.setData(data, 'Uint16')
}
setUint8(data: number) {
return this.setData(data)
}
}
Конструктор этого класса берет длину и вызывает super с новым ArrayBuffer той длины, в которую мы будем записывать и/или читать наши данные. Этот класс расширяет читатель. Таким образом, наряду со всеми операциями чтения мы также можем записывать uint8, uint16 и uint32 в базовый массив ArrayBuffer. Метод setData также продвигает нашу текущую позицию в зависимости от типа числа, которое мы записываем.
Нет, пришло время написать фактическую функцию, которая создает наш вывод. Итак, в нашей папке lib создайте файл с именем to-array-buffer.ts.
import { BinaryWriter } from '../modules'
import { Encoding, EncodingTable, EncodedData } from '../types'
const getCharacterCode = (char: string) => char.charCodeAt(0)
const mapCodeToInteger = (code: Encoding) =>
code.reduce((acc, bit) => (acc << 1) | bit, 0)
const getByteCount = (bitCount: number) => {
const remainder = bitCount % 8
/* Round to whole bytes*/
return (bitCount + (remainder ? 8 - remainder : 0)) / 8
}
const mapEncodingTable = (encodingTable: EncodingTable) => {
let lengthEncodingTable = 0
const entries = Object.entries(encodingTable).map(([ char, code]) => {
const { length } = code
/*
We add 2 bytes for the length and character and 1 or 2 for the code depending
on wether it's code length is bigger then 8 bits
*/
lengthEncodingTable += 2 + (length > 8 ? 2 : 1)
/* For each code, return a triplet [ number, number, number ] */
return [length, getCharacterCode(char), mapCodeToInteger(code)]
})
return [ entries, lengthEncodingTable ] as const
}
export const toArrayBuffer = (data: EncodedData, encodingTable: EncodingTable) => {
const BYTE_COUNT_LENGTH_ENCODING_TABLE = 2
const BYTE_COUNT_LENGTH_ENCODED_DATA = 4
const PADDING_ENCODED_DATA = 1
const [ entries, lengthEncodingTable ]= mapEncodingTable(encodingTable)
const { length: bitCount } = data
const byteCount = getByteCount(bitCount)
const padCountEncodedData = bitCount % 8
const binaryWriter = new BinaryWriter(
byteCount +
BYTE_COUNT_LENGTH_ENCODING_TABLE +
BYTE_COUNT_LENGTH_ENCODED_DATA +
PADDING_ENCODED_DATA +
lengthEncodingTable)
binaryWriter.setUint16(lengthEncodingTable)
entries.forEach(([length, charCode, code]) => {
binaryWriter.setUint8(length)
binaryWriter.setUint8(charCode)
if (length > 8) binaryWriter.setUint16(code)
else binaryWriter.setUint8(code)
})
let chunk = 0
let index = 0
binaryWriter.setUint32(byteCount)
binaryWriter.setUint8(padCountEncodedData)
while (index < bitCount) {
if (index % 8 === 0 && index !== 0) {
binaryWriter.setUint8(chunk)
chunk = 0
}
/* Shift chunk one bit to the left and add current bit */
chunk = (chunk << 1) | data[index]
index++
}
if (chunk) {
/* We add padding to fill out the last chunk to a whole byte */
for (let pad = 0; pad < padCountEncodedData; pad++) chunk = chunk << 1
binaryWriter.setUint8(chunk)
}
return binaryWriter.buffer
}
Функция toArrayBuffer принимает в качестве входных данных наши закодированные данные и таблицу кодирования и выводит, как следует из названия функции, это ArrayBuffer.
Как упоминалось ранее, нам нужно сохранить пару вещей, чтобы позже интерпретировать наши двоичные данные, когда мы захотим их распаковать. Итак, что мы хотим сохранить в нашем ArrayBuffer:
- Таблица кодирования
- Длина таблицы кодирования
- Размер исходных данных в байтах
- Количество битов заполнения, если длина наших закодированных данных не находится на границе 8 бит.
- Наши закодированные данные
Итак, чтобы иметь возможность декодировать наши закодированные данные, нам нужно хранить некоторые метаданные. Эти дополнительные накладные расходы означают, как мы говорили в начале, что размер данных увеличивается. Пример абракадабра, который мы использовали в начале, на самом деле расширяется с 11 байтов (количество символов в строке) до 25 байтов.
Время декодировать
Теперь, когда мы закодировали наши данные, пришло время снова их декодировать.
В нашей папке src создайте файл с именем decode.ts. И добавьте следующее.
import { BinaryReader } from './modules'
import { HuffmanTree, IntermediaryNode, Node } from './types'
const getDecodedData = (binaryReader: BinaryReader) => (huffmanTree: HuffmanTree, bitCountEncodedData: number) => {
const [root] = huffmanTree
let bitsRead = 0
const traverse = (node: Node, binaryReader: BinaryReader): string => {
if (bitsRead > bitCountEncodedData) return ''
const nodes = node[2]
if (!nodes) return node[0]
const bit = binaryReader.getBit()
bitsRead++
if (bit !== null) {
if (nodes) return traverse(nodes[bit], binaryReader)
else return node[0]
} else {
return ''
}
}
let decodedData = '';
while (bitsRead < bitCountEncodedData && binaryReader.peakBit() !== null) {
decodedData += traverse(root, binaryReader)
}
return decodedData
}
const decodeHuffmanTree = (binaryReader: BinaryReader): HuffmanTree => {
const root: IntermediaryNode = ['', 0, []]
const huffmanTreeLength = binaryReader.getUint16()
let indexHeader = 0
while (indexHeader < huffmanTreeLength) {
let lengthCode = binaryReader.getUint8()
let indexCode = lengthCode - 1
const char = String.fromCharCode(binaryReader.getUint8())
const code = lengthCode > 8 ? binaryReader.getUint16() : binaryReader.getUint8()
let entry: Node = root
while (indexCode > -1) {
const bit = (code >> indexCode) & 1
entry[0] += char
entry[1] += 1
const nodes = entry[2] as Node[]
const node = nodes[bit]
if (node) {
if (indexCode === 0) {
nodes[bit] = [char, 1]
} else {
entry = node
}
} else if (indexCode === 0) {
nodes[bit] = [char, 1]
} else {
const newEntry: IntermediaryNode = ['', 0, []]
nodes[bit] = newEntry
entry = newEntry
}
indexCode--
}
indexHeader += 2 + (lengthCode > 8 ? 2 : 1)
}
return [root]
}
const getBitCountEncodedData = (byteCountEncodedData: number, paddingSizeEncodedData: number) => byteCountEncodedData * 8 - paddingSizeEncodedData
export const decode = (buffer: ArrayBuffer) => {
const binaryReader = new BinaryReader(buffer)
const huffmanTree = decodeHuffmanTree(binaryReader)
const byteCountEncodedData = binaryReader.getUint32()
const paddingSizeEncodedData = binaryReader.getUint8()
return getDecodedData(binaryReader)(huffmanTree, getBitCountEncodedData(byteCountEncodedData, paddingSizeEncodedData))
}
Функция декодирования принимает буфер массива. Сначала мы создаем экземпляр нового BinaryReader с нашим ArrayBuffer. Затем мы можем приступить к расшифровке наших данных.
Первое, что мы собираемся сделать, это расшифровать наше дерево Хаффмана. Внутри decodeHuffmanTree первое, что мы делаем, — это извлекаем длину нашего дерева Хаффмана как uint16. Когда у нас есть длина, мы можем считать данные из нашего буфера. Помните, что мы сохраняли каждую запись в нашей таблице в виде триплета [ длина кода: uint8, символ: uint8, код: uint8 | uint16 (в зависимости от размера кода)].
После того, как мы создали наше дерево Хаффмана, мы считываем количество байтов для закодированных данных как uint32 и наш размер заполнения как uint8. Вооружившись этой информацией, мы можем приступить к расшифровке наших закодированных данных.
Внутри функции getEncodedData мы продолжаем обход дерева Хаффмана для каждого бита, который мы читаем, пока не достигнем конечного узла. Если да, то вернем. Мы продолжаем делать это до тех пор, пока у нас есть биты для чтения.
Когда все биты были обработаны, мы должны были декодировать наши закодированные данные обратно в оригинал.
Момент истины
Теперь пришло время посмотреть, действительно ли это работает.
В нашей папке src создайте файл с именем test.ts. Мы импортируем три сэмпла из каталога сэмплов. Вы можете найти эти примеры в репозитории github: https://github.com/vincentcorbee/Huffman/tree/main/src/samples.
import assert from 'assert'
import { encode, decode } from './'
import { sampleOne, sampleTwo, sampleThree } from './samples'
const encodedDataSampleOne = encode(sampleOne)
const encodedDataSampleTwo = encode(sampleTwo)
const encodedDataSampleThree = encode(sampleThree)
const decodedSampleOne = decode(encodedDataSampleOne)
const decodedSampleTwo = decode(encodedDataSampleTwo)
const decodedSampleThree = decode(encodedDataSampleThree)
assert(decodedSampleOne === sampleOne)
assert(decodedSampleTwo === sampleTwo)
assert(decodedSampleThree === sampleThree)
console.log({
encoded: encodedDataSampleOne.byteLength,
decoded: decodedSampleOne.length,
orignal: sampleOne.length
})
console.log({
encoded: encodedDataSampleTwo.byteLength,
decoded: decodedSampleTwo.length,
orignal: sampleTwo.length
})
console.log({
encoded: encodedDataSampleThree.byteLength,
decoded: decodedSampleThree.length,
orignal: sampleThree.length
})
Теперь, если из корня нашего проекта мы запустим:
npx ts-node src/test.ts
{ encoded: 13268, decoded: 24543, orignal: 24543 }
{ encoded: 787, decoded: 1087, orignal: 1087 }
{ encoded: 25, decoded: 11, orignal: 11 }
Наши утверждения должны пройти, и мы должны получить вывод выше. 🎉 Мы убедились, что наши исходные и декодированные сэмплы остались прежними. Наш вывод дает нам закодированные, декодированные и исходные размеры. 🥹
Из наших образцов мы видим, что самый большой образец дает самое большое сжатие. Самая большая выборка дает нам сжатие ~46%, вторая — ~26%, а последняя, абракадабра, фактически расширяется на ~127%.
Заключение
Я нашел это интригующим упражнением в понимании алгоритма и реализации его в Javascript. Я надеюсь, что если вы зашли так далеко, вы могли найти это полезным, и у вас не было чувства, что вы только что потратили впустую нашу жизнь.
