july-class-01（字符和字符串）
· 阅读需 4 分钟
Huffman编码
Huffman编码是一种无损压缩编码方案。
思想：根据源字符出现的概率对字符编码，概率高的字符使用较短的编码，概率低的使用较长的编码，从而使得编码后的字符串长度期望最小。
Huffman编码是一种贪心算法：每次总选择两个最小概率的字符节点合并
移除空格算法
时间复杂度O(n)，空间复杂度O(1)
#include <iostream>
#include <stdio.h>
using namespace std;
void RemoveBlank(char* pString){
int j = 0;
for(int i= 0;pString[i]!='\0';i++){
if(pString[i] != ' '){
if(i != j){
pString[j] = pString[i];
}
j++;
}
}
pString[j] = 0;
}
int main(){
char str [] = "I have Dream o";
RemoveBlank(str);
cout<<str<<endl;
return 0;
}
找大数
#include <iostream>
#include <stdio.h>
using namespace std;
void FindMax(const int* a, int size,int& nMax,int& nSecondMax){
for(int i = 0;i<size;i++){
if(nMax < a[i]){
nSecondMax = nMax;
nMax = a[i];
}else if(nSecondMax < a[i]){
nSecondMax = a[i];
}
}
}
int main(){
int a [] = {1,5,4,8,3,2,9,14};
int nMax=0;
int nSecondMax = 0;
FindMax(a,sizeof(a)/sizeof(int),nMax,nSecondMax);
printf("max=%d,secondMax = %d\n",nMax,nSecondMax);
return 0;
}
Huffman 编码Java版
public static class HuffmanNode {
public HuffmanNode() {
// TODO Auto-generated constructor stub
}
public int weight = 0;
public int parent = 0;
public int leftNode = 0;
public int rightNode = 0;
}
mian函数
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "when I was young I'd listen to the radio waiting for my favorite songs "
+ "when they played I'd sing along,"
+ "it make me smile."
+ "those were such happy times and not so long ago"
+ "how I wondered where they'd gone."
+ "but they're back again just like a long lost friend"
+ "all the songs I love so well."
+ "every shalala every wo'wo"
+ "still shines."
+ "every shing-a-ling-a-ling "
+ "that they're starting" + "to sing so fine";
int[] weight = new int[N];
ArrayList<Integer> list = new ArrayList<Integer>();
CalcFrequency(str, weight);
weight[(int) '\t'] = 0;
CalcExistChar(weight, list);
int N2 = list.size();
ArrayList<ArrayList<Character>> node = new ArrayList<ArrayList<Character>>(N2);
HuffmanCoding(weight, N2, node);
printNode(node,list);
System.out.println("complete");
}
计算字符权重
static void CalcFrequency(String str, int[] arr) {
for (int i = 0; i < str.length(); i++) {
arr[(int) str.charAt(i)]++;
}
}
将字符记录在list中
static void CalcExistChar(int[] arr, ArrayList<Integer> list) {
int j = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
list.add(i);
if (i != j) {
arr[j] = arr[i];
j++;
}
}
}
}
核心代码
static void HuffmanCoding(int[] weight, int N,
ArrayList<ArrayList<Character>> node) {
if (N <= 0)
return;
int m = 2 * N + 1;
// 初始化树
ArrayList<HuffmanNode> huffmanTree = new ArrayList<HuffmanNode>();
for (int i = 0; i < m; i++) {
HuffmanNode huffmanNode = new HuffmanNode();
huffmanTree.add(huffmanNode);
}
for (int i = 0; i < N; i++) {
huffmanTree.get(i).weight = weight[i];
}
// 找出2个权重最小将其组合
for (int i = N; i < m; i++) {
FindMin(huffmanTree, i);
if (s1 == -1 || s2 == -1)
continue;
huffmanTree.get(s1).parent = huffmanTree.get(s2).parent = i;
huffmanTree.get(i).leftNode = s1;
huffmanTree.get(i).rightNode = s2;
huffmanTree.get(i).weight = huffmanTree.get(s1).weight
+ huffmanTree.get(s2).weight;
}
//根据建好的huffman树从叶子到根，计算每个叶子节点的编码
int nParent;
int curNode;
for (int i = 0; i < N; i++) {
ArrayList<Character> cur = new ArrayList<Character>();
nParent = huffmanTree.get(i).parent;
curNode = i;
while (nParent != 0) {
if (huffmanTree.get(nParent).leftNode == curNode) {
cur.add('0');
} else {
cur.add('1');
}
curNode = nParent;
nParent = huffmanTree.get(curNode).parent;
}
Collections.reverse(cur);
node.add(cur);
}
}
打印树编码
static void printNode(ArrayList<ArrayList<Character>> code,
ArrayList<Integer> charList) {
for (int i = 0; i < code.size(); i++) {
printCode((char) charList.get(i).intValue(), code.get(i));
}
}
static void printCode(char c, ArrayList<Character> code) {
System.out.println("char=" + c + "：");
for (int i = 0; i < code.size(); i++) {
System.out.print(code.get(i));
}
System.out.println();
}