@algorithm.ts/huffman NPM

A typescript implementation of the huffman coding.

Install

npm

npm install --save @algorithm.ts/huffman

yarn
```
yarn add @algorithm.ts/huffman
```

Usage

encode: Encode text to Uint8Array and a huffman tree.

import { encode } from '@algorithm.ts/huffman'
const { encodedData, encodingTable, tree } = encode('Hello, world!')

decode: Decode a huffman encoded data to string.

import { decode, fromEncodingTable } from '@algorithm.ts/huffman'

const plaintext = decode(encodedData, tree)

// Or build tree from encodingTable
const tree2 = fromEncodingTable(encodingTable)
const plaintext2 = decode(encodedData, tree2)

compress: Compress the encoded data.

// Array<0 | 1> ==> Uint8Array
const compressedData = compress(encodedData)

decompress: Decompress data.

// Uint8Array ==> Array<0 | 1>
const encodedData2 = decompress(compressedData)

Example

Compress uri data

const data = { name: 'alice', age: 33, gender: 'female' }

compress(JSON.stringify(data))
// => 'WyIzIiwyMCwiLCIsMTYsIn0iLDM0LCJpIiwzNSwiZyIsMTgsIm4iLDE5LCJsIiwyMSwiciIsNDQsImMiLDkwLCJkIiw5MSwiOiIsMjMsIlwiIiw2LCJlIiwxNCwiYSIsMzAsInsiLDEyNCwiZiIsMTI1LCJtIiw2M10_-BvI)(p7lG1oLi06IEWNvMnvd(l0C'

decompress('WyIzIiwyMCwiLCIsMTYsIn0iLDM0LCJpIiwzNSwiZyIsMTgsIm4iLDE5LCJsIiwyMSwiciIsNDQsImMiLDkwLCJkIiw5MSwiOiIsMjMsIlwiIiw2LCJlIiwxNCwiYSIsMzAsInsiLDEyNCwiZiIsMTI1LCJtIiw2M10_-BvI)(p7lG1oLi06IEWNvMnvd(l0C')
// => '{"name":"alice","age":33,"gender":"female"}'

function compress(text) {
  const { encodedData, encodingTable } = huffman.encode(text)
  const cipherBuffer = huffman.compress(encodedData)
  const cipherText = base64.encode(cipherBuffer)

  const textEncoder = new TextEncoder('utf-8')
  const encodingTableText = base64.encode(
    textEncoder.encode(JSON.stringify(compressEncodingTable(encodingTable))),
  )
  const result = (encodingTableText + '-' + cipherText)
    .replace(/\//g, '(')
    .replace(/\+/g, ')')
    .replace(/=/g, '_')
  return result
}

function decompress(text) {
  const [encodingTableText, cipherText] = text
    .replace(/\(/g, '/')
    .replace(/\)/g, '+')
    .replace(/_/g, '=')
    .split('-')
  const textDecoder = new TextDecoder('utf-8')
  const encodingTable = decompressEncodingTable(
    JSON.parse(textDecoder.decode(base64.decode(encodingTableText))),
  )
  const tree = huffman.fromEncodingTable(encodingTable)

  const cipherData = huffman.decompress(base64.decode(cipherText))
  const plaintext = huffman.decode(cipherData, tree)
  return plaintext
}

function compressEncodingTable(table) {
  const entries = Object.entries(table)
    .map(([value, path]) => {
      let p = 1
      for (const x of path) p = (p << 1) | x
      return [value, p]
    })
    .flat()
  return entries
}

function decompressEncodingTable(entries) {
  const table = {}
  for (let i = 0; i < entries.length; i += 2) {
    const value = entries[i]
    const p = entries[i + 1]
    const path = []
    for (let x = p; x > 1; x >>= 1) path.push(x & 1)
    table[value] = path.reverse()
  }
  return table
}