哈夫曼编码算法的实现
发布网友
发布时间：2022-04-22 09:43
共3个回答
懂视网
时间：2022-04-23 02:41
原始版
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-04-22 23:49
在网上看到一个，刚好用到，我试过的，正确
#include <stdio.h>
#include<malloc.h>
#include <string.h>
#include<fstream>
#include<iostream>
using namespace std;
typedef struct {
unsigned int weight;
char ch1;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct {
char ch;
char code[7];
}codenode,*code;
void select(HuffmanTree HT,int n,int & s1,int &s2){ //从哈夫曼树中选择出最小的两个节点
for(int i=1;i<=n;i++)
if(!HT[i].parent){
s1=i; break;
}
for(i++;i<=n;i++)
if(!HT[i].parent){
s2=i; break;
}
if(HT[s1].weight-HT[s2].weight){
int temp; temp=s1; s1=s2; s2=temp;
}
for(i=1;i<=n;i++) //对数组进行遍历，寻找最小的两个节点
if(!HT[i].parent){
if(HT[i].weight<HT[s1].weight){
s2=s1; s1=i;
}
else if(HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}
}
void prin(){ //终端输出选择菜单
cout<<"----------------------------------------------------\n\n"
<<" ∣ I---创建哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ E---文件编码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ D---文件译码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ P---打印代码文件 ∣\n"
<<" ∣ ∣\n"
<<" ∣ T---印哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ O---哈夫曼树的存储结构 ∣\n"
<<" ∣ ∣\n"
<<" ∣ Q---退出 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
}
void output (HuffmanTree th,int n){ //输出哈夫曼树的存储结构
int i=0;
cout<<"序号"<<" "<<"字符"<<" "<<"双亲"<<" "<<"左孩子"<<" "<<"右孩子"<<" "<<"权值"<<endl;
for(;i<2*n-1;i++){
th++;
cout<<i<<" "<<th->ch1<<" "<<th->parent<<" "<<th->lchild<<" "<<th->rchild<<" "<<th->weight <<endl;
}
}
void initial(HuffmanTree &HT,HuffmanCode &HC,int w[],int &n,char ch[],int &k){ //创建哈夫曼树
cout<<"----------------------------------------------------\n\n"
<<" ∣ 1---自定义 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 2---编码课本测试数据 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 3---编码源程序 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
scanf("%d",&k);
if(k==1){
printf("输入需要编码的字符总数: ");
scanf("%d",&n);
printf("\n输入需要编码字符的权值:\n");
for(int d=0;d<n;d++) {
scanf("%d",&w[d]);
}
printf("\n输入需要编码的字符串: ");
scanf("%s",ch);
}
else if(k==2){
ifstream fin2 ("test.txt");
fin2>>n;
for(int d=0;d<n;d++)
fin2>>w[d];
fin2>>ch;
fin2.close();
}
else if(k==3){
ifstream fin1 ("input.txt");
fin1>>n;
for(int d=0;d<n;d++)
fin1>>w[d];
fin1>>ch;
fin1.close();
}
if(n<=1)
return;
int s1,s2,i,num=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++){
p->weight=w[i-1]; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 =ch[i-1];
}
for(;i<=num;p++,i++){
p->weight=0; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 ='$';
}
for(i=n+1;i<=num;i++){
select(HT,i-1,s1,s2);
HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1;
HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
char * temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
for(i=1;i<=n;i++){
int start=n-1;
for(int f=HT[i].parent,h=i;f;h=f,f=HT[f].parent)
if(HT[f].lchild==h)
temp[--start]='0';
else
temp[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&temp[start]);
}
ofstream fout ("hfmTree.txt");
fout<<ch<<endl;
for(int j=1;j<=n;j++)
fout<<HC[j]<<endl;
fout.close();
free(temp);
}
void encoding(int n,int select){ //编码：对文件TobeTran.txt进行译码
char a[100],b[100][20];
ifstream fin ("hfmTree.txt");
fin>>a;
for(int j=0;j<n;j++) fin>>b[j];
fin.close();
ifstream fin1 ("course.txt");
ifstream fin2 ("sorse.txt");
ifstream fin3 ("ToBeTran.txt");
char s[1000];
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
ofstream fout ("CodeFile.txt");
while(s[0]!='\0'){
for(int i=0;s[i]!='\n'&&s[i]!='\0'&&i<30;i++ ){
for(int g=0;a[g]!=s[i];g++) ;
fout<<b[g];
}
fout<<'\n';
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
}
fin3.close();
fin2.close();
fin1.close();
fout.close();
}
void decoding(HuffmanTree ht,int n){ //译码：对CodeFile.txt文件进行译码
ifstream fin ("CodeFile.txt");
ofstream fout ("TextFile.txt");
char s[500];
fin>>s;
HuffmanTree head=ht+2*n-1;
int i=0;
while(s[0]!='\0'){
while(s[i]!='\0'){
if(s[i]=='1') head=ht+head->rchild;
else if(s[i]=='0') head=ht+head->lchild;
if((head->lchild)==0&&(head->rchild) ==0) {
fout<<(head->ch1);
head=ht+2*n-1;
}
i++;
}
fout<<' ' ;
i=0;
fin>>s;
}
fin.close();
fout.close();
}
void Print(){ //打印代码文件，显示在终端，每行50个代码
ifstream fin ("CodeFile.txt");
char s[2000];
int j=0;
int i=1;
fin>>s;
ofstream fout ("CodePrin.txt");
while(s[0]!='\0'){
for(;s[j]!='\0';j++){
printf("%c",s[j]);
fout<<s[j];
if(i%50==0){
fout<<endl;
printf("\n");
}
i++;
}
j=0;
fin>>s;
}
fin.close();
printf("\n");
fout.close();
}
void printTree( HuffmanTree node,HuffmanTree node1, int level ) { //打印哈夫曼树形（在参数的传递上，是文科给自己提出的意见才很好的解决了之后的操作难题^^）
if( node == NULL ) return;
if( node1->rchild!=0) {
printTree( node,node+node1->rchild, level + 1 );
}
fstream fout ;
fout.open ("TreePrint.txt",ios::in | ios::out|ios::ate);//这个挺有用的：在文件末尾加入内容
for( int i = 0; i < level; i++ ) {
fout<<"|……";
printf( "……");
}
fout<<node1->weight<<endl;
printf( "%d\n", node1->weight );
if( node1->lchild!=0 ) {
printTree( node,node+node1->lchild, level + 1 );
}
fout.close();
}
void main(){
int select;
int n;
char ch[100];
int w[100];
HuffmanTree HT=NULL;
HuffmanCode hc=NULL;
prin();
char c='I';
scanf("%c",&c);
while(c!='Q'){
switch(c){
case 'I':
initial(HT,hc,w,n,ch,select);
prin();
break;
case 'E':
encoding(n,select);
prin();
break;
case 'D':
decoding(HT,n);
prin();
break;
case 'P':
Print();
prin();
break;
case 'T':
printTree(HT,HT+2*n-1,1);
prin();
break;
case 'O':
output(HT,n);
prin();
break;
}
scanf("%c",&c);
}
}
热心网友
时间：2022-04-23 01:07
编程论坛上搜搜看吧
