Skip to content

Instantly share code, notes, and snippets.

@hpphat92

hpphat92/unzip_huffman.html

Created February 27, 2017 14:54
Show Gist options
  • Save hpphat92/939b5320f4d5ab148fa1dba069d628dd to your computer and use it in GitHub Desktop.
Save hpphat92/939b5320f4d5ab148fa1dba069d628dd to your computer and use it in GitHub Desktop.
Download ZIP
Unzip data from static huffman algo
Raw
unzip_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>
<div>
Decoded Data:
<blockquote id="Decoded"></blockquote>
</div>
<div>
Result:
<blockquote id="Result"></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 encodeData2(inputStr, encodedTable) {
let encodedStr = '';
for (let i = 0, length = inputStr.length; i < length; i++) {
encodedStr = encodedStr + encodedTable[inputStr[i]];
}
let size = (8 - (encodedStr.length + 3) % 8) % 8;
// The first 32 bit will represent the size of code
let sizeOfFile = stringHelper.zeroPad(size.toString(2), 3);
encodedStr = sizeOfFile + encodedStr;
encodedStr += "0".repeat(size);
console.log('we used ', size, 'additional zero-bit');
return stringHelper.toAscii(encodedStr);
}
function traverseTree(binaryData, tree) {
let originalData = [];
let currentNode = tree;
for (let i = 0, currentBit, length = binaryData.length; i <= length;) {
currentBit = binaryData[i];
if (currentNode.leaf) {
originalData.push(currentNode.representKey);
currentNode = tree;
} else {
if (currentBit === '1') {
currentNode = currentNode.key.right;
} else {
currentNode = currentNode.key.left;
}
i++;
}
}
return originalData.join('');
}
function extractBitData(encodedData, tree) {
let binaryData = stringHelper.toBinary(encodedData, false);
let cSize = parseInt(binaryData.slice(0, 3), 2);
let originalBinaryData = binaryData.slice(3, binaryData.length - cSize);
return {
size: cSize,
originalBinaryData: originalBinaryData,
decodedData: traverseTree(originalBinaryData, tree)
}
}
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 = encodeData2(inputStr, encodedTable);
let restoredHuffmanTree = restoreHuffmanTree(encodedHuffmanTree);
EncodedData.innerHTML = encodedData;
ratio.innerText = ((inputStr.length - encodedData.length) / inputStr.length * 100).toFixed(2) + '%';
let convertedBitData = extractBitData(encodedData, restoredHuffmanTree);
console.log(Decoded.innerText = convertedBitData.decodedData)
console.log(Result.innerText = (convertedBitData.decodedData === inputStr?'Match':'Not Match'))
}
</script>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment