使用霍夫曼算法解压缩 [英] uncompress using huffmen algorithm

问题描述

我使用huffmen算法在javascript中压缩了字符串文本.
现在，我想使用huffmen算法在c#中解压缩压缩的数据.

这是javascript中使用的代码:

I Compressed my string text in javascript using huffmen algorithm.
Now I want to decompress compressed data in c# using huffmen algorithm.

Here''s the code used in javascript:

function compress()
 {
    var input = document.getElementById("input").value;
    var output_str = document.getElementById('<%= OutPutTB.ClientID %>');

    var probabilities = getProbabilities(input);
    var codes = getCodes(probabilities);
    var output = compressHuffman(input, codes);
    output_str.value=output;
}

function sortNumberAsc(a, b) {
    return a[1] - b[1];
}

function getCodes(prob) {
    var tree = new Array();
    var secondTree = new Array();

    this.getNext = function() {
    if (tree.length > 0 && secondTree.length > 0
               && tree[0].prob < secondTree[0].prob)
      return tree.shift();

    if (tree.length > 0 && secondTree.length > 0
                && tree[0].prob > secondTree[0].prob)
      return secondTree.shift();

    if (tree.length > 0)
      return tree.shift();

    return secondTree.shift();
    }
    var sortedProb = new Array();
    var codes = new Array();

    var x = 0;
    for (var elem in prob) {
      sortedProb[x] = new Array(elem, prob[elem]);
      x = x + 1;
    }

    sortedProb = sortedProb.sort(sortNumberAsc);
    x = 0;

    for (var elem in sortedProb) {
      tree[x] = new node();
      tree[x].prob = sortedProb[elem][1];
      tree[x].value = sortedProb[elem][0];
      x = x + 1;
    }
    while (tree.length + secondTree.length > 1) {
        var left = getNext();
        var right = getNext();
        var newnode = new node();
        newnode.left = left;
        newnode.right = right;
        newnode.prob = left.prob + right.prob;
        newnode.left.parent = newnode;
        newnode.right.parent = newnode;
        secondTree.push(newnode);
    }

    var currentnode = secondTree[0];
    var code = "";
    while (currentnode) {
        if (currentnode.value) {
            codes[currentnode.value] = code;
            code = code.substr(0, code.length - 1);
            currentnode.visited = true;
            currentnode = currentnode.parent;
        }
        else if (!currentnode.left.visited) {
            currentnode = currentnode.left;
            code += "0";
        }
        else if (!currentnode.right.visited) {
            currentnode = currentnode.right;
            code += "1";
        }
        else {
            currentnode.visited = true;
            currentnode = currentnode.parent;
            code = code.substr(0, code.length - 1);
        }
    }
    return codes;
}

function node() {
  this.left = null;
  this.right = null;
  this.prob = null;
  this.value = null;
  this.code = "";
  this.parent = null;
  this.visited = false;
}

function compressHuffman(input, codes) {
  var output = input.split("");
  for (var elem in output) {
      output[elem] = codes[output[elem]];
  }
  return output.join("");
}

function getProbabilities(input) {
  var prob = new Array();
  var x = 0;
  var len = input.length;
  while (x < len) {
      var chr = input.charAt(x);
      if (prob[chr]) {
          prob[chr] = prob[chr] + 1;
      }
      else {
          prob[chr] = 1;
      }
      x++;
  }

  for (var elem in prob) {
      prob[elem] = prob[elem] / len;
  }
  return prob;
}

推荐答案

我搜索了一会儿，发现此 [ ^ ]链接.

希望这可以帮助您构建算法

谢谢
-Amit Gajjar.

Hi,

I search for a while and found this[^] link.

hope this may help you to build your algorithm

thanks
-Amit Gajjar.

这篇关于使用霍夫曼算法解压缩的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！