huffman编码

典型的,精妙,但是难以维护的代码。
这里有memory leakage吗?
我说没有,你信吗?
哈哈!!!

#include <iostream>
#include <list>
#include <algorithm>
#include <vector>
#include <iterator>


struct Node{
  Node *parent,*children,*next;
  void* data;
};

struct prob_compare:std::binary_function<Node*,Node*,bool >{
  bool operator( ) ( first_argument_type a, 
                     second_argument_type b ){
      //    std::cout<<"a:"<<*(reinterpret_cast<double*>(a->data))<<std::endl;
      //    std::cout<<"b:"<<*(reinterpret_cast<double*>(b->data))<<std::endl;
    return (result_type) ( *(reinterpret_cast<double*>(b->data)) 
                           > *(reinterpret_cast<double*>(a->data)));
  }
};

///将probs数组中的内容,按照n进制huffman编码
///返回值中,每个std::vector<CodedType>是一个码字的编码
template <typename ProbabilityType //每个码字所对应的概率的类型
          ,typename CodedType> //码字的类型,它的有效值范围从0到n-1
std::vector<std::vector<CodedType> > 
huffmanEncode( ProbabilityType probs[], ///码字的概率
               size_t len  ///上面这个数组的长度
               ,CodedType n  ///采用n进制编码
               ){

  std::list<Node*> nodes;
  for(size_t i=0;i!=len;++i){
    Node* node=new Node;
    node->children=NULL;
    node->data=probs+i;
    nodes.push_back(node);
  }
  typedef std::list<Node*>::iterator Iter;

  while(nodes.size()!=1){
    Node* node_parent= new Node;
    memset(node_parent,0,sizeof(Node));

    Node* prev=NULL;
    for(CodedType i=0;i!=n && nodes.size()!=0;++i){
      Iter min1=std::min_element(nodes.begin(),nodes.end(),prob_compare());
      Node* node1=*min1;
      nodes.erase(min1);
      node1->parent=node_parent;
      if(prev!=NULL){
        *(reinterpret_cast<ProbabilityType*>(node1->data)) +=
          *(reinterpret_cast<ProbabilityType*>(prev->data));
        prev->next=node1;
      }else{ 
        node_parent->children=node1;
      }
      prev=node1;
    }
    prev->next=NULL;
    node_parent->data=prev->data;
    nodes.push_back(node_parent);
  }

  std::vector<std::vector<CodedType > > result(len);

  Node* p=*nodes.begin();

  std::vector<CodedType> status;

  while(1){
    if(p->children==NULL){        
      result[reinterpret_cast<ProbabilityType*>(p->data)-probs]=status;
      while(p->next==NULL){
        status.pop_back();
        delete p;
        p=p->parent;
        if(p==NULL)
          goto out;
      }

      delete p;
      p=p->next;
      status.back()++;
    }
    else{
      p=p->children;
      status.push_back(0);
      continue;
    }      
  };

 out: return result;            
}




int main(int argc,char* argv[]){

  // int a[]={1,2,3,4,5};
  double b[]={0.25,0.25,0.2,0.15,0.15};
  std::vector<std::vector<int > > result=huffmanEncode<double,int>(b,5,2);
  for(std::vector<std::vector<int > >::iterator i=result.begin();
      i!=result.end();
      ++i){
    std::copy(i->begin(),i->end(),std::ostream_iterator<int>(std::cout," "));
    std::cout<<std::endl;
  }
  return 0;
}

n进制huffman编码的时候,有时候是要添字符的。这个目前还是不大清楚。改天再改。
另外,这么小一个东西居然都要把tree扯出来。我觉得这个是严重降低效率。我觉得一定有不用tree就可以实现huffman编码的方式。那些所谓的data structs,除了用来帮我管理内存外,我不知道有啥用途。
不管了不管了
冷飕飕的,我去健身房。

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥