9
\$\begingroup\$

The Huffman-Algorithm

The Huffman-Algorithm, named after David A. Huffman who first published this algorithm in 1952, is a algorithm for lossless data compression. As most encoding-methods, the words for often used symbols are shorter than the ones for not so commonly used symbols. The algorithm returns a binary code-word for every source symbol. The result is a optimal prefix-free code.

The Algorithm in detail

The first step is to count the number of occurences of every char in the text. After that, the algorithm creates a so called forest of tree-nodes, where every node contains one char and the number of occurences of this char:

After that, the algorithm looks at this node as roots of trees.

Then, while there is more than one tree left, the algorithm creates a new node with two children. The children are always the nodes with the two smallest numbers of occurences. For the new node, the number of occurences of the children are added together.

After that, the code-words for every char are created by looking at the path to every leaf.

The code

/*
 * Attribution:
 * https://stackoverflow.com/a/38362821/13634030
 * https://stackoverflow.com/a/14313213/13634030
 */

/*
 * This program is an implementation of the Huffman-algorithm.
 * Huffman-coding is an algorithm for lossless data compression. It was
 * first published by David A. Huffman in 1952.
 * The algorithm returns a binary code-word for every source symbol. Like
 * most encoding methods, the words for often used symbols are shorter than
 * the ones for not so commonly used symbols. The result is a optimal prefix-
 * free code.
 * For more information see https://en.wikipedia.org/wiki/Huffman_coding.
 */

document.getElementById('startHuff').addEventListener('click', huffman);

/*
 * ================================
 * Data-structures for this program
 * ================================
 */

/**
 * Provides the structure called a node for a binary tree
 */
class Node {
  /**
   * Creates a node
   * @param {number} value Number of occurences
   * @param {char} c The char this node represents
   * @param {Node} left The left child-node
   * @param {Node} right The right child-node
   */
  constructor(value, c, left, right) {
    this.value = value;
    this.c = c;
    this.left = left;
    this.right = right;
  }
}

/**
 * Provides a recursive binary-tree structure
 */
class Tree {
  /**
   * Creates a Tree
   * @param {Node} root The root of the tree
   */
  constructor(root) {
    this.root = root;
  }
}

/*
 * ==================
 * Main-functionality
 * ==================
 */

let input; // The text the user wants to compress
let occurences; // Array that contains the number of occurences of every char
let forest; // Array that contains the nodes for every char
let code; // Array that contains the code-words for every char
let text; // Compressed text
let codeWords; // Array code as user-friendly string
let ascii; // ASCII-text

/**
 * This is the only function that has to be called from outside
 * this script.
 */
function huffman() {
  // get user input
  input = document.getElementById('Input').value;

  // reset variables
  forest = [];
  ascii = '';
  text = '';
  codeWords = '';

  /*
   * Program only creates huffman-tree if
   * user only entered (non-extended) ascii-
   * chars
   */
  if (input != '' && isASCII(input)) {
    // Count occurences of every ascii-char
    count();

    // Create node for every char that occures at least once
    createForest();

    // Apply huffman-algorithm on the created nodes
    createTree();

    /*
     * "translates" the position of the leafs to the codeword
     * of the char represented by the leaf
     *
     *                   #
     *                 0/ \
     *                 /   \
     *                #     #
     *               / \1
     *              /   \
     *                   #
     *                 0/
     *                 /
     *                A
     *
     * The code-word of 'A' would be 010 in this example
     */
    code = new Array(128);
    createCode('', code, forest[0].root);

    // Creating html-table with created code-words
    getCode();

    // Creates string with every char replaced by the code-word
    getText();

    // Creates string with every char replaced by the binary ascii-value
    getAscii();

    // Output
    document.getElementById('Text').value = text;
    document.getElementById('CodeWords').innerHTML = codeWords;
    document.getElementById('numOfCharsText').innerHTML = ' ' + text.length;
    document.getElementById('Ascii').value = ascii;
    document.getElementById('numOfCharsAscii').innerHTML = ' ' + ascii.length;
    document.getElementById('compression').innerHTML = ' ' + text.length +
      ' / ' + ascii.length + ' = ' + (text.length / ascii.length).toFixed(4);
  } else {
    window.alert('Please only enter ASCII-characters.');
  }
}

/**
 * Counts the number of occurences of every ascii-char in input
 */
function count() {
  occurences = new Array(128);

  // Initialize with zero
  for (let i = 0; i < occurences.length; i++) {
    occurences[i] = 0;
  }

  // Count occurences
  for (let i = 0; i < input.length; i++) {
    // charCodeAt(i) returns the ascii-code of the i-th character in the string
    occurences[input.charCodeAt(i)]++;
  }
}

/**
 * Creates the forest with one tree for every char
 */
function createForest() {
  // Create tree (with only one node) for every char the text contains
  for (let i = 0; i < occurences.length; i++) {
    // Only chars that really occur in the text will be taken into account
    if (occurences[i] > 0) {
      // String.fromCharCode(i) returns the char with ascii-code i
      const x = String.fromCharCode(i);
      forest.push(new Tree(new Node(occurences[i], x, null, null)));
    }
  }
}

/**
 * Creates the huffman-tree
 */
function createTree() {
  /*
   * The result of the algorithm is just one tree, so the algorithm has
   * not finished yet, if there are more than one trees.
   */
  while (forest.length > 1) {
    // Find the two trees with the smallest number of occurences
    let minIndex = findMinimum();
    const min1 = forest[minIndex].root;

    /*
     * removes the minIndex-th element; the second parameter tells us that
     * only one element should be removed, starting at index minIndex
     */
    forest.splice(minIndex, 1);

    minIndex = findMinimum();
    const min2 = forest[minIndex].root;
    forest.splice(minIndex, 1);

    // Create new node that has min1 and min2 as child-nodes
    forest.push(new Tree(new Node(min1.value + min2.value, null, min1, min2)));
  }
}

/**
 * Creates the code-words from the created huffman-tree
 * @param {String} str (Part of) the codeword for the current leaf
 * @param {Array} code Array of codewords that has to be filled
 * @param {Node} node Current node
 */
function createCode(str, code, node) {
  if (node == null) {
    return;
  }

  // case the node is a leaf
  if (node.left == null && node.right == null) {
    code[node.c.charCodeAt()] = str;

    // Recursive calls if node is not a leaf
  } else {
    createCode(str + '0', code, node.left);
    createCode(str + '1', code, node.right);
  }
}

/*
 * ================
 * Helper-functions
 * ================
 */

/**
 * Creates a html-table with the codewords
 */
function getCode() {
  codeWords = '<table><tr><th>Character</th><th>' +
    'Occurences</th><th>Huffman-code</th></tr>';
  for (let i = 0; i < code.length; i++) {
    if (occurences[i] > 0) {
      codeWords += '<tr>';
      codeWords += '<td>' + String.fromCharCode(i) + '</td>';
      codeWords += '<td>' + occurences[i] + '</td>';
      codeWords += '<td>' + code[i] + '</td>';
      codeWords += '</tr>';
    }
  }
  codeWords += '</table>';
}

/**
 * Replaces every char with its codeword.
 */
function getText() {
  for (let i = 0; i < input.length; i++) {
    text += code[input.charCodeAt(i)] + ' ';
  }
}

/**
 * Replaces every char with its ASCII-code.
 */
function getAscii() {
  for (let i = 0; i < input.length; i++) {
    ascii += '00'.concat(input.charCodeAt(i).toString(2)).slice(-8) + ' ';
  }
}

/**
 * Finds the minimum.
 * @return {number} index of minimum
 */
function findMinimum() {
  let min = forest[0].root.value;
  let minIndex = 0;
  for (let i = 0; i < forest.length; i++) {
    if (min > forest[i].root.value) {
      minIndex = i;
      min = forest[i].root.value;
    }
  }
  return minIndex;
}

/**
 * Returns true, if str only contains ascii-chars.
 * @param {String} str String the function will be applied on
 * @return {Boolean} test True if str only contains ascii-chars
 */
function isASCII(str) {
  /*
   * returns true if str only contains (non-extended) ascii-chars;
   * see https://www.ascii-code.com/ for reference
   */
  const test = /^[\x00-\x7F]*$/.test(str);
  return test;
}
<!-- Just minimal working example -->
<!DOCTYPE html>
<html lang='en'>
    <!-- Head -->
    <head>
        <meta charset='utf-8'>
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <script>
            window.onerror=function(msg, url, linenumber) {
                alert('Error message: ' + msg + '\nURL: ' + url + '\nLine Number: ' + linenumber);
                return true;
            }
        </script>
        <title>Huffman</title>
        <link rel='stylesheet' type='text/css' href='../css/style.css'>
    </head>
    <body>
        <!-- Input Area -->
        <h4>Input:</h4>
        <div>
            <textarea id='Input' rows='8' style='resize: none; background: LightGray; position: relative; width: 80%;'></textarea>
        </div>
        <br><br>
        <button type='button' id='startHuff'>Huffman</button> 

        <!-- Output Area --> 
        <h4>Compressed text:</h4>
        <div>
            <textarea id='Text' rows='8' style='resize: none; background: LightGray; position: relative; width: 80%;' readonly></textarea>
        </div>
        <p>Number of chars:<span id=numOfCharsText></span></p>

        <h4>ASCII text:</h4>
        <div>
            <textarea id='Ascii' rows='8' style='resize: none; background: LightGray; position: relative; width: 80%;' readonly></textarea>
        </div>
        <p>Number of chars:<span id=numOfCharsAscii></span></p>
        <h4>Code:</h4>
        <div id='CodeWords'>
        </div>
        <p>Compression:<span id=compression></span></p>

        <script src='huffman.js'></script>
        

    </body>
</html>

I've checked the code with eslint and it didn't show me any errors for this version.

Question

All suggestions to improve the code are appreciated.

\$\endgroup\$
0
2
+50
\$\begingroup\$

Overall feedback

It seems there are quite a few global variables referenced within various functions. This isn't totally bad but it makes things difficult - like unit testing. If functions accepted parameters and returned certain output then testing might be easier.

The answer by Ted Brownlow suggests using a Plain-old Javascript object (A.K.A. a POJO) to store the occurrences instead of an array - i.e. a mapping of characters to counts. This can eliminate the need to initialize the array and set all values to zero.

You may be interested to read other posts involving Huffman Encoding, including this one.

Suggestions

Initializing an array of zeroes

In the function count() there is this code:

occurences = new Array(128);
// Initialize with zero
for (let i = 0; i < occurences.length; i++) {
  occurences[i] = 0;
}

The loop can be avoided by using array.fill().

Excess variables

in the function isASCII there is the variable test that is returned immediately after being assigned. While this may be leftover from debugging the variable can be eliminated. The whole function could be expressed as a one-line arrow function.

Avoid excess DOM lookups

The code in huffman() accesses DOM elements each time. While it may not be as much of an issue with todays browsers, it is wise to cache DOM references one they are available (e.g. in the DOMContentLoaded event).

bridge toll

”...DOM access is actually pretty costly - I think of it like if I have a bridge - like two pieces of land with a toll bridge, and the JavaScript engine is on one side, and the DOM is on the other, and every time I want to access the DOM from the JavaScript engine, I have to pay that toll”
    - John Hrvatin, Microsoft, MIX09, in this talk Building High Performance Web Applications and Sites at 29:38, also cited in the O'Reilly Javascript book by Nicholas C Zakas Pg 36, as well as mentioned in this post

Alerts

There are two places alert() is called (one in huffman() and one in the window.onerror handler). This can be an issue because some users may have disabled alerts in a browser setting. It is better to use HTML5 <dialog> element - it allows more control over the style and doesn't block the browser. Bear in mind that it isn't supported by IE and Safari (And seemingly Chrome on iOS) but there is a polyfill

\$\endgroup\$
5
\$\begingroup\$

Warning: this is pretty opinionated I just didn't want to sprinkle the word "maybe" halfway through an explanation

There's a lot of things going on here. I see you use a lot of type hints. I'd recommend using TypeScript, as it enforces the hints such that they become rules rather than suggestions. In general, though, the code appears to have a lot of noisy comments. The worst offender is right here.

/**
 * Returns true, if str only contains ascii-chars.
 * @param {String} str String the function will be applied on
 * @return {Boolean} test True if str only contains ascii-chars
 */
function isASCII(str) {
  /*
   * returns true if str only contains (non-extended) ascii-chars;
   * see https://www.ascii-code.com/ for reference
   */
  const test = /^[\x00-\x7F]*$/.test(str);
  return test;
}

The code here is pretty much self explanatory from the method name. Adding the block style comments makes this section appear more complex than it actually is.

let input; // The text the user wants to compress
let occurences; // Array that contains the number of occurences of every char
let forest; // Array that contains the nodes for every char
let code; // Array that contains the code-words for every char
let text; // Compressed text
let codeWords; // Array code as user-friendly string
let ascii; // ASCII-text

That's a lot of global state to be hanging to for a function that requires no persistence. None of these variables need to live in the global scope.

The code is littered with references to the DOM and your output statistics. Only the encoded output and the huffman encoding dictionary are required for the analysis, so generate the DOM elements elsewhere.

With the global state and the DOM references removed, the main huffman() function can be written as such.

function huffman(input) {
    if (input === '' || !isASCII(input))
        throw 'invalid_input';
    const histogram = createHistogram(input);
    const leafs = createLeafs(histogram);
    const tree = createTree(leafs);
    const code = createCode('',tree);
    const encoded = encode(code,input);
    return {
      output:encoded,
      code
    };
}

Note how all of the variables are kept in the scope of the function.

The Tree structure is entirely unnecessary. Sometimes, adding an object like this can help readability. However, in this case, the code is infected with a bunch of .root properties. This is particularly strange in the case where the trees are being joined, and trees must be converted to nodes when they are added to another tree.

/*
 * Attribution:
 * https://stackoverflow.com/a/38362821/13634030
 * https://stackoverflow.com/a/14313213/13634030
 */

/*
 * This program is an implementation of the Huffman-algorithm.
 * Huffman-coding is an algorithm for lossless data compression. It was
 * first published by David A. Huffman in 1952.
 * The algorithm returns a binary code-word for every source symbol. Like
 * most encoding methods, the words for often used symbols are shorter than
 * the ones for not so commonly used symbols. The result is a optimal prefix-
 * free code.
 * For more information see https://en.wikipedia.org/wiki/Huffman_coding.
 */

const MAX_CODE = 128;

class Node {
  constructor(count, char, left, right) {
    this.count = count;
    this.char = char;
    this.left = left;
    this.right = right;
  }
}

function isASCII(str) {
  const test = /^[\x00-\x7F]*$/.test(str);
  return test;
}

function huffman(input) {
    if (input === '' || !isASCII(input))
        throw 'invalid_input';
    const histogram = createHistogram(input);
    const leafs = createLeafs(histogram);
    const tree = createTree(leafs);
    const code = createCode('',tree);
    const encoded = encode(code,input);
    return {
      output:encoded,
      code
    };
}

// builds histogram of letter frequency
function createHistogram(input) {
  const histogram = {};

  for (let i = 0; i < input.length; i++) {
    const code = input.charCodeAt(i);
    ++histogram[code];
  }

  return histogram;
}

// creates the forest with one tree for every char
function createLeafs(histogram) {
  return Object.entries(histogram).map(([code,freq])=>{
      const char = String.fromCharCode(code);
      return new Node(freq,char,null,null);
  })
}

// splits trees into small and big
function splitTrees(forest) {
  const sorted = forest.sort((a,b)=>a.count-b.count);
  const small = sorted.slice(0,2);
  const big = sorted.slice(2);
  return [small,big];
}

function createTree(forest) {
  if (forest.length===1)
    return forest[0]
  const [small_trees,big_trees] = splitTrees(forest);
  const new_tree = new Node(
    small_trees[0].count+small_trees[1].count,
    null,
    small_trees[0],small_trees[1]
  );
  const new_trees = [...big_trees,new_tree];
  return createTree(new_trees);
}

// Creates the code-words from the created huffman-tree
function createCode(prefix, node) {
  // empty root node
  if (!node) return {};
  // leaf node
  if (!node.left && !node.right) {
    return {[node.char] : prefix};
  }
  // recursive call
  return {
    ...createCode(prefix + '0', node.left),
    ...createCode(prefix + '1', node.right)
  }
}

function encode(code,string) {
    return Array.from(string).map(
        c=>code[c]
    );
}

console.log(huffman("hi dude"));

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.