type FrequentieTable = Record; type IntermediaryNode = [string, number, Node[]]; type LeafNode = [string, number]; type Node = IntermediaryNode | LeafNode; type HuffmanTree = [IntermediaryNode]; type Encoding = number[]; type EncodedData = number[]; type EncodingTable = Record; 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(); } } 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); } } 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); }; const createEncodingTable = (frequentieTable: FrequentieTable, huffmanTree: HuffmanTree): EncodingTable => Object.keys(frequentieTable).reduce((table, char) => { table[char] = getCharacterEncoding(huffmanTree)(char); return table; }, {} as EncodingTable); 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; }; 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]); 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; }; const encodeData = (encodingTable: EncodingTable) => (input: string): EncodedData => input .split("") .flatMap(char => encodingTable[char]); const getBitCount = (bits: number) => { let bitCount = 0; while (bits) { /* Shift one bit off and assign result */ bits >>= 1; /* For every shift add a one to the total count */ bitCount++; } return bitCount; }; 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; }; const getPaddingSizeEncodedData = (bitCount: number) => { const remainder = bitCount % 8; if (remainder) return 8 - remainder; return 0; }; 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 paddingSizeEncodedData = getPaddingSizeEncodedData(bitCount); 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(paddingSizeEncodedData); 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 padding = 0; padding < paddingSizeEncodedData; padding++) chunk = chunk << 1; binaryWriter.setUint8(chunk); } return binaryWriter.buffer; }; 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); }; 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), ); }; console.log(decode(encode("asdfasdfasf")));

huffmanEncoding

Versions

v1

v0