hpphat92/huffman.html

## huffman.html
<!doctype html>
<html>
<head>
    <meta charset="utf-8">
    <title></title>
    <meta name="description" content="">
    <meta name="viewport" content="width=device-width">
    <!-- endbuild -->
</head>
<body>
<h3>Huffman Compression</h3>
<input id="OriginalData" type="text" value="ABABBCCCCCD">
<button type="button" onclick="encodeHuffman()">Encode</button>
<div>
    CompressedData: <blockquote id="EncodedData"></blockquote>
</div>
<div>
    Ratio: <blockquote id="ratio"></blockquote>
</div>
</body>
<script>
    // https://gist.github.com/eyecatchup/6742657
    let stringHelper = {
        toAscii: function (bin) {
            return bin.replace(/\s*[01]{8}\s*/g, function (bin) {
                return String.fromCharCode(parseInt(bin, 2))
            })
        },
        toBinary: function (str, spaceSeparatedOctets) {
            return str.replace(/[\s\S]/g, function (str) {
                str = this.zeroPad(str.charCodeAt().toString(2), 8);
                return !1 == spaceSeparatedOctets ? str : str + " "
            }.bind(this))
        },
        zeroPad: function (num, count) {
            return "0".repeat(count).slice(String(num).length) + num
        }
    };
    function createFrequencyTable(str) {
        let tmp_table = {}, table = [];
        for (let i = 0, length = str.length; i < length; i++) {
            tmp_table[str[i]] = tmp_table[str[i]] || 0;
            tmp_table[str[i]]++;
        }
        for (let key in tmp_table) {
            if (tmp_table.hasOwnProperty(key)) {
                table.push({
                    leaf: true,
                    key: key,
                    freq: tmp_table[key]
                })
            }
        }
        table.sort(function (a, b) {
            return a.freq > b.freq;
        });
        return table;
    }
    function createHuffmanTree(freqTable) {
        while (freqTable.length > 1) {
            let firstItem = freqTable.splice(0, 1)[0];
            let secondItem = freqTable.splice(0, 1)[0];
            let newFreq = firstItem.freq + secondItem.freq;
            let hasUpperBoundary = false;
            let _newInstance = {
                leaf: false,
                key: {
                    left: firstItem,
                    right: secondItem
                },
                freq: newFreq
            };
            for (let i = 0; i < freqTable.length; i++) {
                if (freqTable[i].freq > newFreq) {
                    hasUpperBoundary = true;
                    freqTable.splice(i, 0, _newInstance);
                    break;
                }
            }
            if (!hasUpperBoundary) {
                // it append to last
                freqTable.push(_newInstance);
            }
        }
        return freqTable[0];
    }
    function createMappingTableFromTree(tree, hashedData, prefix) {
        // visit current node
        prefix = prefix || '';
        if (tree.leaf) {
            hashedData[tree.key] = prefix;
            return;
        }
        createMappingTableFromTree(tree.key.left, hashedData, prefix + '0');
        createMappingTableFromTree(tree.key.right, hashedData, prefix + '1');
    }
    function encodeData(inputStr, encodedTable) {
        let encodedStr = '';
        for (let i = 0, length = inputStr.length; i < length; i++) {
            encodedStr = encodedStr + encodedTable[inputStr[i]];
        }

        // The first 32 bit will represent the size of code
        let sizeOfFile = stringHelper.zeroPad(encodedStr.length.toString(2), 32);
        encodedStr = sizeOfFile + encodedStr;
        let bitZerosCountAddedAfter = Math.ceil(encodedStr.length / 8) * 8 - encodedStr.length;
        encodedStr += "0".repeat(bitZerosCountAddedAfter);


        return stringHelper.toAscii(encodedStr);
    }
    function encodeHuffman() {
        let inputStr = OriginalData.value;
        let freqTable = createFrequencyTable(inputStr);
        let huffmanTree = createHuffmanTree(freqTable);
        let encodedTable = {};
        createMappingTableFromTree(huffmanTree, encodedTable);
        let encodedData = encodeData(inputStr, encodedTable);
        EncodedData.innerHTML = encodedData;
        ratio.innerText = ((inputStr.length - encodedData.length)/ inputStr.length * 100).toFixed(2)+'%';
    }
</script>
</html>
	<!doctype html>
	<html>
	<head>
	<meta charset="utf-8">
	<title></title>
	<meta name="description" content="">
	<meta name="viewport" content="width=device-width">
	<!-- endbuild -->
	</head>
	<body>
	<h3>Huffman Compression</h3>
	<input id="OriginalData" type="text" value="ABABBCCCCCD">
	<button type="button" onclick="encodeHuffman()">Encode</button>
	<div>
	CompressedData: <blockquote id="EncodedData"></blockquote>
	</div>
	<div>
	Ratio: <blockquote id="ratio"></blockquote>
	</div>
	</body>
	<script>
	// https://gist.github.com/eyecatchup/6742657
	let stringHelper = {
	toAscii: function (bin) {
	return bin.replace(/\s[01]{8}\s/g, function (bin) {
	return String.fromCharCode(parseInt(bin, 2))
	})
	},
	toBinary: function (str, spaceSeparatedOctets) {
	return str.replace(/[\s\S]/g, function (str) {
	str = this.zeroPad(str.charCodeAt().toString(2), 8);
	return !1 == spaceSeparatedOctets ? str : str + " "
	}.bind(this))
	},
	zeroPad: function (num, count) {
	return "0".repeat(count).slice(String(num).length) + num
	}
	};
	function createFrequencyTable(str) {
	let tmp_table = {}, table = [];
	for (let i = 0, length = str.length; i < length; i++) {
	tmp_table[str[i]] = tmp_table[str[i]] \|\| 0;
	tmp_table[str[i]]++;
	}
	for (let key in tmp_table) {
	if (tmp_table.hasOwnProperty(key)) {
	table.push({
	leaf: true,
	key: key,
	freq: tmp_table[key]
	})
	}
	}
	table.sort(function (a, b) {
	return a.freq > b.freq;
	});
	return table;
	}
	function createHuffmanTree(freqTable) {
	while (freqTable.length > 1) {
	let firstItem = freqTable.splice(0, 1)[0];
	let secondItem = freqTable.splice(0, 1)[0];
	let newFreq = firstItem.freq + secondItem.freq;
	let hasUpperBoundary = false;
	let _newInstance = {
	leaf: false,
	key: {
	left: firstItem,
	right: secondItem
	},
	freq: newFreq
	};
	for (let i = 0; i < freqTable.length; i++) {
	if (freqTable[i].freq > newFreq) {
	hasUpperBoundary = true;
	freqTable.splice(i, 0, _newInstance);
	break;
	}
	}
	if (!hasUpperBoundary) {
	// it append to last
	freqTable.push(_newInstance);
	}
	}
	return freqTable[0];
	}
	function createMappingTableFromTree(tree, hashedData, prefix) {
	// visit current node
	prefix = prefix \|\| '';
	if (tree.leaf) {
	hashedData[tree.key] = prefix;
	return;
	}
	createMappingTableFromTree(tree.key.left, hashedData, prefix + '0');
	createMappingTableFromTree(tree.key.right, hashedData, prefix + '1');
	}
	function encodeData(inputStr, encodedTable) {
	let encodedStr = '';
	for (let i = 0, length = inputStr.length; i < length; i++) {
	encodedStr = encodedStr + encodedTable[inputStr[i]];
	}

	// The first 32 bit will represent the size of code
	let sizeOfFile = stringHelper.zeroPad(encodedStr.length.toString(2), 32);
	encodedStr = sizeOfFile + encodedStr;
	let bitZerosCountAddedAfter = Math.ceil(encodedStr.length / 8) * 8 - encodedStr.length;
	encodedStr += "0".repeat(bitZerosCountAddedAfter);


	return stringHelper.toAscii(encodedStr);
	}
	function encodeHuffman() {
	let inputStr = OriginalData.value;
	let freqTable = createFrequencyTable(inputStr);
	let huffmanTree = createHuffmanTree(freqTable);
	let encodedTable = {};
	createMappingTableFromTree(huffmanTree, encodedTable);
	let encodedData = encodeData(inputStr, encodedTable);
	EncodedData.innerHTML = encodedData;
	ratio.innerText = ((inputStr.length - encodedData.length)/ inputStr.length * 100).toFixed(2)+'%';
	}
	</script>
	</html>