SHARE
TWEET

haffman code

a guest Oct 23rd, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. function node(inp_name, inp_fr, inp_used, inp_code, inp_link){
  2.     this.name = inp_name;
  3.     this.fr = inp_fr;
  4.     this.used = inp_used;
  5.     this.code = inp_code;
  6.     this.link = inp_link;
  7. }
  8.  
  9.  
  10. function reverseString(str) {
  11.     return str.split("").reverse().join("");
  12. }
  13.  
  14. str = 'abrakadabra';
  15. alph = new Array();
  16.  
  17. for(i=0;i<str.length;i++){
  18.     if (!alph[str.charAt(i)]) alph[str.charAt(i)] = 0;
  19.     alph[str.charAt(i)]++;
  20. }
  21.  
  22. // for(i in alph){
  23. //     console.log(i,' ',alph[i]);
  24. // }
  25.  
  26. tree = new Array();
  27. var freeIdx = 0;
  28.  
  29. for(i in alph){
  30.     n = new node(i, alph[i], 0, '', null);
  31.     tree.push(n);
  32.     ++freeIdx;
  33. }
  34.  
  35.  
  36. // for(i=0;i<tree.length;i++)
  37. //     console.log(tree[i]);
  38.  
  39. var active = 1e9;
  40. for (;active>1;){
  41.  
  42.     active = 0;
  43.     var firstMin = freeIdx;
  44.     var firstMinVal = 0;
  45.  
  46.     var secondMin = freeIdx;
  47.     var secondMinVal = 0;
  48.    
  49.     for (let i = freeIdx - 1; i >= 0; --i){
  50.         if (tree[i].used == 0){
  51.             if (tree[i].fr < secondMinVal || secondMinVal == 0){
  52.                 if (tree[i].fr < firstMinVal || firstMinVal == 0){
  53.                     secondMin = firstMin;
  54.                     secondMinVal = firstMinVal;
  55.  
  56.                     firstMinVal = tree[i].fr;
  57.                     firstMin = i;                    
  58.                 } else {
  59.                     secondMin = i;
  60.                     secondMinVal = tree[i].fr;
  61.                 }
  62.             }
  63.             ++active;
  64.         }
  65.     }
  66.     console.log(firstMin, secondMin, active);
  67.  
  68.     if (active == 1)
  69.         break;
  70.  
  71.     tree[freeIdx] = new node(tree[firstMin].name.concat(tree[secondMin].name),
  72.         tree[firstMin].fr + tree[secondMin].fr,
  73.         0, '', freeIdx);
  74.  
  75.     tree[firstMin].used = 1;
  76.     tree[firstMin].code = '0';
  77.     tree[firstMin].link = freeIdx;
  78.  
  79.     tree[secondMin].used = 1;
  80.     tree[secondMin].code = '1';
  81.     tree[secondMin].link = freeIdx;
  82.  
  83.     ++freeIdx;
  84. }
  85. for (let i = 0; tree[i].name.length == 1; ++i){
  86.     var curr = i;
  87.     var code = "";
  88.     while(tree[curr].used == 1){
  89.         code = code.concat(tree[curr].code);
  90.         curr = tree[curr].link;
  91.     }
  92.     console.log(tree[i].name + ' ' + reverseString(code));
  93. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top