hpphat92/huffman_store_restruction_tree.html

## huffman_store_restruction_tree.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,
                    representKey: 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
                },
                representKey: firstItem.representKey,
                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 storeHuffmanTree(huffmanTree) {
        let keys = [];
        keys.push(huffmanTree.representKey);
        let queue = [huffmanTree];
        while (queue.length) {
            let currentNode = queue.pop();
            let leftNode = currentNode.key.left,
                    rightNode = currentNode.key.right;
            if (!leftNode.leaf) {
                queue.push(leftNode);
            }
            if (!rightNode.leaf) {
                queue.push(rightNode);
            }
            keys.push(leftNode.representKey);
            keys.push(rightNode.representKey);
        }
        return keys.join('');
    }
    function restoreHuffmanTree(arrCode) {
        arrCode = arrCode.split('');
        if (!arrCode.length) {
            return;
        }
        let rootNode = {
            leaf: true,
            key: arrCode[0],
            representKey: arrCode[0]
        };
        if (arrCode.length === 1) {
            return rootNode;
        }
        let queueNoeds = [rootNode];
        for (let idx = 1, length = arrCode.length; idx < length; idx += 2) {
            let leftNode = arrCode[idx];
            let rightNode = arrCode[idx + 1];
            for (let i = 0, l = queueNoeds.length; i < l; i++) {
                if (queueNoeds[i].representKey === leftNode && queueNoeds[i].leaf) {
                    let left = {
                        leaf: true,
                        key: leftNode,
                        representKey: leftNode
                    };
                    let right = {
                        leaf: true,
                        key: rightNode,
                        representKey: rightNode
                    };
                    queueNoeds[i].leaf = false;
                    queueNoeds[i].key = {
                        left: left,
                        right: right
                    };
                    queueNoeds.push(left);
                    queueNoeds.push(right);
                    break;
                }
            }
        }
        return rootNode;
    }
    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 = {};
        let encodedHuffmanTree = storeHuffmanTree(huffmanTree);
        createMappingTableFromTree(huffmanTree, encodedTable);
        let encodedData = encodeData(inputStr, encodedTable);
        let restoredHuffmanTree = restoreHuffmanTree(encodedHuffmanTree);
        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,
	representKey: 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
	},
	representKey: firstItem.representKey,
	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 storeHuffmanTree(huffmanTree) {
	let keys = [];
	keys.push(huffmanTree.representKey);
	let queue = [huffmanTree];
	while (queue.length) {
	let currentNode = queue.pop();
	let leftNode = currentNode.key.left,
	rightNode = currentNode.key.right;
	if (!leftNode.leaf) {
	queue.push(leftNode);
	}
	if (!rightNode.leaf) {
	queue.push(rightNode);
	}
	keys.push(leftNode.representKey);
	keys.push(rightNode.representKey);
	}
	return keys.join('');
	}
	function restoreHuffmanTree(arrCode) {
	arrCode = arrCode.split('');
	if (!arrCode.length) {
	return;
	}
	let rootNode = {
	leaf: true,
	key: arrCode[0],
	representKey: arrCode[0]
	};
	if (arrCode.length === 1) {
	return rootNode;
	}
	let queueNoeds = [rootNode];
	for (let idx = 1, length = arrCode.length; idx < length; idx += 2) {
	let leftNode = arrCode[idx];
	let rightNode = arrCode[idx + 1];
	for (let i = 0, l = queueNoeds.length; i < l; i++) {
	if (queueNoeds[i].representKey === leftNode && queueNoeds[i].leaf) {
	let left = {
	leaf: true,
	key: leftNode,
	representKey: leftNode
	};
	let right = {
	leaf: true,
	key: rightNode,
	representKey: rightNode
	};
	queueNoeds[i].leaf = false;
	queueNoeds[i].key = {
	left: left,
	right: right
	};
	queueNoeds.push(left);
	queueNoeds.push(right);
	break;
	}
	}
	}
	return rootNode;
	}
	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 = {};
	let encodedHuffmanTree = storeHuffmanTree(huffmanTree);
	createMappingTableFromTree(huffmanTree, encodedTable);
	let encodedData = encodeData(inputStr, encodedTable);
	let restoredHuffmanTree = restoreHuffmanTree(encodedHuffmanTree);
	EncodedData.innerHTML = encodedData;
	ratio.innerText = ((inputStr.length - encodedData.length) / inputStr.length * 100).toFixed(2) + '%';
	}
	</script>
	</html>