Barebones in-memory huffman coding implementation

huff.js

/* INPUT */

const input = 'bcaadddccacacac';

if ( input.length < 2 ) throw new Error ( 'Unimplemented' );

/* FREQUENCIES */

const frequenciesMap = {};

for ( const char of input.split ( '' ) ) {
  frequenciesMap[char] = ( frequenciesMap[char] || 0 ) + 1;
}

const frequenciesList = Object.entries ( frequenciesMap ).sort ( ( a, b ) => {
  return a[1] - b[1];
});

const frequencies = frequenciesList.map ( ([ char, frequency ]) => {
  return { char, frequency };
});

// console.log ( frequencies );

/* TREE */

class Node {
  parent = undefined;
  left = undefined;
  right = undefined;
  leftValue = undefined;
  rightValue = undefined;
  value = undefined;
  constructor ( parent, value ) {
    this.parent = parent;
    this.value = value;
  }
  isLeaf () {
    return !this.left && !this.right;
  }
  toJSON () {
    return {
      left: this.left?.toJSON?.(),
      right: this.right?.toJSON?.(),
      value: this.value
    };
  }
  log () {
    console.log ( JSON.stringify ( this.toJSON (), null, 2 ) );
  }
}

/* TREE - INIT */

let current = new Node ();

const startLeft = frequencies.shift ();
const startRight = frequencies.shift ();

current.left = new Node ( current, startLeft.char );
current.right = new Node ( current, startRight.char );
current.value = startLeft.frequency + startRight.frequency;

while ( true ) {

  const frequency = frequencies.shift ();

  if ( !frequency ) break;

  const parent = new Node ();

  if ( frequency.frequency <= current.value ) {

    parent.value = frequency.frequency + current.value;
    parent.left = new Node ( parent, frequency.char );
    parent.right = current;

    current.parent = parent;
    current = parent;

  } else {

    parent.value = frequency.frequency + current.value;
    parent.right = new Node ( parent, frequency.char );
    parent.left = current;

    current.parent = parent;
    current = parent;

  }

}

/* TREE - EDGING */

const populate = node => {
  if ( node.isLeaf () ) return;
  node.leftValue = 0;
  node.rightValue = 1;
  if ( node.left ) {
    populate ( node.left );
  }
  if ( node.right ) {
    populate ( node.right );
  }
};

populate ( current );

/* TREE - TRAVERSE */

const charsBits = {};

const traverse = node => {
  if ( node.left ) {
    traverse ( node.left );
  }
  if ( node.right ) {
    traverse ( node.right );
  }
  if ( !node.left && !node.right ) {
    const char = node.value;
    const bits = [];
    let child = node;
    while ( true ) {
      const parent = child.parent;
      if ( parent ) {
        if ( parent.left === child ) {
          bits.unshift ( parent.leftValue );
        } else if ( parent.right === child ) {
          bits.unshift ( parent.rightValue );
        }
      } else {
        charsBits[char] = bits;
        break;
      }
      child = parent;
    }
  }
};

traverse ( current );

/* OUTPUT */

const outputBits = [];

for ( const char of input.split ( '' ) ) {
  outputBits.push ( ...charsBits[char] );
}

/* DECODING */

let decoded = '';

let node = current;
for ( const bit of outputBits ) {
  if ( bit ) {
    node = node.right;
  } else {
    node = node.left;
  }
  if ( node.isLeaf () ) {
    decoded += node.value;
    node = current;
  }
}

// console.log ( '--------------' );
// console.log ( frequencies );
console.log ( '--------------' );
current.log ();
console.log ( '--------------' );
console.log ( charsBits );
console.log ( '--------------' );
console.log ( outputBits );
console.log ( '--------------' );
console.log ( input );
console.log ( decoded );
console.log ( '--------------' );
console.log ( input === decoded );