JS实现的哈夫曼编码示例【原始版与修改版】

本文实例讲述了JS实现的哈夫曼编码。分享给大家供大家参考,具体如下:

原始版

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))

修改版

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();

更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

您可能感兴趣的文章:

  • js 编码转换 gb2312 和 utf8 互转的2种方法
  • Javascript下的urlencode编码解码方法附decodeURIComponent
  • js对图片base64编码字符串进行解码并输出图像示例
  • js 显示base64编码的二进制流网页图片
  • utf-8编码引起js输出中文乱码的解决办法
  • 通过javascript进行UTF-8编码的实现方法
  • 将字符串转换成gb2312或者utf-8编码的参数(js版)
  • JS 文字符串转换unicode编码函数
  • JavaScript Base64编码和解码,实现URL参数传递。
  • JavaScript实现Base64编码转换
  • js下用gb2312编码解码实现方法
(0)

相关推荐

  • js 显示base64编码的二进制流网页图片

    Data URI scheme. Data URI scheme是在RFC2397中定义的,目的是将一些小的数据,直接嵌入到网页中,从而不用再从外部文件载入.比如上面那串字符,其实是一张小图片,将这些字符复制黏贴到火狐的地址栏中并转到,就能看到它了,一张2*2的白色gif图片. 在上面的Data URI中,data表示取得数据的协定名称,image/gif是数据类型名称,base64 是数据的编码方法,逗号后面就是这个image/gif文件base64编码后的数据. 目前,Data URI sc

  • JavaScript Base64编码和解码,实现URL参数传递。

    为什么需要对参数进行编码?相信有过开发的经验的广大程序员都知道,在Web中,若是直接在Url地址上传递参数值,若是中文,或者+等什么的就会出现乱码现象,若是数字或者英文的好象没有什么问题,简言之,传递过来的参数是需要进行编码的.在这里,也许有人会说,为什么不直接用Server.UrlDecode和Server.UrlEncode这两个来进行编码和解码的操作呢? 的确,这两个服务器端对象很好使用,用起来也很方便,但是,若在客户端是HTML的Input,查询的时候页面是HTML或者其他的,反正不是.

  • js 编码转换 gb2312 和 utf8 互转的2种方法

    方法一: 复制代码 代码如下: function gb2utf8(data){       var glbEncode = [];       gb2utf8_data = data;       execScript("gb2utf8_data = MidB(gb2utf8_data, 1)", "VBScript");       var t=escape(gb2utf8_data).replace(/%u/g,"").replace(/(.

  • JavaScript实现Base64编码转换

    简介 Base64是一种基于64个可打印字符来表示二进制数据的表示方法.由于2的6次方等于64,所以每6个比特为一个单元,对应某个可打印字符.三个字节有24个比特,对应于4个Base64单元,即3个字节需要用4个可打印字符来表示.它可用来作为电子邮件的传输编码.在Base64中的可打印字符包括字母A-Z.a-z.数字0-9,这样共有62个字符,此外的两个可打印符号在不同的系统中而不同,一般为+和/. 转换原理 Base64的直接数据源是二进制序列(Binary Sequence).当然,你也可以

  • 通过javascript进行UTF-8编码的实现方法

    javascript的字符集: javascript程序是使用Unicode字符集编写的.Unicode是ASCII和Latin-1的超集,并支持地球上几乎所有的语言.ECMAScript3要求JavaScript必须支持Unicode2.1及后续版本,ECMAScript5则要求支持Unicode3及后续版本.所以,我们编写出来的 javascript程序,都是使用Unicode编码的. UTF-8 UTF-8(UTF8-bit Unicode Transformation Format)是一

  • 将字符串转换成gb2312或者utf-8编码的参数(js版)

    在很多时候,我们直接在url中传递中文参数时,读到的中文都是乱码,那么我们应该怎么将这些参数转换呢? 下面我们来介绍一下方法 1.我们新建一个 UrlEncode.js 然后将下面的代码拷贝进去 复制代码 代码如下: //JS版的Server.UrlEncode编码函数 String.prototype.UrlEncodeGB2312 = function () { var str = this; str = str.replace(/./g, function (sHex) { window.

  • js对图片base64编码字符串进行解码并输出图像示例

    复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv=&qu

  • JS 文字符串转换unicode编码函数

    复制代码 代码如下: function uniencode(text) { text = escape(text.toString()).replace(/\+/g, "%2B"); var matches = text.match(/(%([0-9A-F]{2}))/gi); if (matches) { for (var matchid = 0; matchid < matches.length; matchid++) { var code = matches[matchid

  • js下用gb2312编码解码实现方法

    需求 在js中将中文用gb2312编码.如,"我"编码后应该是"%CE%D2". 分析 大家知道,encodeURI和encodeURIComponent会用utf-8编码,如"我"编码后是"%E6%88%91".据实验,似乎没有参数指定编码的地方.只有另寻他法. 大致分析有如下几种解决方案: 1. 用js创建一个隐藏的iframe并指定其为gb2312编码,将需要转换的文本放到iframe的form的一个input中,将fo

  • Javascript下的urlencode编码解码方法附decodeURIComponent

    关于在ASP(Server.UrlEncode).PHP(urlencode())函数编码结果,或是经过asp.php等动态语言直接写入COOKIES的中文字符,用JS读取的时候,都会碰到一个编码的问题,那就是最终字符串被urlencode编码了,而又时有需要从JS在客户端去读取这些数据. 而本文,就大概说说如何在js中通过系统自带的函数去解决这个问题. 而相信碰到过此问题的朋友应该都有所了解,目前网络上流行一些js下的自定义函数去解决这个问题,如说vbscript(URLDecode()).j

  • utf-8编码引起js输出中文乱码的解决办法

    编码规则是utf-8,如网页头中的: <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> 那么js文件中如果有中文输出就会出现乱码,解决此个问题有两个方法: 1.在引用javascript输出的地方加上charset="gb2312" 或 charset="big5"(假设输出的是Big5繁体字). 例: <script

随机推荐