How to use JS to implement Huffman coding
This time I will show you how to use JS to implement Huffman coding, and what are the precautions for using JS to implement Huffman coding. The following is a practical case, let's take a look.
Original version
function cal(str) {
if (typeof str !== 'string' || str.length < 1) {
return;
}
var map = {};
var i = 0;
while(str[i]) {
map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1);
i++;
}
return map;
}
function sort(map) {
map = map || {};
var result = [];
for (key in map) {
if(map.hasOwnProperty(key)) {
var obj = {
key: key,
val: map[key]
};
result.push(new Node(null, null, obj));
}
}
return result.sort(function(x,y){return x.data.val > y.data.val});
}
function Node(left, right, data) {
this.left = left;
this.right = right;
this.data = data;
}
function makeTree(table) {
var i = 0;
var len = table.length;
var node1;
var node2;
var parentNode;
while(table.length > 1) {
parentNode = new Node(table[i], table[i+1], {key: null, val: table[i]['data'].val + table[i+1]['data'].val});
table.splice(i,2);
table.unshift(parentNode);
table.sort(function(x,y){return x.data.val > y.data.val});
}
return table;
}
function encode(str, ret) {
if (typeof str !== 'string' || str.length < 1) {
return;
}
var i = 0;
var result = '';
while(str[i]) {
result += ret[str[i++]];
}
return result
}
function reverseRet(ret) {
var result = {};
for (key in ret) {
if(ret.hasOwnProperty(key)) {
result[ret[key]] = key;
}
}
return result;
}
function decode(str, ret) {
var i = 0;
var result = '';
var data = '';
var map = reverseRet(ret);
while(str) {
result += str[i++];
if (result in map) {
data += map[result];
str = str.replace(new RegExp("^"+result),'');
result = '';
i = 0;
}
}
console.log(data)
}
function traversal(tree, code, ret) {
if (tree.left !== null) {
traversal(tree.left, code + '0', ret);
} else {
ret[tree.data.key] = code;
}
if (tree.right !== null) {
traversal(tree.right,code + '1', ret);
} else {
ret[tree.data.key] = code;
}
}
var ret = {};
var str = 'ew qew qd ef 24 gf ewr getElementsByTagName';
traversal(makeTree(sort(cal(str)))[0],'', ret)
decode(encode(str, ret), ret)
btoa(encode(str,ret))Modified version
function Huffman(str) {
// 需要编码的字符串
this.str = str;
// 键和频率映射表
this.keyCountMap = null;
// 编码和键的映射表
this.codeKeyMap = {};
// 键和编码的映射表
this.keyCodeMap = {};
// 哈夫曼树节点列表
this.nodeList = null;
// 哈夫曼树根节点
this.root = null;
// 哈夫曼编码后的01序列
this.code = null;
}
Huffman.prototype.cal = function cal() {
str = this.str;
var map = {};
var i = 0;
while(str[i]) {
map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1);
i++;
}
this.keyCountMap = map;
}
Huffman.prototype.sort = function sort() {
map = this.keyCountMap;
var result = [];
for (key in map) {
if(map.hasOwnProperty(key)) {
var obj = {
key: key,
val: map[key]
};
result.push(new Node(null, null, obj));
}
}
this.nodeList = result.sort(function(x,y){return x.data.val > y.data.val});
}
function Node(left, right, data) {
this.left = left;
this.right = right;
this.data = data;
}
Huffman.prototype.makeTree = function makeTree() {
var i = 0;
var len = this.nodeList.length;
var node1;
var node2;
var parentNode;
var table = this.nodeList;
while(table.length > 1) {
parentNode = new Node(table[i], table[i+1], {key: null, val: table[i]['data'].val + table[i+1]['data'].val});
table.splice(i,2);
table.unshift(parentNode);
table.sort(function(x,y){return x.data.val > y.data.val});
}
this.root = table[0] || new Node();
return this.root;
}
Huffman.prototype.traversal = function traversal(tree, code) {
if (tree.left !== null) {
traversal.call(this,tree.left, code + '0');
} else {
this.keyCodeMap[tree.data.key] = code;
}
if (tree.right !== null) {
traversal.call(this, tree.right,code + '1');
} else {
this.keyCodeMap[tree.data.key] = code;
}
}
Huffman.prototype.encode = function encode() {
this.cal();
this.sort();
var root = this.makeTree();
this.traversal(root, '');
var ret = this.keyCodeMap;
var i = 0;
var result = '';
var str = this.str;
while(str[i]) {
result += ret[str[i++]];
}
this.code = result;
console.log('encode:' + result);
return result
}
Huffman.prototype.reverseMap = function reverseMap() {
var ret = this.keyCodeMap;
var result = {};
for (key in ret) {
if(ret.hasOwnProperty(key)) {
result[ret[key]] = key;
}
}
this.codeKeyMap = result;
return result;
}
Huffman.prototype.decode = function decode() {
var i = 0;
var result = '';
var data = '';
var map = this.reverseMap();
var str = this.code;
while(str) {
result += str[i++];
if (result in map) {
data += map[result];
str = str.replace(new RegExp("^"+result),'');
result = '';
i = 0;
}
}
console.log("decode:" + data)
}
Huffman.prototype.encodeBase64 = function() {
try {
var base64 = btoa(this.code);
return base64;
} catch(e) {
return '';
}
}
var str = 'ew qew qd ef 24 gf ewr getElementsByTagName';
var huffman = new Huffman(str)
huffman.encode(str)
huffman.decode();
huffman.encodeBase64();Use Vue to make a pager (with code)
How to make a vue mobile implementation Pull-down refresh function
How to use router to pass parameters in Vue.js
The above is the detailed content of How to use JS to implement Huffman coding. For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
How to implement dual WeChat login on Huawei mobile phones?
Mar 24, 2024 am 11:27 AM
How to implement dual WeChat login on Huawei mobile phones? With the rise of social media, WeChat has become one of the indispensable communication tools in people's daily lives. However, many people may encounter a problem: logging into multiple WeChat accounts at the same time on the same mobile phone. For Huawei mobile phone users, it is not difficult to achieve dual WeChat login. This article will introduce how to achieve dual WeChat login on Huawei mobile phones. First of all, the EMUI system that comes with Huawei mobile phones provides a very convenient function - dual application opening. Through the application dual opening function, users can simultaneously
PHP Programming Guide: Methods to Implement Fibonacci Sequence
Mar 20, 2024 pm 04:54 PM
The programming language PHP is a powerful tool for web development, capable of supporting a variety of different programming logics and algorithms. Among them, implementing the Fibonacci sequence is a common and classic programming problem. In this article, we will introduce how to use the PHP programming language to implement the Fibonacci sequence, and attach specific code examples. The Fibonacci sequence is a mathematical sequence defined as follows: the first and second elements of the sequence are 1, and starting from the third element, the value of each element is equal to the sum of the previous two elements. The first few elements of the sequence
Knowledge graph: the ideal partner for large models
Jan 29, 2024 am 09:21 AM
Large language models (LLMs) have the ability to generate smooth and coherent text, bringing new prospects to areas such as artificial intelligence conversation and creative writing. However, LLM also has some key limitations. First, their knowledge is limited to patterns recognized from training data, lacking a true understanding of the world. Second, reasoning skills are limited and cannot make logical inferences or fuse facts from multiple data sources. When faced with more complex and open-ended questions, LLM's answers may become absurd or contradictory, known as "illusions." Therefore, although LLM is very useful in some aspects, it still has certain limitations when dealing with complex problems and real-world situations. In order to bridge these gaps, retrieval-augmented generation (RAG) systems have emerged in recent years. The core idea is
How to implement the WeChat clone function on Huawei mobile phones
Mar 24, 2024 pm 06:03 PM
How to implement the WeChat clone function on Huawei mobile phones With the popularity of social software and people's increasing emphasis on privacy and security, the WeChat clone function has gradually become the focus of people's attention. The WeChat clone function can help users log in to multiple WeChat accounts on the same mobile phone at the same time, making it easier to manage and use. It is not difficult to implement the WeChat clone function on Huawei mobile phones. You only need to follow the following steps. Step 1: Make sure that the mobile phone system version and WeChat version meet the requirements. First, make sure that your Huawei mobile phone system version has been updated to the latest version, as well as the WeChat App.
Master how Golang enables game development possibilities
Mar 16, 2024 pm 12:57 PM
In today's software development field, Golang (Go language), as an efficient, concise and highly concurrency programming language, is increasingly favored by developers. Its rich standard library and efficient concurrency features make it a high-profile choice in the field of game development. This article will explore how to use Golang for game development and demonstrate its powerful possibilities through specific code examples. 1. Golang’s advantages in game development. As a statically typed language, Golang is used in building large-scale game systems.
How to implement exact division operation in Golang
Feb 20, 2024 pm 10:51 PM
Implementing exact division operations in Golang is a common need, especially in scenarios involving financial calculations or other scenarios that require high-precision calculations. Golang's built-in division operator "/" is calculated for floating point numbers, and sometimes there is a problem of precision loss. In order to solve this problem, we can use third-party libraries or custom functions to implement exact division operations. A common approach is to use the Rat type from the math/big package, which provides a representation of fractions and can be used to implement exact division operations.
PHP Game Requirements Implementation Guide
Mar 11, 2024 am 08:45 AM
PHP Game Requirements Implementation Guide With the popularity and development of the Internet, the web game market is becoming more and more popular. Many developers hope to use the PHP language to develop their own web games, and implementing game requirements is a key step. This article will introduce how to use PHP language to implement common game requirements and provide specific code examples. 1. Create game characters In web games, game characters are a very important element. We need to define the attributes of the game character, such as name, level, experience value, etc., and provide methods to operate these
Using PHP to implement SaaS: a comprehensive analysis
Mar 07, 2024 pm 10:18 PM
I'm really sorry that I can't provide real-time programming guidance, but I can provide you with a code example to give you a better understanding of how to use PHP to implement SaaS. The following is an article within 1,500 words, titled "Using PHP to implement SaaS: A comprehensive analysis." In today's information age, SaaS (Software as a Service) has become the mainstream way for enterprises and individuals to use software. It provides a more flexible and convenient way to access software. With SaaS, users don’t need to be on-premises
