3
\$\begingroup\$

Write a program that takes any input text and produces both a frequency table and the corresponding Huffman code.

Take approximately 360 words from any English document as your input text. Ignore all blanks, all punctuation marks, all special symbols. Create an input file with this input text.

Construct the frequency table according to the input text read from the file, in the form:

The Frequency's MUST be listed, in order, from largest (at the top) to smallest (at the bottom).

Only the BELOW Tablet Format will be accepted: Letter Comma Space Percentage

Example: A, 2.5%

symbol frequency

A, .

. .

. .

m, .

. .

. .

7, .

Then, using the Huffman algorithm, construct the optimal prefix binary code for the table.

Can somebody please review and suggest any needed modifications to optimize the performance?

import * as fs from 'fs';
import * as path from 'path';
import * as readline from 'readline';

class HuffmanNodeObject {
    private _character: string = '';
    private _frequency: number = 0;
    private _binaryCode: string = '';
    private _totalBits: number = 0;
    private _leftNode: HuffmanNodeObject = null;
    private _rightNode: HuffmanNodeObject = null;

    public getCharacter(): string {
        return this._character;
    }

    public setCharacter(value: string): void {
        this._character = value;
    }

    public getFrequency(): number {
        return this._frequency;
    }

    public setFrequency(value: number): void {
        this._frequency = value;
    }

    public getBinaryCode(): string {
        return this._binaryCode;
    }

    public setBinaryCode(value: string): void {
        this._binaryCode = value;
    }

    public getTotalBits(): number {
        return this._totalBits;
    }

    public setTotaBits(value: number): void {
        this._totalBits = value;
    }

    public getLeftNode(): HuffmanNodeObject {
        return this._leftNode;
    }

    public setLeftNode(value: HuffmanNodeObject): void {
        this._leftNode = value;
    }

    public getRightNode(): HuffmanNodeObject {
        return this._rightNode;
    }

    public setRightNode(value: HuffmanNodeObject): void {
        this._rightNode = value;
    }
}

class Program {

    private _lstHuffmanNodeObjects: Array<HuffmanNodeObject> = null;
    private _lstHuffmanNodeTree: Array<HuffmanNodeObject> = null;

    private _nodeRootHuffmanObject: HuffmanNodeObject = null;

    private _totalCharacterCount = 0;
    private _totalCodeLength = 0;
    //name of the file.
    private _inputFileName: string = "infile.dat";
    //Reg ex to allow only numbers and characters.
    private _regularExpression: RegExp = /[a-zA-Z0-9]/;

    public Main(): void {
        try {

            //A copy of program object for reference in call backs.
            let _selfProgramObject: Program = this;

            //compelte file path till the folder
            let _filePath: string = path.join(__dirname, this._inputFileName);

            //As per node documentation, instead of checking the existance first, we should directly perform operation and then handle the error within.
            //Open the file directly.
            fs.open(_filePath, fs.R_OK, (_err: NodeJS.ErrnoException, _fd: number) => {
                //in case of an error, handle it
                if (_err) {
                    if (_err.code === 'ENOENT')
                        console.error(`The file with name '${this._inputFileName}' is not found in directory '${__dirname}'. Please check if filename is correct or not.`);
                    else
                        console.error(_err);
                }
                //else process data with in the file.
                else {
                    //instead of reading whole file, we will read it letter by letter.
                    //create the stream to read the input file.
                    let _readable: fs.ReadStream = fs.createReadStream(_filePath, {
                        encoding: 'utf8',
                        fd: null,
                    }).on('error', function (error) {
                        throw error;
                    });

                    //https://nodejs.org/api/stream.html#stream_readable_read_size
                    _readable.on('readable', function () {
                        try {
                            let _chunk: string = '';
                            while (null !== (_chunk = _readable.read(1))) {
                                _selfProgramObject.ProcessCharacter(_chunk);
                            }
                        }
                        catch (exception) {
                            console.log(`An error occurred while reading data from file ${exception}`);
                        }
                    });

                    //once the file read operation is complete process start building graph.
                    _readable.on('end', () => {
                        if (this._totalCharacterCount === 0)
                            console.log(`${this._inputFileName} has no data. Please enter some data`);
                        else {
                            console.log(`number of letters in the file are ${this._totalCharacterCount}`);

                            //Sort the array by the frequency
                            _selfProgramObject._lstHuffmanNodeObjects = _selfProgramObject.SortCollectionInDescending(_selfProgramObject._lstHuffmanNodeObjects);

                            //Display the Character with their frequency
                            _selfProgramObject.DisplayTable();

                            //generation binary tree in the form of node list
                            _selfProgramObject._lstHuffmanNodeTree = _selfProgramObject._lstHuffmanNodeObjects;
                            _selfProgramObject._nodeRootHuffmanObject = _selfProgramObject.GenerateHuffMannTree();

                            //Generate binary codes of each letter
                            _selfProgramObject.CreateEncodings(_selfProgramObject._nodeRootHuffmanObject, '');

                            //Display the Character with their code
                            _selfProgramObject._lstHuffmanNodeTree = _selfProgramObject.SortCollectionInDescending(_selfProgramObject._lstHuffmanNodeTree);
                            _selfProgramObject.DisplayBinaryCode();
                        }
                    });
                }
            });
        }
        catch (exception) {
            console.error(exception);
        }
    }

    private CreateEncodings(rootObject: HuffmanNodeObject, binaryCode: string): void {
        if (rootObject.getLeftNode() !== null) {
            this.CreateEncodings(rootObject.getLeftNode(), binaryCode + '0');
            this.CreateEncodings(rootObject.getRightNode(), binaryCode + '1');
        }
        else {
            rootObject.setBinaryCode(binaryCode);
            this._lstHuffmanNodeTree.push(rootObject);
        }
    }

    private SortCollectionInDescending(huffMannNodeCollection: Array<HuffmanNodeObject>): Array<HuffmanNodeObject> {
        let _rtnVal: Array<HuffmanNodeObject> = null;
        try {
            _rtnVal = huffMannNodeCollection.sort(function (firstNode, secondNode) {
                try {
                    if (firstNode.getFrequency() > secondNode.getFrequency())
                        return -1;
                    if (firstNode.getFrequency() < secondNode.getFrequency())
                        return 1;
                    if (firstNode.getFrequency() === secondNode.getFrequency())
                        return 0;
                }
                catch (exception) {
                    console.log(`exception ${exception} for ${firstNode.getCharacter()} and ${secondNode.getCharacter()}`);
                }
            });
        }
        catch (exception) {
            console.error(`Error while sorting in descending order. Error Info ${exception}`);
        }
        return _rtnVal;
    }

    private GenerateHuffMannTree(): HuffmanNodeObject {
        let _rtnVal: HuffmanNodeObject = null;
        let _leastFrequencyObject: HuffmanNodeObject = null;
        let _secondLeastFrequencyObject: HuffmanNodeObject = null;
        while (this._lstHuffmanNodeTree.length > 1) {
            try {
                _leastFrequencyObject = this._lstHuffmanNodeTree.pop();
                _secondLeastFrequencyObject = this._lstHuffmanNodeTree.pop();
                let _newCombinedHuffMannObject: HuffmanNodeObject = new HuffmanNodeObject();
                _newCombinedHuffMannObject.setLeftNode(_leastFrequencyObject);
                _newCombinedHuffMannObject.setRightNode(_secondLeastFrequencyObject);
                _newCombinedHuffMannObject.setFrequency(_leastFrequencyObject.getFrequency() + _secondLeastFrequencyObject.getFrequency());
                this._lstHuffmanNodeTree.push(_newCombinedHuffMannObject);
                this._lstHuffmanNodeTree = this.SortCollectionInDescending(this._lstHuffmanNodeTree);
            }
            catch (exception) {
                console.log(`exception ${exception} for ${_leastFrequencyObject.getCharacter()} and ${_secondLeastFrequencyObject.getCharacter()}`);
            }
        }
        _rtnVal = this._lstHuffmanNodeTree.pop();
        return _rtnVal;
    }

    private DisplayTable(): void {
        console.log('symbol\tfrequency');
        for (let _tempHuffmannObject of this._lstHuffmanNodeObjects) {
            let _fre: number = _tempHuffmannObject.getFrequency();
            _fre = ((_fre / this._totalCharacterCount) * 100);
            console.log(`${_tempHuffmannObject.getCharacter()},\t${Number(Math.round(+(_fre + 'e2')) + 'e-2').toFixed(2)}%`);
        }
    }

    private DisplayBinaryCode(): void {
        for (let _tempHuffmannObject of this._lstHuffmanNodeTree) {
            console.log(`${_tempHuffmannObject.getCharacter()},\t${_tempHuffmannObject.getFrequency()},\t${_tempHuffmannObject.getBinaryCode()} `);
            this._totalCodeLength += this._totalCodeLength + (_tempHuffmannObject.getFrequency() * _tempHuffmannObject.getBinaryCode().length);
        }

        console.log(`Total length of the message is ${this._totalCodeLength} bits`);
    }

    private ProcessCharacter(chunkData: string): void {
        if (typeof (chunkData) !== 'undefined'
            && chunkData !== null
            && this._regularExpression.test(chunkData)) {
            //console.log(_chunk); // chunk is one symbol
            if (typeof (this._lstHuffmanNodeObjects) === 'undefined' || this._lstHuffmanNodeObjects === null)
                this._lstHuffmanNodeObjects = new Array<HuffmanNodeObject>();
            //look up if the character is already present in the array.
            let _existingObject: HuffmanNodeObject = this._lstHuffmanNodeObjects.find(x => x.getCharacter() === chunkData);
            if (typeof (_existingObject) === 'undefined' || _existingObject === null) {
                //if not then add it up
                _existingObject = new HuffmanNodeObject();
                _existingObject.setCharacter(chunkData);
                _existingObject.setFrequency(1);
                this._lstHuffmanNodeObjects.push(_existingObject);
            }
            else {
                //if present increment the frequency 
                let _position: number = this._lstHuffmanNodeObjects.findIndex(x => x === _existingObject);
                //get the original frequency
                let _originalFrequency: number = _existingObject.getFrequency();
                //Increment the frequency
                _existingObject.setFrequency(++_originalFrequency);
                //Update the object in collection
                this._lstHuffmanNodeObjects[_position] = _existingObject;
            }
            this._totalCharacterCount += 1;
        }
    }
}

new Program().Main();
\$\endgroup\$
2
\$\begingroup\$

Starting point

Unfortunately, I am not familiar enough with node.js to make high confidence claims about the code. My guess is that I/O operations are more likely to be the bottleneck in the code rather anything else. Even the GenerateHuffMannTree does not look too heavy computationally.

Experiment with the way the data is being read. Now the code does this:

while (null !== (_chunk = _readable.read(1)))

but what if the read asked for a block of characters instead of a single character, and then iterated through the characters one-by-one? Usually, it is way more efficient. However, the documentation says that the data is being read from the buffer, so there may not be any performance improvement at all. I'd still give it a try for the sake of curiosity.

Another thing which might be slow is console.[log|error]. Again, I'm not sure whether it's really expensive in node.js but it might be, since it deals with I/O. Try benchmarking your program without any console output invocation. If it works faster, you may collect all the messages in memory while doing the job, and dump them all at once when the program is done (since your input is really small -- 360 words).

Minor performance improvement

There's no need in three ifs, and try-catches in SortCollectionInDescending. Assuming that all node objects in the provided array are in a good shape, you can sort using a fat arrow function that relies on simple subtraction operation. This approach is very commonly used for comparison.

private SortCollectionInDescending(huffMannNodeCollection: Array<HuffmanNodeObject>): Array<HuffmanNodeObject> {
  return huffMannNodeCollection.sort((firstNode, secondNode) => secondNode.getFrequency() - firstNode.getFrequency());
}

Possible bug

This seems to be a bug, but could be that I simply misunderstand the intent. The construction a += a + b is strange and not idiomatic (usually, we either see a += b or a = a + b).

this._totalCodeLength += this._totalCodeLength + (_tempHuffmannObject.getFrequency() * _tempHuffmannObject.getBinaryCode().length);

Getters/setters in HuffmanNodeObject

In my humble opinion, they are not providing any value at all. It's okay to expose the fields (_character, _frequency, etc.) and treat this class as a value type (or a "structure" if you will). This will allow removing the get*/set*, thus shortening the code by about 50 lines. The class works as data holder and has absolutely no logic, therefore no need to complicate things. I don't think this code change will lead to any noticeable performance gains.

\$\endgroup\$
-1
\$\begingroup\$

I don't see any asymptotic improvements possible. Just small things like minimizing setters/getters etc. But that shouldn't matter much.

\$\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.