哈夫曼编码的程序实现
发布网友
发布时间：2022-04-22 02:59
共2个回答
懂视网
时间：2022-05-15 03:39
原始版
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.encodeBase = function() {
try {
var base = btoa(this.code);
return base;
} catch(e) {
return '';
}
}
var str = 'ew qew qd ef 24 gf ewr getElementsByTagName';
var huffman = new Huffman(str)
huffman.encode(str)
huffman.decode();
huffman.encodeBase();相信看了本文案例你已经掌握了方法，更多精彩请关注Gxl网其它相关文章！
推荐阅读：
使用Vue做出分页器（附代码）
如何做出vue移动端实现下拉刷新功能
如何使用Vue.js中router传参
热心网友
时间：2022-05-15 00:47
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define M 100
typedef struct Fano_Node
{
char ch;
float weight;
}FanoNode[M];
typedef struct node
{
int start;
int end;
struct node *next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode *front;
LinkQueueNode *rear;
}LinkQueue;
//建立队列
void EnterQueue(LinkQueue *q,int s,int e)
{
LinkQueueNode *NewNode;
//生成新节点
NewNode=(LinkQueueNode*)malloc(sizeof( LinkQueueNode ));
if(NewNode!=NULL)
{
NewNode->start=s;
NewNode->end=e;
NewNode->next=NULL;
q->rear->next=NewNode;
q->rear=NewNode;
}
else
{
printf(Error!);
exit(-1);
}
}
//按权分组
void Divide(FanoNode f,int s,int *m,int e)
{
int i;
float sum,sum1;
sum=0;
for(i=s;i<=e;i++)
sum+=f[i].weight;//
*m=s;
sum1=0;
for(i=s;i<e;i++)
{
sum1+=f[i].weight;
*m=fabs(sum-2*sum1)>fabs(sum-2*sum1-2*f[i+1].weight)?(i+1):*m;
if(*m==i) break;
}
}
void main()
{
int i,j,n,max,m,h[M];
int sta,end;
float w;
char c,fc[M][M];
FanoNode FN;
LinkQueueNode *p;
LinkQueue *Q;
//初始化队Q
Q=(LinkQueue *)malloc(sizeof(LinkQueue));
Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));
Q->rear=Q->front;
Q->front->next=NULL;
printf(\t***FanoCoding***\n);
printf(Please input the number of node:);
//输入信息
scanf(%d,&n);
//超过定义M,退出
if(n>=M)
{
printf(>=%d,M);
exit(-1);
}
i=1; //从第二个元素开始录入
while(i<=n)
{
printf(%d weight and node:,i);
scanf(%f %c,&FN[i].weight,&FN[i].ch);
for(j=1;j<i;j++)
{
if(FN[i].ch==FN[j].ch)//查找重复
{
printf(Same node!!!\n); break;
}
}
if(i==j)
i++;
}
//排序(降序)
for(i=1;i<=n;i++)
{
max=i+1;
for(j=max;j<=n;j++)
max=FN[max].weight<FN[j].weight?j:max;
if(FN[i].weight<FN[max].weight)
{
w=FN[i].weight;
FN[i].weight=FN[max].weight;
FN[max].weight=w;
c=FN[i].ch;
FN[i].ch=FN[max].ch;
FN[max].ch=c;
}
}
for(i=1;i<=n;i++) //初始化h
h[i]=0;
EnterQueue(Q,1,n); //1和n进队
while(Q->front->next!=NULL)
{
p=Q->front->next; //出队
Q->front->next=p->next;
if(p==Q->rear)
Q->rear=Q->front;
sta=p->start;
end=p->end;
free(p);
Divide(FN,sta,&m,end); /*按权分组*/
for(i=sta;i<=m;i++)
{
fc[i][h[i]]='0';
++h[i];
}
if(sta!=m)
EnterQueue(Q,sta,m);
else
fc[sta][h[sta]]='\0';
for(i=m+1;i<=end;i++)
{
fc[i][h[i]]='1';
++h[i];
}
if(m==sta&&(m+1)==end)
//如果分组后首元素的下标与中间元素的相等，
//并且和最后元素的下标相差为1，则编码码字字符串结束
{
fc[m][h[m]]='\0';
fc[end][h[end]]='\0';
}
else
EnterQueue(Q,m+1,end);
}
for(i=1;i<=n;i++) /*打印编码信息*/
{
printf(%c:,FN[i].ch);
printf(%s\n,fc[i]);
}
system(pause);
} #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
#define M 2*N-1
typedef char * HuffmanCode[2*M];//haffman编码
typedef struct
{
int weight;//权值
int parent;//父节节点
int LChild;//左子节点
int RChild;//右子节点
}HTNode,Huffman[M+1];//huffman树
typedef struct Node
{
int weight; //叶子结点的权值
char c; //叶子结点
int num; //叶子结点的二进制码的长度
}WNode,WeightNode[N];
/***产生叶子结点的字符和权值***/
void CreateWeight(char ch[],int *s,WeightNode CW,int *p)
{
int i,j,k;
int tag;
*p=0;//叶子节点个数
//统计字符出现个数,放入CW
for(i=0;ch[i]!='\0';i++)
{
tag=1;
for(j=0;j<i;j++)
if(ch[j]==ch[i])
{
tag=0;
break;
}
if(tag)
{
CW[++*p].c=ch[i];
CW[*p].weight=1;
for(k=i+1;ch[k]!='\0';k++)
if(ch[i]==ch[k])
CW[*p].weight++;//权值累加
}
}
*s=i;//字符串长度
}
/********创建HuffmanTree********/
void CreateHuffmanTree(Huffman ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
//初始化哈夫曼树
for(i=1;i<=n;i++)
{
ht[i].weight =w[i].weight;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s1=j; //找到第一个双亲为零的结点
for(;j<=i-1;j++)
if(!ht[j].parent)
s1=ht[s1].weight>ht[j].weight?j:s1;
ht[s1].parent=i;
ht[i].LChild=s1;
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s2=j; //找到第二个双亲为零的结点
for(;j<=i-1;j++)
if(!ht[j].parent)
s2=ht[s2].weight>ht[j].weight?j:s2;
ht[s2].parent=i;
ht[i].RChild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;//权值累加
}
}
/***********叶子结点的编码***********/
void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode h,WeightNode weight,int m,int n)
{
int i,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';//末尾置0
for(i=1;i<=n;i++)
{
start=n-1; //cd串每次从末尾开始
c=i;
p=ht[i].parent;//p在n+1至2n-1
while(p) //沿父亲方向遍历,直到为0
{
start--;//依次向前置值
if(ht[p].LChild==c)//与左子相同,置0
cd[start]='0';
else //否则置1
cd[start]='1';
c=p;
p=ht[p].parent;
}
weight[i].num=n-start; //二进制码的长度(包含末尾0)
h[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(h[i],&cd[start]);//将二进制字符串拷贝到指针数组h中
}
free(cd);//释放cd内存
system(pause);
}
/*********所有字符的编码*********/
void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)
{
int i,k;
for(i=0;i<m;i++)
{
for(k=1;k<=n;k++) /*从weight[k].c中查找与ch[i]相等的下标K*/
if(ch[i]==weight[k].c)
break;
hc[i]=(char *)malloc((weight[k].num)*sizeof(char));
strcpy(hc[i],h[k]); //拷贝二进制编码
}
}
/*****解码*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf(***StringInformation***\n);
while(i<m)
{
p=2*n-1;//从父亲节点向下遍历直到叶子节点
for(j=0;hc[i][j]!='\0';j++)
{
if(hc[i][j]=='0')
p=ht[p].LChild;
else
p=ht[p].RChild;
}
printf(%c,w[p].c); /*打印原信息*/
i++;
}
}
/*****释放huffman编码内存*****/
void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)
{
int i;
for(i=1;i<=n;i++)//释放叶子结点的编码
free(h[i]);
for(i=0;i<m;i++) //释放所有结点的编码
free(hc[i]);
}
void main()
{
int i,n=0; /*n为叶子结点的个数*/
int m=0; /*m为字符串ch[]的长度*/
char ch[N]; /*ch[N]存放输入的字符串*/
Huffman ht; /*Huffman二叉数*/
HuffmanCode h,hc; /*h存放叶子结点的编码，hc 存放所有结点的编码*/
WeightNode weight; /*存放叶子结点的信息*/
printf(\t***HuffmanCoding***\n);
printf(please input information :);
gets(ch); /*输入字符串*/
CreateWeight(ch,&m,weight,&n); /*产生叶子结点信息，m为字符串ch[]的长度*/
printf(***WeightInformation***\n Node );
for(i=1;i<=n;i++) /*输出叶子结点的字符与权值*/
printf(%c ,weight[i].c);
printf(\nWeight );
for(i=1;i<=n;i++)
printf(%d ,weight[i].weight);
CreateHuffmanTree(ht,weight,n); /*产生Huffman树*/
printf(\n***HuffamnTreeInformation***\n);
printf(\ti\tweight\tparent\tLChild\tRChild\n);
for(i=1;i<=2*n-1;i++) /*打印Huffman树的信息*/
printf(\t%d\t%d\t%d\t%d\t%d\n,i,ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild);
CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*叶子结点的编码*/
printf( ***NodeCode***\n); /*打印叶子结点的编码*/
for(i=1;i<=n;i++)
{
printf(\t%c:,weight[i].c);
printf(%s\n,h[i]);
}
CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字符的编码*/
printf(***StringCode***\n); /*打印字符串的编码*/
for(i=0;i<m;i++)
printf(%s,hc[i]);
system(pause);
TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/
FreeHuffmanCode(h,hc,n,m);
system(pause);
} Matlab 中简易实现Huffman编译码：
n=input('Please input the total number: ');
hf=zeros(2*n-1,5);
hq=[];
for ki=1:n
hf(ki,1)=ki;
hf(ki,2)=input('Please input the frequency: ');
hq=[hq,hf(ki,2)];
end
for ki=n+1:2*n-1
hf(ki,1)=ki;
mhq1=min(hq);
m=size(hq);
m=m(:,2);
k=1;
while k<=m%del min1
if hq(:,k)==mhq1
hq=[hq(:,1:(k-1)) hq(:,(k+1):m)];
m=m-1;
break
else
k=k+1;
end
end
k=1;
while hf(k,2)~=mhq1|hf(k,5)==1%find min1 location
k=k+1;
end
hf(k,5)=1;
k1=k;
mhq2=min(hq);
k=1;
while k<=m%del min2
if hq(:,k)==mhq2
hq=[hq(:,1:(k-1)) hq(:,(k+1):m)];
m=m-1;
break
else
k=k+1;
end
end
k=1;
while hf(k,2)~=mhq2|hf(k,5)==1%find min2 location
k=k+1;
end
hf(k,5)=1;
k2=k;
hf(ki,2)=mhq1+mhq2;
hf(ki,3)=k1;
hf(ki,4)=k2;
hq=[hq hf(ki,2)];
end
clc
choose=input('Please choose what you want:\n1: Encoding\n2: Decoding\n3:.Exit\n');
while choose==1|choose==2
if choose==1
a=input('Please input the letter you want to Encoding: ');
k=1;
while hf(k,2)~=a
k=k+1;
if k>=n
display('Error! You did not input this number.');
break
end
end
if k>=n
break
end
r=[];
while hf(k,5)==1
kc=n+1;
while hf(kc,3)~=k&hf(kc,4)~=k
kc=kc+1;
end
if hf(kc,3)==k
r=[0 r];
else
r=[1 r];
end
k=kc;
end
r
else
a=input('Please input the metrix you want to Decoding: ');
sa=size(a);
sa=sa(:,2);
k=2*n-1;
while sa~=0
if a(:,1)==0
k=hf(k,3);
else
k=hf(k,4);
end
a=a(:,2:sa);
sa=sa-1;
if k==0
display('Error! The metrix you entered is a wrong one.');
break
end
end
if k==0
break
end
r=hf(k,2);
end
choose=input('Choose what you want:\n1: Encoding\n2: Decoding\n3:.Exit\n');
clc;
end
if choose~=1&choose~=2
clc;
end
